第一部分 数据库模型与访问方法 2
第1章 数据库导论 2
1.1 数据库系统的动机 2
目录 2
1.2 数据库系统的定义 4
1.3 数据库模型概述 6
1.3.1 关系数据库模型 6
1.3.2 面向对象数据库模型 6
1.3.3 演绎数据库模型 6
1.3.4 层次数据库模型 7
1.3.5 网状数据库模型 8
1.3.6 其他方面的比较 8
1.4 数据库系统的组成 9
1.4.2 概念层 10
1.4.1 物理层 10
1.4.3 外层 11
1.4.4 数据库管理员 11
1.5 一个连续的例子 12
小结 12
第2章 关系数据库 14
2.1 关系数据库的一个非正式的描述 14
2.2 关系术语 16
2.3 二元联系 20
2.3.1 一对多联系 21
2.3.2 多对多联系 23
2.3.3 分解多对多联系 25
2.3.4 一对一联系 27
2.4 高阶联系 29
2.5 递归联系 32
2.5.1 一对多递归联系 32
2.5.2 多对多递归联系 32
2.6 约束 34
2.6.1 关键字约束 35
2.6.2 函数依赖约束 36
2.6.3 实体和参照完整性 37
2.7 基本的实体-联系图 38
2.7.1 ER图中的实体及其属性 38
2.7.2 ER图中的二元联系 39
2.7.3 ER图中的联系属性 41
2.7.4 ER图中的高阶联系 42
2.7.5 ER图中的递归联系 44
2.8 模式规范 45
2.9 元数据和系统目录 46
小结 48
练习 49
第3章 关系代数 53
3.1 重命名和集合运算 53
3.2 选择、投影和连接运算 55
3.2.1 一元运算：选择和投影 55
3.2.2 笛卡儿乘积 56
3.2.3 自然连接 58
3.2.4 有关连接的其他变种 60
3.3 存在型查询 62
3.3.1 连接到锚元组的较长路径 63
3.3.2 存在型查询的一种解决方案 64
3.4 全称查询 65
3.4.1 除法运算 67
3.4.2 全称查询的一种解决方案 68
3.4.3 商关系的大小 69
3.4.4 广义除法 70
3.5 聚集和划分 72
3.5.1 聚集运算的语法变种 72
3.5.2 聚集查询进一步的例子 73
3.5.3 聚集中的算术运算 74
3.6 关系代数表达能力的限制 75
3.7 初步的查询优化 76
小结 78
练习 79
第4章 关系演算 83
4.1 谓词演算的回顾 83
4.2 通过谓词进行选择 86
4.3 存在型查询 89
4.4 全称查询 90
4.5 聚集与划分 93
4.5.1 等价类和商集 94
4.5.2 多划分 95
4.6 域关系演算 96
4.6.1 存在型查询 97
4.6.2 全称查询 98
小结 99
练习 99
第5章 基本SQL 103
5.1 简单检索查询的概念模型 103
5.1.1 从单一的表中进行查询 103
5.1.3 从多个表中进行查询 106
5.1.2 名称限定和别名 106
5.1.4 使用表的多个副本进行查询 109
5.2 子查询 111
5.3 存在型查询 115
5.4 全称查询 117
5.4.1 集合包含解决方案 117
5.4.2 双重否定结构 118
5.4.3 较长的全称路径束 119
5.4.4 混合式全称和存在查询 120
5.5 聚集和划分 121
5.5.1 orderby子句 121
5.5.2 groupby子句 122
5.5.3 orderby和groupby之间的区别 123
5.6 抑制划分 125
5.5.4 划分组中出现重复表示元组的情况 125
5.7 完整的select语法 127
5.7.1 将SQL操作可视化的一种思维模型 127
5.7.2 从SQL到关系代数 128
5.7.3 几个语法上的细节 130
5.8 数据编辑操作 131
5.8.1 SQL插入 131
5.8.2 SQL删除 133
5.8.3 SQL修改 134
5.9 嵌入式SQL 135
5.9.1 立即执行 135
5.9.2 结束和错误反馈 136
5.9.3 准备SQL语句 137
5.9.4 SQL游标 138
5.9.5 输入和输出描述符 141
小结 143
练习 143
第6章 高级SQL 148
6.1 视图 148
6.1.1 from子句中表的表达 148
6.1.2 视图作为虚表 149
6.1.3 通过视图更新元组 151
6.1.4 视图的check选项 154
6.2 空值 154
6.2.1 空值操作 155
6.2.2 聚集函数中的空值操作和SQL谓词 157
6.2.3 match谓词和引用完整性 158
6.2.4 具有any和all的谓词 160
6.3 外操作 161
6.3.1 外连接 162
6.3.2 外并 164
6.4 约束 166
6.4.1 SQL约束的目的和格式 166
6.4.2 域约束 167
6.4.3 表约束：主关键字、外关键字和check约束 169
6.4.4 列约束：主关键字、引用和check约束 170
6.4.5 全局约束 170
6.5 触发器 171
6.6 关系数据库的扩展定义 173
6.7 关系模型的缺陷 174
小结 176
练习 178
7.1 面向对象数据库的非正式介绍 181
第7章 面向对象数据库 181
7.1.1 属性值可以是其他对象 182
7.1.2 从对象中抽取查询解决方案 183
7.1.3 通过逻辑包含表示联系 186
7.2 面向对象术语 187
7.2.1 使用信号的对象通信 187
7.2.2 属性信号 188
7.2.3 类和方法 189
7.2.4 类层次和继承 190
7.2.5 常用类的内置类层次 191
7.2.6 方法的放置和多态 192
7.2.7 信号优先级：一元、二元、关键字 195
7.3 面向对象数据库定义 196
7.3.1 将应用类放置在内置层次中 197
7.3.2 属性方法和错误捕获 199
7.3.3 创建应用对象 200
7.4 联系 200
7.4.1 二元联系 200
7.4.2 高阶联系 201
7.4.3 递归联系 205
7.5 约束 206
7.5.1 一般性约束：域、键、实体完整性和引用完整性 206
7.5.2 函数依赖约束 206
7.5.3 触发器：用于更一般性的约束 207
7.5.4 进一步讨论约束 209
7.5.5 使用读属性信号可能破坏对象封装 210
7.6 面向对象与关系数据库的比较 211
小结 214
练习 215
第8章 面向对象查询 218
8.1 简单数据检索的概念模型 218
8.1.1 涉及单个类的查询 218
8.1.2 涉及多个类的查询 221
8.1.3 等价于SQL子查询的信号表达式 223
8.1.4 其他一些说明中间对象的计算的例子 224
8.2 存在型查询 225
8.2.1 直接检测属性对象 225
8.2.2 使用数据库路径的简化语法 226
8.3 全称查询 230
8.3.1 模仿SQL中的集合包含解决方案 230
8.3.2 使用双重否定模仿SQL解决方案 231
8.3.3 进一步的例子 232
8.4 聚集和划分 233
8.4.1 模仿SQL的orderby子句 233
8.4.2 模仿SQL的groupby子句 234
8.5 递归查询 236
8.5.1 一对多的递归联系 236
8.5.2 多对多的递归联系 237
8.6 数据编辑操作 238
8.6.1 插入新对象 238
8.6.2 删除对象 239
8.6.3 更新对象 240
8.7 从SQL到信号表达式 240
8.7.1 对特定SQL形式的限制转换 241
8.7.2 将关系表转换成类 241
8.7.4 转换算法的概括形式 243
8.7.3 转换select-project-join查询的一般形式 243
8.7.5 最初转换形式的另一种转换 245
8.7.6 将算法扩展到子查询 246
8.7.7 将算法扩展到划分和聚集 247
8.8 对象查询语言（Object Query Language,OQL） 248
8.8.1 OQL符号 248
8.8.2 OQL举例 249
小结 249
练习 251
第9章 演绎数据库 255
9.1 数据库环境下的逻辑程序设计 255
9.1.1 数据库与算术谓词 255
9.1.2 演绎规则与导出谓词 256
9.1.3 可能世界与演绎规则模型 258
9.1.4 最小模型 260
9.1.5 逻辑程序 261
9.2 演绎数据库的非正式介绍 261
9.2.1 查询语法 261
9.2.2 持久演绎规则和源于查询的逻辑程序 263
9.3 演绎数据库的定义 265
9.3.1 公理的表示 265
9.3.2 对联系、约束和隐含事实的演绎规则 267
9.3.3 无环演绎数据库和惟一最小模型 268
9.4 作为满足的目标的查询解 271
9.4.1 无否定自由变量的查询解算法 271
9.4.2 消除否定自由变量 273
9.4.3 从首选最小模型提交解的算法 274
9.5 联系 275
9.5.1 二元联系 276
9.5.2 高阶联系 277
9.5.3 递归联系 278
9.6 约束 279
9.6.1 用演绎规则设置结构性约束 280
9.6.2 函数依赖约束 282
9.6.3 聚集谓词和相关约束 283
小结 285
练习 287
第10章 演绎查询 290
10.1 存在型查询 290
10.1.1 包括一个应用对象的查询 290
10.1.2 包括多个应用对象的查询 292
10.2 全称查询 293
10.3 聚集和划分 295
10.4 逻辑程序与关系代数 298
10.4.1 关系和数据库谓词的对应 298
10.4.2 从关系代数到演绎规则 299
10.4.3 综合转换的例子 303
10.4.4 反向过程：从导出谓词到关系代数 303
10.5 超出无环演绎数据库 305
10.5.1 Horn（霍恩）子句系统 305
10.5.2 在依赖图中存在受限环的系统 306
10.6 递归查询 309
小结 313
练习 314
第11章 网状数据库 319
11.1 对网状数据库的非正式介绍 319
11.2.1 网状记录类型 323
11.2 网状数据库定义 323
11.2.2 系 325
11.2.3 Insertion和retention子句 327
11.2.4 完整性考虑：set-selection和check子句 328
11.3 网状数据操纵语言（DML） 330
11.3.1 当前指针 330
1 1.3.2 在记录中导航 331
1 1.3.3 记录的插入、修改和删除 334
11.3.4 记录到系的连接 336
11.4 联系 338
11.4.1 高阶联系 338
11.4.2 一对多的递归联系 340
11.4.3 多对多递归联系 342
11.5 约束 345
11.6.1 存在型查询 347
11.6 网状查询 347
11.6.2 全称查询 349
11.6.3 聚集查询 350
11.7 网状数据库和以前模型的比较 350
小结 351
练习 352
第12章 层次数据库 355
12.1 层次数据库的非正式介绍 355
12.1.1 实体和其实例的树结构 355
12.1.2 通过逻辑邻接来表示联系 358
12.1.3 在相关记录中导航 360
12.1.4 针对层次数据库的查询形式概览 362
12.2 联系 364
12.2.1 线性化层次之外的虚孩子 365
12.2.2 高阶联系 367
12.3 层次定义和数据操纵 368
12.3.1 层次模式 368
12.3.2 使用get命令定位记录 369
12.3.3 插入记录 371
12.3.4 删除和修改记录 372
12.4 约束 373
12.5 层次查询 374
12.5.1 存在型查询 374
12.5.2 全称查询 375
12.5.3 聚集查询 376
小结 376
练习 377
13.1 模型的相似之处 381
第13章 数据库模型之间的比较 381
13.2 各个模型的优点和缺点 383
13.2.1 层次和网状模型 383
13.2.2 关系模型 385
13.2.3 面向对象模型 385
13.2.4 演绎模型 386
第二部分 磁盘存储管理 388
第14章 文件结构 388
14.1 磁盘存储单元的物理组织 388
14.2 块定位模式 391
14.3 索引顺序文件 394
14.4 散列文件 397
14.4.1 选择散列函数 398
14.4.2 计算记录在桶中的分布 399
14.4.3 单次随机检索需要的平均磁盘探测次数 402
14.4.4 对α〉1.0展开分析 403
14.4.5 散列非数字值 405
14.5 动态文件结构 406
14.5.1 动态索引顺序文件 406
14.5.2 通过模数加倍进行动态散列 407
14.5.3 通过目录加倍进行动态散列 411
14.5.4 其他散列模式 414
小结 415
练习 416
第15章 索引 418
15.1 稀疏层次索引 418
15.1.1 无重复关键字的稀疏索引 418
15.1.2 有重复关键字的稀疏索引 422
15.1.3 在删除期间维护稀疏层次索引 423
15.1.4 在插入期间维护稀疏层次索引 426
15.2 稠密索引 429
15.3 B树 432
15.3.1 查找范围 433
15.3.2 定义B+树的特性 434
15.3.3 在插入期间维护B+树的平衡 435
15.3.4 在删除期间维持B+树的平衡 441
15.3.5 B+树的性能统计 443
15.3.6 B树家族的其他成员 446
小结 447
练习 448
第16章 数据库模型的文件结构 451
16.1 关系模型 451
16.2 网状模型 454
16.3 层次模型 459
16.4 面向对象模型 462
16.5 演绎模型 465
小结 465
练习 466
第三部分 数据库设计 470
第17章 应用设计描述 470
17.1 实体联系模型 470
17.2 类层次和继承 471
17.2.1 类的特化和概化 472
17.2.2 重叠子类和多继承 474
17.3 从ER图到数据库模式的映射 477
17.3.1 映射为关系模式 477
17.3.2 映射为网状模式 486
17.3.3 映射为层次模式 489
17.3.4 映射为面向对象模式 492
17.3.5 映射为演绎模式 494
17.4 对象建模技术（OMT） 496
小结 500
练习 501
第18章 函数依赖分析 503
18.1 函数依赖约束的起源 503
18.1.1 泛关系和它的投影 503
18.1.2 函数依赖集的闭包 506
18.1.3 Armstrong公理 507
18.2 最小覆盖集 509
18.2.1 一个判断闭包成员的算法 509
18.2.2 确定关键字和超关键字 510
18.2.3 确定最小覆盖集 511
18.2.4 计算最小覆盖集的算法 512
18.2.5 一个综合的例子 515
18.2.6 水族馆数据库约束的最小覆盖集 517
18.3 无损连接分解 517
18.4 Boyce-Codd范式（BCNF） 519
18.4.1 使用函数依赖减少冗余 519
18.4.2 通过分解删除违反BCNF的约束 520
18.4.3 分解水族馆数据库为BCNF 522
18.4.4 一个BCNF分解的算法 523
18.5 保持函数依赖 524
18.5.1 一个检查保持函数依赖的算法 525
18.6 前三种范式 527
18.6.1 第一范式 527
18.6.2 第二范式 528
18.6.3 第三范式 529
18.6.4 一个3NF、无损连接、保持函数依赖的分解算法 532
18.7 FD分析的有限性和扩展 534
小结 536
练习 537
第19章 连接依赖分析 540
19.1 多值依赖 540
19.1.1 由MVD引起的冗余 542
19.2 多值依赖和函数依赖的相互作用 543
19.2.1 函数依赖和多值依赖集合的闭包 544
19.2.2 函数依赖可以强制某些多值依赖进入闭包 544
19.2.3 函数依赖和多值依赖能够强制新的函数依赖进入闭包 545
19.2.4 补充律与增补律 546
19.2.5 FD-MVD推理规则 546
19.3.1 集合群的最小基 549
19.2.6 属性决定因素的必要条件 549
19.3 依赖基 549
19.3.2 决定因素的依赖基 551
19.3.3 FD-MVD推理规则的完备性 555
19.3.4 存在MVD时无损连接的一个新准则 555
19.4 第四范式 558
19.4.1 由MVD引入的冗余 558
19.4.2 利用分解消除违反4NF的情况 558
19.4.3 4NF关系集合严格地被包含在BCNF关系集合中 561
19.4.4 在水族馆数据库语境中的MVD 562
19.4.5 左部为空的MVD约束 562
19.5 普通的连接依赖 563
19.5.1 由多分量连接产生的元组 563
19.5.2 由普通连接依赖引入的冗余 564
19.5.3 从已有的JD推出新的JD 565
19.5.4 允许JD没有冗余的条件 565
19.5.5 由FD和MVD强制的JD 567
19.5.6 一个JD允许没有冗余当且仅当它由某些FD所蕴含 568
19.5.7 嵌入的连接依赖 569
19.5.8 一个引入冗余的JD的例子 570
19.6 第5范式 572
19.6.1 5NF包含4NF 574
19.6.2 一个满足4NF却不满足5NF的实例 574
19.6.3 确定JD在闭包中的追赶算法 575
19.6.4 单关键字提供的简化 577
19.7 连接依赖以外的话题 578
19.7.1 模板约束 579
小结 580
19.7.2 域关键字范式 580
练习 582
第四部分 后记 586
第20章 性能 586
20.1 并发 586
20.1.1 事务 587
20.1.2 可串行化调度 588
20.1.3 通过锁实现可串行化 589
20.1.4 死锁和事务依赖图 590
20.1.5 脏读、不可重复读和幻像 591
20.1.6 隔离级别 594
20.1.7 通过时间戳实现可串行化 595
20.2 恢复 599
20.2.1 日志文件在事务回滚和故障恢复中的作用 599
20.2.2 利用检查点来限制大范围的日志文件搜索 602
20.2.3 从数据库备份中恢复 603
20.2.4 对重启长事务的特殊防范 603
20.3 安全性 606
20.3.1 权限描述符 606
20.3.2 权限收回和失控权限问题 610
20.4 查询优化 611
20.4.1 在关系代数表达式树中记录操作 612
20.4.2 转换计算树的启发信息 613
20.4.3 一个综合的例子 614
20.4.4 估计连接操作的代价：写输出 616
20.4.5 估计连接操作的代价：组织输入流 617
小结 619
参考文献 621
术语表 625