数据库管理系统概论 PDF下载

编辑推荐

数据库管理系统已经成为继操作系统之后*复杂的系统软件。本书详尽介绍了数据库管理系统的体系结构、各大基本功能以及实现技术。本书可以做为院校师生的辅助教材，做为数据库基础原理的后继学习资料，加深对握数据库管理系统原理的理解；也可供数据库管理员和数据库系统开发人员参考，使他们从宏观、总体的角度掌握数据库管理系统的基本概念和基本原理，了解数据库管理系统与操作系统之间的运作原理，以更好的使用和维护数据库管理系统。；

内容简介

本书系统阐述数据库技术的核心软件——数据库管理系统，详细讲解其基本功能、工作模式、系统结构和实现技术，并对新型数据库管理系统予以介绍和展望，为有兴趣的读者指明研读方向。全书共分为11章：第1章绪论；第2章数据库管理系统的数据组织与存储；第3章DBMS数据定义、操纵与完整性约束；第4章查询处理；第5章查询优化；第6章事务；第7章并发控制；第8章数据库安全；第9章数据库恢复；第10章数据库管理系统性能配置；第11章新型数据库管理系统。本书可以作为高等学校计算机类专业、信息管理与信息系统等相关专业本科生和研究生“数据库”及相关课程的教材或教学参考书，也可供从事数据库管理系统研究、开发和应用的人员参考。

作者简介

暂无

数据库管理系统概论 PDF下载

目录
第1章绪论1
1.1数据库管理系统1
1.1.1数据库管理系统概述1
1.1.2数据库管理系统工作模式2
1.2数据库管理系统结构3
1.2.1应用层4
1.2.2语言处理层4
1.2.3存储管理层4
1.3语言处理层5
1.4存储管理层7
1.4.1数据存取7
1.4.2缓冲区管理7
1.4.3数据存储的物理组织8
1.5数据库管理系统基本功能10
1.6小结11
思考题11
第2章数据库管理系统的数据组织与存储13
2.1数据库系统存储结构13
2.1.1数据库磁盘存储器中的数据结构13
2.1.2数据库系统存储介质16
2.1.3存储介质层次结构18
2.2数据文件的记录格式19
2.2.1定长记录格式19
2.2.2变长记录格式22数据库管理系统概论目录2.3数据文件格式23
2.3.1文件格式23
2.3.2顺序文件24
2.3.3聚集文件25
2.4索引技术26
2.4.1索引基本概念26
2.4.2顺序索引27
2.4.3辅助索引30
2.4.4索引的更新31
2.4.5索引的自动生成32
2.5B 树索引文件32
2.5.1B 树结构33
2.5.2B 树的查询34
2.5.3B 树的更新35
2.5.4B 树文件组织36
2.5.5B树索引文件37
2.6散列索引文件38
2.6.1散列技术38
2.6.2静态散列索引40
2.6.3可扩充散列结构42
2.7小结45
思考题46
第3章DBMS数据定义、操纵与完整性约束47
3.1SQL概述47
3.1.1数据定义语言48
3.1.2数据操纵语言48
3.1.3数据完整性控制48
3.1.4数据控制语言48
3.1.5事务管理48
3.1.6嵌入式SQL和动态SQL48
3.2项目工程公司数据库49
3.3DBMS数据定义52
3.3.1模式的定义与删除53
3.3.2基本表的定义、修改与删除54
3.3.3视图建立与删除简介57
3.3.4索引的建立、修改与删除57
3.4DBMS数据操纵58
3.4.1数据查询58
3.4.2数据更新67
3.4.3视图69
3.5DBMS完整性约束74
3.5.1完整性概述74
3.5.2实体完整性75
3.5.3参照完整性77
3.5.4非空约束79
3.5.5唯一约束79
3.5.6CHECK约束80
3.5.7完整性约束命名80
3.5.8触发器81
3.6小结84
思考题84
第4章查询处理87
4.1概述87
4.2查询的选择运算实现89
4.2.1使用单文件扫描和索引的选择89
4.2.2涉及比较的选择91
4.2.3复合条件选择92
4.3查询的排序处理93
4.3.1外部归并排序算法93
4.3.2外部归并排序的代价分析94
4.4查询的连接处理95
4.4.1嵌套循环算法95
4.4.2索引嵌套循环连接96
4.4.3归并连接算法96
4.4.4散列连接算法98
4.5表达式计算101
4.5.1物化101
4.5.2流水线101
4.6小结102
思考题103
第5章查询优化105
5.1概述105
5.2代数优化106
5.2.1关系代数表达式等价变换规则106
5.2.2基于启发式规则的代数优化108
5.2.3代数优化实例109
5.3物理优化112
5.3.1基于启发式规则的物理优化112
5.3.2基于代价估算的物理优化113
5.4基于语义的查询优化113
5.5小结114
思考题114
第6章事务115
6.1事务的概念115
6.2事务的ACID性质116
6.3一个简单的事务实例116
6.4事务抽象模型与状态变迁118
6.5SQL中事务的存取模式和隔离级别120
6.6小结121
思考题121
第7章并发控制123
7.1事务的并发执行123
7.1.1事务并发执行的必要性123
7.1.2事务并发执行趋势124
7.1.3并发操作带来的问题124
7.1.4并发事务调度可串行化与可恢复性126
7.1.5并发控制技术133
7.2封锁技术134
7.2.1封锁类型134
7.2.2封锁协议135
7.2.3两段锁协议138
7.2.4封锁的实现141
7.3封锁带来的问题142
7.3.1活锁142
7.3.2死锁142
7.4多粒度封锁145
7.4.1多粒度树145
7.4.2意向锁146
7.4.3多粒度封锁协议148
7.5时间戳技术148
7.5.1时间戳148
7.5.2时间戳排序协议149
7.5.3改进的时间戳协议——Thomas写规则150
7.6多版本机制与快照隔离151
7.6.1多版本并发控制151
7.6.2多版本两段锁协议152
7.6.3快照隔离153
7.7幻行现象155
7.8小结157
思考题158
第8章数据库安全159
8.1数据库安全概述159
8.1.1威胁数据库的安全因素159
8.1.2数据库安全标准简介160
8.2数据库系统安全控制163
8.2.1数据库系统安全模型163
8.2.2数据库管理系统安全性控制模型163
8.2.3用户身份标识与鉴别164
8.3存取控制概述165
8.3.1自主存取控制166
8.3.2强制存取控制172
8.4审计173
8.4.1审计事件173
8.4.2审计的作用174
8.4.3AUDIT语句和NOAUDIT语句174
8.4.4ORACLE的审计技术174
8.5数据加密175
8.5.1加密技术175
8.5.2数据库中的加密支持176
8.6更高安全性保护177
8.6.1推理控制177
8.6.2隐蔽信道178
8.6.3数据隐私179
8.7小结179
思考题180
第9章数据库恢复181
9.1故障类型181
9.1.1事务故障181
9.1.2系统故障182
9.1.3介质故障182
9.2恢复机制下的存储器与数据访问182
9.2.1存储器种类182
9.2.2稳定存储器的实现183
9.2.3事务数据访问机制183
9.3恢复的基本原理与实现方法184
9.3.1恢复与事务原子性184
9.3.2日志恢复的基本原则与实现方法185
9.3.3影子复制恢复的基本原理185
9.4日志恢复技术186
9.4.1数据转储186
9.4.2日志文件格式187
9.4.3日志登记原则188
9.4.4使用日志重做和撤销事务189
9.4.5检查点191
9.5缓冲区管理192
9.5.1日志记录缓冲192
9.5.2数据库缓冲193
9.5.3模糊检查点194
9.6恢复算法194
9.6.1事务故障恢复——事务回滚195
9.6.2系统故障恢复195
9.6.3介质故障后的恢复197
9.7ARIES恢复技术197
9.7.1ARIES特点198
9.7.2ARIES数据结构198
9.7.3ARIES恢复算法200
9.7.4ARIES恢复算法特征202
9.8容灾备份系统203
9.9小结205
思考题206
第10章数据库管理系统性能配置207
10.1性能配置207
10.1.1瓶颈位置208
10.1.2硬件调整208
10.1.3数据库系统参数调整210
10.1.4模式与事务调整210
10.2性能基准程序211
10.2.1任务集211
10.2.2数据库应用类型212
10.2.3TPC基准测试213
10.3数据库标准217
10.3.1SQL标准217
10.3.2数据库连接标准218
10.3.3对象数据库标准218
10.3.4XML标准218
10.4小结219
思考题219
第11章新型数据库管理系统221
11.1数据库管理系统发展的三个阶段222
11.1.1第一代数据库管理系统——基于格式化模型DBMS222
11.1.2第二代数据库管理系统——关系DBMS222
11.1.3第三代数据库管理系统——新一代DBMS222
11.2基于新型数据模型的数据库管理系统223
11.2.1面向对象数据库管理系统223
11.2.2关系对象数据库管理系统224
11.2.3XML数据库管理系统224
11.3大数据管理系统225
11.3.1大数据225
11.3.2大数据建模——基于分析的用户建模227
11.3.3大数据管理系统228
11.4小结230
思考题231
参考文献232

前沿

出版说明在我国高等教育逐步实现大众化后，越来越多的高等学校将会面向国民经济发展的第一线，为行业、企业培养各级各类高级应用型专门人才。为此，教育部已经启动了“高等学校教学质量和教学改革工程”，强调要以信息技术为手段，深化教学改革和人才培养模式改革。如何根据社会的实际需要，根据各行各业的具体人才需求，培养具有特色显著的人才，是我们共同面临的重大问题。具体地，培养具有一定专业特色的和特定能力强的计算机专业应用型人才则是计算机教育要解决的问题。
为了适应21世纪人才培养的需要，培养具有特色的计算机人才，急需一批适合各种人才培养特点的计算机专业教材。目前，一些高校在计算机专业教学和教材改革方面已经做了大量工作，许多教师在计算机专业教学和科研方面已经积累了许多宝贵经验。将他们的教研成果转化为教材的形式，向全国其他学校推广，对于深化我国高等学校的教学改革是一件十分有意义的事。
清华大学出版社在经过大量调查研究的基础上，决定编写出版一套“普通高校本科计算机专业特色教材精选”。本套教材是针对当前高等教育改革的新形势，以社会对人才的需求为导向，主要以培养应用型计算机人才为目标，立足课程改革和教材创新，广泛吸纳全国各地的高等院校计算机优秀教师参与编写，从中精选出版确实反映计算机专业教学方向的特色教材，供普通高等院校计算机专业学生使用。
本套教材具有以下特点：
1. 编写目的明确
本套教材是深入研究各地各学校办学特色的基础上，面向普通高校的计算机专业学生编写的。学生通过本套教材，主要学习计算机科学与技术专业的基本理论和基本知识，接受利用计算机解决实际问题的基本训练，培养研究和开发计算机系统，特别是应用系统的基本能力。2. 理论知识与实践训练相结合
根据计算学科的三个学科形态及其关系，本套教材力求突出学科理论与实践紧密结合的特征，结合实例讲解理论，使理论来源于实践，又进一步指导实践得到自然的体现，使学生通过实践深化对理论的理解，更重要的是使学生学会理论方法的实际运用。
3. 注意培养学生的动手能力
数据库管理系统概论出版说明每种教材都增加了能力训练部分的内容，学生通过学习和练习，能比较熟练地应用计算机知识解决实际问题。既注意培养学生分析问题的能力，也注重培养学生解决问题的能力，以适应新经济时代对人才的需要，满足就业要求。
4. 注重教材的立体化配套
大多数教材都将陆续配套教师用课件、习题及其解答提示，学生上机实验指导等辅助教学资源，有些教材还提供能用于网上下载的文件，以方便教学。
由于各地区各学校的培养目标、教学要求和办学特色均有所不同，所以对特色教学的理解也不尽一致，我们恳切希望大家在使用教材的过程中，及时地给我们提出批评和改进意见，以便我们做好教材的修订改版工作，使其日趋完善。
我们相信经过大家的共同努力，这套教材一定能成为特色鲜明、质量上乘的优秀教材，同时，我们也希望通过本套教材的编写出版，为“高等学校教学质量和教学改革工程”作出贡献。

清华大学出版社前言数据库管理系统是对数据进行存储、管理、处理与维护的系统软件，是数据库技术的核心部分。随着计算机硬件、软件技术的迅速发展，数据库技术在各行各业的广泛应用以及大数据时代的到来，数据库管理系统的理论与技术及其发展越来越成为计算机科学与技术教育中必不可少的部分。
本书详细讲述数据库管理系统的基本概念、工作模式、体系结构、功能模块组成以及主流实现技术；并介绍大数据时代下，数据库管理系统发展的新兴成果与方向。
全书分为11章，第1章对数据库管理系统及其工作模式、系统结构与主要功能进行综述；第2章讲述数据库管理系统的数据组织与存储，包括记录格式、文件格式、索引结构与实现技术；第3章讲述数据库管理系统的数据操纵与数据完整性约束；第4章讲述查询处理，包括查询处理的一般步骤、选择运算实现、排序与连接处理、表达式计算；第5章讲述查询优化，包括代数优化与物理优化；第6章讲述数据库管理系统运行与管理的基本单位——事务；第7章讲述并发控制，包括并发操作问题、并发事务调度的可串行化与可恢复性、并发控制主流技术，重点讨论封锁技术；第8章讲述数据库安全性控制，基于数据库系统安全模型与数据库管理系统安全控制模型讨论自主存取控制、审计、强制存取控制、数据加密等DBMS安全性措施；第9章讲述数据库恢复，包括故障类型、恢复原理、恢复算法、最佳恢复算法ARIES以及容灾备份机制等；第10章讲述数据库管理系统性能配置；第11章介绍新型数据库管理系统，包括面向对象数据库管理系统、对象关系数据库管理系统、XML数据库管理系统、大数据管理系统。
本书针对数据库管理系统的内容详细丰富，弥补了数据库教学中对DBMS原理、实现技术与算法涉及不深的不足。读者可以根据需要阅读或者学习书中部分章节。数据库管理系统概论全书由徐述组织与执笔。湖南城市学院习胜丰教授、谭新良教授、何骞博士参与编撰和校阅，并提出了许多宝贵意见；杨轶芳老师、汪彦老师给予了英文检索与翻译支持。在此也感谢家人特别是女儿的默默付出与支持！
限于水平，书中难免存在疏漏、欠妥之处，欢迎读者批评指正。

徐述
2018年3月数据库管理系统概论前言

免费在线读

第5章查询优化由第4章的描述可知，对于一个给定查询，尤其是复杂的查询，数据库管理系统有许多种可能的执行策略，好的查询策略和差的查询策略在执行代价上（执行时间）通常会有相当大的区别，它们之间可能相差几个数量级。因此，数据库管理系统为查询处理选择一个好的查询策略而付出额外的时间开销是完全值得的。数据库管理系统能够构造一个让查询执行代价最小化的等价查询执行计划，即查询优化。
5.1概述
为了达到用户可以接受的性能，数据库管理系统必须进行查询优化；而恰好关系表达式的语义级别很高，关系数据库管理系统可以分析关系式的语义，对其进行优化。查询优化使得关系系统在性能上接近甚至超过了非关系系统。查询优化是关系数据库管理系统的关键技术。关系数据库系统及其SQL语言之所以广泛流行，很大程度得益于查询优化技术的发展成熟。
关系系统中，用户使用非过程化的语言表达查询要求时，只需要描述做什么，不必指出怎么做，这使得用户选择数据存取路径的负担大大减轻。对比非关系系统，用户需要了解数据的存取路径，查询的效率由用户的查询策略决定；如果用户做了不当选择，系统不能对此加以改进。这实际上要求非关系系统的用户具有较高的数据库技术和程序设计水平。
让DBMS做查询优化，不仅可以让用户关注查询问题本身，无须考虑如何表达查询以获得较高的效率，而且系统优化比用户程序优化做得更好。数据库管理系统的查询优化器可以从数据字典获取许多统计信息（例如关系的元组数，关系的每个属性值的分布情况，哪些属性上建立了索引等），优化器可以根据这些信息做出估算，选择高效的执行计划，而用户程序难以做到；另外，如果物理统计信息改变了，数据库管理系统会自动更新数据字典，自动调整查询执行计划。系统优化器可以利用很多复杂的优化技术，同时比较数百种不同的执行计划，而用户程序难以企及。
实际数据库管理系统的查询优化步骤如下。
（1）将查询转换成某种内部表示，通常是语法树。
（2）根据一定的等价变换规则把语法树转换成标准（优化）形式。
（3）选择底层的操作算法：对于语法树中的每一个操作，计算各种执行算法的执行代价，选择代价小的执行算法。
数据库管理系统概论第5章查询优化（4）生成查询计划（查询执行方案），查询计划是由一系列内部操作组成的。
查询优化主要分为代数优化（即上述优化步骤的步骤（2））与物理优化（即上述优化步骤的步骤（3））。
查询优化的总目标是选择有效的策略，求得给定关系表达式的值，使得查询代价较小。而查询优化的搜索空间实际是非常大的，因此实际系统选择的策略不一定是最优的，而是较优的。
5.2代数优化
4.1节讲解了SQL语句经过语法分析与翻译后变换为关系代数表达式的内部表示——语法查询树，本节介绍基于关系代数等价变化规则的优化方法——代数优化。
代数优化策略通过对关系代数表达式的等价变换来提高查询效率，只改变查询语句中操作的次序与组合，不涉及底层的存取路径。
5.2.1关系代数表达式等价变换规则
关系代数表达式的等价变换是指用相同的关系代替两个代数表达式中相应的关系，二者所得到的结果是相同的。如果两个关系代数表达式在每一个数据库实例中都会产生相同的元组集合，那么这两个表达式有可能以不同的顺序产生元组，而元组的顺序是无关紧要的，因此只要元组集合内容一致，就认为二者等价。
等价规则指出两种不同形式的表达式是等价的。第一种可以代替第二种，反之亦然。优化器利用等价规则将表达式转换成逻辑上等价的其他表达式。两个关系表达式E1和E2是等价的，记为E1≡E2。
下面列出关系代数表达式的通用等价规则。
1. 连接、笛卡尔积交换律
设E1和E2是关系代数表达式，F是连接运算的条件，则有：
E1×E2≡ E2×E1
E1E2≡E2E1
E1FE2≡E2FE1
2. 连接、笛卡尔积的结合律
设E1，E2，E3是关系代数表达式，F1和F2是连接运算的条件，则有：
（E1×E2）×E3 ≡E1×（E2×E3）
（E1E2）E3≡E1（E2E3）
（E1FE2）FE3≡E1F（E2FE3）
3. 投影的串接定律
∏A1,A2,…,An（∏B1,B2,…,Bm（E））≡∏A1,A2,…,An（E）
这里，E是关系代数表达式，Ai（i=1，2，…，n）, Bj（j=1，2，…，m）是属性名，并且{A1, A2, …, An}构成{B1，B2，…，Bm}的子集。
4. 选择的串接定律
F1（F2（E））≡F1∧ F2（E）
这里，E是关系代数表达式，F1和F2是选择条件。选择的串接定律说明选择条件可以合并，这样一次就可检查全部条件。
5. 选择与投影操作的交换律
如果选择条件F只涉及属性A1，A2，…，An，交换律表达如下：
F（∏A1,A2,…,An（E））≡∏A1,A2,…,An（F（E））
若F中有不属于A1,A2,…,An的属性B1,B2,…,Bm，则有更一般的交换律如下：
∏A1,A2,…,An（F（E））≡∏A1,A2,…,An（F（∏A1,A2,…,An,B1,B2,…,Bm（E）））
6. 选择与笛卡尔积的交换律
如果F中涉及的属性都是E1中的属性，则有：
F（E1×E2）≡F（E1）×E2
如果F=F1∧F2，并且F1只涉及E1中的属性，F2只涉及E2中的属性，则由上述等价变换规则1、4、6可推出：
F（E1×E2）≡F1（E1）×F2（E2）
如果F=F1∧F2，F1只涉及E1中的属性，F2涉及E1和E2两者的属性，选择与笛卡尔积交换律表达为：
F（E1×E2）≡F2（F1（E1）×E2）
它使部分选择在笛卡尔积前先做。
7. 选择与并的交换律
假设： E=E1∪E2、E1，E2有相同的属性名，则有：
F（E1∪E2）≡F（E1）∪F（E2）
8. 选择与差运算的交换律
假设E1与E2有相同的属性名，则有：
F（E1-E2）≡F（E1）-F（E2）
9. 选择对自然连接的分配律
F（E1E2）≡F（E1）F（E2）
这里，F只涉及E1与E2的公共属性。
10. 投影与笛卡尔积的交换律
设E1和E2是两个关系表达式，A1，A2，…，An是E1的属性，B1，B2，…，Bm是E2的属性，则：
∏A1,A2, …,An,B1,B2, …,Bm（E1×E2）≡∏A1,A2, …,An（E1）×∏B1,B2, …,Bm（E2）
11. 投影与并的交换律
设E1和E2 有相同的属性名，则：
∏A1,A2, …,An（E1∪E2）≡∏A1,A2, …,An（E1）∪∏A1,A2, …,An（E2）
5.2.2基于的启发式规则的代数优化
对于关系代数表达式的图形化表示——语法查询树，典型的代数优化启发式规则如下。
（1）选择运算应尽可能先做。这是优化规则中最重要、最基本的一条。因为先做选择运算可以使中间关系大幅变小，执行代价可以达到数量级地减小。
（2）投影运算和选择运算同时做。如果有若干个投影运算和选择运算对同一个关系操作，则可以在扫描此关系的同时完成所有这些运算，以避免重复扫描关系。
（3）将投影运算与其前或其后的双目运算结合。没有必要为了去掉某些字段而扫描一遍关系。
（4）把某些选择同在其前面的笛卡尔积结合起来成为一个连接运算，连接运算特别是等值连接，要比同样关系上的笛卡尔积的执行代价小很多。
（5）找出公共子表达式。如果重复出现的公共子表达式结果不大，并且从外存读入这个关系比计算该子表达式的执行代价小，则先计算出公共子表达式，并将结果写入临时文件。当利用视图执行查询时，定义视图的语句就是公共子表达式的情况。
根据启发式规则，应用5.2节的表达式等价变换公式中优化关系表达式的代数优化算法描述如下。
算法：关系表达式的优化。
输入：一个关系表达式的语法树。
输出：优化的查询树。
算法步骤如下。
第一步，分解选择运算，利用等价变换规则4把形如F1 ∧F2 ∧ … ∧ Fn（E）变换为F1（F2（… ；（Fn（E））…））形式。
第二步，交换选择运算，将其尽可能移到叶端，利用规则4～9尽可能把每一个选择移到树的叶端。
第三步，交换投影运算，将其尽可能移到叶端，利用规则3、5、10、11中的一般形式尽可能把每一个投影移向树的叶端。
第四步，合并同一关系上串接的选择和投影，以便同时执行这些操作或在一次扫描中完成这些操作。利用规则3、4、5把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影的形式。由于投影或者选择操作是对同一个关系的操作，这样处理的效果是使多个选择或投影能同时执行，或在一次扫描中全部完成。
第五步，将经过上述步骤得到的语法树的内结点分组：每一双目运算（×，，∪，-）和它所有的直接祖先划分为一组（这些直接祖先是，∏运算）。如果其后代直到叶子全是单目运算，则也将它们并入该组，但当双目运算是笛卡尔积（×），并且其后的选择运算不能与它结合为等值连接时除外，这种情况的单目运算单独分为一组。
第六步，生成程序。生成一个程序，第五步划分的每组结点的计算是程序中的一步。各步的顺序是任意的，只要保证任何一组的计算不会在它的后代组之前计算即可。
5.2.3代数优化实例
例51对于学生选课关系数据库：
student（SNO,SNAME,SSEX,SAGE,SDEPT）关系模式存放学生基本信息，包括学号、姓名、性别、年龄、系名；
sc（SNO,CNO,GRADE）关系模式存放选课信息，包括选课学生学号、课程号、成绩；
course（CNO,CNAME,CPNO,CCREDIT）关系模式存放课程信息，包括课程号、课程名、先修课号、学分。
执行查询语句，求选修了“信息系统”的女同学的学号与姓名。该查询语句的关系代数表达式如下：
∏SNO,SNAME（CNAME=信息系统∧SSEX= 女（studentsccourse）)
上式中，符号用∏、、×操作表示，可得到等价的表达式如下：
∏SNO,SNAME（CNAME= 信息系统∧SSEX=女（∏L（student.SNO=sc.SNO∧sc.CNO=course.CNO
（student×sc×course））））
此处，L是属性{student.SNO,SNAME,SSEX,SAGE,SDEPT, course.CNO,GRADE,CNAME,CPNO,CCREDIT}的集合（student、sc、course三表自然连接的属性集合）。
将等价的表达式构成初始语法查询树，如图51所示。
使用优化算法对初始语法树进行优化。
第一步，将选择运算尽量往叶端放。
将图51的每个选择操作分裂成两个选择运算，得到4个选择操作：CNAME= 信息系统、SSEX=女、student.SNO=sc.SNO、sc.CNO=course.CNO；使用等价变换规则4～8，将上述4个选择操作尽可能向树的叶子靠拢。根据规则4和5可以将选择CNAME= 信息系统和SSEX=女移到投影和另外两个选择操作下面，直接放在笛卡尔积外面得到子表达式：
CNAME=信息系统（SSEX= 女（student×sc）×course）
其中，外层选择仅涉及关系course，内层选择仅涉及关系student，所以上述子表达式又可以变换成如下形式：
（SSEX= 女（student）×sc）×CNAME=信息系统（course）
选择sc.CNO=course.CNO不能再往叶子端移动，因为它的属性涉及sc和course两个关系，而选择student.SNO=sc.SNO还可以与笛卡尔积交换，往叶端移动一步。
最后根据规则3，从树的根往下的两个投影操作合并成一个投影操作∏student.SNO,SNAME。
经过上述等价变换，使4个简单选择操作尽量往叶端放，等价变换后的语法树如图52所示。
图51例51初始语法查询树
图52例51选择往叶端放等价交换后的语法树

第二步，将投影运算尽量往叶端放。
对于根的投影操作，根据等价变换规则5的更一般规则，把投影跟其下的选择进行交换，在选择下面增加一个投影操作，如图53所示。
根据等价变换规则10，将∏student.SNO,SNAME,sc.CNO,course.CNO分成∏student.SNO,SNAME,sc.CNO和∏course.CNO，与其下的笛卡尔积交换，使它们分别对student.SNO=sc.SNO（…）和CNAME=信息系统（…）做投影操作。转换后的语法树如图54所示。
对于更靠近根的笛卡尔积交换的投影操作∏student.SNO,SNAME, sc.CNO，类似地，又根据等价规则5的更一般规则，将这个投影分别与其下的选择操作形成级联运算： ∏student.SNO,SNAME,sc.CNO（student.SNO=sc.SNO（∏student.SNO,SNAME,sc.SNO,sc.CNO（…））。
再根据等价规则10，将∏student .SNO,SNAME,sc.SNO,sc.CNO与靠近叶子结点student与叶子结点sc的笛卡尔积交换，如图55所示。
第三步，对优化后的语法树进行分组。图55用虚线划分了两个运算组。
执行时，从叶端依次向上执行，每组运算对关系扫描一次。图53例51根投影往叶端放等价交换后的语法树
图54例51根投影继续与笛卡尔积
交换后的语法树图55例51投影往叶端放等价变换后
的最终语法树5.3物理优化
对于一个查询语句，代数优化后得到的关系代数语法树可以有多种执行这个语法树的算法，多种存取路径，也就是代数优化后的查询可以有许多存取方案，这些方案的执行效率各不相同，有的执行时间相差很大。因此，要继续进行物理优化。
物理优化就是选择高效合理的操作算法或者存取路径，求得优化的查询计划，达到执行代价的优化。
物理优化的常用方法有以下3种。
（1）基于规则的启发式优化。启发式规则是指那些在大多数情况下适用，但不是每一种情况下都是最好的规则。
（2）基于代价估算的优化。使用查询优化器估算不同执行策略的代价，选出其中具有最小代价的执行计划。
（3）两者结合的优化方法。查询优化器通常会把这两种技术结合在一起使用。因为可能的执行策略很多，要执行所有的策略进行代价估算往往是不可行的，因为估算需要代价，若对所有策略都进行代价估算并选出最优的策略，很可能造成查询优化本身付出的代价大于获得的益处。因此结合启发式规则与代价估算，先使用启发式规则，挑选若干较优的候选方案，减少代价估算的工作量；然后分别计算这些候选方案的执行代价，从中选出最优方案。
5.3.1基于启发式规则的物理优化
基于启发式规则的物理优化通常是指存取路径和底层操作算法的选择，下面介绍最常用的物理优化启发式规则。
1. 选择操作的物理优化启发式规则
对于小型关系，即使选择列上有索引，也使用全表顺序扫描。
对于大型关系，启发式规则如下。
对于选择条件是“主码=值”的查询，也就是查询结果是空或者唯一元组，可以选择主码上的索引。一般的关系数据库系统在主码上会自动创建一个唯一属性的聚集索引。
对于选择条件是“非主属性=值”的查询，并且非主属性列上建有索引，查询优化器则会利用数据字典的统计信息估算查询结果涉及的元组数目。如果结果元组行数目小于关系元组行数目的10％，就使用索引扫描方法；否则还是使用全表顺序扫描。
对于选择条件是属性上的非等值查询或者范围查询，并且选择列上有索引，同样要估算查询结果的元组数目。如果结果元组行数目小于关系元组行数目的10％，就使用索引扫描方法；否则还是使用全表顺序扫描。
对于使用AND连接的复合选择条件，如果有涉及这些属性的组合索引，优先采用组合索引扫描；如果某个属性上有一般索引，可以利用该索引找到符合涉及该属性单条件的记录指针集，再对集合里涉及的记录测试，看是否符合其他的条件。
对于使用OR连接的复合选择条件，一般使用全表顺序扫描。
2. 连接操作的物理优化启发式规则
如果两个关系都已经按照连接属性排序，则选用归并连接算法。如果一个关系在连接属性上有索引，则可以选用索引嵌套循环连接算法。如果上面两个规则都不适用，其中一个关系较小，可以选用散列连接算法。否则可以选用嵌套循环算法，并且选择其中较小的关系（但不能完全放在内存里），即占用的磁盘块数较少的表作为外部关系（外循环的表）。如果两个关系中某一个关系小到能完全放在内存里，那么将这个小的关系作为内层关系来处理可以减少很多I/O操作。这时内层关系常驻内存反复被扫描，外层关系逐块读入即可。
实际的关系型数据库管理系统中代数优化启发式规则很多，本节只展示其中最主要的规则。启发式规则是定性选择，实现简单并且优化选择本身代价小，特别适合解释执行的系统。因为解释执行的数据库系统的优化开销包含在查询总代价中。
5.3.2基于代价估算的物理优化
编译执行数据库系统中，一次编译优化，多次执行，查询优化与查询执行是分开的。因此，可以采用精细复杂一些的基于代价估算的物理优化方法。
基于代价估算的物理优化需要计算各种操作算法的执行代价，很多时候执行代价与数据库状态密切相关。为此，数据库内模式在数据字典中设计存储了查询优化器需要的统计信息，其统计内容主要包括以下3个方面。
（1）对于每个基本关系，统计关系的元组个数（N）、元组长度、占用的块数、占用的溢出块数。
（2）对于每个基本关系的每个属性，统计该属性不同取值的个数（m）、属性取值的最大值、最小值、该属性上是否创建了索引、是哪种索引（B 树索引、散列索引、聚集索引）以及根据这些统计信息计算出谓词条件的选择率（f），如果不同值的分布是均匀的，则f=1/m；如果不同值的分布不均匀，则要计算每个值的选择率，f=具有该值的元组数目/N。
（3）对于索引，例如B 树索引，统计该索引的层数、不同索引值的个数、索引的选择基数S（有S个元组具有某一索引值）、索引的叶结点数。
5.4基于语义的查询优化
这种技术根据数据库的语义约束，把查询转换成为另一个执行效率更高的查询。本节不对这种技术做详细讨论，只通过一个SQL语句来简要说明其原理，有兴趣的读者可以查阅数据库系统手册。
考虑如下SQL语句：SELECT  FROM student WHERE sage>；300；这里，用户在写年龄值sage时，把30误写成300。假设数据库模式上定义了一个约束，限定学生年龄的取值在18～50周岁。查询优化器在对上述SQL语句进行语法分析与检查时，由于约束的存在，马上可以判断查询的结果为空，所以不需要执行这个SQL语句。
5.5小结
查询优化技术是查询处理的关键技术。
对于给定的查询，通常有许多计算这个查询的方案。将用户输入的查询语句转换为等价的、执行效率更高的查询执行方案，是查询优化的目标。
查询优化主要分为代数优化与物理优化。
代数优化策略通过对关系代数表达式的等价变换来提高查询效率，改变查询语句中操作的次序与组合，不涉及底层的存取路径。
物理优化就是选择高效合理的操作算法或者存取路径，求得优化的查询计划，达到执行代价的优化。
物理优化的常用方法有：基于规则的启发式优化、基于代价估算的优化、两者结合的优化方法。
思考题
1. 试述关系型数据库管理系统查询优化的一般准则。
2. 试述关系型数据库管理系统查询优化的一般步骤。
3. 对于例51的学生选课关系数据库，查询选修了2号课程的学生姓名。试画出用关系代数表示的语法树，并用关系代数表达式优化算法对原始语法树进行优化处理，画出优化后的标准语法树。