《数据库管理系统原理与设计》由于内容全面,实践性强,已经成为了数据库课程的**教材。全书分为数据库基础,应用程序开发、存储与索引、查询评估、事务管理、数据库设计与调整、**主题等七大部分,对数据库的设计与使用、数据库管理系统基本原理与实现技术,以及数据库研究的新进展做了详细论述。《数据库管理系统原理与设计》以一个网上书店的完整设计为例,介绍了数据库 系统的具体实现过程。第3版保留了前两版的传统优点,并且加入了许多关于数据库*新研究和发展的内容,每章后面精选的复习题和练习使《数据库管理系统原理与设计》更加吸引人,可读性更强。
《数据库管理系统原理与设计》可作为高等院校计算机专业本科生、研究生和教师的教材和教学参考,对于从事数据库系统研究以及学习数据库系统技术的人也很有参考价值。

数据库管理系统(DBMS)是管理信息的基本工具,它得到广泛的使用,同时数据库系统原理和实践也是计算机科学课程的有机组成部分。本书覆盖了现代DBMS的基础,尤其是关系数据库系统。作为本科生的数据库入门课程的教材,我们希望以清晰而简洁的方式组织书中的内容。
全书注重“数量”对于教学效果的影响,给出了大量而详细的示例。每一章还有大量的练习(教师可以从网上得到答案),用于巩固学生应用概念,提高解决实际问题的能力。本书丰富的内容,再加上精选的研究性论文就可以支持一门**课程。与本书配套的软件和编程训练相结合,本书可以用在两种不同的入门级课程中。
(1) 侧重应用的课程:涵盖了数据库系统的原理,侧重于应用开发。第3版新增两章关于数据库的应用与开发(一章是关于数据库后台应用,另一章是关于Java和Internet应用架构),全书也进行了很大的修改以适应应用类课程的需求。本书还提供实际问题和充足的联机资料(例如,SQL查询和Java应用的代码,联机数据库和解决方案),使讲授这类侧重应用的课程更加容易。
(2) 侧重系统的课程:侧重于有关系统的知识,要求学生具有良好的C和C++的编程经验。Minibase软件可以用作学生实现关系DBMS课程作业的软件基础。该软件的几个核心模块(例如,堆文件、缓冲区管理器、B+树、哈希索引、各种连接算法、并发控制和恢复算法)在文中都有详细的描述,从而使得学生能够使用给定的类接口(C++)来完成项目。
毫无疑��,很多教师会选择讲授介于这两者之间的课程。本书第3版提供了模块化的知识组织方式,为混合类型授课提供了方便。同时,本书也为更**的课程提供了充足的资料。
第3版的内容
本书主要分为七大部分,如图0.1所示。基础知识部分主要介绍数据库系统、ER模型和关系模型的相关知识,讲述了如何创建和使用数据库,涵盖了数据库的设计和查询,以及对SQL查询语句的深入研究。教师可以根据自己的需要省略某些内容(例如,关系演算、ER模型或者SQL查询语句的某些部分),但是,这些内容对每个学习数据库知识的学生都是重要的,所以建议教师尽可能地详细讲解这些知识。部分内容侧 重 关 系一数据库基础侧重应用与系统二应用程序开发侧重应用三存储与索引侧重系统四查询评估侧重系统五事务管理侧重系统六数据库设计与调整侧重应用七**主题侧重应用与系统图0.1第3版的内容组织方式在其余的六个主要部分中,每一部分或者侧重应用或者侧重系统。三个侧重系统讲解的部分都有对本部分内容进行概述的章节,例如,本书第8章是对存储与索引部分的概述。教师可以单独讲授这些章节,也可以将其作为某部分的一章。例如,在侧重应用的课程中,第8章可能是惟一涉及到存储和索引的章节,然而在侧重系统的课程中,可以从第9章到第11章中挑出一章来对第8章的内容进行补充。数据库设计与性能调整部分,主要讲述如何为实现**访问而进行性能调整和设计。这些侧重应用的部分*好是在学生们掌握了数据库系统结构之后讲授,因此放到了本书靠后的部分。
建议课程大纲
本书可以用在两种不同的入门级课程中,一种课程侧重于应用,另一种侧重于系统知识。
侧重于应用的入门课程的课程大纲如下:基础知识部分,应用开发部分,接着第三、四和五部分的概述章节,以数据库设计与调整结束。按照该方法,章节从属依赖关系保持在*低点,可以使讲授者能够很容易调整和添加其他内容。**部分是基础知识部分,应该*先讲授,在讲授第三、第四和第五部分时,应讲授其概述部分。在**部分到第四部分的章节中惟一的依赖关系如图0.2所示。**部分的章节应该按图中的顺序讲解。但是,为了尽快开始SQL查询内容,我们也可以跳过关系代数和关系演算部分(尽管我们认为这些内容是重要的,并且建议*好在开始SQL语句之前讲授)。
侧重于系统的入门课程包括基础知识部分和侧重系统的部分。对于侧重系统的课程,重要的是编程计划的时间安排(例如,使用Minibase软件),这需要早接触系统方面的知识。章节之间的依赖和从属关系已被尽量降低,以保证在讲授第1章和第3章之后能够尽早开始侧重系统的内容学习。
本书提供的充足资料使课程的选择更加多样化。在入门级课程中选择以应用为**或者以系统为**将某些内容割舍;实际上,本书提供的资料足以满足对数据库知识全面的学习。扩展部分的内容覆盖范围广,可以作为**课程的核心内容,满足更深层次的读者需求。
补充材料
本书提供了大量的联机补充资料:
■联机章节:为了在书中给新的内容留出空间,例如应用与开发,知识获取和XML,我们把讲述QBE的章节放到了网上。学生可以从本书的网站上下载这一章的内容。本章的习题的答案包含在答案集中。
■课程幻灯片:包括所有章节的MS Powerpoint、Postscript和PDF格式的讲义的幻灯片都可以从网站上下载。另外,教师还可以从网上得到本书中使用的所有图片(xfig格式),根据教学需要进行修改。
■练习答案:本书提供了大量有深度的练习题。学生可以通过因特网获得Postscript和PDF格式的奇数题号的习题答案和每章的幻灯片,教师则可以获得全部的习题答案。
■软件:本书提供两种软件。一种是Minibase,这是为侧重系统的课程提供的一个小型的关系DBMS。在第30章中,本书提供了以Minibase为基础的例题和答案,这些内容仅提供给教师。另一种是,本书提供了书中所有SQL和Java应用开发习题的代码,如何创建数据库的示例和如何创建商业DBMS的方案。同样,学生只能得到奇数题号习题的答案,而教师可以得到全部的答案。
■教师手册:提供对每章中内容的注释和小结,使教师在强调或者省略某些内容时有所参考。手册中还包括对联机资料的注释,为布置习题和课程作业提供了很多建议。手册还包括了本书作者教学时使用的考试卷子,当然,这些也仅提供给教师。
其他信息
本书主页的URL:
http://www.cs.wisc.edu/~dbbook
该主页上列出了从第2版到第3版的内容变动,该主页经常更新,同时含有针对书中所有错误、幻灯片和补充材料的链接。教师可以定期访问该站点,或者在站点上注册,这样就可以得到电子邮件形式的重要更新通知。
致谢
本书由CS564的讲义演变而来,CS564是UWMadison为本科高年级学生和研究生开设的介绍性的数据库课程。David DeWitt开设了本课程,同时开发了Minirel课程设计,该设计要求学生编写经过精心挑选的关系DBMS的某些部分。关于本材料的想法是在讲授CS564的过程中形成的,而Minirel则促进了Minibase的出现。Minibase更为全面(例如带有查询优化器和可视化软件),同时又尽量保持Minirel的实质。Mike Carey和我共同设计了Minibase的许多部分。我的讲义(后来成了本书)受到了Mike的讲义和Yannis Ioannidis的讲稿幻灯片的影响。
Joe Hellerstein在Berkeley使用了本书的测试版,同时提供了非常宝贵的反馈信息、幻灯片的支持和对本书一些引人入胜的引用。与他一起写面向对象数据库一章实在是一种乐趣。
C. Mohan提供了非常宝贵的帮助,他耐心地回答了许多在各种商业系统中的实现技术问题,尤其是索引、并发控制和恢复算法。Moshe Zloof回答了许多关于QBE语义和基于QBE的商业系统问题。Ron Fagin、Krishna Kulkarni、Len Shapiro、Jim Melton、Dennis Shasha和Dirk Van Gucht审阅了本书,提出了详细的反馈意见,大大改进了本书的内容和表达。Beloit College的Michael Goldweber、Wyoming的Matthew Haines、SUNY StonyBrook的Michael Kifer、Wisconsin的Jeff Naughton、Cornell的Praveen Seshadri和Brown的Stan Zdonik在其数据库课程中也使用了本书的**版,同时提供了反馈和书中某些错误的报告。尤其是Michael Kifer指出了第2章中的一个老算法的错误,该算法用来计算*小覆盖,同时为了提高模块性,建议在第2章中增加一些SQL特征。Gio Wiederhold的参考书目(被S. Sudarshan转化为Latex格式)和Michael Ley关于数据库和逻辑编程的联机参考书目对编辑本书各章节的参考书目有很大帮助。Shaun Flisakowshi和Uri Shaft在我使用Latex的漫长过程中经常给予我帮助。
我要特别感谢许多许多学生对Minibase软件做出的贡献。当我开发第1版(其中的大部分都被废弃了,但是它们影响了以后的版本)的时候,Emmanuel Ackaouy、Jim Pruyne、Lee Schumacher和Michael Lee与我一起工作。Emmanuel Ackaouy和Bryan So是我使用该版本教授CS564时的助教研究生,他们改进该项目的努力超出了对助教研究生的要求。在Berkeley,Paul Aoki使用Minibase的一个版本并提供了许多有用的注解。在CS764(研究生数据库课程)的整个班级中,学生们在我和Mike Carey领导的大量的课程项目中开发了当前Minibase版本的许多部分。当我**次使用Minibase教授CS564时,Amit Shukla和Michael Lee是我的助教研究生,他们进一步开发了该软件。
为开发Minibase组件,几个学生跟我工作了很长时间。这些组件包括可视化的缓冲区管理器和B+树的软件包(Huseyin Bektas、Harry Stavropoulos和Weiqing Huang);查询优化器和可视界面visualizer(Stephen Harris、Michael Lee和Donko Donjerkovic);基于Opossum模式编辑器的ER图工具(Eben Haber)和用于规范化的基于GUI的工具(Andrew Prock和Andy Therber)。另外,Bill Kimmel将CS764课程项目产生的大部分代码进行了综合和修改,它们包括以下部分:存储管理器、缓冲管理程序、文件和存取方法、关系操作和查询计划执行器。Ranjani Ramamurty在整理和综合不同模块上进一步扩展了Bill的工作。Luke Blanshard、Uri Shaft和Shaun Flisakowski把已发布代码的版本组装起来,开发了测试套件和基于Minibase软件的练习。Krishna Kunchithapadam测试了优化器,开发了Minibase GUI部分。
很显然,如果没有这么多天才们的贡献,Minibase软件是不可能产生的。由于该软件是对公众免费使用的,我希望更多的教师能够在讲授面向系统的数据库课程时把大量实现和实验的内容补充到讲义中。
我要感谢许多学生,他们开发和检查了练习的答案,同时对本书的草稿提供了有价值的反馈。按照字母顺序,他们是:X. Bao、S. Biao、M. Chakrabarti、C. Chan、W. Chen、N. Cheung、D. Colwell、C. Fritz、V. Ganti、J. Gehrke、G. Glass、V. Gopalakrishnan、M. Higgrins、T. Jasmin、M. Krishnaprasad、Y. Lin、C. Liu、M. Lusignan、H. Modi、S. Narayanan、D. Randolph、A. Ranganathan、J. Reminga、A. Therber、M. Thomas、Q. Wang、R. Wang、Z. Wang和J. Yuan。Wisconsin的Arcady Grenader、James Harrington和Marti Reames以及Berkeley的Nina Tang提供了特别详细的反馈。
当我与出版商打交道的时候,Charlie Fischer、Avi Siberschatz和Jeff Ullman给了我非常有价值的建议。从McGrawHill、Betsy Jones和Eric Munson的编辑那里得到了大量的评审意见,对本书给出了指导。无论什么时候对于突然出现的问题,Emily Gray和Brad Kosirog总能及时解决。在Wisconsin,Ginny Werner真诚地帮助我处理这些事情。
*后,本书非常耗费时间,在许多方面它带给我家庭的困难比带给我的还多。我的儿子们坦白地表明了他们的观点。那时五岁的Ketan说:“爸爸,不要再写那本无聊的书了。你没有任何时间来陪我。”两岁的Vivek说:“你还在写书?不陪我玩篮球!”他们所有的不满都由我的妻子Apu来承受。虽然如此,在我埋头写这本书的所有夜晚和**,她都努力使这个家庭像往常一样的热闹而幸福(更不用提那些当我埋头于成为一个教员的日子)。同样,在所有这些事情中,我都能看到我双亲的影子:我的父亲酷爱学习,我的母亲疼爱我们,这都影响了我。我的兄弟Kartik对本书的贡献主要是用电话不时地将我从工作中拉回来,但是如果我不感谢他,那么他会生气的。在这里我要感谢我的家庭,他们使我觉得所做的每一件事情都非常有意义(好极了!我知道我找到了一个合理的理由来感谢Kartik)。
第2版的致谢
当我们准备第2版的时候,McGrawHill出版社的Emily Gray和Betsy Jones进行了大量的审阅并提供了指导和帮助。Jonathan Goldstein帮助完成了空间数据库的参考书目。下面列出的审阅者在内容和组织上提供了有价值的反馈意见:Ohio大学的Liming Cai、Kansas大学的Costas Tsatsoulis、Houston大学的KwokBun Yue、Wayne州立大学的Clear Lake和William Grosky、Virginia大学的Sang H. Son、Minnesota大学的James M. Slack、Twente大学(荷兰)的Mankato和Herman Balsters、Caincinnati大学的Karen C. Davis、Florida大学的Joachim Hamer、Tulane大学的Fred Petry、Baylor大学的Gregory Speegle、Texas A&M大学的Salih Yurttas和San Francisco州立大学的David Chao。
许多人指出了第1版中的许多错误。我们要特别感谢下列人士:Portland州立大学的Joseph Albert、Wisconsin大学的Hanyin Chen、Oregon研究生院的Lois Delcambre、Southern Methodist大学的Maggie Eich、Curtin技术大学的Raj Gopalan、Toronto大学的Davood Raflei、South Australia大学的Michael Schrefl、Connecticut大学的Alex Thomasian和Siena大学的Scott Vandenberg。
我要特别感谢那些详细回答商业系统是如何支持各种功能的人们,他们是:IBM公司的Mike Carey、Bruce Lindsay、C. Mohan和James Teng;Informix公司的M. Muralikrishna和Michael Ubell;Microsoft公司的David Campbell、Goetz Graefe和Peter Spiro;Oracle公司的Hakan Jacobsson、Jonathan D. Klein、Muralidhar Krishnaprasad和M. Ziauddin;以及Sybase公司的Marc Chanliau、Lucien Dimino、Sangeeta Doraiswamy、Roger MacNicol和Tirumanjanam Rengarajan。
当Ketan(今年8岁)读了第1版中对自己的感谢后,他提出了一个简单问题:“为什么不把这本书献给我们?为什么不给妈妈?”Ketan,我注意到了这个无法说明的疏漏。Vivek(今年5岁)更关心自己的名声:“爸爸,我的名字是不是出现在本书的所有拷贝上?本书是否在世界上的每一个计算机科学系中人们都使用它?”Vivek,我希望是这样。*后,没有Apu和Keiko的支持,本次修订是不可能完成的。
第3版的致谢
我们感谢Raghav Kaushik在XML讨论中的贡献和Alex Thomasian在并发控制中的贡献。我们还要特别感谢Jim Melton,他提供了自己一本尚未出版的书籍,内容涉及到SQL∶1999标准中面向对象扩展,同时还为第3版草稿检查出错误。Berkeley的Marti Hearst非常慷慨,她提供给我们关于知识获取的幻灯片,Alon Levy和Dan Suciu也乐于让我们采用他们关于XML的课程笔记。Mike Carey则提供给我们关于Web Services的资料。
McGrawHill的Emily Lupash一直在支持和鼓励我们,她整理了由EmbryRiddle Aeronautical大学的Ming Wang,RPI的Cheng Hsu,Masshachusettes大学的Paul Bergstein,SJSU的Archana Sathaye,Purdue的Bharat Bhargava,Bradley的John Fendrich,Central Michigan的Ahmet Ugur,Colorado的Richard Osborne,CCNY的Akira Kawaguchi,Ben Gurion的Mark Last,California大学的Vassilis Tsotras,和Central Florida的Ronald Eaglin提出的大量修改意见。同时,我们对这些给本书建议的学者表示衷心的感谢,他们的宝贵意见大大地提高了本书修订后的水平。我要感谢Gloria Schiesl和Jade Moran非常乐观和**地解决了*后时刻的混乱,他们和Sherry Kane一起为我们制定了非常紧凑合理的日程安排。我还要感谢Michelle Whitaker对本书的封面和封底设计进行了多次的修改。
在Raghu的日记中写道,Ketan模仿骆驼分享帐篷的示例,认为“只有这样是公平的”——Raghu把这本书只献给他和Vivek,因为“妈妈已经享受到这本书了”。尽管这种说法得到Vivek大力热情的支持,再加上溺爱他们的父亲的纵容,然而,这本书仍然献给Apu,就像从第1版开始一样。
对于Johannes来说,没有Keiko的支持和鼓励,没有Elisa睡着时平静可爱的面庞,本次修订是无法完成的。

**部分 数据库基础
第1章 数据库系统概述3
1.1 管理数据4
1.2 历史回顾5
1.3 文件系统和数据库管理系统6
1.4 数据库管理系统的优点7
1.5 数据库管理系统中数据的描述和存储8
1.5.1关系模型8
1.5.2数据库管理系统的抽象级别9
1.5.3数据独立性11
1.6 数据库管理系统中的查询11
1.7 事务管理12
1.7.1事务的并发执行13
1.7.2未完成的事务和系统崩溃13
1.7.3注意要点14
1.8 数据库管理系统的结构14
1.9 与数据库打交道的人15
1.10复习题16

第2章 实体联系模型19
2.1 数据库设计与ER图20
2.1.1其他步骤20
2.2 实体、属性和实体集21
2.3 联系和联系集22
2.4ER模型的其他特征24
2.4.1码约束24
2.4.2参与约束25
2.4.3弱实体25
2.4.4类层次27
2.4.5聚合29
2.5 用ER模型进行概念数据库设计29
2.5.1实体对属性30
2.5.2实体与联系31
2.5.3二元与三元联系32
2.5.4聚合与三元联系33
2.6 大型企业的概念数据库设计34
2.7 统一建模语言34
2.8 案例研究:网上书店35
2.8.1需求分析36
2.8.2概念设计36
2.9 复习题37

第3章 关系模型42
3.1 关系模型简介43
3.1.1使用SQL创建和修改关系45
3.2 关系的完整性约束46
3.2.1码约束47
3.2.2外码约束48
3.2.3一般约束50
3.3 完整性约束的强制执行50
3.3. 1事务与约束52
3.4 查询关系数据53
3.5 逻辑数据库设计:从ER模型到关系模型55
3.5.1从实体集到关系表55
3.5.2从联系集(不包括约束)到关系表56
3.5.3转换带码约束的联系集57
3.5.4转换带有参与约束的联系集58
3.5.5转换弱实体集60
3.5.6转换类层次60
3.5.7转换带聚合的ER图61
3.5.8ER模型到关系模型:更多的示例62
3.6 视图简介63
3.6.1视图、数据独立性和**64
3.6.2视图的更新64
3.7 删除/修改关系表和视图67
3.8 案例研究:网上书店67
3.9 复习题69

第4章 关系代数和演算74
4.1 预备知识74
4.2 关系代数75
4.2.1选择和投影75
4.2.2集合操作76
4.2.3重命名78
4.2.4连接78
4.2.5除80
4.2.6关系代数查询的其他示例81
4.3 关系演算85
4.3.1元组关系演算86
4.3.2域关系演算89
4.4 代数与演算的表达能力91
4.5 复习题92

第5章 SQL:查询、约束与触发器96
5.1 概述97
5.1.1章节组织97
5.2 基本SQL查询的形式99
5.2.1基本SQL查询的示例102
5.2.2SELECT命令中的表达式和字符串103
5.3 UNION、INTERSECT和EXCEPT104
5.4 嵌套查询107
5.4.1嵌套查询简介107
5.4.2相关嵌套查询109
5.4.3集合比较操作109
5.4.4有关嵌套查询的其他示例110
5.5 聚集操作符111
5.5.1GROUP BY和HAVING子句114
5.5.2聚集查询的其他示例117
5.6 空值120
5.6.1使用空值的比较121
5.6.2逻辑连接运算AND、OR和NOT121
5.6.3SQL构造符的作用121
5.6.4外连接122
5.6.5禁止使用空值122
5.7 SQL中的复杂完整性约束123
5.7.1单个表上的约束123
5.7.2域约束与DISTINCT类型123
5.7.3断言:多个表上的完整性约束124
5.8 触发器和主动数据库125
5.8.1SQL的触发器示例125
5.9 设计主动数据库127
5.9.1为什么触发器难以理解127
5.9.2约束和触发器127
5.9.3触发器的其他用途128
5.10 复习题128

第二部分 应用程序开发

第6章 数据库应用开发139
6.1 从应用程序中访问数据库140
6.1.1嵌入式SQL140
6.1.2游标142
6.1.3动态SQL145
6.2 JDBC简介146
6.2.1JDBC体系结构147
6.3 JDBC类和接口148
6.3.1JDBC驱动器管理148
6.3.2连接到数据源148
6.3.3执行SQL语句150
6.3.4结果集151
6.3.5异常和警告152
6.3.6检查数据库元数据153
6.4 SQLJ154
6.4.1编写SQLJ代码155
6.5 存储过程157
6.5.1创建一个简单的存储过程157
6.5.2调用存储过程158
6.5.3SQL/PSM159
6.6 案例研究:网上书店160
6.7 复习题163

第7章 Internet应用166
7.1 引言166
7.2 Internet的一些概念167
7.2.1统一资源标识符167
7.2.2超文本传输协议HTTP168
7.3 HTML文档170
7.4 XML文档171
7.4.1XML简介172
7.4.2XML DTD174
7.4.3特定领域的DTD177
7.5 三层应用体系结构178
7.5.1单层和客户服务器体系结构178
7.5.2三层体系结构180
7.5.3三层体系结构的优点181
7.6 展示层182
7.6.1HTML表单182
7.6.2JavaScript184
7.6.3样式表185
7.7 中间层188
7.7.1CGI:通用网关接口188
7.7.2应用服务器189
7.7.3Servlet190
7.7.4JSP192
7.7.5维护状态193
7.8 案例研究:网上书店195
7.9 复习题197

第三部分 存储与索引

第8章 存储与索引概述207
8.1 外部存储上的数据208
8.2 文件组织与索引208
8.2.1聚簇索引209
8.2.2主索引和次索引210
8.3 索引数据结构210
8.3.1基于哈希的索引211
8.3.2基于树的索引212
8.4 不同文件组织的比较213
8.4.1代价模型214
8.4.2堆文件214
8.4.3排序文件215
8.4.4聚簇文件216
8.4.5具有非聚簇树索引的堆文件217
8.4.6具有非聚簇哈希索引的堆文件218
8.4.7I/O代价的比较219
8.5 索引和性能调整219
8.5.1工作负载的影响220
8.5.2聚簇索引组织220
8.5.3复合搜索码222
8.5.4SQL∶1999中的索引规范225
8.6 复习题225

第9章 存储数据:磁盘和文件230
9.1 存储层次230
9.1.1磁盘231
9.1.2磁盘结构对性能的影响233
9.2 廉价冗余磁盘阵列(RAID)233
9.2.1数据划分234
9.2.2冗余234
9.2.3冗余的层次235
9.2.4RAID级别的选择238
9.3 磁盘空间管理238
9.3.1跟踪空闲块238
9.3.2使用操作系统的文件系统来管理磁盘空间238
9.4 缓冲区管理器239
9.4.1缓冲区替换策略241
9.4.2数据库管理系统和操作系统的缓冲区管理241
9.5 记录文件243
9.5.1堆文件的实现243
9.6 页格式245
9.6.1定长记录245
9.6.2变长记录246
9.7 记录格式247
9.7.1定长记录248
9.7.2变长记录248
9.8 复习题249

第10章 树结构索引253
10.1 树索引介绍254
10.2 索引顺序存取方法255
10.2.1溢出页与加锁考虑257
10.3 B+树:一种动态索引结构257
10.3.1节点格式258
10.4 搜索259
10.5 插入260
10.6 删除262
10.7 重复266
10.8 实际的B+树267
10.8.1码压缩267
10.8.2块加载B+树268
10.8.3秩的概念270
10.8.4rid上插入和删除的影响271
10.9 复习题271

第11章 基于哈希的索引277
11.1 静态哈希278
11.1.1记号与约定279
11.2 可扩展哈希279
11.3 线性哈希283
11.4 可扩展哈希与线性哈希的关系288
11.5 复习题288

第四部分 查 询 评 估

第12章 查询求解概述295
12.1 系统目录296
12.1.1目录中的信息296
12.2 操作符求解概述298
12.2.1三种常用技术298
12.2.2访问路径298
12.3 关系型操作的算法300
12.3.1选择300
12.3.2投影301
12.3.3连接301
12.3.4其他操作302
12.4 查询优化概述303
12.4.1查询求解计划303
12.4.2多处理器查询:流水线求解304
12.4.3迭代操作的接口305
12.5 可选计划:研究这一问题动机的示例306
12.5.1下推选择306
12.5.2使用索引307
12.6 一个典型的优化器做些什么310
12.6.1考虑不同的查询计划310
12.6.2估算计划的代价311
12.7 复习题312

第13章 外排序315
13.1 什么时候DBMS需要对数据进行排序315
13.2 简单的两路归并排序算法316
13.3外归并排序318
13.3.1段数的*小化320
13.4 *小化I/O开销和I/O的次数321
13.4.1块I/O321
13.4.2双缓冲323
13.5 使用B+树来排序323
13.5.1聚簇索引324
13.5.2非聚簇索引324
13.6 复习题326

第14章 关系操作求解328
14.1 选择操作329
14.1.1无索引、未排序的数据329
14.1.2无索引、排序的数据330
14.1.3B+树索引330
14.1.4哈希排序、等价选择331
14.2 一般的选择条件331
14.2.1CNF和索引匹配332
14.2.2求解无析取的选择332
14.2.3求解有析取的选择333
14.3 投影操作334
14.3.1基于排序的投影334
14.3.2基于哈希函数的投影335
14.3.3用于投影的排序和哈希336
14.3.4用于投影的索引使用337
14.4 连接操作337
14.4.1嵌套循环连接算法338
14.4.2排序归并连接算法341
14.4.3哈希连接345
14.4.4一般的连接条件348
14.5 集合操作349
14.5.1用于并和差的排序349
14.5.2用于并和差的哈希349
14.6 聚集操作350
14.6.1使用索引实现聚集351
14.7 缓冲的影响351
14.8 复习题352

第15章 典型的关系查询优化器357
15.1 将SQL查询转换成关系代数表达式358
15.1.1将SQL查询分解成块358
15.1.2把查询块表示成关系代数表达式359
15.2 估算执行计划的开销360
15.2.1估计结果的大小360
15.3 关系代数的等价364
15.3.1选择364
15.3.2投影364
15.3.3叉积和连接364
15.3.4选择、投影和连接365
15.3.5其他的等价366
15.4 列举可选的执行计划366
15.4.1单关系查询367
15.4.2多关系查询370
15.5 嵌套子查询375
15.6 System R优化器377
15.7 查询优化的其他方法377
15.8 复习题378

第五部分 事 务 管 理

第16章 事务管理概述389
16.1 ACID属性390
16.1.1一致性和隔离性390
16.1.2原子性和持久性391
16.2 事务和调度391
16.3 事务的并发执行392
16.3.1并发执行的动机392
16.3.2可串行化392
16.3.3交叉执行带来的异常394
16.3.4包括中止事务的调度396
16.4 基于加锁的并发控制397
16.4.1严格的两阶段加锁397
16.4.2死锁398
16.5 加锁的性能399
16.6SQL对事务的支持399
16.6.1创建和结束事务399
16.6.2应该锁住什么400
16.6.3SQL中事务的特性401
16.7 崩溃恢复简介403
16.7.1偷帧和强制写页403
16.7.2正常执行时与恢复相关的执行步骤404
16.7.3ARIES简介405
16.7.4原子性:实现回滚405
16.8 复习题405

第17章 并发控制409
17.1 2PL、可串行性和可恢复性410
17.1.1观测可串行化411
17.2 加锁管理简介412
17.2.1实现加锁和解锁请求412
17.3 锁转换413
17.4 死锁处理414
17.4.1死锁预防415
17.5 特殊的加锁技术416
17.5.1动态数据库和幻影问题416
17.5.2B+树的并发控制417
17.5.3多粒度锁419
17.6 不加锁的并发控制420
17.6.1乐观的并发控制420
17.6.2基于时间戳的并发控制422
17.6.3多版本并发控制424
17.7 复习题425

第18章 崩溃恢复431
18.1 ARIES算法简介432
18.2 日志433
18.3 与恢复相关的其他数据结构435
18.4 写优先日志协议435
18.5 检查点436
18.6 从系统崩溃中恢复436
18.6.1分析阶段437
18.6.2重做阶段438
18.6.3反做阶段439
18.7 介质恢复442
18.8 其他算法以及与并发控制的交互作用442
18.9 复习题443

第六部分 数据库设计与调整

第19章 模式求精与范式451
19.1 模式求精简介452
19.1.1冗余导致的问题452
19.1.2模式分解453
19.1.3模式分解中的一些问题454
19.2 函数依赖455
19.3 函数依赖推理456
19.3.1函数依赖集的闭包456
19.3.2属性闭包457
19.4 范式458
19.4.1鲍依斯柯德范式458
19.4.2第三范式459
19.5 分解的特性461
19.5.1无损连接分解461
19.5.2保持依赖分解462
19.6 规范化463
19.6.1分解为BCNF463
19.6.2分解为3NF464
19.7 数据库设计中的模式求精467
19.7.1一个实体集上的约束467
19.7.2一个联系集上的约束468
19.7.3识别实体的属性468
19.7.4识别实体集469
19.8 其他类型的依赖470
19.8.1多值依赖470
19.8.2第四范式472
19.8.3连接依赖473
19.8.4第五范式473
19.8.5包含依赖473
19.9 案例研究:网上书店474
19.10 复习题475

第20章 物理数据库设计和调整482
20.1 物理数据库设计简介483
20.1.1数据库负载483
20.1.2物理设计与调整决策484
20.1.3数据库调整的必要性484
20.2 索引选择的指导方针485
20.3 索引选择的基本示例486
20.4 聚簇和索引488
20.4.1两个关系的协同聚簇489
20.5 使只需索引的计划成为可能的索引490
20.6 用于确定索引的辅助工具491
20.6.1自动的索引选择491
20.6.2索引调整向导如何工作492
20.7 数据库调整简介494
20.7.1调整索引494
20.7.2调整概念模式495
20.7.3调整查询和视图496
20.8 调整概念模式时的选择496
20.8.1设置一个弱范式497
20.8.2非规范化497
20.8.3分解的选择497
20.8.4BCNF关系的垂直分解498
20.8.5水平分解499
20.9 调整查询和视图中的选择499
20.10 并发控制的影响501
20.10.1减少锁的保持时间501
20.10.2减少热点502
20.11 案例研究:网上书店503
20.11.1数据库的调整504
20.12 DBMS评测基准504
20.12.1**的DBMS评测基准505
20.12.2评测基准的使用505
20.13 复习题506

第21章 **与认证512
21.1 数据库**简介513
21.2 访问控制513
21.3 任意访问控制514
21.3.1授予和回收视图的访问控制和完整性约束520
21.4 强制性访问控制522
21.4.1多级关系和多实例化523
21.4.2转换通道,DoD**级别524
21.5 Internet应用的**性525
21.5.1加密525
21.5.2认证服务器:SSL协议526
21.5.3数字签名527
21.6 有关**的其他问题528
21.6.1数据库管理员的任务528
21.6.2统计数据库的**529
21.7 案例研究:网上书店530
21.8 复习题531

第七部分 高 级 主 题
第22章 并行与分布式数据库537
22.1 简介537
22.2 并行数据库系统的可用结构538
22.3 并行查询处理539
22.3.1数据划分540
22.3.2并行化顺序数据操作处理程序541
22.4 数据操作的并行化541
22.4.1批量载入和扫描541
22.4.2排序541
22.4.3连接542
22.5 并行查询优化544
22.6 分布式数据库简介544
22.6.1分布式数据库系统的类型545
22.7分布式DBMS的体系结构545
22.7.1客户/服务器系统545
22.7.2协同服务器系统546
22.7.3中间件系统546
22.8 分布式DBMS的数据存储546
22.8.1划分547
22.8.2复制547
22.9 分布式目录管理548
22.9.1命名对象548
22.9.2目录结构548
22.9.3分布数据的独立性549
22.10 分布式查询处理549
22.10.1分布式DBMS中无连接的查询550
22.10.2分布式DBMS中的连接操作550
22.10.3基于代价的查询优化553
22.11 分布式数据的更新554
22.11.1同步复制554
22.11.2异步复制555
22.12 分布式事务557
22.13 分布式并发控制557
22.13.1分布式死锁558
22.14 分布式事务恢复559
22.14.1事务正常执行和提交协议559
22.14.2发生故障后进行恢复560
22.14.3重新讨论两阶段提交561
22.14.4三阶段提交562
22.15 复习题563

第23章 对象数据库系统571
23.1 研究动机示例572
23.1.1新的数据类型573
23.1.2操纵新类型数据574
23.2 结构化数据类型576
23.2.1集合类型576
23.3 结构化类型的数据操纵577
23.3.1行操作577
23.3.2数组操作577
23.3.3其他集合类型的操作578
23.3.4涉及嵌套集合的查询示例578
23.4 封装和抽象数据类型579
23.4.1定义方法580
23.5 继承581
23.5.1定义带有继承的类型582
23.5.2方法联编582
23.5.3集合层次583
23.6对象、对象标识符和引用类型583
23.6.1相等的概念584
23.6.2引用类型的解除584
23.6.3SQL∶1999中的URL和oid584
23.7 ORDBMS的数据库设计585
23.7.1集合类型和ADTs585
23.7.2对象标识符587
23.7.3扩展ER模型588
23.7.4使用嵌套集合589
23.8 实现ORDBMS的挑战590
23.8.1存储和访问方法590
23.8.2查询处理591
23.8.3查询优化593
23.9 OODBMS594
23.9.1ODMG数据模型和ODL594
23.9.2OQL596
23.10 RDBMS与OODBMS和ORDBMS的比较597
23.10.1RDBMS和ORDBMS597
23.10.2OODBMS和ORDBMS的相似点597
23.10.3OODBMS和ORDBMS的不同点597
23.11 复习题598

第24章 演绎数据库604
24.1 递归查询简介605
24.1.1Datalog605
24.2 理论基础607
24.2.1*小模型语义608
24.2.2不动点操作符609
24.2.3**的Datalog程序610
24.2.4*小模型=*小不动点610
24.3 带有否定的递归查询611
24.3.1分层612
24.4 从Datalog到SQL614
24.5 递归查询的求解616
24.5.1无重复推理的不动点求解616
24.5.2下移选择操作来避免不相关的推理618
24.5.3魔集算法619
24.6 复习题621

第25章 数据仓库与决策支持625
25.1 决策支持简介626
25.2 OLAP:多维数据模型627
25.2.1多维数据库设计629
25.3 多维聚集查询630
25.3.1SQL∶1999中的ROLLUP和CUBE631
25.4 SQL∶1999中的WINDOW查询633
25.4.1构造窗口635
25.4.2新的聚集函数635
25.5 快速得到查询结果635
25.5.1得到前N个结果的查询636
25.5.2联机聚集637
25.6 OLAP实现技术638
25.6.1位图索引638
25.6.2连接索引640
25.6.3文件组织640
25.7 数据仓库641
25.7.1创建和维护数据仓库641
25.8 视图和决策支持642
25.8.1视图、OLAP和数据仓库642
25.8.2视图上的查询643
25.9 视图实体化643
25.9.1视图实体化的问题644
25.10 实体化视图的维护645
25.10.1视图的增量维护645
25.10.2维护数据仓库视图647
25.10.3进行视图同步的时机648
25.11 复习题649

第26章 数据挖掘655
26.1 数据挖掘简介655
26.1.1知识发现的过程656
26.2 关联计数657
26.2.1频繁项集657
26.2.2冰山式查询659
26.3 规则挖掘660
26.3.1关联规则660
26.3.2找出关联规则的算法661
26.3.3关联规则和ISA层次661
26.3.4通用化关联规则662
26.3.5顺序模式663
26.3.6使用关联规则进行预测664
26.3.7贝叶斯网络664
26.3.8分类和回归规则665
26.4 树结构规则666
26.4.1决策树667
26.4.2建立决策树的算法668
26.5 聚簇670
26.5.1一个聚簇算法671
26.6 在序列上的相似搜索671
26.6.1找出相似序列的算法673
26.7 增量挖掘和数据流673
26.7.1频繁项集的增量维护674
26.8 其他的数据挖掘任务675
26.9 复习题676

第27章 信息检索和XML数据681
27.1 冲突的世界:数据库、IR和XML682
27.1.1DBMS与IR系统682
27.2 信息检索介绍683
27.2.1向量空间模型683
27.2.2词的TF/IDF权重684
27.2.3文档相似性排序685
27.2.4对成功的衡量:查准率和查全率686
27.3 为文本搜索建立索引686
27.3.1倒排索引686
27.3.2签名文件688
27.4 Web搜索引擎689
27.4.1搜索引擎体系结构689
27.4.2使用链接信息690
27.5 管理DBMS中的文本693
27.5.1松耦合的倒排索引693
27.6 一个XML的数据模型693
27.6.1松散结构的动机694
27.6.2图模型694
27.7 XQuery:查询XML数据695
27.7.1路径表达式696
27.7.2FLWR表达式696
27.7.3元素的排序697
27.7.4分组以及集合值的生成698
27.8 XML查询的有效求值698
27.8.1在RDBMS中存储XML699
27.8.2对XML库进行索引701
27.9 复习题704

第28章 空间数据管理712
28.1 空间数据和查询类型713
28.2 涉及空间数据的应用714
28.3 空间索引简介715
28.3.1已提出的索引结构概述716
28.4 基于空间填充曲线的索引717
28.4.1区域四叉树和Z排序区域数据718
28.4.2使用Z排序的空间查询719
28.5 网格文件719
28.5.1使用网格文件来处理区域721
28.6 R树:点和区域数据721
28.6.1查询722
28.6.2插入和删除操作723
28.6.3并发控制724
28.6.4通用化搜索树725
28.7 高维索引问题726
28.8 复习题726

第29章 其他专题729
29.1 **事务处理729
29.1.1事务处理监视程序729
29.1.2新的事务模型730
29.1.3实时DBMS730
29.2 数据集成730
29.3 移动数据库731
29.4 主存数据库732
29.5 多媒体数据库732
29.6 地理信息系统733
29.7 时态数据库734
29.8 生物数据库734
29.9 信息可视化734
29.10 小结735

第30章 MINIBASE教学辅助软件736
30.1 可用内容736
30.2 MINIBASE作业概述736
30.3 致谢737
参考文献
……