数据库系统实现PDF电子书下载

第1章 DBMS系统概述 1

1.1　数据库系统的发展 1

1.1.1　早期的数据库管理系统 1

1.1.2　关系数据库系统 2

1.1.3　越来越小的系统 2

1.1.4　越来越大的系统 2

1.1.5　信息集成 3

1.2　数据库管理系统概述 3

1.2.1　数据定义语言命令 3

1.2.2　查询处理概述 3

1.2.3　主存和缓冲区管理器 5

1.2.4　事务处理 5

1.2.5　查询处理器 6

1.3　本书概述 6

1.4　数据库模型和语言回顾 7

1.4.1　关系模型回顾 7

1.4.2 SQL回顾 7

1.5　参考文献 9

第一部分　数据库系统实现第2章 辅助存储管理 11

2.1　存储器层次 11

2.1.1　存储器层次 11

2.1.2　在存储器层次间传送数据 12

2.1.3　易失和非易失存储器 13

2.1.4　虚拟存储器 13

2.1.5　习题 13

2.2　磁盘 14

2.2.1　磁盘结构 14

2.2.2　磁盘控制器 15

2.2.3　磁盘存取特性 15

2.2.4　习题 16

2.3　加速对辅助存储器的访问 17

2.3.1　计算的I/O模型 17

2.3.2　按柱面组织数据 18

2.3.3　使用多个磁盘 18

2.3.4　磁盘镜像 19

2.3.5　磁盘调度和电梯算法 19

2.3.6　预取和大规模缓冲 20

2.3.7　习题 20

2.4　磁盘故障 21

2.4.1　间断性故障 21

2.4.2　校验和 22

2.4.3　稳定存储 22

2.4.4　稳定存储的错误处理能力 23

2.4.5　从磁盘崩溃中恢复 23

2.4.6　作为冗余技术的镜像 23

2.4.7　奇偶块 24

2.4.8　一种改进：RAID 5 26

2.4.9　多个盘崩溃时的处理 26

2.4.10　习题 28

2.5　组织磁盘上的数据 29

2.5.1　定长记录 29

2.5.2　定长记录在块中的放置 30

2.5.3　习题 31

2.6　块和记录地址的表示 31

2.6.1　客户机-服务器系统中的地址 31

2.6.2　逻辑地址和结构地址 32

2.6.3　指针混写 33

2.6.4　块返回磁盘 35

2.6.5　被钉住的记录和块 36

2.6.6　习题 36

2.7　变长数据和记录 37

2.7.1　具有变长字段的记录 37

2.7.2　具有重复字段的记录 38

2.7.3　可变格式的记录 39

2.7.4　不能装入一个块中的记录 40

2.7.5 BLOB 40

2.7.6　列存储 41

2.7.7　习题 41

2.8　记录的修改 42

2.8.1　插入 42

2.8.2　删除 43

2.8.3　修改 44

2.8.4　习题 44

2.9　小结 44

2.10　参考文献 45

第3章 索引结构 47

3.1　索引结构基础 47

3.1.1　顺序文件 48

3.1.2　稠密索引 48

3.1.3　稀疏索引 49

3.1.4　多级索引 49

3.1.5　辅助索引 49

3.1.6　辅助索引的运用 50

3.1.7　辅助索引中的间接 51

3.1.8　文档检索和倒排索引 52

3.1.9　习题 55

3.2 B-树 55

3.2.1 B-树的结构 56

3.2.2 B-树的应用 57

3.2.3 B-树的查找 59

3.2.4　范围查询 59

3.2.5 B-树的插入 60

3.2.6 B-树的删除 62

3.2.7 B-树的效率 64

3.2.8　习题 64

3.3　散列表 65

3.3.1　辅存散列表 65

3.3.2　散列表的插入 66

3.3.3　散列表的删除 66

3.3.4　散列表索引的效率 67

3.3.5　可扩展散列表 67

3.3.6　可扩展散列表的插入 68

3.3.7　线性散列表 69

3.3.8　线性散列表的插入 70

3.3.9　习题 71

3.4　多维索引 72

3.4.1　多维索引的应用 72

3.4.2　利用传统索引执行范围查询 73

3.4.3　利用传统索引执行最近邻查询 73

3.4.4　多维索引结构综述 74

3.5　多维数据的散列结构 74

3.5.1　网格文件 74

3.5.2　网格文件的查找 74

3.5.3　网格文件的插入 75

3.5.4　网格文件的性能 76

3.5.5　分段散列函数 77

3.5.6　网格文件和分段散列的比较 78

3.5.7　习题 79

3.6　多维数据的树结构 79

3.6.1　多键索引 80

3.6.2　多键索引的性能 80

3.6.3　kd-树 81

3.6.4　kd-树的操作 81

3.6.5　使kd-树适合辅助存储器 83

3.6.6　四叉树 83

3.6.7 R-树 84

3.6.8 R-树的操作 85

3.6.9　习题 86

3.7　位图索引 87

3.7.1　位图索引的动机 88

3.7.2　压缩位图 89

3.7.3　分段长度编码位向量的操作 90

3.7.4　位图索引的管理 91

3.7.5　习题 91

3.8　小结 92

3.9　参考文献 93

第4章　查询执行 96

4.1　物理查询计划操作符介绍 97

4.1.1　扫描表 97

4.1.2　扫描表时的排序 97

4.1.3　物理操作符计算模型 98

4.1.4　衡量代价的参数 98

4.1.5　扫描操作符的I/O代价 99

4.1.6　实现物理操作符的迭代器 99

4.2　一趟算法 101

4.2.1　一次单个元组操作的一趟算法 102

4.2.2　整个关系的一元操作的一趟算法 102

4.2.3　二元操作的一趟算法 104

4.2.4　习题 106

4.3　嵌套循环连接 106

4.3.1　基于元组的嵌套循环连接 106

4.3.2　基于元组的嵌套循环连接的迭代器 107

4.3.3　基于块的嵌套循环连接算法 107

4.3.4　嵌套循环连接的分析 108

4.3.5　迄今为止的算法的总结 109

4.3.6　习题 109

4.4　基于排序的两趟算法 109

4.4.1　两阶段多路归并排序 110

4.4.2　利用排序去除重复 111

4.4.3　利用排序进行分组和聚集 111

4.4.4　基于排序的并算法 111

4.4.5　基于排序的交和差算法 112

4.4.6　基于排序的一个简单的连接算法 112

4.4.7　简单的排序连接的分析 113

4.4.8　一种更有效的基于排序的连接 113

4.4.9　基于排序的算法的总结 114

4.4.10　习题 114

4.5　基于散列的两趟算法 115

4.5.1　通过散列划分关系 115

4.5.2　基于散列的消除重复算法 115

4.5.3　基于散列的分组和聚集算法 116

4.5.4　基于散列的并、交、差算法 116

4.5.5　散列连接算法 116

4.5.6　节省一些磁盘I/O 117

4.5.7　基于散列的算法的总结 118

4.5.8　习题 119

4.6　基于索引的算法 119

4.6.1　聚簇和非聚簇索引 119

4.6.2　基于索引的选择 120

4.6.3　使用索引的连接 121

4.6.4　使用有序索引的连接 122

4.6.5　习题 123

4.7　缓冲区管理 124

4.7.1　缓冲区管理结构 124

4.7.2　缓冲区管理策略 124

4.7.3　物理操作符选择和缓冲区管理的关系 126

4.7.4　习题 126

4.8　使用超过两趟的算法 127

4.8.1　基于排序的多趟算法 127

4.8.2　基于排序的多趟算法的性能 127

4.8.3　基于散列的多趟算法 128

4.8.4　基于散列的多趟算法的性能 128

4.8.5　习题 129

4.9　小结 129

4.10　参考文献 130

第5章　查询编译器 132

5.1　语法分析和预处理 132

5.1.1　语法分析与语法分析树 132

5.1.2 SQL的一个简单子集的语法 133

5.1.3　预处理器 135

5.1.4　预处理涉及视图的查询 135

5.1.5　习题 137

5.2　用于改进查询计划的代数定律 137

5.2.1　交换律与结合律 137

5.2.2　涉及选择的定律 138

5.2.3　下推选择 140

5.2.4　涉及投影的定律 141

5.2.5　有关连接与积的定律 142

5.2.6　有关消除重复的定律 142

5.2.7　涉及分组与聚集的定律 143

5.2.8　习题 144

5.3　从语法分析树到逻辑查询计划 145

5.3.1　转换成关系代数 145

5.3.2　从条件中去除子查询 146

5.3.3　逻辑查询计划的改进 149

5.3.4　可结合／可分配的运算符的分组 150

5.3.5　习题 151

5.4　运算代价的估计 151

5.4.1 中间关系大小的估计 151

5.4.2　投影运算大小的估计 152

5.4.3　选择运算大小的估计 152

5.4.4　连接运算大小的估计 154

5.4.5　多连接属性的自然连接 155

5.4.6　多个关系的连接 156

5.4.7　其他运算大小的估计 157

5.4.8　习题 157

5.5　基于代价的计划选择介绍 158

5.5.1　大小参数估计值的获取 158

5.5.2　统计量的计算 160

5.5.3　减少逻辑查询计划代价的启发式估计 161

5.5.4　枚举物理计划的方法 162

5.5.5　习题 164

5.6　连接顺序的选择 165

5.6.1　连接的左右参数的意义 165

5.6.2　连接树 165

5.6.3　左深连接树 165

5.6.4　通过动态规划来选择连接顺序和分组 168

5.6.5　带有更具体的代价函数的动态规划 170

5.6.6　选择连接顺序的贪婪算法 171

5.6.7　习题 171

5.7　物理查询计划选择的完成 172

5.7.1　选取一个选择方法 172

5.7.2　选取连接方法 173

5.7.3　流水操作与物化 174

5.7.4　一元流水运算 175

5.7.5　二元运算的流水操作 175

5.7.6　物理查询计划的符号 176

5.7.7　物理运算的排序 178

5.7.8　习题 179

5.8　小结 179

5.9　参考文献 180

第6章 系统故障对策 182

6.1　可恢复操作的问题和模型 182

6.1.1　故障模式 182

6.1.2　关于事务的进一步讨论 183

6.1.3　事务的正确执行 184

6.1.4　事务的原语操作 185

6.1.5　习题 186

6.2 undo日志 187

6.2.1 日志记录 187

6.2.2 undo日志规则 188

6.2.3　使用undo日志的恢复 189

6.2.4　检查点 191

6.2.5　非静止检查点 191

6.2.6　习题 193

6.3 redo日志 194

6.3.1 redo日志规则 194

6.3.2　使用redo日志的恢复 195

6.3.3 redo日志的检查点 195

6.3.4　使用带检查点redo日志的恢复 196

6.3.5　习题 197

6.4 undo/redo日志 197

6.4.1 undo/redo规则 197

6.4.2　使用undo/redo日志的恢复 198

6.4.3 undo/redo日志的检查点 199

6.4.4　习题 200

6.5　针对介质故障的防护 200

6.5.1　备份 201

6.5.2　非静止转储 201

6.5.3　使用备份和日志的恢复 202

6.5.4　习题 203

6.6　小结 203

6.7　参考文献 204

第7章 并发控制 205

7.1 串行调度和可串行化调度 205

7.1.1　调度 205

7.1.2　串行调度 205

7.1.3　可串行化调度 206

7.1.4　事务语义的影响 207

7.1.5　事务和调度的一种记法 207

7.1.6　习题 208

7.2　冲突可串行化 208

7.2.1 冲突 208

7.2.2　优先图及冲突可串行化判断 209

7.2.3　优先图测试发挥作用的原因 211

7.2.4　习题 211

7.3　使用锁的可串行化实现 213

7.3.1　锁 213

7.3.2　封锁调度器 214

7.3.3　两阶段封锁 214

7.3.4　两阶段封锁发挥作用的原因 215

7.3.5　习题 216

7.4　有多种锁模式的封锁系统 217

7.4.1　共享锁与排他锁 217

7.4.2　相容性矩阵 218

7.4.3　锁的升级 219

7.4.4　更新锁 220

7.4.5　增量锁 220

7.4.6　习题 221

7.5　封锁调度器的一种体系结构 223

7.5.1　插入锁动作的调度器 223

7.5.2　锁表 225

7.5.3　习题 226

7.6　数据库元素的层次 226

7.6.1　多粒度的锁 227

7.6.2　警示锁 227

7.6.3　幻象与插入的正确处理 229

7.6.4　习题 230

7.7　树协议 230

7.7.1　基于树的封锁的动机 230

7.7.2　访问树结构数据的规则 231

7.7.3　树协议发挥作用的原因 232

7.7.4　习题 233

7.8　使用时间戳的并发控制 233

7.8.1　时间戳 234

7.8.2　事实上不可实现的行为 234

7.8.3　脏数据的问题 235

7.8.4　基于时间戳调度的规则 235

7.8.5　多版本时间戳 237

7.8.6　时间戳与封锁 238

7.8.7　习题 238

7.9　使用有效性确认的并发控制 239

7.9.1　基于有效性确认调度器的结构 239

7.9.2　有效性确认规则 239

7.9.3　三种并发控制机制的比较 241

7.9.4　习题 242

7.10　小结 242

7.11　参考文献 243

第8章　再论事务管理 245

8.1　可串行性和可恢复性 245

8.1.1　脏数据问题 245

8.1.2　级联回滚 246

8.1.3　可恢复的调度 246

8.1.4　避免级联回滚的调度 247

8.1.5　基于锁对回滚的管理 247

8.1.6　成组提交 249

8.1.7　逻辑日志 249

8.1.8　从逻辑日志中恢复 251

8.1.9　习题 252

8.2　死锁 253

8.2.1　超时死锁检测 253

8.2.2　等待图 253

8.2.3　通过元素排序预防死锁 255

8.2.4　通过时间戳检测死锁 256

8.2.5　死锁管理方法的比较 257

8.2.6　习题 258

8.3　长事务 258

8.3.1　长事务的问题 259

8.3.2 saga（系列记载） 260

8.3.3　补偿事务 260

8.3.4　补偿事务发挥作用的原因 261

8.3.5　习题 262

8.4　小结 262

8.5　参考文献 263

第9章 并行与分布式数据库 265

9.1　关系的并行算法 265

9.1.1　并行模型 265

9.1.2　一次一个元组的操作的并行 267

9.1.3　整个关系的操作的并行算法 267

9.1.4　并行算法的性能 268

9.1.5　习题 270

9.2 map-reduce并行架构 270

9.2.1　存储模式 270

9.2.2　映射函数 270

9.2.3　归约函数 271

9.2.4　习题 272

9.3　分布式数据库 272

9.3.1　数据的分布 272

9.3.2　分布式事务 273

9.3.3　数据复制 273

9.3.4　习题 274

9.4　分布式查询处理 274

9.4.1　分布式连接操作问题 274

9.4.2　半连接化简 274

9.4.3　多个关系的连接 275

9.4.4　非循环超图 276

9.4.5　非循环超图的完全化简 277

9.4.6　为什么完全化简算法有效 277

9.4.7　习题 278

9.5　分布式提交 278

9.5.1　支持分布式原子性 278

9.5.2　两阶段提交 279

9.5.3　分布式事务的恢复 280

9.5.4　习题 281

9.6　分布式封锁 282

9.6.1　集中封锁系统 282

9.6.2　分布式封锁算法的代价模型 282

9.6.3　封锁多副本的元素 283

9.6.4　主副本封锁 283

9.6.5　局部锁构成的全局锁 284

9.6.6　习题 285

9.7　对等分布式查找 285

9.7.1　对等网络 285

9.7.2　分布式散列问题 286

9.7.3　分布式散列的集中式解决方案 286

9.7.4　带弦的圆 287

9.7.5　带弦的圆上的链接 287

9.7.6　使用手指表查找 288

9.7.7　加入新结点 289

9.7.8　当一个端离开网络 291

9.7.9　当一个端崩溃了 291

9.7.10　习题 291

9.8　小结 292

9.9　参考文献 293

第二部分　现代数据库系统专题第10章 信息集成 295

10.1　信息集成介绍 295

10.1.1　为什么要进行信息集成 295

10.1.2　异质性问题 296

10.2　信息集成的方式 298

10.2.1　联邦数据库系统 298

10.2.2　数据仓库 299

10.2.3 mediator 300

10.2.4　习题 301

10.3　基于mediator的系统中的包装器 302

10.3.1　查询模式的模板 302

10.3.2　包装器生成器 303

10.3.3　过滤器 304

10.3.4　包装器上的其他操作 304

10.3.5　习题 305

10.4　基于能力的优化 306

10.4.1　有限的数据源能力问题 306

10.4.2　描述数据源能力的记号 306

10.4.3　基于能力的查询计划选择 307

10.4.4　加入基于成本的优化 308

10.4.5　习题 308

10.5　优化mediator查询 309

10.5.1　简化的修饰符记号 309

10.5.2　获得子目标的回答 310

10.5.3 Chain算法 310

10.5.4　在mediator上结合并视图 312

10.5.5　习题 313

10.6　以局部作为视图的mediator 314

10.6.1 LAV mediator的动机 314

10.6.2 LAV mediator的术语 315

10.6.3　扩展解决方案 316

10.6.4　合取查询的包含 317

10.6.5　为什么包含映射测试有效 318

10.6.6　发现mediator查询的解决方法 319

10.6.7　为什么LMSS定理能成立 320

10.6.8　习题 320

10.7　实体解析 320

10.7.1　决定是否记录代表一个共同实体 321

10.7.2　合并相似记录 322

10.7.3　相似性和合并函数的有用性质 323

10.7.4　ICAR记录的R-Swoosh算法 324

10.7.5　为什么R-Swoosh算法会有效 325

10.7.6　实体解析的其他方法 325

10.7.7　习题 326

10.8　小结 327

10.9　参考文献 328

第11章 数据挖掘 330

11.1　频繁项集挖掘 330

11.1.1　市场-购物篮模型 330

11.1.2　基本定义 331

11.1.3　关联规则 332

11.1.4　频繁项集的计算模型 333

11.1.5　习题 334

11.2　发现频繁项集的算法 334

11.2.1　频繁项集的分布 334

11.2.2　寻找频繁项集的朴素算法 335

11.2.3 A-Priori算法 336

11.2.4 A-Priori算法的实现 337

11.2.5　更好地使用主存 337

11.2.6　何时使用PCY算法 338

11.2.7　多级算法 339

11.2.8　习题 340

11.3　发现近似的商品 341

11.3.1　相似度的Jaccard度量 341

11.3.2 Jaccard相似度的应用 341

11.3.3　最小散列 342

11.3.4　最小散列与Jaccard相似度 343

11.3.5　为什么能用最小散列估计相似度 343

11.3.6　最小散列的实现 343

11.3.7　习题 344

11.4　局部敏感散列 345

11.4.1 LSH实例：实体分辨 345

11.4.2　标签的局部敏感散列 346

11.4.3　最小散列法和局部敏感散列的结合 347

11.4.4　习题 348

11.5　大规模数据的聚簇 348

11.5.1　聚簇的应用 349

11.5.2　距离的定义 350

11.5.3　凝聚式聚簇 352

11.5.4　k-Means算法 353

11.5.5　大规模数据的k-Means方法 354

11.5.6　内存中满载点后的处理过程 355

11.5.7　习题 356

11.6　小结 357

11.7　参考文献 358

第12章 数据库系统与互联网 360

12.1　搜索引擎体系结构 360

12.1.1　搜索引擎的组成 360

12.1.2 Web爬虫 361

12.1.3　搜索引擎中的查询处理 363

12.1.4　对网页进行排名 363

12.2　用于识别重要网页的PageRank 364

12.2.1 PageRank的直观思想 364

12.2.2 PageRank的递归公式——初步尝试 364

12.2.3　爬虫陷阱和死角 366

12.2.4　考虑爬虫陷阱和死角的PageRank 367

12.2.5　习题 368

12.3　特定主题的PageRank 369

12.3.1 “远距离移动”集 369

12.3.2　计算主题相关的PageRank 370

12.3.3　链接作弊 371

12.3.4　主题相关的PageRank和链接作弊 371

12.3.5　习题 372

12.4　数据流 372

12.4.1　数据流管理系统 372

12.4.2　数据流应用 373

12.4.3　数据流数据模型 374

12.4.4　数据流转换为关系 374

12.4.5　关系转换为数据流 375

12.4.6　习题 376

12.5　数据流挖掘 377

12.5.1　动机 377

12.5.2　统计二进制位数 378

12.5.3　统计不同元素的个数 381

12.5.4　习题 381

12.6　小结 382

12.7　参考文献 383