本书是关于资料库系统实现方面内容最为全面的着作之一，是美国史丹福大学计算机科学专业资料库系列课程第二门课程的指定教材。史丹福大学计算机科学专业资料库系列课程第一门课程的内容包括资料库设计和资料库编程。本书的后两位作者Jeffrey D.UIIman和Jennifer Widom为该课程编写的教材《资料库系统基础教程》（A First Course in Database Systems）第3版的中文翻译版和英文影印版已由机械工业出版社出版。

本书内容深入且全面，技术实用且先进，叙述深入浅出，是一本难得的高层次的教材，适合作为高等院校计算机专业研究生的教材或本科生的教学参考书，也适合作为从事相关研究或开发工作的专业技术人员的高级参考资料。

本书从资料库实现者的角度对资料库系统实现原理进行了深入阐述。并具体讨论了资料库管理系统的三个主要成分——存储管理器、查询处理器和事务管理器的实现技术。

加西亚－莫利纳（Hector Garcia-Molina）史丹福大学计算机科学与电子工程系的Leonard Bosack和Sandra Lerner教授。他在资料库系统、分散式系统和数字图书馆领域中发表了大量论文。研究兴趣包括分散式计算系统、资料库系统和数字图书馆。他是ACM会士、美国艺术与科学院会士和美国国家工程院成员。他在1999年获得TACM SIGMOD创新奖。

出版者的话

译者序

译者简介

出版前言

第1章dbms系统概述

1.1资料库系统的发展

1.1.1早期的资料库管理系统

1.1.2关係资料库系统

1.1.3越来越小的系统

1.1.4越来越大的系统

1.1.5信息集成

1.2资料库管理系统概述

1.2.1数据定义语言命令

1.2.2查询处理概述

1.2.3主存和缓冲区管理器

1.2.4事务处理

1.2.5查询处理器

1.3本书概述

1.4资料库模型和语言回顾

1.4.1关係模型回顾

.1.4.2sql回顾

1.5参考文献

第一部分资料库系统实现

第2章辅助存储管理

2.1存储器层次

2.1.1存储器层次

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

2.1.3易失和非易失存储器

2.1.4虚拟存储器

2.1.5习题

2.2磁碟

2.2.1磁碟结构

2.2.2磁碟控制器

2.2.3磁碟存取特性

2.2.4习题

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

2.3.1计算的i/o模型

2.3.2按柱面组织数据

2.3.3使用多个磁碟

2.3.4磁碟镜像

2.3.5磁碟调度和电梯算法

2.3.6预取和大规模缓冲

2.3.7习题

2.4磁碟故障

2.4.1间断性故障

2.4.2校验和

2.4.3稳定存储

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

2.4.5从磁碟崩溃中恢复

2.4.6作为冗余技术的镜像

2.4.7奇偶块

2.4.8一种改进：raid 5

2.4.9多个盘崩溃时的处理

2.4.10习题

2.5组织磁碟上的数据

2.5.1定长记录

2.5.2定长记录在块中的放置

2.5.3习题

2.6块和记录地址的表示

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

2.6.2逻辑地址和结构地址

2.6.3指针混写

2.6.4块返回磁碟

2.6.5被钉住的记录和块

2.6.6习题

2.7变长数据和记录

2.7.1具有变长栏位的记录

2.7.2具有重複栏位的记录

2.7.3可变格式的记录

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

2.7.5blob

2.7.6列存储

2.7.7习题

2.8记录的修改

2.8.1插入

2.8.2删除

2.8.3修改

2.8.4习题

2.9小结

2.10参考文献

第3章索引结构

3.1索引结构基础

3.1.1顺序档案

3.1.2稠密索引

3.1.3稀疏索引

3.1.4多级索引

3.1.5辅助索引

3.1.6辅助索引的运用

3.1.7辅助索引中的间接

3.1.8文档检索和倒排索引

3.1.9习题

3.2b-树

3.2.1b-树的结构

3.2.2b-树的套用

3.2.3b-树的查找

3.2.4範围查询

3.2.5b-树的插入

3.2.6b-树的删除

3.2.7b-树的效率

3.2.8习题

3.3散列表

3.3.1辅存散列表

3.3.2散列表的插入

3.3.3散列表的删除

3.3.4散列表索引的效率

3.3.5可扩展散列表

3.3.6可扩展散列表的插入

3.3.7线性散列表

3.3.8线性散列表的插入

3.3.9习题

3.4多维索引

3.4.1多维索引的套用

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

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

3.4.4多维索引结构综述

3.5多维数据的散列结构

3.5.1格线档案

3.5.2格线档案的查找

3.5.3格线档案的插入

3.5.4格线档案的性能

3.5.5分段散列函式

3.5.6格线档案和分段散列的比较

3.5.7习题

3.6多维数据的树结构

3.6.1多键索引

3.6.2多键索引的性能

3.6.3kd-树

3.6.4kd-树的操作

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

3.6.6四叉树

3.6.7r-树

3.6.8r-树的操作

3.6.9习题

3.7点阵图索引

3.7.1点阵图索引的动机

3.7.2压缩点阵图

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

3.7.4点阵图索引的管理

3.7.5习题

3.8小结

3.9参考文献

第4章查询执行

4.1物理查询计画操作符介绍

4.1.1扫描表

4.1.2扫描表时的排序

4.1.3物理操作符计算模型

4.1.4衡量代价的参数

4.1.5扫描操作符的i/o代价

4.1.6实现物理操作符的叠代器

4.2一趟算法

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

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

4.2.3二元操作的一趟算法

4.2.4习题

4.3嵌套循环连线

4.3.1基于元组的嵌套循环连线

4.3.2基于元组的嵌套循环连线的叠代器

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

4.3.4嵌套循环连线的分析

4.3.5迄今为止的算法的总结

4.3.6习题

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.4.9基于排序的算法的总结

4.4.10习题

4.5基于散列的两趟算法

4.5.1通过散列划分关係

4.5.2基于散列的消除重複算法

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

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

4.5.5散列连线算法

4.5.6节省一些磁碟i/o

4.5.7基于散列的算法的总结

4.5.8习题

4.6基于索引的算法

4.6.1聚簇和非聚簇索引

4.6.2基于索引的选择

4.6.3使用索引的连线

4.6.4使用有序索引的连线

4.6.5习题

4.7缓冲区管理

4.7.1缓冲区管理结构

4.7.2缓冲区管理策略

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

4.7.4习题

4.8使用超过两趟的算法

4.8.1基于排序的多趟算法

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

4.8.3基于散列的多趟算法

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

4.8.5习题

4.9小结

4.10参考文献

第5章查询编译器

5.1语法分析和预处理

5.1.1语法分析与语法分析树

5.1.2sql的一个简单子集的语法

5.1.3预处理器

5.1.4预处理涉及视图的查询

5.1.5习题

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

5.2.1交换律与结合律

5.2.2涉及选择的定律

5.2.3下推选择

5.2.4涉及投影的定律

5.2.5有关连线与积的定律

5.2.6有关消除重複的定律

5.2.7涉及分组与聚集的定律

5.2.8习题

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

5.3.1转换成关係代数

5.3.2从条件中去除子查询

5.3.3逻辑查询计画的改进

5.3.4可结合/可分配的运算符的分组

5.3.5习题

5.4运算代价的估计

5.4.1中间关係大小的估计

5.4.2投影运算大小的估计

5.4.3选择运算大小的估计

5.4.4连线运算大小的估计

5.4.5多连线属性的自然连线

5.4.6多个关係的连线

5.4.7其他运算大小的估计

5.4.8习题

5.5基于代价的计画选择介绍

5.5.1大小参数估计值的获取

5.5.2统计量的计算

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

5.5.4枚举物理计画的方法

5.5.5习题

5.6连线顺序的选择

5.6.1连线的左右参数的意义

5.6.2连线树

5.6.3左深连线树

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

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

5.6.6选择连线顺序的贪婪算法

5.6.7习题

5.7物理查询计画选择的完成

5.7.1选取一个选择方法

5.7.2选取连线方法

5.7.3流水操作与物化

5.7.4一元流水运算

5.7.5二元运算的流水操作

5.7.6物理查询计画的符号

5.7.7物理运算的排序

5.7.8习题

5.8小结

5.9参考文献

第6章系统故障对策

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

6.1.1故障模式

6.1.2关于事务的进一步讨论

6.1.3事务的正确执行

6.1.4事务的原语操作

6.1.5习题

6.2undo日誌

6.2.1日誌记录

6.2.2undo日誌规则

6.2.3使用undo日誌的恢复

6.2.4检查点

6.2.5非静止检查点

6.2.6习题

6.3redo日誌

6.3.1redo日誌规则

6.3.2使用redo日誌的恢复

6.3.3redo日誌的检查点

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

6.3.5习题

6.4undo/redo日誌

6.4.1undo/redo规则

6.4.2使用undo/redo日誌的恢复

6.4.3undo/redo日誌的检查点

6.4.4习题

6.5针对介质故障的防护

6.5.1备份

6.5.2非静止转储

6.5.3使用备份和日誌的恢复

6.5.4习题

6.6小结

6.7参考文献

第7章并发控制

7.1串列调度和可串列化调度

7.1.1调度

7.1.2串列调度

7.1.3可串列化调度

7.1.4事务语义的影响

7.1.5事务和调度的一种记法

7.1.6习题

7.2冲突可串列化

7.2.1冲突

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

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

7.2.4习题

7.3使用锁的可串列化实现

7.3.1锁

7.3.2封锁调度器

7.3.3两阶段封锁

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

7.3.5习题

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

7.4.1共享锁与排他锁

7.4.2相容性矩阵

7.4.3锁的升级

7.4.4更新锁

7.4.5增量锁

7.4.6习题

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

7.5.1插入锁动作的调度器

7.5.2锁表

7.5.3习题

7.6资料库元素的层次

7.6.1多粒度的锁

7.6.2警示锁

7.6.3幻象与插入的正确处理

7.6.4习题

7.7树协定

7.7.1基于树的封锁的动机

7.7.2访问树结构数据的规则

7.7.3树协定发挥作用的原因

7.7.4习题

7.8使用时间戳的并发控制

7.8.1时间戳

7.8.2事实上不可实现的行为

7.8.3髒数据的问题

7.8.4基于时间戳调度的规则

7.8.5多版本时间戳

7.8.6时间戳与封锁

7.8.7习题

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

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

7.9.2有效性确认规则

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

7.9.4习题

7.10小结

7.11参考文献

第8章再论事务管理

8.1可串列性和可恢复性

8.1.1髒数据问题

8.1.2级联回滚

8.1.3可恢复的调度

8.1.4避免级联回滚的调度

8.1.5基于锁对回滚的管理

8.1.6成组提交

8.1.7逻辑日誌

8.1.8从逻辑日誌中恢复

8.1.9习题

8.2死锁

8.2.1逾时死锁检测

8.2.2等待图

8.2.3通过元素排序预防死锁

8.2.4通过时间戳检测死锁

8.2.5死锁管理方法的比较

8.2.6习题

8.3长事务

8.3.1长事务的问题

8.3.2saga（系列记载）

8.3.3补偿事务

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

8.3.5习题

8.4小结

8.5参考文献

第9章并行与分散式资料库

9.1关係的并行算法

9.1.1并行模型

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

9.1.3整个关係的操作的并行算法

9.1.4并行算法的性能

9.1.5习题

9.2map?reduce并行架构

9.2.1存储模式

9.2.2映射函式

9.2.3归约函式

9.2.4习题

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.4.6为什幺完全化简算法有效

9.4.7习题

9.5分散式提交

9.5.1支持分散式原子性

9.5.2两阶段提交

9.5.3分散式事务的恢复

9.5.4习题

9.6分散式封锁

9.6.1集中封锁系统

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

9.6.3封锁多副本的元素

9.6.4主副本封锁

9.6.5局部锁构成的全局锁

9.6.6习题

9.7对等分散式查找

9.7.1对等网路

9.7.2分散式散列问题

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

9.7.4带弦的圆

9.7.5带弦的圆上的连结

9.7.6使用手指表查找

9.7.7加入新结点

9.7.8当一个端离开网路

9.7.9当一个端崩溃了

9.7.10习题

9.8小结

9.9参考文献

第二部分现代资料库系统专题

第10章信息集成

10.1信息集成介绍

10.1.1为什幺要进行信息集成

10.1.2异质性问题

10.2信息集成的方式

10.2.1联邦资料库系统

10.2.2数据仓库

10.2.3mediator

10.2.4习题

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

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.4.5习题

10.5最佳化mediator查询

10.5.1简化的修饰符记号

10.5.2获得子目标的回答

10.5.3chain算法

10.5.4在mediator上结合併视图

10.5.5习题

10.6以局部作为视图的mediator

10.6.1lav mediator的动机

10.6.2lav mediator的术语

10.6.3扩展解决方案

10.6.4合取查询的包含

10.6.5为什幺包含映射测试有效

10.6.6发现mediator查询的解决方法

10.6.7为什幺lmss定理能成立

10.6.8习题

10.7实体解析

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

10.7.2合併相似记录

10.7.3相似性和合併函式的有用性质

10.7.4icar记录的r?swoosh算法

10.7.5为什幺r?swoosh算法会有效

10.7.6实体解析的其他方法

10.7.7习题

10.8小结

10.9参考文献

第11章数据挖掘

11.1频繁项集挖掘

11.1.1市场-购物篮模型

11.1.2基本定义

11.1.3关联规则

11.1.4频繁项集的计算模型

11.1.5习题

11.2发现频繁项集的算法

11.2.1频繁项集的分布

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

11.2.3a?priori算法

11.2.4a?priori算法的实现

11.2.5更好地使用主存

11.2.6何时使用pcy算法

11.2.7多级算法

11.2.8习题

11.3发现近似的商品

11.3.1相似度的jaccard度量

11.3.2jaccard相似度的套用

11.3.3最小散列

11.3.4最小散列与jaccard相似度

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

11.3.6最小散列的实现

11.3.7习题

11.4局部敏感散列

11.4.1lsh实例：实体分辨

11.4.2标籤的局部敏感散列

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

11.4.4习题

11.5大规模数据的聚簇

11.5.1聚簇的套用

11.5.2距离的定义

11.5.3凝聚式聚簇

11.5.4k?means算法

11.5.5大规模数据的k?means方法

11.5.6记忆体中满载点后的处理过程

11.5.7习题

11.6小结

11.7参考文献

第12章资料库系统与网际网路

12.1搜索引擎体系结构

12.1.1搜索引擎的组成

12.1.2web爬虫

12.1.3搜索引擎中的查询处理

12.1.4对网页进行排名

12.2用于识别重要网页的pagerank

12.2.1pagerank的直观思想

12.2.2pagerank的递归公式——初步尝试

12.2.3爬虫陷阱和死角

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

12.2.5习题

12.3特定主题的pagerank

12.3.1“远距离移动”集

12.3.2计算主题相关的pagerank

12.3.3连结作弊

12.3.4主题相关的pagerank和连结作弊

12.3.5习题

12.4数据流

12.4.1数据流管理系统

12.4.2数据流套用

12.4.3数据流数据模型

12.4.4数据流转换为关係

12.4.5关係转换为数据流

12.4.6习题

12.5数据流挖掘

12.5.1动机

12.5.2统计二进制位数

12.5.3统计不同元素的个数

12.5.4习题

12.6小结

12.7参考文献