数据库系统实现PDF|Epub|txt|kindle电子书版本网盘下载

数据库系统实现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 526

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 BLOB40

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/O117

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 mediator300

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　以局部作为视图的mediator314

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　用于识别重要网页的PageRank364

12.2.1 PageRank的直观思想364

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

12.2.3　爬虫陷阱和死角366

12.2.4　考虑爬虫陷阱和死角的PageRank367

12.2.5　习题368

12.3　特定主题的PageRank369

12.3.1 “远距离移动”集369

12.3.2　计算主题相关的PageRank370

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