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

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

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

目录1

作者简介1

译者序1

前言1

第1章 DBMS实现概述1

1.1 Megatron 2000数据库系统介绍1

1.1.1 Megatron 2000实现细节2

1.1.2 Megatron 2000如何执行查询3

1.1.3 Megatron 2000有什么问题4

1.2 数据库管理系统概述4

1.2.1 数据定义语言命令4

1.2.2 查询处理概述5

1.2.4 事务处理6

1.2.3 主存缓冲区和缓冲区管理器6

1.2.5 查询处理器7

1.3 本书梗概8

1.3.1 预备知识8

1.3.2 存储管理概述8

1.3.3 查询处理概述9

1.3.4 事务处理概述9

1.3.5 信息集成概述9

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

1.4.1 关系模型回顾10

1.4.2 SQL回顾10

1.4.3 关系的和面向对象的数据12

1.5 小结13

1.6 参考文献14

2.1 存储器层次15

第2章 数据存储15

2.1.1 高速缓冲存储器16

2.1.2 主存储器16

2.1.3 虚拟存储器17

2.1.4 第二级存储器18

2.1.5 第三级存储器19

2.1.6 易失和非易失存储器20

习题21

2.2 磁盘21

2.2.1 磁盘结构21

2.2.2 磁盘控制器23

2.2.3 磁盘存储特性24

2.2.4 磁盘访问特性25

习题28

2.2.6 块的修改28

2.2.5 块的写入28

2.3 第二级存储器的有效使用29

2.3.1 计算的I/O模型30

2.3.2 第二级存储器中的数据排序30

2.3.3 归并排序31

2.3.4 两阶段多路归并排序32

2.3.5 扩展多路归并以排序更大的关系34

习题35

2.4 改善第二级存储器的访问时间36

2.4.1 按柱面组织数据37

2.4.2 使用多磁盘38

2.4.3 磁盘镜像39

2.4.4 磁盘调度和电梯算法39

2.4.5 预取和大规模缓冲42

2.4.6 各种策略及其优缺点43

习题44

2.5 磁盘故障45

2.5.1 间断性故障45

2.5.2 校验和46

2.5.3 稳定存储47

2.5.4 稳定存储的错误处理能力47

习题48

2.6 从磁盘崩溃中恢复48

2.6.1 磁盘的故障模型48

2.6.2 作为冗余技术的镜像49

2.6.3 奇偶块50

2.6.4 一种改进：RAID 552

2.6.5 多个盘崩溃时的处理53

习题55

2.7 小结57

2.8 参考文献58

第3章 数据元素的表示60

3.1 数据元素和字段60

3.1.1 关系型数据库元素的表示60

3.1.2 对象的表示61

3.1.3 数据元素的表示62

3.2 记录65

3.2.1 定长记录的构造65

3.2.2 记录首部67

3.2.3 定长记录在块中的放置68

习题68

3.3 块和记录地址的表示69

3.3.1 客户机-服务器系统69

3.3.2 逻辑地址和结构地址70

3.3.3 指针混写71

3.3.4 块返回磁盘74

3.3.5 被固定的记录和块74

习题75

3.4 变长数据和记录77

3.4.1 具有变长字段的记录77

3.4.2 具有重复字段的记录78

3.4.3 可变格式记录79

3.4.4 不能装入一个块中的记录80

3.4.5 BLOBS81

习题82

3.5 记录的修改83

3.5.1 插入83

3.5.2 删除84

习题85

3.5.3 更新85

3.6 小结86

3.7 参考文献87

第4章 索引结构88

4.1 顺序文件上的索引89

4.1.1 顺序文件89

4.1.2 稠密索引90

4.1.3 稀疏索引92

4.1.4 多级索引93

4.1.5 重复查找键的索引94

4.1.6 数据修改期间的索引维护97

习题101

4.2 辅助索引102

4.2.1 辅助索引的设计103

4.2.2 辅助索引的应用104

4.2.3 辅助索引中的间接105

4.2.4 文档检索和倒排索引107

习题109

4.3 B树111

4.3.1 B树的结构111

4.3.2 B树的应用114

4.3.3 B树中的查找116

4.3.4 范围查询116

4.3.5 B树的插入117

4.3.6 B树的删除119

4.3.7 B树的效率122

习题123

4.4 散列表124

4.4.1 辅存散列表124

4.4.2 散列表的插入125

4.4.3 散列表的删除126

4.4.4 散列表索引的效率126

4.4.5 可扩展散列表127

4.4.6 可扩展散列表的插入127

4.4.7 线性散列表129

4.4.8 线性散列表的插入130

习题132

4.5 小结133

4.6 参考文献134

第5章 多维索引136

5.1 需要多维的应用136

5.1.1 地理信息系统137

5.1.2 数据立方体138

5.1.3 SQL多维查询138

5.1.4 使用传统索引执行范围查询139

5.1.5 利用传统索引执行最邻近查询140

5.1.6 传统索引的其他限制141

5.1.7 多维索引结构综述141

习题142

5.2 多维数据的类散列结构143

5.2.1 网格文件143

5.2.2 网格文件的查找144

5.2.3 网格文件的插入145

5.2.4 网格文件的性能146

5.2.5 分段散列函数147

5.2.6 网格文件和分段散列的比较148

习题149

5.3 多维数据的类树结构151

5.3.1 多键索引151

5.3.2 多键索引的性能152

5.3.3 kd树153

5.3.4 kd树的操作154

5.3.5 使kd树适合辅存156

5.3.6 四叉树157

5.3.7 R树158

5.3.8 R树的操作159

习题161

5.4 位图索引162

5.4.1 位图索引的诱因163

5.4.2 压缩位图164

5.4.3 游程长度编码位向量的操作166

5.4.4 位图索引的管理166

习题168

5.5 小结168

5.6 参考文献169

第6章 查询执行171

6.1 一种查询代数172

6.1.1 并、交和差173

6.1.2 选择操作符174

6.1.3 投影操作符175

6.1.4 关系的积176

6.1.5 连接177

6.1.6 消除重复179

6.1.7 分组和聚集179

6.1.8 排序操作符181

6.1.9 表达式树181

习题183

6.2 物理查询计划操作符介绍185

6.2.3 物理操作符计算模型186

6.2.2 扫描表时的排序186

6.2.1 扫描表186

6.2.4 衡量代价的参数187

6.2.5 扫描操作符的I/O代价188

6.2.6 实现物理操作符的迭代器188

6.3 数据库操作的一趟算法191

6.3.1 一次多元组操作的一趟算法192

6.3.2 全关系的一元操作的一趟算法193

6.3.3 二元操作的一趟算法195

习题197

6.4 嵌套循环连接198

6.4.1 基于元组的嵌套循环连接198

6.4.2 基于元组的嵌套循环连接的迭代器199

6.4.3 基于块的嵌套循环连接算法200

6.4.5 迄今为止的算法小结201

6.4.4 嵌套循环连接的分析201

6.5 基于排序的两趟算法202

6.5.1 利用排序消除重复202

习题202

6.5.2 利用排序进行分组和聚集204

6.5.3 基于排序的并算法204

6.5.4 基于排序的交和差算法205

6.5.5 基于排序的一个简单的连接算法206

6.5.6 简单排序连接的分析208

6.5.7 一种更有效的基于排序的连接208

6.5.8 基于排序的算法小结209

习题209

6.6.1 通过散列划分关系211

6.6.2 基于散列的消除重复算法211

6.6 基于散列的两趟算法211

6.6.3 基于散列的分组和聚集算法212

6.6.4 基于散列的并、交、差算法212

6.6.5 散列连接算法213

6.6.6 节省一些磁盘I/O213

6.6.7 基于散列的算法小结215

习题216

6.7 基于索引的算法216

6.7.1 聚簇和非聚簇索引217

6.7.2 基于索引的选择217

6.7.3 使用索引的连接219

6.7.4 使用有排序索引的连接220

习题221

6.8 缓冲区管理222

6.8.1 缓冲区管理结构222

6.8.2 缓冲区管理策略223

6.8.3 物理操作符选择和缓冲区管理的关系225

习题226

6.9 使用超过两趟的算法226

6.9.1 基于排序的多趟算法227

6.9.2 基于排序的多趟算法的性能227

6.9.3 基于散列的多趟算法228

6.9.4 基于散列的多趟算法的性能228

习题229

6.10 关系操作的并行算法229

6.10.1 并行模型229

6.10.2 一次一个元组的并行操作232

6.10.3 全关系操作的并行算法233

6.10.4 并行算法的性能233

6.11 小结235

习题235

6.12 参考文献237

第7章 查询编译器238

7.1 语法分析238

7.1.1 语法分析与语法分析树239

7.1.2 SQL的一个简单子集的语法239

7.1.3 预处理器243

习题243

7.2 用于改进查询计划的代数定律244

7.2.1 交换律与结合律244

7.2.2 涉及选择的定律246

7.2.3 下推选择248

7.2.4 涉及投影的定律249

7.2.6 有关消除重复的定律252

7.2.5 有关连接与积的定律252

7.2.7 涉及分组与聚集的定律253

习题254

7.3 从语法分析树到逻辑查询计划255

7.3.1 转换成关系代数255

7.3.2 从条件中去除子查询256

7.3.3 逻辑查询计划的改进261

7.3.4 结合／交换操作符的分组262

习题263

7.4 操作代价的估计264

7.4.1 中间关系大小的估计264

7.4.2 投影大小的估计265

7.4.3 选择大小的估计266

7.4.4 连接大小的估计268

7.4.5 多连接属性的自然连接269

7.4.6 多个关系的连接271

7.4.7 其他操作的大小估计272

习题273

7.5 基于代价的计划选择介绍274

7.5.1 大小参数估计值的获取275

7.5.2 统计量的增量计算277

7.5.3 减少逻辑查询计划代价的启发式278

7.5.4 枚举物理计划的方法279

习题281

7.6 连接顺序的选择283

7.6.1 连接的左右变元的意义283

7.6.2 连接树283

7.6.3 左深连接树284

7.6.4 通过动态编程来选择连接顺序和分组286

7.6.5 带有更具体的代价函数的动态编程289

7.6.6 选择连接顺序的贪婪算法290

习题291

7.7 物理查询计划选择的完成292

7.7.1 选取选择方法292

7.7.2 选取连接方法294

7.7.3 流水线操作与物化294

7.7.4 一元流水线操作295

7.7.5 二元流水线操作296

7.7.6 物理查询计划的符号298

7.7.7 物理操作的顺序300

习题300

7.8 小结301

7.9 参考文献302

8.1.1 故障模式304

8.1 可回复操作的问题和模型304

第8章 系统故障对策304

8.1.2 关于事务的进一步讨论306

8.1.3 事务的正确执行307

8.1.4 事务的原语操作308

习题310

8.2 undo日志310

8.2.1 日志记录311

8.2.2 undo日志规则312

8.2.3 使用undo日志的恢复314

8.2.4 检查点315

8.2.5 非静止检查点316

习题318

8.3 redo日志319

8.3.2 使用redo日志的恢复320

8.3.1 redo日志规则320

8.3.3 redo日志的检查点321

8.3.4 使用带检查点的redo日志的恢复322

习题323

8.4 undo/redo日志323

8.4.1 undo/redo规则323

8.4.2 使用undo/redo日志的恢复324

8.4.3 undo/redo日志的检查点325

习题326

8.5 防备介质故障327

8.5.1 备份327

8.5.2 非静止转储328

8.5.3 使用备份和日志的恢复329

8.6 小结330

习题330

8.7 参考文献331

第9章 并发控制333

9.1 串行调度和可串行化调度333

9.1.1 调度333

9.1.2 串行调度334

9.1.3 可串行化调度335

9.1.4 事务语义的影响335

9.1.5 事务和调度的一种记法336

习题337

9.2 冲突可串行性337

9.2.1 冲突337

9.2.2 优先图及冲突可串行性判断339

9.2.3 优先图测试发挥作用的原因341

习题341

9.3.1 锁343

9.3 使用锁的可串行性实现343

9.3.2 封锁调度器345

9.3.3 两阶段封锁346

9.3.4 两阶段封锁发挥作用的原因346

习题347

9.4 用多种锁方式的封锁系统349

9.4.1 共享锁与排他锁349

9.4.2 相容性矩阵350

9.4.3 锁的升级351

9.4.4 更新锁352

9.4.5 增量锁353

习题354

9.5.1 插入锁动作的调度器356

9.5 封锁调度器的一种体系结构356

9.5.2 锁表358

习题360

9.6 数据库元素层次的管理360

9.6.1 多粒度的锁360

9.6.2 警示锁361

9.6.3 幻像与插入的正确处理363

习题364

9.7 树协议364

9.7.1 基于树的封锁的动机365

9.7.2 访问树结构数据的规则365

9.7.3 树协议发挥作用的原因366

习题368

9.8.1 时间戳369

9.8.2 物理上不可实现的行为369

9.8 使用时间戳的并发控制369

9.8.3 脏数据的问题370

9.8.4 基于时间戳调度的规则371

9.8.5 多版本时间戳373

9.8.6 时间戳与封锁374

习题374

9.9 使用有效性确认的并发控制375

9.9.1 基于有效性确认的调度器的结构375

9.9.2 有效性确认规则376

9.9.3 三种并发控制机制的比较378

习题379

9.10 小结379

9.11 参考文献380

10.1.1 脏数据问题382

10.1 读未提交数据的事务382

第10章 再论事务管理382

10.1.2 级联回滚384

10.1.3 回滚的管理384

10.1.4 成组提交385

10.1.5 逻辑日志387

习题388

10.2 视图可串行性389

10.2.1 视图等价性389

10.2.2 多重图与视图可串行性的判断390

10.2.3 视图可串行性的判断393

习题393

10.3 死锁处理394

10.3.1 超时死锁检测394

10.3.2 等待图394

10.3.3 通过元素排序预防死锁396

10.3.4 时间戳死锁检测397

10.3.5 死锁管理方法的比较399

习题400

10.4 分布式数据库401

10.4.1 数据的分布401

10.4.2 分布式事务402

10.4.3 数据复制402

10.4.4 分布式查询优化403

习题403

10.5 分布式提交404

10.5.1 分布式原子性的支持404

10.5.2 阶段提交404

10.5.3 分布式事务的恢复406

习题407

10.6.1 集中封锁系统408

10.6 分布式封锁408

10.6.2 分布式封锁算法的代价模型409

10.6.3 封锁多副本的元素410

10.6.4 主副本封锁410

10.6.5 局部锁构成的全局锁410

习题411

10.7 长事务412

10.7.1 长事务的问题412

10.7.2 saga（系列记载）414

10.7.3 补偿事务414

10.7.4 补偿事务发挥作用的原因416

习题416

10.8 小结417

10.9 参考文献418

11.1.1 信息集成的问题420

11.1 信息集成的方式420

第11章 信息集成420

11.1.2 联邦数据库系统421

11.1.3 数据仓库423

11.1.4 Mediator425

习题426

11.2 基于Mediator系统的包装器427

11.2.1 查询模式的模板428

11.2.2 包装器生成器429

11.2.3 过滤器429

11.2.4 其他在包装器上进行的操作430

习题431

11.3 联机分析处理432

11.3.1 OLAP应用433

11.3.2 OLAP数据的多维视图433

11.3.3 星型模式434

11.3.4 切片和切块436

习题437

11.4 数据立方体438

11.4.1 立方体操作符438

11.4.2 通过物化视图实现立方体441

11.4.3 视图的格443

习题444

11.5 数据挖掘445

11.5.1 数据挖掘的应用446

11.5.2 关联规则的挖掘447

11.5.3 A-Priori算法449

11.6 小结450

11.7 参考文献451

索引453