第一部分 数据库基础 3
第1章 数据库系统概述 3
1.1 管理数据 4
1.2 历史回顾 5
1.3 文件系统和数据库管理系统 6
1.4 数据库管理系统的优点 7
1.5 数据库管理系统中数据的描述和存储 8
1.5.1 关系模型 8
1.5.2 数据库管理系统的抽象级别 9
1.5.3 数据独立性 11
1.6 数据库管理系统中的查询 11
1.7 事务管理 12
1.7.1 事务的并发执行 13
1.7.2 未完成的事务和系统崩溃 13
1.7.3 注意要点 14
1.8 数据库管理系统的结构 14
1.9 与数据库打交道的人 15
1.10 复习题 16
第2章 实体联系模型 19
2.1 数据库设计与ER图 20
2.1.1 其他步骤 20
2.2 实体、属性和实体集 21
2.3 联系和联系集 22
2.4 ER模型的其他特征 24
2.4.1 码约束 24
2.4.2 参与约束 25
2.4.3 弱实体 25
2.4.4 类层次 27
2.4.5 聚合 29
2.5 用ER模型进行概念数据库设计 29
2.5.1 实体对属性 30
2.5.2 实体与联系 31
2.5.3 二元与三元联系 32
2.5.4 聚合与三元联系 33
2.6 大型企业的概念数据库设计 34
2.7 统一建模语言 34
2.8 案例研究：网上书店 35
2.8.1 需求分析 36
2.8.2 概念设计 36
2.9 复习题 37
第3章 关系模型 42
3.1 关系模型简介 43
3.1.1 使用SQL创建和修改关系 45
3.2 关系的完整性约束 46
3.2.1 码约束 47
3.2.2 外码约束 48
3.2.3 一般约束 50
3.3 完整性约束的强制执行 50
3.3.1 事务与约束 52
3.4 查询关系数据 53
3.5 逻辑数据库设计：从ER模型到关系模型 55
3.5.1 从实体集到关系表 55
3.5.2 从联系集（不包括约束）到关系表 56
3.5.3 转换带码约束的联系集 57
3.5.4.转换带有参与约束的联系集 58
3.5.5 转换弱实体集 60
3.5.6 转换类层次 60
3.5.7 转换带聚合的ER图 61
3.5.8 ER模型到关系模型：更多的示例 62
3.6 视图简介 63
3.6.1 视图、数据独立性和安全 64
3.6.2 视图的更新 64
3.7 删除／修改关系表和视图 67
3.8 案例研究：网上书店 67
3.9 复习题 69
第4章 关系代数和演算 74
4.1 预备知识 74
4.2 关系代数 75
4.2.1 选择和投影 75
4.2.2 集合操作 76
4.2.3 重命名 78
4.2.4 连接 78
4.2.5 除 80
4.2.6 关系代数查询的其他示例 81
4.3 关系演算 85
4.3.1 元组关系演算 86
4.3.2 域关系演算 89
4.4 代数与演算的表达能力 91
4.5 复习题 92
第5章 SQL：查询、约束与触发器 96
5.1 概述 97
5.1.1 章 节 组织 97
5.2 基本SQL查询的形式 99
5.2.1 基本SQL查询的示例 102
5.2.2 SELECT命令中的表达式和字符串 103
5.3 UNION、INTERSECT和EXCEPT 104
5.4 嵌套查询 107
5.4.1 嵌套查询简介 107
5.4.2 相关嵌套查询 109
5.4.3 集合比较操作 109
5.4.4 有关嵌套查询的其他示例 110
5.5 聚集操作符 111
5.5.1 GROUP BY和HAVING子句 114
5.5.2 聚集查询的其他示例 117
5.6 空值 120
5.6.1 使用空值的比较 121
5.6.2 逻辑连接运算AND、OR和NOT 121
5.6.3 SQL构造符的作用 121
5.6.4 外连接 122
5.6.5 禁止使用空值 122
5.7 SQL中的复杂完整性约束 123
5.7.1 单个表上的约束 123
5.7.2 域约束与DISTINCT类型 123
5.7.3 断言：多个表上的完整性约束 124
5.8 触发器和主动数据库 125
5.8.1 SQL的触发器示例 125
5.9 设计主动数据库 127
5.9.1 为什么触发器难以理解 127
5.9.2 约束和触发器 127
5.9.3 触发器的其他用途 128
5.10 复习题 128
第二部分应用程序开发 139
第6章 数据库应用开发 139
6.1 从应用程序中访问数据库 140
6.1.1 嵌入式SQL 140
6.1.2 游标 142
6.1.3 动态SQL 145
6.2 JDBC简介 146
6.2.1 JDBC体系结构 147
6.3 JDBC类和接口 148
6.3.1 JDBC驱动器管理 148
6.3.2 连接到数据源 148
6.3.3 执行SQL语句 150
6.3.4 结果集 151
6.3.5 异常和警告 152
6.3.6 检查数据库元数据 153
6.4 SQLJ 154
6.4.1 编写SQLJ代码 155
6.5 存储过程 157
6.5.1 创建一个简单的存储过程 157
6.5.2 调用存储过程 158
6.5.3 SQL/PSM 159
6.6 案例研究：网上书店 160
6.7 复习题 163
第7章 Internet应用 166
7.1 引言 166
7.2 Internet的一些概念 167
7.2.1 统一资源标识符 167
7.2.2 超文本传输协议HTTP 168
7.3 HTML文档 170
7.4 XML文档 171
7.4.1 XML简介 172
7.4.2 XML DTD 174
7.4.3 特定领域的DTD 177
7.5 三层应用体系结构 178
7.5.1 单层和客户－服务器体系结构 178
7.5.2 三层体系结构 180
7.5.3 三层体系结构的优点 181
7.6 展示层 182
7.6.1 HTML表单 182
7.6.2 JavaScript 184
7.6.3 样式表 185
7.7 中间层 188
7.7.1 CGI：通用网关接口 188
7.7.2 应用服务器 189
7.7.3 Servlet 190
7.7.4 JSP 192
7.7.5 维护状态 193
7.8 案例研究：网上书店 195
7.9 复习题 197
第三部分存储与索引 207
第8章 存储与索引概述 207
8.1 外部存储上的数据 208
8.2 文件组织与索引 208
8.2.1 聚簇索引 209
8.2.2 主索引和次索引 210
8.3 索引数据结构 210
8.3.1 基于哈希的索引 211
8.3.2 基于树的索引 212
8.4 不同文件组织的比较 213
8.4.1 代价模型 214
8.4.2 堆文件 214
8.4.3 排序文件 215
8.4.4 聚簇文件 216
8.4.5 具有非聚簇树索引的堆文件 217
8.4.6 具有非聚簇哈希索引的堆文件 218
8.4.7 I/O代价的比较 219
8.5 索引和性能调整 219
8.5.1 工作负载的影响 220
8.5.2 聚簇索引组织 220
8.5.3 复合搜索码 222
8.5.4 SQL:1999中的索引规范 225
8.6 复习题 225
第9章 存储数据：磁盘和文件 230
9.1 存储层次 230
9.1.1 磁盘 231
9.1.2 磁盘结构对性能的影响 233
9.2 廉价冗余磁盘阵列（RAID） 233
9.2.1 数据划分 234
9.2.2 冗余 234
9.2.3 冗余的层次 235
9.2.4 RAID级别的选择 238
9.3 磁盘空间管理 238
9.3.1 跟踪空闲块 238
9.3.2 使用操作系统的文件系统来管理磁盘空间 238
9.4 缓冲区管理器 239
9.4.1 缓冲区替换策略 241
9.4.2 数据库管理系统和操作系统的缓冲区管理 241
9.5 记录文件 243
9.5.1 堆文件的实现 243
9.6 页格式 245
9.6.1 定长记录 245
9.6.2 变长记录 246
9.7 记录格式 247
9.7.1 定长记录 248
9.7.2 变长记录 248
9.8 复习题 249
第10章 树结构索引 253
10.1 树索引介绍 254
10.2 索引顺序存取方法 255
10.2.1 溢出页与加锁考虑 257
10.3 B＋树：一种动态索引结构 257
10.3.1 节 点格式 258
10.4 搜索 259
10.5 插入 260
10.6 删除 262
10.7 重复 266
10.8 实际的B＋树 267
10.8.1 码压缩 267
10.8.2 块加载B＋树 268
10.8.3 秩的概念 270
10.8.4 rid上插入和删除的影响 271
10.9 复习题 271
第11章 基于哈希的索引 277
11.1 静态哈希 278
11.1.1 记号与约定 279
11.2 可扩展哈希 279
11.3 线性哈希 283
11.4 可扩展哈希与线性哈希的关系 288
11.5 复习题 288
第四部分查询评估 295
第12章 查询求解概述 295
12.1 系统目录 296
12.1.1 目录中的信息 296
12.2 操作符求解概述 298
12.2.1 三种常用技术 298
12.2.2 访问路径 298
12.3 关系型操作的算法 300
12.3.1 选择 300
12.3.2 投影 301
12.3.3 连接 301
12.3.4 其他操作 302
12.4 查询优化概述 303
12.4.1 查询求解计划 303
12.4.2 多处理器查询：流水线求解 304
12.4.3 迭代操作的接口 305
12.5 可选计划：研究这一问题动机的示例 306
12.5.1 下推选择 306
12.5.2 使用索引 307
12.6 一个典型的优化器做些什么 310
12.6.1 考虑不同的查询计划 310
12.6.2 估算计划的代价 311
12.7 复习题 312
第13章 外排序 315
13.1 什么时候DBMS需要对数据进行排序 315
13.2 简单的两路归并排序算法 316
13.3 外归并排序 318
13.3.1 段数的最小化 320
13.4 最小化I/O开销和I/O的次数 321
13.4.1 块I/O 321
13.4.2 双缓冲 323
13.5 使用B＋树来排序 323
13.5.1 聚簇索引 324
13.5.2 非聚簇索引 324
13.6 复习题 326
第14章 关系操作求解 328
14.1 选择操作 329
14.1.1 无索引、未排序的数据 329
14.1.2 无索引、排序的数据 330
14.1.3 B＋树索引 330
14.1.4 哈希排序、等价选择 331
14.2 一般的选择条件 331
14.2.1 CNF和索引匹配 332
14.2.2 求解无析取的选择 332
14.2.3 求解有析取的选择 333
14.3 投影操作 334
14.3.1 基于排序的投影 334
14.3.2 基于哈希函数的投影 335
14.3.3 用于投影的排序和哈希 336
14.3.4 用于投影的索引使用 337
14.4 连接操作 337
14.4.1 嵌套循环连接算法 338
14.4.2 排序归并连接算法 341
14.4.3 哈希连接 345
14.4.4 一般的连接条件 348
14.5 集合操作 349
14.5.1 用于并和差的排序 349
14.5.2 用于并和差的哈希 349
14.6 聚集操作 350
14.6.1 使用索引实现聚集 351
14.7 缓冲的影响 351
14.8 复习题 352
第15章 典型的关系查询优化器 357
15.1 将SQL查询转换成关系代数表达式 358
15.1.1 将SQL查询分解成块 358
15.1.2 把查询块表示成关系代数表达式 359
15.2 估算执行计划的开销 360
15.2.1 估计结果的大小 360
15.3 关系代数的等价 364
15.3.1 选择 364
15.3.2 投影 364
15.3.3 叉积和连接 364
15.3.4 选择、投影和连接 365
15.3.5 其他的等价 366
15.4 列举可选的执行计划 366
15.4.1 单关系查询 367
15.4.2 多关系查询 370
15.5 嵌套子查询 375
15.6 System R优化器 377
15.7 查询优化的其他方法 377
15.8 复习题 378
第五部分 事务管理 389
第16章 事务管理概述 389
16.1 ACID属性 390
16.1.1 一致性和隔离性 390
16.1.2 原子性和持久性 391
16.2 事务和调度 391
16.3 事务的并发执行 392
16.3.1 并发执行的动机 392
16.3.2 可串行化 392
16.3.3 交叉执行带来的异常 394
16.3.4 包括中止事务的调度 396
16.4 基于加锁的并发控制 397
16.4.1 严格的两阶段加锁 397
16.4.2 死锁 398
16.5 加锁的性能 399
16.6 SQL对事务的支持 399
16.6.1 创建和结束事务 399
16.6.2 应该锁住什么 400
16.6.3 SQL中事务的特性 401
16.7 崩溃恢复简介 403
16.7.1 偷帧和强制写页 403
16.7.2 正常执行时与恢复相关的执行步骤 404
16.7.3 ARIES简介 405
16.7.4 原子性：实现回滚 405
16.8 复习题 405
第17章 并发控制 409
17.1 2PL、可串行性和可恢复性 410
17.1.1 观测可串行化 411
17.2 加锁管理简介 412
17.2.1 实现加锁和解锁请求 412
17.3 锁转换 413
17.4 死锁处理 414
17.4.1 死锁预防 415
17.5 特殊的加锁技术 416
17.5.1 动态数据库和幻影问题 416
17.5.2 B＋树的并发控制 417
17.5.3 多粒度锁 419
17.6 不加锁的并发控制 420
17.6.1 乐观的并发控制 420
17.6.2 基于时间戳的并发控制 422
17.6.3 多版本并发控制 424
17.7 复习题 425
第18章 崩溃恢复 431
18.1 ARIES算法简介 432
18.2 日志 433
18.3 与恢复相关的其他数据结构 435
18.4 写优先日志协议 435
18.5 检查点 436
18.6 从系统崩溃中恢复 436
18.6.1 分析阶段 437
18.6.2 重做阶段 438
18.6.3 反做阶段 439
18.7 介质恢复 442
18.8 其他算法以及与并发控制的交互作用 442
18.9 复习题 443
第六部分数据库设计与调整 451
第19章 模式求精与范式 451
19.1 模式求精简介 452
19.1.1 冗余导致的问题 452
19.1.2 模式分解 453
19.1.3 模式分解中的一些问题 454
19.2 函数依赖 455
19.3 函数依赖推理 456
19.3.1 函数依赖集的闭包 456
19.3.2 属性闭包 457
19.4 范式 458
19.4.1 鲍依斯－柯德范式 458
19.4.2 第三范式 459
19.5 分解的特性 461
19.5.1 无损连接分解 461
19.5.2 保持依赖分解 462
19.6 规范化 463
19.6.1 分解为BCNF 463
19.6.2 分解为3NF 464
19.7 数据库设计中的模式求精 467
19.7.1 一个实体集上的约束 467
19.7.2 一个联系集上的约束 468
19.7.3 识别实体的属性 468
19.7.4 识别实体集 469
19.8 其他类型的依赖 470
19.8.1 多值依赖 470
19.8.2 第四范式 472
19.8.3 连接依赖 473
19.8.4 第五范式 473
19.8.5 包含依赖 473
19.9 案例研究：网上书店 474
19.10 复习题 475
第20章 物理数据库设计和调整 482
20.1 物理数据库设计简介 483
20.1.1 数据库负载 483
20.1.2 物理设计与调整决策 484
20.1.3 数据库调整的必要性 484
20.2 索引选择的指导方针 485
20.3 索引选择的基本示例 486
20.4 聚簇和索引 488
20.4.1 两个关系的协同聚簇 489
20.5 使只需索引的计划成为可能的索引 490
20.6 用于确定索引的辅助工具 491
20.6.1 自动的索引选择 491
20.6.2 索引调整向导如何工作 492
20.7 数据库调整简介 494
20.7.1 调整索引 494
20.7.2 调整概念模式 495
20.7.3 调整查询和视图 496
20.8 调整概念模式时的选择 496
20.8.1 设置一个弱范式 497
20.8.2 非规范化 497
20.8.3 分解的选择 497
20.8.4 BCNF关系的垂直分解 498
20.8.5 水平分解 499
20.9 调整查询和视图中的选择 499
20.10 并发控制的影响 501
20.10.1 减少锁的保持时间 501
20.10.2 减少热点 502
20.11 案例研究：网上书店 503
20.11.1 数据库的调整 504
20.12 DBMS评测基准 504
20.12.1 著名的DBMS评测基准 505
20.12.2 评测基准的使用 505
20.13复习题 506
第21章 安全与认证 512
21.1 数据库安全简介 513
21.2 访问控制 513
21.3 任意访问控制 514
21.3.1 授予和回收视图的访问控制和完整性约束 520
21.4 强制性访问控制 522
21.4.1 多级关系和多实例化 523
21.4.2 转换通道，DoD安全级别 524
21.5 Internet应用的安全性 525
21.5.1 加密 525
21.5.2 认证服务器：SSL协议 526
21.5.3 数字签名 527
21.6 有关安全的其他问题 528
21.6.1 数据库管理员的任务 528
21.6.2 统计数据库的安全 529
21.7 案例研究：网上书店 530
21.8 复习题 531
第七部分 高级主题 537
第22章 并行与分布式数据库 537
22.1 简介 537
22.2 并行数据库系统的可用结构 538
22.3 并行查询处理 539
22.3.1 数据划分 540
22.3.2 并行化顺序数据操作处理程序 541
22.4 数据操作的并行化 541
22.4.1 批量载入和扫描 541
22.4.2 排序 541
22.4.3 连接 542
22.5 并行查询优化 544
22.6 分布式数据库简介 544
22.6.1 分布式数据库系统的类型 545
22.7 分布式DBMS的体系结构 545
22.7.1 客户／服务器系统 545
22.7.2 协同服务器系统 546
22.7.3 中间件系统 546
22.8 分布式DBMS的数据存储 546
22.8.1 划分 547
22.8.2 复制 547
22.9 分布式目录管理 548
22.9.1 命名对象 548
22.9.2 目录结构 548
22.9.3 分布数据的独立性 549
22.10 分布式查询处理 549
22.10.1 分布式DBMS 中无连接的查询 550
22.10.2 分布式DBMS 中的连接操作 550
22.10.3 基于代价的查询优化 553
22.11 分布式数据的更新 554
22.11.1 同步复制 554
22.11.2 异步复制 555
22.12 分布式事务 557
22.13 分布式并发控制 557
22.13.1 分布式死锁 558
22.14 分布式事务恢复 559
22.14.1 事务正常执行和提交协议 559
22.14.2 发生故障后进行恢复 560
22.14.3 重新讨论两阶段提交 561
22.14.4 三阶段提交 562
22.15 复习题 563
第23章 对象数据库系统 571
23.1 研究动机示例 572
23.1.1 新的数据类型 573
23.1.2 操纵新类型数据 574
23.2 结构化数据类型 576
23.2.1 集合类型 576
23.3 结构化类型的数据操纵 577
23.3.1 行操作 577
23.3.2 数组操作 577
23.3.3 其他集合类型的操作 578
23.3.4 涉及嵌套集合的查询示例 578
23.4 封装和抽象数据类型 579
23.4.1 定义方法 580
23.5 继承 581
23.5.1 定义带有继承的类型 582
23.5.2 方法联编 582
23.5.3 集合层次 583
23.6 对象、对象标识符和引用类型 583
23.6.1 相等的概念 584
23.6.2 引用类型的解除 584
23.6.3 SQL:1999中的URL和oid 584
23.7 ORDBMS的数据库设计 585
23.7.1 集合类型和ADTs 585
23.7.2 对象标识符 587
23.7.3 扩展ER模型 588
23.7.4 使用嵌套集合 589
23.8 实现ORDBMS的挑战 590
23.8.1 存储和访问方法 590
23.8.2 查询处理 591
23.8.3 查询优化 593
23.9 OODBMS 594
23.9.1 ODMG数据模型和ODL 594
23.9.2 OQL 596
23.10 RDBMS与OODBMS和ORDBMS的比较 597
23.10.1 RDBMS和ORDBMS 597
23.10.2 OODBMS和ORDBMS的相似点 597
23.10.3 OODBMS和ORDBMS的不同点 597
23.11 复习题 598
第24章 演绎数据库 604
24.1 递归查询简介 605
24.1.1 Datalog 605
24.2 理论基础 607
24.2.1 最小模型语义 608
24.2.2 不动点操作符 609
24.2.3 安全的Datalog程序 610
24.2.4 最小模型＝最小不动点 610
24.3 带有否定的递归查询 611
24.3.1 分层 612
24.4 从Datalog到SQL 614
24.5 递归查询的求解 616
24.5.1 无重复推理的不动点求解 616
24.5.2 下移选择操作来避免不相关的推理 618
24.5.3 魔集算法 619
24.6 复习题 621
第25章 数据仓库与决策支持 625
25.1 决策支持简介 626
25.2 OLAP：多维数据模型 627
25.2.1 多维数据库设计 629
25.3 多维聚集查询 630
25.3.1 SQL:1999中的ROLLUP和CUBE 631
25.4 SQL:1999中的WINDOW查询 633
25.4.1 构造窗口 635
25.4.2 新的聚集函数 635
25.5 快速得到查询结果 635
25.5.1 得到前N个结果的查询 636
25.5.2 联机聚集 637
25.6 OLAP实现技术 638
25.6.1 位图索引 638
25.6.2 连接索引 640
25.6.3 文件组织 640
25.7 数据仓库 641
25.7.1 创建和维护数据仓库 641
25.8 视图和决策支持 642
25.8.1 视图、OLAP和数据仓库 642
25.8.2 视图上的查询 643
25.9 视图实体化 643
25.9.1 视图实体化的问题 644
25.10 实体化视图的维护 645
25.10.1 视图的增量维护 645
25.10.2 维护数据仓库视图 647
25.10.3 进行视图同步的时机 648
25.11 复习题 649
第26章 数据挖掘 655
26.1 数据挖掘简介 655
26.1.1 知识发现的过程 656
26.2 关联计数 657
26.2.1 频繁项集 657
26.2.2 冰山式查询 659
26.3 规则挖掘 660
26.3.1 关联规则 660
26.3.2 找出关联规则的算法 661
26.3.3 关联规则和ISA层次 661
26.3.4 通用化关联规则 662
26.3.5 顺序模式 663
26.3.6 使用关联规则进行预测 664
26.3.7 贝叶斯网络 664
26.3.8 分类和回归规则 665
26.4 树结构规则 666
26.4.1 决策树 667
26.4.2 建立决策树的算法 668
26.5 聚簇 670
26.5.1 一个聚簇算法 671
26.6 在序列上的相似搜索 671
26.6.1 找出相似序列的算法 673
26.7 增量挖掘和数据流 673
26.7.1 频繁项集的增量维护 674
26.8 其他的数据挖掘任务 675
26.9 复习题 676
第27章 信息检索和XML数据 681
27.1 冲突的世界：数据库、IR和XML 682
27.1.1 DBMS与IR系统 682
27.2 信息检索介绍 683
27.2.1 向量空间模型 683
27.2.2 词的TF/IDF权重 684
27.2.3 文档相似性排序 685
27.2.4 对成功的衡量：查准率和查全率 686
27.3 为文本搜索建立索引 686
27.3.1 倒排索引 686
27.3.2 签名文件 688
27.4 Web搜索引擎 689
27.4.1 搜索引擎体系结构 689
27.4.2 使用链接信息 690
27.5 管理DBMS中的文本 693
27.5.1 松耦合的倒排索引 693
27.6 一个XML的数据模型 693
27.6.1 松散结构的动机 694
27.6.2 图模型 694
27.7 XQuery：查询XML数据 695
27.7.1 路径表达式 696
27.7.2 FLWR表达式 696
27.7.3 元素的排序 697
27.7.4 分组以及集合值的生成 698
27.8 XML查询的有效求值 698
27.8.1 在RDBMS中存储XML 699
27.8.2 对XML库进行索引 701
27.9 复习题 704
第28章 空间数据管理 712
28.1 空间数据和查询类型 713
28.2 涉及空间数据的应用 714
28.3 空间索引简介 715
28.3.1 已提出的索引结构概述 716
28.4 基于空间填充曲线的索引 717
28.4.1 区域四叉树和z－排序区域数据 718
28.4.2 使用z－排序的空间查询 719
28.5 网格文件 719
28.5.1 使用网格文件来处理区域 721
28.6 R树：点和区域数据 721
28.6.1 查询 722
28.6.2 插入和删除操作 723
28.6.3 并发控制 724
28.6.4 通用化搜索树 725
28.7 高维索引问题 726
28.8 复习题 726
第29章 其他专题 729
29.1 高级事务处理 729
29.1.1 事务处理监视程序 729
29.1.2 新的事务模型 730
29.1.3 实时DBMS 730
29.2 数据集成 730
29.3 移动数据库 731
29.4 主存数据库 732
29.5 多媒体数据库 732
29.6 地理信息系统 733
29.7 时态数据库 734
29.8 生物数据库 734
29.9 信息可视化 734
29.10 小结 735
第30章 MINIBASE教学辅助软件 736
30.1 可用内容 736
30.2 MINIBASE作业概述 736
30.3 致谢 737
参考文献 738