第1部分 数据库系统基础 3
第1章 数据库系统导论 3
1.1数据模型 3
1.1.1数据模型定义与分类 3
1.1.2一些典型数据模型特点综述 5
1.2数据库方法特点与应用简史 8
1.3数据库系统体系结构 11
1.3.1DB数据的三层抽象模型 11
1.3.2一种典型的DBMS实现体系结构 11
1.3.3五层DBMS体系结构模型 13
1.4数据库系统的发展与演化 16
1.4.1五层模型体系结构的发展综述 16
1.4.2层次模型与事务特性 18
1.4.3体系结构变体 20
1.4.4可靠性与可适应性 24
1.4.5结论与展望 25
习题1 25
第2章 关系模型与关系数据库 27
2.1关系数据模型 27
2.1.1关系模型基础 27
2.1.2关系模型的约束及其表达 29
2.1.3关系数据库 33
2.2关系操作与关系查询语言 34
2.2.1关系代数 35
2.2.2关系演算 40
2.3SQL语言 43
2.3.1用DDL定义数据库 44
2.3.2用DML操纵数据库 45
2.3.3视图 53
2.4应用关系数据库 55
2.4.1DB存储过程与SQL／PSM 55
2.4.2在通用编程语言中嵌入SQL命令 57
2.4.3基于API接口访问数据库：ODBC和JDBC 61
习题2 66
第3章 数据库设计 68
3.1ER数据模型 69
3.1.1实体类型、实体集、属性和键 69
3.1.2关系、关系类型和关系集 71
3.1.3ER模型的其他特性 72
3.2EER数据模型 76
3.2.1EER模型核心概念的形式定义 77
3.2.2子类、超类与类层次结构 77
3.2.3特化与泛化 78
3.2.4利用union子类建模 80
3.2.5值集属性与复合结构属性的建模表示 81
3.2.6EER与UML类图比较 82
3.2.7EER作为知识表示模型 85
3.2.8为大型企业／组织进行DB概念设计 86
3.3逻辑数据库设计：映射ER／EER模式到关系模式 86
3.3.1映射常规实体集到关系表 87
3.3.2映射关系集到关系表 87
3.3.3映射弱实体集 89
3.3.4映射带有聚集关系的ER图 90
3.3.5映射EER扩展结构 90
3.3.6ER模型至关系模型映射小结 93
3.4关系模式求精与规范化 93
3.4.1模式求精问题 93
3.4.2函数依赖 95
3.4.3基本规范范式 101
3.4.4无损分解与依赖保持分解 104
3.4.5分解与规范化关系模式 106
3.4.6多值依赖与第四范式 108
习题3 111
第2部分 关系数据库系统实现 117
第4章 数据存储与组织管理 117
4.1物理存储介质 117
4.1.1存储介质的层次 117
4.1.2磁盘的物理特性 118
4.1.3磁盘故障及其处理策略 120
4.1.4磁盘块存取的优化 123
4.2磁盘空间管理 125
4.2.1磁盘空间管理器 125
4.2.2利用OS管理磁盘空间 126
4.2.3跟踪自由块 126
4.3文件的页组织 127
4.3.1堆文件 127
4.3.2排序文件 128
4.3.3索引文件 129
4.4页表示格式 130
4.4.1定长记录 130
4.4.2变长记录 130
4.5记录表示格式 132
4.5.1定长记录的字段表示 133
4.5.2变长记录的字段表示 133
4.5.3跨页记录管理技术 134
4.5.4巨型字段／对象管理技术 135
4.5.5指针字段管理技术——指针混写 136
4.6DB元信息及其存储管理 137
4.7缓冲区管理 138
4.7.1DB缓冲池与缓冲区管理器 138
4.7.2缓冲区置换策略 139
4.7.3DBMS与OS的缓冲区管理对比 140
习题4 141
第5章 数据库索引技术 143
5.1几种文件组织方式的特性对比分析 143
5.1.1文件的记录组织方式 143
5.1.2各种文件组织方式的特性分析 144
5.2索引技术基础 146
5.2.1索引技术综述 146
5.2.2顺序索引及其特性 147
5.2.3创建索引语句 150
5.3B＋树索引 150
5.3.1B＋树概述 150
5.3.2B＋树操作 151
5.3.3B＋树的效率与实用化 156
5.4散列索引 160
5.4.1静态散列存储表 160
5.4.2可扩展的动态散列 161
5.4.3线性散列 163
5.5位图索引 166
5.5.1位图索引的结构 166
5.5.2位图索引的应用 167
5.5.3压缩位图 167
5.5.4压缩位图的游程解码操作 168
5.5.5位图索引的维护 169
5.6多维空间索引 169
5.6.1多维空间索引技术综述 169
5.6.2网格文件 176
5.6.3R树 179
5.6.4k-d树与四叉树 181
习题5 183
第6章 关系操作符赋值 189
6.1外部排序 190
6.1.1一种简单的两路归并排序 190
6.1.2多路归并排序 191
6.1.3两阶段多路归并排序 192
6.1.4最小化外部排序时间 193
6.2关系操作符赋值实现基础 195
6.2.1关系操作符赋值实现的三个基本操作 195
6.2.2存取路径 195
6.2.3代价计算模型 196
6.2.4关系操作符赋值的实现算法分类 196
6.2.5迭代器技术 197
6.2.6主存散列表技术 198
6.2.7本章查询用例说明 199
6.3RDBMS系统的目录信息 200
6.3.1存储在DB系统目录中的信息 200
6.3.2DB系统目录组织结构 201
6.4选择操作符赋值 201
6.4.1简单扫描方法 202
6.4.2利用排序特性进行选择赋值 202
6.4.3利用索引进行选择赋值 202
6.4.4一般的选择条件处理 204
6.5投影与消除重复操作赋值 206
6.5.1基于排序实现消除重复投影 206
6.5.2基于散列实现消除重复投影 207
6.5.3排序与散列算法比较 207
6.5.4利用索引来执行消除重复投影 208
6.6连接操作赋值 208
6.6.1嵌套循环连接 208
6.6.2基于索引的嵌套循环连接 210
6.6.3排序-归并连接 211
6.6.4散列连接 213
6.6.5一般连接条件处理 215
6.7集合操作的赋值实现 216
6.7.1集合操作一趟实现算法 216
6.7.2包运算的一趟实现算法 217
6.7.3实现集合并与集合差的两趟算法 218
6.8聚合操作符的赋值实现 218
6.9各类代数操作符赋值实现小结 219
6.9.1缓冲区的影响 219
6.9.2各类代数操作符赋值实现小结 220
习题6 221
第7章 查询处理与优化 223
7.1查询处理简介 223
7.1.1查询预编译简介 224
7.1.2从语法树生成初步的逻辑查询计划 225
7.1.3将查询基本块转化为关系代数表达式 226
7.2查询优化综述 227
7.2.1查询赋值计划 227
7.2.2流水线赋值 228
7.2.3操作符的迭代器接口与存取方法 229
7.2.4IBM System R优化器 229
7.3关系代数等价规则 229
7.3.1选择 230
7.3.2投影 230
7.3.3叉积与连接 230
7.3.4选择、投影和连接 230
7.3.5其他等价规则 231
7.4基于等价和启发式规则的查询优化 231
7.4.1下推选择与下推投影 231
7.4.2利用索引改进计划 233
7.5作为中间结果的操作符输出大小估计 234
7.5.1选择输出的大小估计 235
7.5.2连接大小的估计 236
7.5.3消除重复操作的大小估计 238
7.5.4其他操作符的结果大小估计 238
7.6基于代价的枚举与优化 238
7.6.1枚举候选计划 239
7.6.2单关系查询优化 240
7.6.3多关系查询优化 242
7.7处理嵌入子查询 247
7.8Oracle优化器简介 249
7.8.1基于规则的优化器 249
7.8.2Oracle基于代价的优化器 250
7.8.3如何设定Oracle优化器的工作模式 251
7.9查询处理小结 252
习题7 253
第8章 事务并发控制 256
8.1事务并发执行管理概述 256
8.1.1事务的概念与基本特性 256
8.1.2调度的基本概念 257
8.1.3事务的并发执行 258
8.1.4优先图 260
8.1.5视可串行化 260
8.2基于封锁的并发控制 261
8.2.1严格两阶段封锁协议 261
8.2.2一般两阶段封锁协议 262
8.2.3封锁管理 263
8.3死锁及其处理 265
8.3.1预防死锁 266
8.3.2死锁检测 266
8.3.3基于封锁的并发控制性能 268
8.4扩展封锁处理技术 269
8.4.1动态数据库与幻象问题 269
8.4.2B＋树的并发控制 270
8.4.3多粒度封锁 272
8.5基于优化的并发控制 273
8.5.1基于有效确认的并发控制 273
8.5.2基于时间戳的并发控制 275
8.5.3三种并发机制比较 278
8.6SQL-92的事务支持 279
8.6.1事务的基本特征 279
8.6.2事务与约束 280
习题8 282
第9章 数据库恢复技术 284
9.1DB恢复问题及其处理概述 284
9.1.1故障类型 284
9.1.2故障恢复策略 285
9.1.3数据存取的有关概念 286
9.1.4事务写操作相关问题 286
9.2数据库日志 288
9.2.1日志技术概述 288
9.2.2基于WAL规则的日志 289
9.2.3检查点技术 289
9.3ARIES日志管理技术 290
9.3.1ARIES简介 290
9.3.2ARIES的检查点记录 294
9.4基于ARIES日志的系统崩溃恢复 294
9.4.1分析阶段 295
9.4.2Redo阶段 297
9.4.3Undo阶段 298
9.4.4重启时再次崩溃处理 299
9.4.5其他相关算法以及ARIES的并发控制特性 300
9.5转储备份与恢复 301
9.5.1静态转储与动态转储 301
9.5.2利用检查点的备份恢复 301
9.6再论脏读与回滚管理 302
9.6.1读未提交数据的事务 302
9.6.2回滚管理 304
习题9 305
第3部分 对象数据库和Web数据库 311
第10章 对象数据库 311
10.1关系数据库的局限性 311
10.2面向对象数据模型 312
10.2.1对象模型概述 312
10.2.2对象 313
10.2.3直接量 315
10.2.4对象类型 316
10.2.5继承 318
10.2.6数据库操作 320
10.2.7封锁和并发控制 321
10.2.8事务模型 321
10.3对象定义语言 321
10.4对象查询语言 323
10.4.1OQL综述 323
10.4.2OQL语言简介 325
10.5C++语言绑定与OODBMS实现 331
10.5.1OODBMS概述 332
10.5.2C++语言绑定综述 333
10.5.3C++ODL 337
10.5.4C++OML 340
10.5.5C++OQL 343
10.6对象-关系数据库系统 344
10.6.1嵌套关系表 345
10.6.2复杂数据类型 346
10.6.3继承 348
10.6.4引用类型 349
10.6.5复杂类型查询 351
10.6.6函数、过程和方法 352
10.6.7ADT及其封装 353
10.6.8新型关系数据库 354
10.6.9实现ORDBMSS面临的一些新挑战 358
10.7OODBMSS与ORDBMSS对比 361
习题10 362
第11章 Web数据库 365
11.1Web技术 366
11.1.1HTML 366
11.1.2HTTP协议 368
11.2数据库与Web 369
11.2.1基于Web的数据库应用体系结构 370
11.2.2服务API与应用服务器 371
11.2.3服务器侧处理技术 373
11.3XML技术 375
11.3.1XML文档 375
11.3.2XML约束 376
11.3.3XML数据模型 378
11.3.4XML查询语言 380
11.4基于关键字的文本搜索 381
11.4.1倒排文件 382
11.4.2签名索引文件 383
11.5基于分级排序的网页搜索 383
习题11 385
第4部分 其他高级主题部分 389
第12章 数据仓库与决策支持系统 389
12.1数据仓库技术概述 389
12.1.1决策支持查询的新特征 389
12.1.2支持决策支持查询的系统类型 390
12.1.3数据仓库 390
12.2OLAP 391
12.2.1多维数据模型 391
12.2.2OLAP查询 393
12.2.3与SQL操作比较 394
12.2.4统计数据库 395
12.2.5OLAP设计 395
12.3OLAP的实现技术 396
12.3.1位图索引 396
12.3.2连接索引 396
12.3.3文件组织 397
12.3.4其他OLAP实现问题 397
12.4视图与决策支持系统 398
12.4.1视图、OLAP和DW 398
12.4.2改写基于视图的查询 398
12.4.3视图物化 399
12.4.4视图物化相关问题 399
12.5快速返回部分查询结果 400
12.5.1TOP N查询 400
12.5.2在线汇总 401
习题12 402
第13章 数据挖掘 404
13.1数据挖掘综述 404
13.2数据关联模式 405
13.2.1频繁项集 405
13.2.2冰川查询 407
13.2.3挖掘关联规则 408
13.3决策树 409
13.3.1决策树与分类规则 409
13.3.2构造决策树算法 410
13.4聚类 413
13.4.1几种典型的聚类方法 414
13.4.2BIRCH聚类算法 415
13.5基于序列的相似搜索 415
13.5.1数据序列及其相似度定义 415
13.5.2一种发现相似序列的算法 416
习题13 416
第14章 演绎数据库 418
14.1递归查询 418
14.2演绎数据库理论基础 421
14.2.1最小模型语义 422
14.2.2安全Datalog程序 423
14.2.3不动点操作 423
14.2.4最小模型与不动点模型关系 424
14.3含否定的递归查询 424
14.3.1范围限制与否定 425
14.3.2分层概念 425
14.3.3聚合操作 426
14.4有效赋值递归查询 427
14.4.1没有重复推导的不动点赋值 428
14.4.2魔集算法 428
习题14 430
参考文献 431