数据库技术讲义 第4章 查询优化

《数据库技术讲义 第4章 查询优化》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章关系系统及其查询优化4.1关系系统关系模型的三个基本要素：关系数据结构、关系的完整性和关系操作。关系系统和关系模型是两个密切相关而又不同的概念。支持关系模型的数据库管理系统统称为关系系统，但关系模型中并非每一部分都同等重要，所有并不苛求数据库管理系统必须完全支持关系模型，也不苛求完全支持关系模型的系统才称为关系系统。因此，可以给出一个关系系统的最要要求及分类的定义。4.1.1关系系统的定义一个系统可定义为关系系统，当且仅当它：支持关系数据库(关系数据结构)支持选择、投影和连接运算，对这些运算不必要求

2、定义任何存取路径。4.1.2关系系统的分类可以按照对数据结构、数据操作和完整性的支持把关系系统分为4类：表式系统：只支持关系数据结构最小关系系统：支持数据结构和基本的三类操作关系完备的系统：支持数据结构和所有关系操作全关系系统：支持关系模型的所有特性全关系系统的十二条基本准则。4.2关系数据库系统的查询优化查询优化在关系数据库系统中有着非常重要的地位，是影响数据库系统性能的关键因素。因为SQL是非过程化的语言，用户只需要指出做什么，具体的操作由数据库完成因此必须对用户的查询要求进行优化，达到一个较高的效率

3、。4.2.1关系系统及其查询优化SQL只需要用户指出做什么，而不需要指出怎么做。而非关系数据库要用户自己完成全部查询操作，用户必须了解存取路径等信息，查询效率由用户的存取策略决定。这要求用户有较高的数据库技术和程序设计技术。4.2.1关系系统及其查询优化查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化”做的更好：优化器可以从数据字典中获得许多统计信息如果数据库的物理统计信息变了，系统可以自动对查询进行重新优化优化器可以考虑很多种不同的执行计划优化器中

4、包括了很多复杂的优化技术4.2.1关系系统及其查询优化查询优化一般可分为4个步骤：将查询转换成某种内部表示，通常是语法树根据一定的等价变换规则把语法树转换成优化形式选择底层的操作算法生成查询计划4.2.1关系系统及其查询优化目前的商品化数据库大都采用了基于代价的优化算法。这种算法要求优化器充分考虑系统中的各种参数，计算出各种查询执行方案的代价，选择代价最小的执行方案。查询代价主要包括：总代价＝I/O代价＋CPU代价在多用户系统中还有考虑内存代价。4.2.2实例例：查询选修了2号课程的学生姓名SELECTS

5、tudent.SnameFROMStudent,SCWHEREStudent.Sno=SC.SnoANDSC.Cno=‘2’;可以有很多种等价的关系代数表达式完成该查询。4.2.3查询优化的一般准则1.选择运算尽可能先做。2.在执行连接欠对关系做适当预处理，主要包括在连接属性上建立索引和对关系排序。3.把投影运算和选择运算同时进行。4.把投影同其前或其后的双目运算结合起来进行，没有必要为了投影扫描一遍关系。5.把某些选择同在它前面要执行的笛卡儿积结合起来形成一个连接运算。6.找出公共子表达式。4.2.4关

6、系代数等价变换规则所谓关系代数表达式的等价是指用相同的关系代替表达式中相应的关系所得到的结果是相同的。常用的等价变换有：1.连接、笛卡儿积交换律2.连接笛卡儿积结合律3.投影的串接定律4.选择的串接定律5.选择与投影的交换律4.2.4关系代数等价变换规则6.选择与笛卡儿积的交换律7.选择与并的交换8.选择与差的交换9.投影与笛卡儿积的交换10.投影与并的交换4.2.5关系代数表达式的优化算法优化算法一般为：1.利用规则4把选择分解2.对于每一个选择利用规则4～8尽可能下移3.对于每一个投影利用规则尽可能下

7、移4.把投影和选择的串接合并5.把语法树的内节点分组6.生成一个程序，每组节点的计算是程序中的一步。4.2.6优化的一般步骤优化的一般步骤如下：1.把查询转换为内部表示2.把语法树转换为优化形式3.选择底层的存取路径4.生成查询计划，选择代价最小的