数据库系统得以实现

作者： Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom 本书是斯坦福大学计算机科学专业数据库系列课程第二门课的教科书。书中对数据库系统实现原理进行了深入阐述，并具体讨论了数据库管理系统的三个主要成分—存储管理器、查询处理器和事务管理器的实现技术。书中还对信息集成的最新技术，例如数据仓库、OLAP、数据挖掘、Mediator、数据立方体系统等进行了介绍。本书适合于作为高等院校计算机专业研究生的教材或本科生的教学参考书，也适合作为从事相关研究或开发工作的专业技术人员的高级参考资料 译者序 前言 第1章 DBMS实现概述 1.1 Megatr on 2000数据库系统介绍 1.1.1 Megatr on 2000实现细节 1.1.2 Megatron 2000如何执行查询 1.1.3 Megatron 2000有什么问题 1.2 数据库管理系统概述 1.2.1 数据定义语言命令 1.2.2 查询处理概述 1.2.3 主存缓冲区和缓冲区管理器 1.2.4 事务处理 1.2.5 查询处理器 1.3 本书梗概 1.3.1 预备知识 1.3.2 存储管理概述 1.3.3 查询处理概述 1.3.4 事务处理概述 1.3.5 信息集成概述 1.4 数据库模型和语言回顾 1.4.1 关系模型回顾 1.4.2 SQL回顾 1.4.3 关系的和面向对象的数据 1.5 小结 1.6 参考文献 第2章 数据存储 2.1 存储器层次 2.1.1 高速缓冲存储器 2.1.2 主存储器 2.1.3 虚拟存储器 2.1.4 第二级存储器 2.1.5 第三级存储器 2.1.6 易失和非易失存储器 习题 2.2 磁盘 2.2.1 磁盘结构 2.2.2 磁盘控制器 2.2.3 磁盘存储特性 2.2.4 磁盘访问特性 2.2.5 块的写入 2.2.6 块的修改 习题 2.3 辅助存储器的有效使用 2.3.1 计算的I/O模型 2.3.2 辅助存储器中的数据排序 2.3.3 归并排序 2.3.4 两阶段多路归并排序 2.3.5 扩展多路归并以排序更大的关系 习题 2.4 改善辅助存储器的访问时间 2.4.1 按柱面组织数据 2.4.2 使用多个磁盘 2.4.3 磁盘镜像 2.4.4 磁盘调度和电梯算法 2.4.5 预取和大规模缓冲 2.4.6 各种策略及其优缺点 习题 2.5 磁盘故障 2.5.1间断性故障 2.5.2 校验和 2.5.3 稳定存储 2.5.4 稳定存储的错误处理能力 习题 2.6 从磁盘崩溃中恢复 2.6.1 磁盘的故障模型 2.6.2 作为冗余技术的镜像 2.6.3 奇偶块 2.6.4 一种改进：RAID 2.6.5 多个盘崩溃时的处理 习题 2.7 小结 2.8 参考文献 第3章 数据元素的表示 3.1 数据元素和字段 3.1.1 关系型数据库元素的表示 3.1.2 对象的表示 3.1.3 数据元素的表示 3.2 记录 3.2.1 定长记录的构造 3.2.2 记录首部 3.2.3 定长记录在块中的放置 习题 3.3 块和记录地址的表示 3.3.1 客户机-服务器系统 3.3.2 逻辑地址和结构地址 3.3.3 指针混写 3.3.4 块返回磁盘 3.3.5 被固定的记录和块 习题 3.4 变长数据和记录 3.4.1 具有变长字段的记录 3.4.2 具有重复字段的记录 3.4.3 变格式的记录 3.4.4 不能装入一个块中的记录 3.4.5 BLOBS 习题 3.5 记录的修改 3.5.1 插入 3.5.2 删除 3.5.3 修改 习题 3.6 小结 3.7 参考文献 第4章 索引结构 4.1 顺序文件上的索引 4.1.1 顺序文件 4.1.2 稠密索引 4.1.3 稀疏索引 4.1.4 多级索引 4.1.5 重复键的索引 4.1.6 数据修改期间的索引维护 习题 4.2 辅助索引 4.2.1 辅助索引的设计 4.2.2 辅助索引的应用 4.2.3 辅助索引中的间接 4.2.4 文档检索和倒排索引 习题 4.3 B树 4.3.1 B树的结构 4.3.2 B树的应用 4.3.3 B树中的查找 4.3.4 范围查询 4.3.5 B树的插入 4.3.6 B树的删除 4.3.7 B树的效率 习题 4.4 散列表 4.4.1 辅存散列表 4.4.2 散列表的插入 4.4.3 散列表的删除 4.4.4 散列表索引的效率 4.4.5 可扩展散列表 4.4.6 可扩展散列表的插入 4.4.7 线性散列表 4.4.8 线性散列表的插入 习题 4.5 小结 4.6 参考文献 第5章 多维索引 5.1 需要多维的应用 5.1.1 地理信息系统 5.1.2 数据立方体 5.1.3 SQL多维查询 5.1.4 使用传统索引执行范围查询 5.1.5 利用传统索引执行最邻近查询 5.1.6 传统索引的其他限制 5.1.7 多维索引结构综述 习题 5.2 多维数据的类散列结构 5.2.1 网格文件 5.2.2 网格文件的查找 5.2.3 网格文件的插入 5.2.4 网格文件的性能 5.2.5 分段散列函数 5.2.6 网格文件和分段散列的比较 习题 5.3 多维数据的类树结构 5.3.1 多键索引 5.3.2 多键索引的性能 5.3.3 kd树 5.3.4 kd树的操作 5.3.5 使kd树适合辅存 5.3.6 四叉树 5.3.7 R树 5.3.8 R树的操作 习题 5.4 位图索引 5.4.1 位图索引的诱因 5.4.2 压缩位图 5.4.3 游程长度编码位向量的操作 5.4.4 位图索引的管理 习题 5.5 小结 5.6 参考文献 第6章 查询执行 6.1 一种查询代数 6.1.1 并、交和差 6.1.2 选择操作符 6.1.3 投影操作符 6.1.4 关系的积 6.1.5 连接 6.1.6 消除重复 6.1.7 分组和聚集 6.1.8 排序操作符 6.1.9 表达式树 习题 6.2 物理查询计划操作符介绍 6.2.1 扫描表 6.2.2 扫描表时的排序 6.2.3 物理操作符计算模型 6.2.4 衡量代价的参数 6.2.5 扫描操作符的I/O 代价 6.2.6 实现物理操作符的迭代器 6.3 数据库操作的一趟算法 6.3.1 一次多元组操作的一趟算法 6.3.2 全关系的一元操作的一趟算法 6.3.3 二元操作的一趟算法 习题 6.4 嵌套循环连接 6.4.1 基于元组的嵌套循环连接 6.4.2 基于元组的嵌套循环连接的迭代器 6.4.3 基于块的嵌套循环连接算法 6.4.4 嵌套循环连接的分析 6.4.5 迄今为止的算法的小结 习题 6.5 基于排序的两趟算法 6.5.1 利用排序去除重复 6.5.2 利用排序进行分组和聚集 6.5.3 基于排序的并算法 6.5.4 基于排序的交和差算法 6.5.5 基于排序的一个简单的连接算法 6.5.6 简单排序连接的分析 6.5.7 一种更有效的基于排序的连接 6.5.8 基于排序的算法小结 习题 6.6 基于散列的两趟算法 6.6.1 通过散列划分关系 6.6.2 基于散列的消除重复算法 6.6.3 基于散列的分组和聚集算法 6.6.4 基于散列的并、交、差算法 6.6.5 散列连接算法 6.6.6 节省一些磁盘I/O 6.6.7 基于散列的算法小结 习题 6.7 基于索引的算法 6.7.1 聚簇和非聚簇索引 6.7.2 基于索引的选择 6.7.3 使用索引的连接 6.7.4 使用有排序索引的连接 习题 6.8 缓冲区管理 6.8.1 缓冲区管理结构 6.8.2 缓冲区管理策略 6.8.3 物理操作符选择和缓冲区管理的关系 习题 6.9 使用超过两趟的算法 6.9.1 基于排序的多趟算法 6.9.2 基于排序的多趟算法的性能 6.9.3 基于散列的多趟算法 6.9.4 基于散列的多趟算法的性能 习题 6.10 关系操作的并行算法 6.10.1 并行模型 6.10.2 一次一个元组的并行操作 6.10.3 全关系操作的并行算法 6.10.4 并行算法的性能 习题 6.10 小结 6.11 参考文献 第7章 查询编译器 7.1 语法分析 7.1.1 语法分析与语法分析树 7.1.2 SQL的一个简单子集的语法 7.1.3 预处理器 习题 7.2 用于改进查询计划的代数定律 7.2.1 交换律与结合律 7.2.2 涉及选择的定律 7.2.3 下推选择 7.2.4 涉及投影的定律 7.2.5 有关连接与积的定律 7.2.6 有关重复消除的定律 7.2.7 涉及分组与聚集的定律 习题 7.3 从语法分析树到逻辑查询计划 7.3.1 转换成关系代数 7.3.2 从条件中去除子查询 7.3.3 逻辑查询计划的改进 7.3.4 结合/分配运算符的分组 习题 7.4 操作代价的估计 7.4.1 中间关系大小的估计 7.4.2 投影大小的估计 7.4.3 选择大小的估计 7.4.4 连接大小的估计 7.4.5 多连接属性的自然连接 7.4.6 多个关系的连接 7.4.7 其他操作的大小估计 习题 7.5 基于代价的计划选择介绍 7.5.1 大小参数估计值的获取 7.5.2 统计量的增量计算 7.5.3 减少逻辑查询计划代价的启发式 7.5.4 枚举物理计划的方法 习题 7.6 连接顺序的选择 7.6.1 连接的左右变元的意义 7.6.2 连接树 7.6.3 左深连接树 7.6.4 通过动态编程来选择连接顺序和分组 7.6.5 带有更具体的代价函数的动态编程 7.6.6 选择连接顺序的贪婪算法 习题 7.7 物理查询计划选择的完成 7.7.1 选取选择方法 7.7.2 选取连接方法 7.7.3 流水线操作与物化 7.7.4 一元流水线操作 7.7.5 二元流水线操作 7.7.6 物理查询计划的符号 7.7.7 物理操作的顺序 习题 7.8 小结 7.9 参考文献 第8章 系统故障对策 8.1 可回复操作的问题和模型 8.1.1 故障模式 8.1.2 关于事务的进一步讨论 8.1.3 事务的正确执行 8.1.4 事务的原语操作 习题 8.2 undo日志 8.2.1 日志记录 8.2.2 undo日志规则 8.2.3 使用undo日志的恢复 8.2.4 检查点 8.2.5 非静止检查点 习题 8.3 redo日志 8.3.1 redo日志规则 8.3.2 使用redo日志的恢复 8.3.3 redo日志的检查点 8.3.4 使用带检查点的redo日志的恢复 习题 8.4 undo/redo日志 8.4.1 undo/redo规则 8.4.2 使用undo/redo日志的恢复 8.4.3 undo/redo日志的检查点 习题 8.5 防备介质故障 8.5.1 备份 8.5.2 非静止转储 8.5.3 使用备份和日志的恢复 习题 8.6 小结 8.7 参考文献 第9章 并发控制 9.1 串行调度和可串行化调度 9.1.1 调度 9.1.2 串行调度 9.1.3 可串行化调度 9.1.4 事务语义的影响 9.1.5 事务和调度的一种记法 习题 9.2 冲突可串行性 9.2.1 冲突 9.2.2 优先图及冲突可串行性判断 9.2.3 优先图测试发挥作用的原因 习题 9.3 使用锁的可串行性实现 9.3.1 锁 9.3.2 *调度器 9.3.3 两阶段* 9.3.4 两阶段*发挥作用的原因 习题 9.4 用多种锁方式的*系统 9.4.1 共享锁与排他锁 9.4.2 相容性矩阵 9.4.3 锁的升级 9.4.4 更新锁 9.4.5 增量锁 习题 9.5 *调度器的一种体系结构 9.5.1 插入锁动作的调度器 9.5.2 锁表 习题 9.6 数据库元素层次的管理 9.6.1 多粒度的锁 9.6.2 警示锁 9.6.3 幻象与插入的正确处理 习题 9.7 树协议 9.7.1 基于树的*的动机 9.7.2 访问树结构数据的规则 9.7.3 树协议发挥作用的原因 习题 9.8 使用时间戳的并发控制 9.8.1 时间戳 9.8.2 物理上不可实现的行为 9.8.3 脏数据的问题 9.8.4 基于时间戳调度的规则 9.8.5 多版本时间戳 9.8.6 时间戳与* 习题 9.9 使用有效性确认的并发控制 9.9.1 基于有效性确认的调度器的结构 9.9.2 有效性确认规则 9.9.3 三种并发控制机制的比较 习题 9.10 小结 9.11 参考文献 第10章 再论事务管理 10.1 读未提交数据的事务 10.1.1 脏数据问题 10.1.2 级联回滚 10.1.3 回滚的管理 10.1.4 成组提交 10.1.5 逻辑日志 习题 10.2 视图可串行性 10.2.1 视图等价性 10.2.2 多重图与视图可串行性的判断 10.2.3 视图可串行性的判断 习题 10.3 死锁处理 10.3.1 超时死锁检测 10.3.2 等待图 10.3.3 通过元素排序预防死锁 10.3.4 时间戳死锁检测 10.3.5 死锁管理方法的比较 习题 10.4 分布式数据库 10.4.1 数据的分布 10.4.2 分布式事务 10.4.3 数据复制 10.4.4 分布式查询优化 习题 10.5 分布式提交 10.5.1 分布式原子性的支持 10.5.2 两阶段提交 10.5.3 分布式事务的恢复 习题 10.6 分布式* 10.6.1 集中*系统 10.6.2 分布式*算法的代价模型 10.6.3 *多副本的元素 10.6.4 主副本* 10.6.5 局部锁构成的全局锁 习题 10.7 长事务 10.7.1 长事务的问题 10.7.2 saga（系列记载） 10.7.3 补偿事务 10.7.4 补偿事务发挥作用的原因 习题 10.8 小结 10.9 参考文献 第11章 信息集成 11.1 信息集成的方式 11.1.1 信息集成的问题 11.1.2 联邦数据库系统 11.1.3 数据仓库 11.1.4 Mediator 习题 11.2 基于Mediator系统的包装器 11.2.1 查询模式的模板 11.2.2 包装器生成器 11.2.3 过滤器 11.2.4 其他在包装器上进行的操作 习题 11.3 联机分析处理 11.3.1 OLAP应用 11.3.2 OLAP数据的多维视图 11.3.3 星型模式 11.3.4 切片和切块 习题 11.4 数据立方体 11.4.1 立方体操作符 11.4.2 通过物化视图实现立方体 11.4.3 视图的格 习题 11.5 数据挖掘 11.5.1 数据挖掘的应用 11.5.2 关联规则的挖掘 11.5.3 A-Priori算法 11.6 小结 11.7 参考文献