数据库管理系统原理与实现

**篇基础篇
第1章概述31.1数据库系统概述3
1.1.1数据库系统的基本概念3
1.1.2为什么使用数据库系统5
1.2数据库技术的发展5
1.2.1数据模型推动数据库技术发展6
1.2.2应用需求推动数据库技术发展9
1.2.3计算平台推动数据库技术发展13
1.3数据库管理系统组成17
1.3.1数据库管理系统的功能结构17
1.3.2数据库管理系统的模式结构19
1.3.3数据库管理系统的体系结构20
1.3.4数据库管理系统的执行过程21
1.4我国数据库的发展历程23
1.5本章小结25
习题25
第2章关系数据模型27
2.1关系模型的数据结构及形式化定义27
2.1.1关系概述27
2.1.2关系模式30
2.1.3关系数据库30
2.1.4关系模型的存储结构31
2.2关系代数31
2.2.1传统的集合运算31
2.2.2专门的关系运算32
2.3关系的完整性34
2.3.1实体完整性34
2.3.2参照完整性35
2.3.3用户定义的完整性36
2.4本章小结36习题36
第3章关系数据库标准语言SQL37
3.1SQL概述37
3.2数据定义37
3.2.1模式的定义与删除37
3.2.2基本表的定义、修改与删除38
3.2.3索引的创建41
3.3基本SQL查询41
3.3.1单表查询41
3.3.2连接查询43
3.3.3集合查询45
3.3.4空值查询46
3.3.5聚集查询46
3.4数据更新47
3.4.1插入数据47
3.4.2修改数据48
3.4.3删除数据48
3.5视图49
3.5.1定义视图49
3.5.2查询视图50
3.5.3更新视图50
3.6本章小结50
习题51
实验51
第4章高级SQL53
4.1复杂SQL查询53
4.1.1嵌套查询53
4.1.2递归查询55
4.1.3基于派生表的查询56
4.2数据库完整性57
4.2.1实体完整性57
4.2.2参照完整性57
4.2.3用户定义的完整性58
4.3数据库安全性58
4.3.1数据库安全性等级58
4.3.2自主存取控制60
4.3.3强制存取控制61
4.4数据库编程62
4.4.1过程化SQL62
4.4.2存储过程与函数65
4.4.3触发器65
4.5本章小结66
习题67
实验67
第二篇数据存取篇
第5章存储管理715.1物理存储系统71
5.1.1存储介质概述71
5.1.2常用存储介质72
5.1.3磁盘I/O性能的提升策略75
5.2数据组织76
5.2.1数据库的逻辑与物理组织方式76
5.2.2记录表示77
5.2.3块的组织78
5.2.4关系表的组织81
5.3元数据存储84
5.4缓冲区85
5.4.1缓冲区管理85
5.4.2页面置换策略86
5.5本章小结88
习题89
实验89
第6章索引91
6.1顺序表的索引92
6.1.1稠密索引92
6.1.2稀疏索引93
6.1.3多级索引94
6.2辅助索引95
6.3B 树索引96
6.3.1B 树索引的结构96
6.3.2B 树索引的查询97
6.3.3B 树索引的维护98
6.4哈希索引100
6.4.1静态哈希索引100
6.4.2动态哈希索引102
6.5Bitmap索引106
6.5.1Bitmap索引概述106
6.5.2编码Bitmap索引107
6.6本章小结109
习题109
实验110
第三篇查询处理篇
第7章查询处理1137.1查询处理概述113
7.2查询编译114
7.2.1查询编译概述114
7.2.2词法与语法分析115
7.2.3语义分析118
7.2.4查询优化119
7.3物理操作符121
7.3.1物理操作符的代价模型121
7.3.2扫描操作122
7.3.3排序操作124
7.3.4连接操作126
7.3.5去除重复值132
7.3.6分组聚集132
7.3.7集合操作133
7.4本章小结133
习题134
实验134
第8章查询优化135
8.1查询优化概述135
8.1.1查询优化的意义135
8.1.2查询优化的方法136
8.1.3查询优化器的结构137
8.2关系代数表达式等价变换规则138
8.2.1选择运算的相关规则138
8.2.2投影运算的相关规则139
8.2.3连接运算的相关规则140
8.2.4去重运算的相关规则143
8.2.5聚集运算的相关规则144
8.2.6集合运算的相关规则147
8.3统计信息147
8.4基数估算148
8.4.1选择运算结果集的估算149
8.4.2连接运算结果集的估算152
8.4.3其他运算结果集的估算153
8.5多表连接的优化154
8.5.1多表连接的查询计划树154
8.5.2多表连接顺序的搜索空间155
8.5.3动态规划157
8.5.4贪心算法160
8.6本章小结161
习题161
实验162
第9章查询执行163
9.1查询执行概述163
9.1.1物化164
9.1.2流水线165
9.1.3查询计划的执行166
9.2查询执行模型167
9.2.1火山模型167
9.2.2向量执行模型168
9.3查询并行执行169
9.3.1并行执行概述169
9.3.2并行执行模型170
9.3.3并行执行算法172
9.4查询编译执行173
9.5本章小结174
习题175
实验175
第四篇事务处理篇
第10章事务处理概述17910.1事务基本概念179
10.1.1事务的定义179
10.1.2事务的ACID特性181
10.2数据异常与隔离级别182
10.2.1事务的执行模型182
10.2.2数据异常183
10.2.3隔离级别186
10.3正确的调度187
10.3.1调度与串行调度187
10.3.2可串行化调度189
10.3.3冲突可串行化调度190
10.3.4基于优先图的冲突可串行化验证191
10.4本章小结192
习题192
实验193
第11章并发控制195
11.1两阶段封锁协议196
11.1.1基本实现技术196
11.1.2严格与强严格两阶段封锁协议198
11.1.3死锁预防实现技术200
11.1.4小结202
11.2时间戳排序协议203
11.2.1基本实现技术203
11.2.2避免级联回滚205
11.2.3小结207
11.3乐观并发控制协议208
11.3.1基本实现技术208
11.3.2小结210
11.4三级封锁协议210
11.5多版本并发控制技术212
11.5.1基本实现技术212
11.5.2快照隔离214
11.5.3写偏序214
11.5.4版本管理215
11.6本章小结217
习题217
实验218
第12章故障恢复219
12.1故障恢复概述219
12.1.1故障的分类219
12.1.2事务读写的访问模式220
12.1.3故障下数据一致性的破坏222
12.2恢复的基本实现技术225
12.2.1日志文件225
12.2.2WAL日志226
12.2.3备份227
12.3恢复的基本原理229
12.3.1事务故障的恢复229
12.3.2系统故障的恢复230
12.3.3介质故障的恢复232
12.4ARIES算法233
12.4.1系统正常运行时的日志记录233
12.4.2WAL算法的实现234
12.4.3模糊检查点235
12.4.4系统故障恢复236
12.5本章小结238
习题238
实验240
参考文献241