本书是斯坦福大学计算机科学专业数据库系列课程第二门课的教科书。书中对数据库系统实现原理进行了深入阐述，并具体讨论了数据库管理系统的三个主要成分——存储管理器、查询处理器和事务管理器的实现技术。此外，第2版充分反映了数据管理技术的新进展，对内容进行了扩充，除了在第1版中原有的“信息集成”一章中加入了新的内容外，还增加了两个全新的章：“数据挖掘”和“数据库系统与互联网”。
本书适合作为高等院校计算机专业研究生的教材或本科生的教学参考书，也适合作为从事相关研究或开发工作的专业技术人员的高级参考资料。

数据库系统实现　第2版
Database System Implementation
Second Edition　
(美) Hector Garcia-Molina　 Jeffrey D. Ullman　 Jennifer Widom　（斯坦福大学）著　杨冬青 吴愈青 包小源 唐世渭 等译

本书是关于数据库系统实现方面内容最为全面的著作之一，是美国斯坦福大学计算机科学专业数据库系列课程第二门课程的指定教材。书中从数据库实现者的角度对数据库系统实现原理进行了深入阐述，并具体讨论了数据库管理系统的三个主要成分——存储管理器、查询处理器和事务管理器的实现技术。斯坦福大学计算机科学专业数据库系列课程第一门课程的内容包括数据库设计和数据库编程，本书的后两位作者Jeffrey D. Ullman和Jennifer Widom为该课程编写的教材《数据库系统基础教程》（A First Course in Database Systems）第3版的中文翻译版和英文影印版已由机械工业出版社出版。
本书内容深入且全面，技术实用且先进，叙述深入浅出，是一本难得的高层次的教材，适合作为高等院校计算机专业研究生的教材或本科生的教学参考书，也适合作为从事相关研究或开发工作的专业技术人员的高级参考资料。

作者简介
Hector Garcia-Molina
斯坦福大学计算机科学与电子工程系的Leonard Bosack和Sandra Lerner教授。他在数据库系统、分布式系统和数字图书馆领域中发表了大量论文，研究兴趣包括分布式计算系统、数据库系统和数字图书馆。他是ACM会士、美国艺术与科学院会士和美国国家工程院成员。他在1999年获得了ACM SIGMOD创新奖。

Jeffrey D. Ullman
斯坦福大学计算机科学与电子工程系Stanford W. Ascherman教授，数据库技术专家。他独立或与人合作出版了15本著作，发表了170多篇技术论文，研究兴趣包括数据库理论、数据库集成、数据挖掘和利用信息基础设施进行教育。他是美国国家工程院成员，曾获得Knuth奖、SIGMOD贡献奖、Karlstrom杰出教育家奖和Edgar F. Codd发明奖。

Jennifer Widom
美国康奈尔大学计算机科学博士，现为斯坦福大学计算机科学与电子工程系教授，研究兴趣包括半结构化数据的数据库系统和XML、数据仓库以及主动数据库系统。她是ACM会士、Guggenheim会士和美国国家工程院成员，并且是多个编辑委员会、程序委员会和顾问委员会的成员。她在2007年获得了ACM SIGMOD Edgar F. Codd发明奖。

在斯坦福大学，因为实行的是一年四学期制，所以数据库引论课被分为两门课程。第一门课程是CS145，该课程只要求学生学会使用数据库系统，而不要求知道DBMS实现的内容。CS145是CS245的预修课，CS245介绍DBMS实现。学生若想进一步学习数据库方面的课程，可以学习CS345（此课是理论课）、CS346（此课是DBMS实现实验课）以及CS347课程（此课介绍事务处理及分布式数据库）。
　　从1997年开始，我们已经出版了两本配套教材：《数据库系统基础教程》是为CS145课程编写的，《数据库系统实现》是为CS245课程以及部分CS346课程编写的。本书就是《数据库系统实现》的最新版——第2版。
　　第2版保持了第1版的总体风格，但对于数据存储和索引结构的阐述进行了适当的压缩，分别将原来的两章合并为一章；另外，增加了一章“并行与分布式数据库”（第9章），其中包括了第1版中分散在查询处理和事务管理的相关章节中的内容，并增加了有关分布式查询执行的一些新内容。同时，第2版充分反映了数据管理技术的新进展，对内容进行了扩充，除了在第1版中原有的“信息集成”一章（第10章）中加入了新的内容外，还增加了两个全新的章：“数据挖掘”（第11章）和“数据库系统与互联网”（第12章）。
预备知识
　　学生一般不会在大学的第一学年选修数据库系统实现课程，所以本书读者应具有广泛的计算机科学背景知识。我们假定读者已经学过数据库语言，特别是SQL。读者最好了解关系代数，并且熟悉基本的数据结构。同样，关于文件系统和操作系统的知识也是很有用的。
习题
　　本书几乎在每一节都包括大量的练习，我们用感叹号对难题做了标记，对最难的习题用双感叹号做了标记。
网上支持
　　本书的网址是：
　　http：//infolabstanfordedu/~ullman/fcdbhtml
　　该网站包括勘误表及支持材料。
　本书中文版（ISBN 9787111268284）和影印版（ISBN 9787111247333）已由机械工业出版社出版。——编辑注 

计算机\数据库

本书是关于数据库系统实现方面内容最为全面的著作之一，是美国斯坦福大学计算机科学专业数据库系列课程第二门课程的指定教材。书中从数据库实现者的角度对数据库系统实现原理进行了深入阐述，并具体讨论了数据库管理系统的三个主要成分——存储管理器、查询处理器和事务管理器的实现技术。斯坦福大学计算机科学专业数据库系列课程第一门课程的内容包括数据库设计和数据库编程，本书的后两位作者Jeffrey D. Ullman和Jennifer Widom为该课程编写的教材《数据库系统基础教程》（A First Course in Database Systems）第3版的中文翻译版和英文影印版已由机械工业出版社出版。
本书内容深入且全面，技术实用且先进，叙述深入浅出，是一本难得的高层次的教材，适合于作为高等院校计算机专业研究生的教材或本科生的教学参考书，也适合作为从事相关研究或开发工作的专业技术人员的高级参考资料。

（美） Hector Garcia-Molina （斯坦福大学） Jeffrey D. Ullman （斯坦福大学） Jennifer Widom（斯坦福大学）著：Hector Garcia-Molina 斯坦福大学计算机科学与电子工程系的Leonard Bosack和Sandra Lerner教授。他在数据库系统、分布式系统和数字图书馆领域中发表了大量论文，研究兴趣包括分布式计算系统、数据库系统和数字图书馆。他是ACM会士、美国艺术与科学院会士和美国国家工程院成员。他在1999年获得了ACM SIGMOD创新奖。 Jeffrey D. Ullman 斯坦福大学计算机科学与电子工程系教授Stanford W. Ascherman教授，数据库技术专家。他独立或与人合作出版了15本著作，发表了170多篇技术论文。研究兴趣包括数据库理论、数据库集成、数据挖掘和利用信息基础设施进行教育。他是美国国家工程院成员，曾获得Knuth奖、SIGMOD贡献奖、Karlstrom杰出教育家奖和Edgar F. Codd发明奖。 Jennifer Widom 美国康奈尔大学计算机科学博士，现为斯坦福大学计算机科学与电子工程系教授，研究兴趣包括半结构化数据的数据库系统和XML、数据仓库以及主动数据库系统。她是ACM会士、Guggenheim会士和美国国家工程院成员，并且是多个编辑委员会、程序委员会和顾问委员会的成员。她在2007年获得了ACM SIGMOD Edgar F. Codd发明奖。

杨冬青　吴愈青　包小源　唐世渭　等译：暂无简介

随着计算机硬件、软件技术的飞速发展和计算机系统在各行各业的广泛应用，数据已经成为各种机构的宝贵资源，数据库系统对于当今科研部门、政府机关、企事业单位等来说都是至关重要的。而数据库系统中的核心软件是数据库管理系统（DBMS）。DBMS用于高效地创建和存储大量的数据，并对数据进行有效的管理、处理和维护，是数据库专家和技术人员数十年研究开发的结果，是当前最复杂的系统软件之一。要深入掌握数据库系统的原理和技术，进而从事数据库管理软件和工具的开发，必须学习和研究数据库管理系统实现技术。要深入了解数据库系统的内部结构，以开发出高效的数据库应用系统，也需要学习和研究数据库管理系统实现技术。
　　Hector GarciaMolina、Jeffrey DUllman和Jennifer Widom是斯坦福大学著名的计算机科学家，多年来他们在数据库系统领域中做了大量的开创性工作，由他们撰写的《数据库系统实现》一书是关于数据库系统实现方面内容最为全面的著述之一。我们于2000年将《数据库系统实现》的第1版译成中文，国内许多大学采用它作为研究生数据库课程的教材或主要教学参考书，收到了良好的效果。
　　现在我们又翻译了《数据库系统实现》第2版。第2版保持了第1版的总体风格，首先对数据库系统实现原理进行了深入阐述，并具体讨论了数据库管理系统的三个主要成分——存储管理器、查询处理器和事务管理器的实现技术。与第1版相比，第2版对于数据存储和索引结构的阐述进行了适当的压缩，分别将原来的两章合并为一章；另外，增加了一章“并行与分布式数据库”（第9章），其中包括了第1版中分散在查询处理和事务管理的相关章节中的内容，并增加了有关分布式查询执行的一些新内容，例如，mapreduce并行架构、P2P数据库以及分布式散列的实现等。同时，第2版充分反映了数据管理技术的新进展，对内容进行了扩充，除了在第1版中原有的“信息集成”一章（第10章）中加入了新的内容外，还增加了两个全新的章：“数据挖掘”（第11章）和“数据库系统与互联网”（第12章）。“数据挖掘”一章中包含了关联规则与频繁项集挖掘技术，从一个非常大的数据库或Web页面集合中发现“相似”的项的“最小散列”和“局部敏感散列”等关键技术，以及高维空间中大规模数据的聚簇问题等。“数据库系统与互联网”一章中重点阐述了与互联网相关的两个方面的数据库技术：Web搜索引擎及其PageRank算法，流数据模型以及管理数据流形式的大量数据所需的技术。
　　我们认为这本书既适合作为高等院校计算机专业研究生的教材或本科生的教学参考书，又适合作为从事相关研究或开发工作的专业技术人员的高级参考资料。
　　杨冬青全面组织了本书的翻译，吴愈青、包小源、唐世渭在本书的翻译和审校中做了大量的工作。除此之外，参加翻译的还有闫秋玲、郑丽丽、蔡慧慧、马煜、张棋、陈巍、郭思祺、夏海峰、翁学天、郭少松、李树节。
　　限于译者水平，译文中难免有疏漏和错误，欢迎批评指正。
译者
于北京大学

出版者的话
译者序
译者简介
出版前言
第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参考文献