数据库系统全书

出版者的话
专家指导委员会
译者序
作者简介
前言
第1章   数据库系统世界 1
1.1   数据库系统的发展 1
1.1.1   早期的数据库管理系统 1
1.1.2   关系数据库系统 2
1.1.3   越来越小的系统 3
1.1.4   越来越大的系统 4
1.1.5   客户-服务器和多层体系结构 4
1.1.6   多媒体数据 5
1.1.7   信息集成 5
1.2   数据库管理系统概述 6
1.2.1   数据定义语言命令 6
1.2.2   查询处理概述 6
1.2.3   存储器和缓冲区管理器 8
1.2.4   事务处理 8
1.2.5   查询处理器 9
1.3   数据库系统研究概述 9
1.3.1   数据库设计 10
1.3.2   数据库程序设计 10
1.3.3   数据库系统实现 11
1.3.4   信息集成概述 12
1.4   小结 12
1.5   参考文献 12
第2章   实体-联系数据模型 15
2.1   E/R模型的要素 15
2.1.1   实体集 15
2.1.2   属性 16
2.1.3   联系 16
2.1.4   实体－联系图 16
2.1.5   E/R图实例 17
2.1.6   二元E/R联系的多样性 17
2.1.7   多路联系 18
2.1.8   联系中的角色 18
2.1.9   联系的属性 19
2.1.10   多路联系到二元联系的转换 20
2.1.11   E/R模型中的子类 21
2.1.12   习题 22
2.2   设计原则 24
2.2.1   忠实性   24
2.2.2   避免冗余 24
2.2.3   简单性考虑 25
2.2.4   选择正确的联系 25
2.2.5   选择正确的元素种类 26
2.2.6   习题 27
2.3   约束的建模 28
2.3.1   约束的分类 29
2.3.2   E/R模型中的键 29
2.3.3   E/R模型中键的表示 30
2.3.4   单值约束 31
2.3.5   引用完整性 31
2.3.6   E/R图中的引用完整性 31
2.3.7  其他类型的约束 32
2.3.8   习题 32
2.4   弱实体集 33
2.4.1   弱实体集的来源 33
2.4.2   弱实体集的要求 34
2.4.3   弱实体集的符号 35
2.4.4   习题 35
2.5   小结 35
2.6   参考文献 36
第3章   关系数据模型 37
3.1   关系模型的基础 37
3.1.1   属性 37
3.1.2   模式 37
3.1.3   元组 38
3.1.4   域 38
3.1.5   关系的等价描述 38
3.1.6   关系实例 38
3.1.7   习题 39
3.2   从E/R图到关系设计 39
3.2.1   实体集到关系的转化 40
3.2.2   E/R联系到关系的转化 41
3.2.3   组合关系 42
3.2.4   处理弱实体集 43
3.2.5   习题 45
3.3   子类结构到关系的转化 46
3.3.1   E/R方式转化 46
3.3.2   面向对象的方法 47
3.3.3   使用空值组合关系 48
3.3.4   各种方法的比较 48
3.3.5   习题 48
3.4   函数依赖 49
3.4.1   函数依赖的定义 50
3.4.2   关系的键 50
3.4.3   超键 52
3.4.4   找出关系中的键 52
3.4.5   习题 53
3.5   函数依赖的规则 54
3.5.1   分解/结合规则 54
3.5.2   平凡函数依赖 55
3.5.3   计算属性的闭包 55
3.5.4   为什么能用闭包算法 57
3.5.5   传递规则 58
3.5.6   函数依赖的闭包集合 59
3.5.7   投影函数依赖 59
3.5.8   习题 60
3.6   关系数据库模式设计 61
3.6.1   异常 62
3.6.2   分解关系 62
3.6.3   Boyce-Codd范式 63
3.6.4   分解为 BCNF 65
3.6.5   从分解中恢复信息 68
3.6.6   第三范式 69
3.6.7   习题 71
3.7   多值依赖 71
3.7.1   属性独立及伴随其产生的冗余 71
3.7.2   多值依赖的定义 72
3.7.3   多值依赖的推论 73
3.7.4   第四范式 74
3.7.5   分解到第四范式 75
3.7.6   范式间的联系 76
3.7.7   习题 76
3.8   小结 77
3.9   参考文献 78
第4章   其他数据模型 81
4.1   面向对象概念的复习 81
4.1.1   类型系统 82
4.1.2   类与对象 82
4.1.3   对象标识 82
4.1.4   方法 82
4.1.5   类的层次 83
4.2   ODL简介 83
4.2.1   面向对象设计 83
4.2.2   类声明 84
4.2.3   ODL中的属性 84
4.2.4   ODL中的联系 85
4.2.5   反向联系 86
4.2.6   联系的多重性 87
4.2.7   ODL中的方法 88
4.2.8   ODL中的类型 89
4.2.9   习题 90
4.3   ODL中的其他概念 91
4.3.1   ODL中的多路联系 92
4.3.2   ODL中的子类 92
4.3.3   ODL中的多继承 93
4.3.4   范围 94
4.3.5   ODL中键声明 94
4.3.6   习题 96
4.4   从ODL设计到关系设计 96
4.4.1   从ODL属性到关系属性 97
4.4.2   类中的非原子类型属性 97
4.4.3   集合类型属性的表示 98
4.4.4   其他类型构建器的表示 99
4.4.5   ODL中联系的表示 100
4.4.6   如果没有键会怎样? 102
4.4.7   习题 102
4.5   对象关系模型 103
4.5.1   从关系到对象关系 104
4.5.2   嵌套关系 104
4.5.3   引用 105
4.5.4   面向对象与对象关系的比较 106
4.5.5   ODL设计到对象关系设计的转化 107
4.5.6   习题 107
4.6   半结构化数据 107
4.6.1   为何需要半结构化数据模型 108
4.6.2   半结构化数据表示 108
4.6.3   信息集成与半结构化数据 109
4.6.4   习题 110
4.7   XML及其数据模型 110
4.7.1   语义标签 111
4.7.2  格式规范的XML 111
4.7.3  文档类型定义（DTD） 112
4.7.4  使用DTD 113
4.7.5  属性列表 114
4.7.6  习题 115
4.8   小结 116
4.9   参考文献 116
第5章   关系代数 119
5.1   一个数据库模式的例子 119
5.2   关系代数操作 120
5.2.1   关系代数基础 121
5.2.2   关系中的集合操作 121
5.2.3   投影 122
5.2.4   选择 123
5.2.5   笛卡儿积 124
5.2.6   自然连接 124
5.2.7   q连接 125
5.2.8   使用组合操作生成查询 126
5.2.9   重命名 127
5.2.10   依赖的和非依赖的操作 128
5.2.11   关系代数表达式中的线性符号 129
5.2.12   习题 129
5.3   包上的关系操作 134
5.3.1   为什么采用包 134
5.3.2   包的并. 交. 差 135
5.3.3   包的投影操作 136
5.3.4   包的选择 137
5.3.5   包的笛卡儿积 137
5.3.6   包的连接 137
5.3.7   习题 138
5.4   关系代数的扩展操作 139
5.4.1   消除重复 139
5.4.2   聚集操作符 140
5.4.3   分组 140
5.4.4   分组操作符 141
5.4.5   扩展的投影操作符 142
5.4.6   排序操作符 143
5.4.7   外连接 143
5.4.8   习题 144
5.5   关系的约束 145
5.5.1   作为约束语言的关系代数 145
5.5.2   引用完整性约束 146
5.5.3   其他的约束举例 147
5.5.4   习题 148
5.6   小结 149
5.7   参考文献 149
第6章   数据库语言SQL 151
6.1   SQL中的简单查询 151
6.1.1   SQL中的投影 152
6.1.2   SQL中的选择 154
6.1.3   字符串比较 155
6.1.4   日期和时间 156
6.1.5   空值和涉及空值的比较 157
6.1.6   布尔值UNKNOWN 158
6.1.7   输出排序 159
6.1.8   习题 159
6.2   多个关系上的查询 160
6.2.1   SQL中的积和连接 161
6.2.2   避免属性歧义 161
6.2.3   元组变量 162
6.2.4   多关系查询的解释 163
6.2.5   查询的并. 交. 差 165
6.2.6   习题 166
6.3   子查询 167
6.3.1   产生标量值的子查询 167
6.3.2   含有关系的条件表达式 168
6.3.3   含有元组的条件表达式 169
6.3.4   关联子查询 170
6.3.5   FROM子句中的子查询 171
6.3.6   SQL 的连接表达式 171
6.3.7   自然连接 172
6.3.8   外连接 173
6.3.9   习题 174
6.4   全关系操作 176
6.4.1   消除重复 176
6.4.2   交. 并. 差中的重复 176
6.4.3   SQL 中的分组和聚集 177
6.4.4   聚集操作符 177
6.4.5   分组 178
6.4.6   HAVING子句 179
6.4.7   习题 180
6.5   数据库更新 181
6.5.1   插入 181
6.5.2   删除 183
6.5.3   更新 183
6.5.4   习题 184
6.6   SQL中的关系模式定义 185
6.6.1   数据类型 185
6.6.2   简单表定义 186
6.6.3   修改关系模式 186
6.6.4   默认值 187
6.6.5   索引 187
6.6.6   索引选择简介 188
6.6.7   习题 190
6.7   视图定义 191
6.7.1   视图声明 191
6.7.2   视图查询 192
6.7.3   重命名属性 193
6.7.4   视图更新 193
6.7.5   涉及视图的查询解释 195
6.7.6   习题 197
6.8   小结 197
6.9   参考文献 198
第7章   约束和触发器 201
7.1   键和外键 201
7.1.1   主键声明 201
7.1.2   用UNIQUE声明键 202
7.1.3   强制键约束 203
7.1.4   外键约束声明 203
7.1.5   维护引用完整性 204
7.1.6   延迟约束检查 205
7.1.7   习题 207
7.2   属性和元组上的约束 208
7.2.1   非空值约束 208
7.2.2   基于属性的 CHECK 约束 209
7.2.3   基于元组的 CHECK 约束 210
7.2.4   习题 211
7.3   修改约束 212
7.3.1   给约束命名 212
7.3.2   修改表上约束 212
7.3.3   习题 213
7.4   模式层的约束和触发器 214
7.4.1   断言 214
7.4.2   事件-条件-动作规则 216
7.4.3   SQL中的触发器 216
7.4.4   替换触发器（Instead of Triggers） 219
7.4.5   习题 219
7.5   小结 221
7.6   参考文献 221
第8章   SQL 的系统特征 223
8.1   编程环境下的 SQL  223
8.1.1   阻抗不匹配问题 224
8.1.2   SQL/宿主语言接口 224
8.1.3   DECLARE节 225
8.1.4   使用共享变量 225
8.1.5   单元组选择语句 226
8.1.6   游标 226
8.1.7   游标修改 229
8.1.8   防止并发更新 229
8.1.9   卷型游标 230
8.1.10   动态SQL 231
8.1.11   习题 232
8.2   模式中的存储过程 233
8.2.1   创建PSM函数和过程 233
8.2.2   PSM中的简单语句格式 234
8.2.3   分支语句 235
8.2.4   PSM中的查询 236
8.2.5   PSM中的循环 236
8.2.6   For 循环 238
8.2.7   PSM的异常处理 238
8.2.8   使用PSM函数和过程 240
8.2.9   习题 240
8.3   SQL 环境 242
8.3.1   环境 242
8.3.2   模式 242
8.3.3   目录 243
8.3.4   SQL 环境中的客户和服务器 244
8.3.5   连接 244
8.3.6   会话 245
8.3.7   模块 245
8.4   使用调用层接口 245
8.4.1   SQL/CLI简介 246
8.4.2   处理语句 247
8.4.3   从查询结果中取数据 248
8.4.4   向查询传递参数 250
8.4.5   习题 250
8.5   Java数据库连接 250
8.5.1   JDBC 简介 250
8.5.2   JDBC 中的创建语句 251
8.5.3   JDBC 中的游标操作 252
8.5.4   参数传递 252
8.5.5   习题 253
8.6   SQL 中的事务 253
8.6.1   可串行性 253
8.6.2   原子性 255
8.6.3   事务 256
8.6.4   只读事务 257
8.6.5   读脏数据 258
8.6.6   其他隔离级别 259
8.6.7   习题 260
8.7   SQL 中的安全机制和用户认证 261
8.7.1   权限 261
8.7.2   创建权限 262
8.7.3   检查权限的处理 263
8.7.4   授权 264
8.7.5   授权图 265
8.7.6   销权 266
8.7.7   习题 268
8.8   小结 269
8.9   参考文献 270
第9章   面向对象查询语言 271
9.1   OQL简介 271
9.1.1   一个面向对象的电影例子 271
9.1.2   路径表达式 271
9.1.3   OQL 中 Select-From-Where 表
达式 273
9.1.4   修改结果的类型 273
9.1.5   复杂输出类型 274
9.1.6   子查询 275
9.1.7   习题 276
9.2   OQL 表达式的其他格式 278
9.2.1   量词表达式 278
9.2.2   聚集表达式 279
9.2.3   分组表达式 279
9.2.4   HAVING 子句 281
9.2.5   并. 交和差操作 281
9.2.6   习题 282
9.3   OQL 中对象的赋值与创建 283
9.3.1   宿主语言变量的赋值 283
9.3.2   集合元素的提取 283
9.3.3   获取集合的每一个成员 283
9.3.4   OQL 中的常量 284
9.3.5   创建新对象 285
9.3.6   习题 286
9.4   SQL 中的用户定义类型 286
9.4.1   在SQL 中定义类型 286
9.4.2   用户定义类型中的方法 287
9.4.3   用UDT声明关系 288
9.4.4   引用 288
9.4.5   习题 290
9.5   对象关系数据上的操作 290
9.5.1   引用的跟随（Following Refe-
rence） 290
9.5.2   访问UDT类型元组的属性 291
9.5.3   生成器和转换器函数 292
9.5.4   UDT类型联系的排序 293
9.5.5   习题 294
9.6   小结 295
9.7   参考文献 295
第10章   逻辑查询语言 297
10.1   一种关系逻辑 297
10.1.1   谓词和原子 297
10.1.2   算术原子 297
10.1.3   Datalog 规则和查询 298
10.1.4   Datalog 规则的意义 299
10.1.5   扩展谓词和内涵谓词 300
10.1.6   Datalog规则应用于包 301
10.1.7   习题 302
10.2   从关系代数到Datalog 302
10.2.1   交 302
10.2.2   并 302
10.2.3   差 303
10.2.4   投影 303
10.2.5   选择 303
10.2.6   积 305
10.2.7   连接 305
10.2.8   用 Datalog 模拟多重操作 306
10.2.9   习题 307
10.3   Datalog 的递归编程 308
10.3.1   递归规则 309
10.3.2   计算递归Datalog 规则 309
10.3.3   递归规则中的非 313
10.3.4   习题 315
10.4   SQL 中的递归 316
10.4.1   在SQL 中定义IDB关系 316
10.4.2   分层非 318
10.4.3   有问题的递归SQL表达式 319
10.4.4   习题 321
10.5   小结 322
10.6   参考文献 322
第11章   数据存储 325
11.1   Megatron 2002数据库系统 325
11.1.1   Megatron 2002实现细节 325
11.1.2   Megatron 2002如何执行查询 326
11.1.3   Megatron 2002有什么问题 327
11.2   存储器层次 327
11.2.1   高速缓冲存储器 327
11.2.2   主存储器 328
11.2.3   虚拟存储器 329
11.2.4   二级存储器 329
11.2.5   三级存储器 330
11.2.6   易失和非易失存储器 332
11.2.7   习题 332
11.3   磁盘 332
11.3.1   磁盘结构 332
11.3.2   磁盘控制器 334
11.3.3   磁盘存储特性 334
11.3.4   磁盘访问特性 335
11.3.5   块的写操作 338
11.3.6   块的修改 338
11.3.7   习题 338
11.4   有效使用二级存储器 339
11.4.1   计算的I/O模型 339
11.4.2   二级存储器中的数据排序 340
11.4.3   归并排序 341
11.4.4   两趟多路归并排序 342
11.4.5   更大型关系的多路归并 343
11.4.6   习题 344
11.5   加速二级存储的访问 345
11.5.1   按柱面组织数据 346
11.5.2   使用多个磁盘 346
11.5.3   磁盘镜像 347
11.5.4   磁盘调度和电梯算法 348
11.5.5   预取和大规模缓冲 350
11.5.6   对策略和折中的小结 351
11.5.7   习题 352
11.6   磁盘故障 353
11.6.1   间断性故障 353
11.6.2   校验和 353
11.6.3   稳定存储 354
11.6.4   稳定存储的错误处理能力 354
11.6.5   习题 355
11.7   从磁盘崩溃中恢复 355
11.7.1   磁盘的故障模型 355
11.7.2   镜像冗余技术 356
11.7.3   奇偶块 356
11.7.4   一种改进：RAID 5 359
11.7.5   多个盘崩溃时的处理 359
11.7.6   习题 361
11.8   小结 363
11.9   参考文献 364
第12章   数据元素的表示 365
12.1   数据元素和字段 365
12.1.1   关系数据库元素的表示 365
12.1.2   对象的表示 366
12.1.3   数据元素的表示 366
12.2   记录 368
12.2.1   定长记录的构造 368
12.2.2   记录首部 370
12.2.3   定长记录在块中的放置 371
12.2.4   习题 371
12.3   块和记录地址的表示 372
12.3.1   客户-服务器系统 372
12.3.2   逻辑地址和结构地址 373
12.3.3   指针混写 374
12.3.4   块返回磁盘 376
12.3.5   被固定的记录和块 377
12.3.6   习题 378
12.4   变长数据和记录 379
12.4.1   具有变长字段的记录 379
12.4.2   具有重复字段的记录 380
12.4.3   可变格式记录 381
12.4.4   不能装入一个块中的记录 382
12.4.5   BLOBS 383
12.4.6   习题 383
12.5   记录的修改 384
12.5.1   插入 384
12.5.2   删除 385
12.5.3   更新 386
12.5.4   习题 386
12.6   小结 387
12.7   参考文献 387
第13章   索引结构 389
13.1   顺序文件上的索引 389
13.1.1   顺序文件 390
13.1.2   稠密索引 390
13.1.3   稀疏索引 391
13.1.4   多级索引 392
13.1.5   重复查找键的索引 393
13.1.6   数据修改期间的索引维护 395
13.1.7   习题 398
13.2   辅助索引 399
13.2.1   辅助索引的设计 399
13.2.2   辅助索引的应用 400
13.2.3   辅助索引的间接性 401
13.2.4   文档检索和倒排索引 403
13.2.5   习题 405
13.3   B树 406
13.3.1   B树的结构 406
13.3.2   B树的应用 409
13.3.3   B树中的查找 410
13.3.4   范围查询 410
13.3.5   B树的插入 411
13.3.6   B树的删除 413
13.3.7   B树的效率 415
13.3.8   习题 416
13.4   散列表 417
13.4.1   辅存散列表 418
13.4.2   散列表的插入 418
13.4.3   散列表的删除 419
13.4.4   散列表索引的效率 419
13.4.5   可扩展散列表 419
13.4.6   可扩展散列表的插入 420
13.4.7   线性散列表 421
13.4.8   线性散列表的插入 422
13.4.9   习题 423
13.5   小结 425
13.6   参考文献 425
第14章   多维索引和位图索引 427
14.1   需要多维的应用 427
14.1.1   地理信息系统 428
14.1.2   数据立方体 428
14.1.3   SQL多维查询 428
14.1.4   使用传统索引执行范围查询 430
14.1.5   利用传统索引执行最邻近查询 430
14.1.6   传统索引的其他限制 431
14.1.7   多维索引结构综述 432
14.1.8   习题 432
14.2   多维数据的类散列结构 433
14.2.1   网格文件 433
14.2.2   网格文件的查找 434
14.2.3   网格文件的插入 434
14.2.4   网格文件的性能 435
14.2.5   分段散列函数 436
14.2.6   网格文件和分段散列的比较 438
14.2.7   习题 438
14.3   多维数据的树形结构 440
14.3.1   多键索引 440
14.3.2   多键索引的性能 441
14.3.3   kd树 441
14.3.4   kd树的操作 442
14.3.5   使kd树适合辅存 444
14.3.6   四叉树 444
14.3.7   R树 446
14.3.8   R树的操作 446
14.3.9   习题 448
14.4   位图索引 449
14.4.1   位图索引的诱因 449
14.4.2   压缩位图 451
14.4.3   游程长度编码位向量的操作 452
14.4.4   位图索引的管理 452
14.4.5   习题 454
14.5   小结 454
14.6   参考文献 455
第15章   查询执行 457
15.1   物理查询计划操作符介绍 458
15.1.1   扫描表 458
15.1.2   扫描表时的排序 459
15.1.3   物理操作符计算模型 459
15.1.4   衡量代价的参数 459
15.1.5   扫描操作符的I/O代价 460
15.1.6   实现物理操作符的迭代器 461
15.2   数据库操作的一趟算法 463
15.2.1   一次多元组操作的一趟算法 464
15.2.2   全关系的一元操作的一趟算法 464
15.2.3   二元操作的一趟算法 466
15.2.4   习题 468
15.3   嵌套循环连接 469
15.3.1   基于元组的嵌套循环连接 469
15.3.2   基于元组的嵌套循环连接的迭
代器 470
15.3.3   基于块的嵌套循环连接算法 470
15.3.4   嵌套循环连接的分析 471
15.3.5   迄今为止的算法小结 472
15.3.6   习题 472
15.4   基于排序的两趟算法 472
15.4.1   利用排序消除重复 473
15.4.2   利用排序进行分组和聚集 474
15.4.3   基于排序的并算法 475
15.4.4   基于排序的交和差算法 475
15.4.5   基于排序的一个简单的连接
算法 476
15.4.6   简单排序连接的分析 478
15.4.7   一种更有效的基于排序的连接 478
15.4.8   基于排序的算法小结 479
15.4.9   习题 479
15.5   基于散列的两趟算法 480
15.5.1   通过散列划分关系 481
15.5.2   基于散列的消除重复算法 481
15.5.3   基于散列的分组和聚集算法 481
15.5.4   基于散列的并. 交. 差算法 482
15.5.5   散列连接算法 482
15.5.6   节省一些磁盘I/O 483
15.5.7   基于散列的算法小结 484
15.5.8   习题 485
15.6   基于索引的算法 485
15.6.1   聚簇和非聚簇索引 485
15.6.2   基于索引的选择 486
15.6.3   使用索引的连接 488
15.6.4   使用有排序索引的连接 488
15.6.5   习题 489
15.7   缓冲区管理 490
15.7.1   缓冲区管理结构 491
15.7.2   缓冲区管理策略 491
15.7.3   物理操作符选择和缓冲区管理的
关系 493
15.7.4   习题 494
15.8   使用超过两趟的算法 494
15.8.1   基于排序的多趟算法 494
15.8.2   基于排序的多趟算法的性能 495
15.8.3   基于散列的多趟算法 495
15.8.4   基于散列的多趟算法的性能 496
15.8.5   习题 496
15.9   关系操作的并行算法 497
15.9.1   并行模型 497
15.9.2   一次一个元组的并行操作 498
15.9.3   全关系操作的并行算法 499
15.9.4   并行算法的性能 500
15.9.5   习题 501
15.10   小结 502
15.11   参考文献 503
第16章   查询编译器 505
16.1   语法分析 505
16.1.1   语法分析与语法分析树 505
16.1.2   SQL的一个简单子集的语法 506
16.1.3   预处理器 508
16.1.4   习题 509
16.2   用于改进查询计划的代数定律 510
16.2.1   交换律与结合律 510
16.2.2   涉及选择的定律 512
16.2.3   下推选择 513
16.2.4   涉及投影的定律 514
16.2.5   有关连接与积的定律 516
16.2.6   有关消除重复的定律 517
16.2.7   涉及分组与聚集的定律 517
16.2.8   习题 518
16.3   从语法分析树到逻辑查询计划 520
16.3.1   转换成关系代数 520
16.3.2   从条件中去除子查询 520
16.3.3   逻辑查询计划的改进 524
16.3.4   结合/交换操作符的分组 525
16.3.5   习题 525
16.4   操作代价的估计 526
16.4.1   中间关系大小的估计 526
16.4.2   投影大小的估计 527
16.4.3   估计选择的大小 527
16.4.4   连接大小的估计 529
16.4.5   多连接属性的自然连接 531
16.4.6   多个关系的连接 532
16.4.7   其他操作的大小估计 533
16.4.8   习题 534
16.5   基于代价的计划选择介绍 535
16.5.1   大小参数估计值的获取 535
16.5.2   计算统计量 538
16.5.3   减少逻辑查询计划代价的启
发式 538
16.5.4   物理计划的枚举技术 539
16.5.5   习题 541
16.6   连接顺序的选择 543
16.6.1   连接的左右变元的意义 543
16.6.2   连接树 543
16.6.3   左深连接树 544
16.6.4   通过动态规划来选择连接顺序
和分组 546
16.6.5   带有更具体的代价函数的动态
规划法 549
16.6.6   选择连接顺序的贪婪算法 549
16.6.7   习题 550
16.7   物理查询计划选择的完成 551
16.7.1   选取选择方法 551
16.7.2   选取连接方法 552
16.7.3   流水线操作与实体化 553
16.7.4   一元流水线操作 553
16.7.5   二元流水线操作 554
16.7.6   物理查询计划的符号 556
16.7.7   物理操作的顺序 557
16.7.8   习题 558
16.8   小结 559
16.9   参考文献 560
第17章   系统故障对策 561
17.1   可回复操作的问题和模型 561
17.1.1   故障模式 561
17.1.2   关于事务的进一步讨论 562
17.1.3   事务的正确执行 563
17.1.4   事务的原语操作 564
17.1.5   习题 566
17.2   undo日志 566
17.2.1   日志记录 567
17.2.2   undo日志规则 568
17.2.3   使用undo日志的恢复 569
17.2.4   检查点 571
17.2.5   非静止检查点 571
17.2.6   习题 573
17.3   redo日志 574
17.3.1   redo日志规则 574
17.3.2   使用redo日志的恢复 575
17.3.3   redo日志的检查点 576
17.3.4   使用带检查点的redo日志的
恢复 577
17.3.5   习题 577
17.4   undo/redo日志 578
17.4.1   undo/redo规则 578
17.4.2   使用undo/redo日志的恢复 579
17.4.3   undo/redo日志的检查点 579
17.4.4   习题 580
17.5   防备介质故障 581
17.5.1   备份 581
17.5.2   非静止转储 582
17.5.3   使用备份和日志的恢复 583
17.5.4   习题 584
17.6   小结 584
17.7   参考文献 585
第18章   并发控制 587
18.1   串行调度和可串行化调度 587
18.1.1   调度 587
18.1.2   串行调度 588
18.1.3   可串行化调度 588
18.1.4   事务语义的影响 589
18.1.5   事务和调度的一种记法 590
18.1.6   习题 590
18.2   冲突可串行性 591
18.2.1   冲突 591
18.2.2   优先图及冲突可串行性判断 592
18.2.3   优先图测试发挥作用的原因 593
18.2.4   习题 594
18.3   使用锁的可串行性实现 595
18.3.1   锁 596
18.3.2   封锁调度器 597
18.3.3   两阶段封锁 598
18.3.4   两阶段封锁发挥作用的原因 598
18.3.5   习题 599
18.4   用多种锁方式的封锁系统 600
18.4.1   共享锁与排他锁 601
18.4.2   相容性矩阵 602
18.4.3   锁的升级 602
18.4.4   更新锁 603
18.4.5   增量锁 604
18.4.6   习题 605
18.5   封锁调度器的一种体系结构 607
18.5.1   插入锁动作的调度器 607
18.5.2   锁表 609
18.5.3   习题 611
18.6   数据库元素层次的管理 611
18.6.1   多粒度的锁 611
18.6.2   警示锁 612
18.6.3   幻像与插入的正确处理 613
18.6.4   习题 614
18.7   树协议 615
18.7.1   基于树的封锁的动机 615
18.7.2   访问树结构数据的规则 615
18.7.3   树协议发挥作用的原因 616
18.7.4   习题 618
18.8   使用时间戳的并发控制 618
18.8.1   时间戳 619
18.8.2   物理上不可实现的行为 619
18.8.3   脏数据的问题 620
18.8.4   基于时间戳调度的规则 621
18.8.5   多版本时间戳 622
18.8.6   时间戳与封锁 623
18.8.7   习题 623
18.9   使用有效性确认的并发控制 624
18.9.1   基于有效性确认的调度器的
结构 624
18.9.2   有效性确认规则 625
18.9.3   三种并发控制机制的比较 627
18.9.4   习题 627
18.10   小结 628
18.11   参考文献 629
第19章   再论事务管理 631
19.1   读未提交数据的事务 631
19.1.1   脏数据问题 631
19.1.2   级联回滚 632
19.1.3   可恢复调度 633
19.1.4   避免级联回滚的调度 633
19.1.5   回滚的管理 634
19.1.6   成组提交 635
19.1.7   逻辑日志 636
19.1.8   根据逻辑日志恢复 637
19.1.9   习题 638
19.2   视图可串行性 639
19.2.1   视图等价性 639
19.2.2   多重图与视图可串行性的判断 640
19.2.3   视图可串行性的判断 643
19.2.4   习题 643
19.3   死锁处理 643
19.3.1   超时死锁检测 644
19.3.2   等待图 644
19.3.3   通过元素排序预防死锁 645
19.3.4   时间戳死锁检测 646
19.3.5   死锁管理方法的比较 648
19.3.6   习题 649
19.4   分布式数据库 649
19.4.1   数据的分布 649
19.4.2   分布式事务 650
19.4.3   数据复制 651
19.4.4   分布式查询优化 651
19.4.5   习题 652
19.5   分布式提交 652
19.5.1   分布式原子性的支持 652
19.5.2   两阶段提交 653
19.5.3   分布式事务的恢复 654
19.5.4   习题 655
19.6   分布式封锁 656
19.6.1   集中封锁系统 656
19.6.2   分布式封锁算法的代价模型 656
19.6.3   封锁多副本的元素 657
19.6.4   主副本封锁 658
19.6.5   局部锁构成的全局锁 658
19.6.6   习题 659
19.7   长事务 659
19.7.1   长事务的问题 659
19.7.2   saga（系列记载） 661
19.7.3   补偿事务 662
19.7.4   补偿事务发挥作用的原因 663
19.7.5   习题 663
19.8   小结 663
19.9   参考文献 665
第20章   信息集成 667
20.1   信息集成的方式 667
20.1.1   信息集成的问题 667
20.1.2   联邦数据库系统 668
20.1.3   数据仓库 669
20.1.4   协调器 671
20.1.5   习题 673
20.2   基于协调器系统的包装器 674
20.2.1   查询模式的模板 674
20.2.2   包装器生成器 675
20.2.3   过滤器 676
20.2.4   其他在包装器上进行的操作 677
20.2.5   习题 678
20.3   协调器基于能力的优化 678
20.3.1   数据源能力有限的问题 678
20.3.2   描述数据源能力的符号 679
20.3.3   基于能力的查询计划选择 680
20.3.4   增加基于代价的优化 681
20.3.5   习题 681
20.4   联机分析处理 682
20.4.1   OLAP应用 682
20.4.2   OLAP数据的多维视图 683
20.4.3   星型模式 684
20.4.4   切片和切块 685
20.4.5   习题 687
20.5   数据立方体 687
20.5.1   立方体操作符 687
20.5.2   通过物化视图实现立方体 689
20.5.3   视图的格 691
20.5.4   习题 692
20.6   数据挖掘 693
20.6.1   数据挖掘的应用 694
20.6.2   寻找频繁项目集 695
20.6.3   A-Priori算法 696
20.6.4   习题 698
20.7   小结 698
20.8   参考文献 699
索引 701