[正版新书] 数据库管理系统原理与实现 杜小勇、陈红、卢卫 清华大学出版社 数据库系统-高等学校-教材

本书是教育部“101计划”数据库系统课程建设配套教材，面向数据库零基础的读者，系统讲授数据库的基本概念、SQL、数据库管理系统基本原理与实现技术。全书分为4篇共12章。第一篇为基础篇（第1～4章），主要介绍数据库系统的基本概念和基础知识，内容包括概述、关系数据模型、关系数据库标准语言SQL、高级SQL；第二篇为数据存取篇（第5～6章），主要介绍数据库管理系统的数据存取管理，内容包括存储管理、索引；第三篇为查询处理篇（第7～9章），主要介绍查询处理的过程和两个核心步骤，内容包括查询处理、查询优化、查询执行；第四篇为事务处理篇（第10～12章），主要介绍事务处理技术，内容包括事务处理概述、并发控制、故障恢复。

本书重点讲授如何“造数据库”，视角新颖，内容全面系统，实现原理与实现算法取舍合理，并提供配套实验平台，可作为高等学校计算机大类相关专业数据库系统课程的教材，也可供从事数据库系统开发与应用的科研人员、工程技术人员以及其他有关人员参考。

“101计划”数据库系统核心课程教材，覆盖了“101计划”数据库系统课程的全部知识点，结构清晰合理，章节关联性强，文字表达流畅，格式统一，质量符合“101计划”教材的出版要求，系统、完整地讲述了当前数据库技术的基本原理和实现技术。

目录

第一篇基础篇

第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