关系数据库的查询与优化

２．４查询优化关系系统和关系模型既密切相关，又是不相同的概念。一般支持关系模型的ＤＢＭＳ称之为关系系统，但是一个实际的关系数据库管理系统，不必苛求它完全支持关系模型，所以要讨论关系系统的最小要求和分类。对于一个给定的查询问题会有多种等价的实现办法，能否找出一个与之等价而操作时间又少的表达式，换句话说，究竟哪一种方法是最优的？这就是查询优化要讨论的问题。２．４．１关系代数表达式的优化问题查询处理：是指从数据库中提取数据的一系列活动。这一系列活动包括：将高级数据库语言表示的查询语句翻译成为能在文件系统这一物理层次上实现的表达式，为优化查询进行各种转换，以及查询的实际执行。查询处理的代价：通常取决于磁盘的访问，磁盘的访问比内存访问速度要慢。对于一个给定的查询，可以有许多可能的处理策略，复杂查询更是如此。就所需的磁盘访问次数而言，策略好坏差别很大，有时甚至相差几个数量级。所以，多花一点时间选择一个较好的查询策略是很值得的。查询优化：是为了查询选择最有效的查询计划的过程。查询优化一方面是在关系代数级进行优化，要做的是力图找出与给定表达式等价，但执行效率更高的一个表达式。查询优化的另一方面涉及查询语句处理的详细策略的选择，例如选择执行运算所采用的具体算法，以及将使用的特定索引，等等。一个查询往往会有许多实现办法，关键是如何找出一个与之等价的且操作时间又少的表达式。下面将专门讨论这个问题。２．４．２关系代数表达式的等价变换规则关系系统的查询优化既是关系数据库管理系统实现的关键技术，又是关系系统的优点。第２章关系数据库·４３·因为，用户只要提出“干什么”，不必指出“怎么干”。在关系代数表达式中需要指出若干关系的操作步骤，问题是怎样做才能保证省时、省空间、效率高，这就是查询优化的问题。需要注意的是，在关系代数运算中，笛卡儿积、连接运算最费时间和空间，究竟应采用什么样的策略，才能节省时间和空间？这就是优化的准则。１．优化的准则（１）提早执行选取运算。对于有选择运算的表达式，应优化成尽可能先执行选择运算的等价表达式，以得到较小的中间结果，减少运算量和从外存读块的次数。（２）合并乘积与其后的选择运算为连接运算。在表达式中，当乘积运算后面是选择运算时，应该合并为连接运算，使选择与乘积一道完成，以避免做完乘积后，需再扫描一个大的乘积关系进行选择运算。（３）将投影运算与其后的其他运算同时进行，以避免重复扫描关系。（４）将投影运算和其前后的二目运算结合起来，使得没有必要为去掉某些字段再扫描一遍关系。（５）在执行连接前对关系适当地预处理，就能快速地找到要连接的元组。方法有两种：索引连接法、排序合并连接法。（６）存储公共子表达式。对于有公共子表达式的结果应存于外存（中间结果），这样，当从外存读出它的时间比计算的时间少时，就可节约操作时间。２．关系代数表达式的等价变换规则优化的策略均涉及关系代数表达式，所以讨论关系代数表达式的等价变换规则显得十分重要。常用的等价变换规则有如下１０种：１）连接、笛卡儿积交换率设Ｅ１和Ｅ２是关系代数表达式，Ｆ是连接运算的条件，则有Ｅ１×Ｅ２≡Ｅ２×Ｅ１Ｅ１Ｅ２≡Ｅ２Ｅ１ＦＦ２）连接、笛卡儿积结合率设Ｅ１，Ｅ２，Ｅ３是关系代数表达式，Ｆ１，Ｆ２是连接运算的条件，则有（Ｅ１×Ｅ２）×Ｅ３≡Ｅ１×（Ｅ２×Ｅ３）（Ｅ１Ｅ２）Ｅ３≡Ｅ１（Ｅ２Ｅ３）Ｆ１Ｆ２Ｆ１Ｆ２３）投影的串接定律设Ｅ是关系代数表达式，Ａ１，…，Ａｎ和Ｂ１，…，Ｂｍ是属性名，且Ｂ１，…，Ｂｍ是Ａ１，…，Ａｎ的子集。则有πＡ１，…，Ａｎ（πＢ１，…，Ｂｍ（Ｅ））≡πＡ１，…，Ａｎ（Ｅ）该规则的目的是使一些投影消失。４）选择的串接定律设Ｅ是关系代数表达式，Ｆ１，Ｆ２是选取条件表达式，选择的串接定律说明选择条件可以合并，则有σＦ１（σＦ２（Ｅ））≡σＦ１∧Ｆ２（Ｅ）·４４·数据库原理及应用５）选择与投影的交换律设Ｅ是关系代数表达式，Ｆ是选取条件表达式，并且只涉及Ａ１，…，Ａｎ属性，则有σＦ（πＡ１，…，Ａｎ（Ｅ））≡πＡ１，…，Ａｎ（σＦ（Ｅ））若Ｆ中有不属于Ａ１，…，Ａｎ属性，Ｂ１，…，Ｂｍ，那么有更一般的规则：σＦ（πＡ１，…，Ａｎ（Ｅ））≡πＡ１，…，Ａｎ（σＦ（πＡ１，…，ＡｎＢ１，…，Ｂｍ（Ｅ）））该规则可将投影分裂为两个，使得其中的一个可能被移到树的叶端。６）选择与笛卡儿积的交换律若Ｆ涉及的都是Ｅ１中的属性，则σＦ（Ｅ１×Ｅ２）≡σＦ（Ｅ１）×Ｅ２如果Ｆ＝Ｆ１∧Ｆ２，并且，Ｆ１只涉及Ｅ１中的属性，Ｆ２只涉及Ｅ２中的属性，则有σＦ（Ｅ１×Ｅ２）≡σＦ１（Ｅ１）×σＦＥ２２７）选择与并的交换律设Ｅ＝Ｅ１∪Ｅ２，Ｅ１，Ｅ２有相同的属性，则σＦ（Ｅ１∪Ｅ２）≡σＦ（Ｅ１）∪σＦ（Ｅ２）８）选择与差的交换律设Ｅ１，Ｅ２有相同的属性，则σＦ（Ｅ１－Ｅ２）≡σＦ（Ｅ１）－σＦＥ２９）投影与笛卡儿积的交换律设Ｅ１，Ｅ２是两个关系表达式，Ａ１，…，Ａｎ是Ｅ１中的属性，Ｂ１，…，Ｂｍ是Ｅ２中的属性，则πＡ１，…，Ａｎ，Ｂ１，Ｋ，Ｂｍ（Ｅ１×Ｅ２）≡πＡ１，…，Ａｎ（Ｅ１）×πＢ１，Ｋ，Ｂｍ（Ｅ２）１０）投影与并的交换律设Ｅ１，Ｅ２有相同的属性，则πＡ１，…，Ａｎ（Ｅ１∪Ｅ２）≡πＡ１，…，Ａｎ（Ｅ１）∪πＡ１，…，Ａｍ（Ｅ２）２．４．３关系代数表达式的优化算法算法：关系代数表达式的优化。输入：一个关系代数表达式的语法树。输出：计算该表达式的程序。方法：（１）利用规则４将形如σＦ１∧Ｆ２∧…Ｆｎ（Ｅ）变换为σＦ１（σＦ２ＫσＦｎ（Ｅ））…）（２）对每一个选择，利用规则４～８尽可能将它移到树的叶端。（３）对每一个投影，利用规则３，５，９，１０中的一般形式尽可能将它移到树的叶端。（４）利用规则３～５将选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时进行，或在一次扫描中全部完成。（５）将上述得到的语法树的内节点分组。每一双目运算（×，∪，，－）和它所有的直接祖先为一组（这些直接祖先是σ，π运算）。如果其后代直到叶子全部是单目运算，则将它并入该组。（６）生成一个程序，每组节点的计算是程序中的一步。各步的顺序是任意的，只要保证第２章关系数据库·４５·任何一组的计算不会在它的后代组之前计算。【例２．１２】供应商数据库中有供应商、零件、项目、供应４个基本表（关系）：Ｓ（Ｓｎｏ，Ｓｎａｍｅ，Ｓｔａｔｕｓ，Ｃｉｔｙ）Ｐ（Ｐｎｏ，Ｐｎａｍｅ，Ｃｏｌｏｒ，Ｗｅｉｇｈｔ）Ｊ（Ｊｎｏ，Ｊｎａｍｅ，Ｃｉｔｙ）ＳＰＪ（Ｓｎｏ，Ｐｎｏ，Ｊｎｏ，Ｑｔｙ）用户有一查询语句：检索使用上海供应商生产的红色零件的工程号。（１）试写出该查询的关系代数表达式。（２）试写出查询优化的关系代数表达式。（３）画出该查询初始的关系代数表达式的语法树。（４）使用优化算法，对语法树进行优化，并画出优化后的语法树。解：（１）该查询的关系代数表达式如下：πＪｎｏ（σＣｔｉｙ＝ＳＰＪＰ））（２）查询优化的关系代数表达式如下：πＪｎｏ（πＳｎｏ（σＣｔｉｙ＝πＳｎｏ，Ｐｎｏ，Ｊｎｏ（ＳＰＪ）（３）画出该查询初始的关系代数表达式的语法树如图２－２１所示。（４）使用优化算法，对语法树进行优化，并画出优化后的语法树如图２－２２所示。图２－２１优化前图２－２２优化后２．５关系数据库的规范化理论在关系模型中，一个数据库模式是关系模式的集合。要保证构造的关系既能准确地反应现实世界，又有利于应用和具体的操作。规范化理论研究的是关系模式中各属性之间的依赖关系及其对关系模式性能的影响，提供判断关系模式优劣的理论标准，预测可能出现的问题，提供了自动产生各种模式的算法。因此，它是设计人员的有力工具和理论基础。关系数据库设计理论的核心是数据间的函数依赖，衡量的标准是关系规范化的程度及分解的无损连接和保持函数依赖性。关系数据库设计的目标是生成一组合适的、性能良好的关系模式，以·４６·数据库原理及应用减少系统中信息存储的冗余度，但又可方便地获取信息。２．５．１函数依赖数据依赖是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系，是现实世界属性间联系和约束的抽象，是数据内在的性质，是语义的体现。函数依赖则是一种最重要、最基本的数据依赖。１．函数依赖的定义【定义２．４】设Ｒ（Ｕ）是属性集Ｕ上的关系模式，Ｘ，Ｙ是Ｕ的子集。若对Ｒ（Ｕ）的任何一个可能的关系ｒ，ｒ中不可能存在两个元组在Ｘ上的属性值相等，而在Ｙ上的属性值不等，则称Ｘ函数决定Ｙ或Ｙ函数依赖于Ｘ，记作：Ｘ→Ｙ。注意：函数依赖Ｘ→Ｙ的定义要求关系模式Ｒ的任何可能的ｒ都满足上述条件。因此不能仅考察关系模式Ｒ在某一时刻的关系ｒ，就断定某函数依赖成立。例如，关系模式Ｓｔｕｄｅｎｔ（Ｓｎｏ，Ｓｎａｍｅ，ＳＤ，Ｓａｇｅ，Ｓｅｘ）可能在某一时刻，Ｓｔｕｄｅｎｔ的关系ｒ中每个学生的年龄都不同，也就是说没有两个元组在Ｓａｇｅ属性上取值相同，而在Ｓｎｏ属性上取值不同，但我们决不可据此就断定Ｓａｇｅ→Ｓｎｏ。很有可能在某一时刻，Ｓｔｕｄｅｎｔ的关系ｒ中有两个元组在Ｓａｇｅ属性上取值相同，而在Ｓｎｏ属性上取值不同。函数依赖是语义范畴的概念，我们只能根据语义来确定函数依赖。例如，在没有同名的情况下，Ｓｎａｍｅ→Ｓａｇｅ，而在有同名的情况下，这个函数依赖就不成立了。非平凡的函数依赖：如果Ｘ→Ｙ，但ＹＸ，则称Ｘ→Ｙ是非平凡的函数依赖。一般情况下总是讨论非平凡的函数依赖。平凡的函数依赖：如果Ｘ→Ｙ，但ＹＸ，则称Ｘ→Ｙ是平凡的函数依赖。【定义２．５】在Ｒ（Ｕ）中，如果Ｘ→Ｙ，并且对于Ｘ的任何一个真子集Ｘ′，都有Ｘ′不能ｆ决定Ｙ，则称Ｙ对Ｘ完全函数依赖，记做：ＸＹ。ｐ如果Ｘ→Ｙ，但Ｙ不完全函数依赖于Ｘ，则称Ｙ对Ｘ部分函数依赖，记做：ＸＹ。部分函数依赖也称局部函数依赖。【定义２．６】在Ｒ（Ｕ，Ｆ）中，如果Ｘ→Ｙ，ＹＸ，Ｙ→／Ｘ，Ｙ→Ｚ，则称Ｚ对Ｘ传递函数依赖。【例２．１３】在关系模式ＳＣ（Ｓｎｏ，Ｃｎｏ，Ｇｒａｄｅ，Ｃｒｅｄｉｔ）中，ｆ（Ｓｎｏ，Ｃｎｏ）Ｇｒａｄｅ成绩完全函数依赖于学号和课程号Ｃｎｏ→Ｃｒｅｄｉｔ学分函数依赖于课程号ｐ（Ｓｎｏ，Ｃｎｏ）Ｃｒｅｄｉｔ学分部分函数依赖于学号在关系模式Ｓｔｕｄｅｎｔ（Ｓｎｏ，Ｓｎａｍｅ，ＳＤ，ＳＤｎａｍｅ，Ｓａｇｅ，Ｓｅｘ）中，Ｓｎｏ→Ｓｎａｍｅ，Ｓｎｏ→Ｓａｇｅ又因为Ｓｎｏ→ＳＤ，ＳＤ→／Ｓｎｏ，ＳＤ→ＳＤｎａｍｅ，所以可以得出Ｓｎｏ→ＳＤｎａｍｅ，即系名传递依赖于学号。２．码ｆ【定义２．７】设Ｋ为Ｒ（Ｕ，Ｆ）中的属性或属性的组合，若ＫＵ，且对于Ｋ的任何一第２章关系数据库·４７·个真子集Ｋ若有多个候选码，则选一个作为主码（Ｐｒｉｍａｒｙｋｅｙ）。候选码通常也称候选关键字。包含在任何一个候选码中的属性叫做主属性（Ｐｒｉｍｅａｔｔｒｉｂｕｔｅ），否则叫做非主属性（Ｎｏｎｐｒｉｍｅａｔｔｒｉｂｕｔｅ）。【例２．１４】关系模式ＣＳＺ（ＣＩＴＹ，ＳＴ，ＺＩＰ），其属性组上的函数依赖集为Ｆ＝｛（ＣＩＴＹ，ＳＴ）→ＺＩＰ，ＺＩＰ→ＣＩＴＹ｝即城市、街道决定邮政编码，邮政编码决定城市。容易看出，（ＣＩＴＹ，ＳＴ）和（ＳＴ，ＺＩＰ）是两个候选码。ＣＩＴＹ，ＳＴ，ＺＩＰ都是主属性。【定义２．８】若Ｒ（Ｕ，Ｆ）中的属性或属性组Ｘ非Ｒ的码，但Ｘ是另一个关系的码，则称Ｘ是Ｒ的外码（Ｆｏｒｅｉｇｎｋｅｙ）。【定义２．９】若关系模式Ｒ（Ｕ）中，Ｘ，Ｙ，Ｚ是Ｕ的子集，并且Ｚ＝Ｕ－Ｘ－Ｙ。当且仅当对Ｒ（Ｕ）的任何一个关系ｒ，给定一对（Ｘ，Ｚ）值，有一组Ｙ的值，这组值仅仅决定于Ｘ值而与Ｚ值无关，则称“Ｙ多值依赖于Ｘ”或“Ｘ多值决定Ｙ”成立。记为Ｘ→→Ｙ。多值依赖具有如下６条性质：（１）多值依赖具有对称性。即若Ｘ→→Ｙ，则Ｘ→→Ｚ，其中Ｚ＝Ｕ－Ｘ－Ｙ。（２）多值依赖的传递性。即若Ｘ→→Ｙ，Ｙ→→Ｚ，则Ｘ→→Ｚ－Ｙ。（３）函数依赖可以看成是多值依赖的特殊情况。（４）若Ｘ→→Ｙ，Ｘ→→Ｚ，则Ｘ→→ＹＺ。（５）若Ｘ→→Ｙ，Ｘ→→Ｚ，则Ｘ→→ＹＺ。（６）若Ｘ→→Ｙ，Ｘ→→Ｚ，则Ｘ→→Ｚ－Ｙ。３．逻辑蕴涵与Ａｒｍｓｔｒｏｎｇ公理系统【定义２．１０】设Ｒ（Ｕ，Ｆ）是一个关系模式，Ｘ，Ｙ是Ｕ中的属性组，若在Ｒ（Ｕ，