搜索
4关系系统及其查询优化关系系统：支持关系模型的数据库管理系统称为关系系统一个系统可定义为关系系统，当且仅当它：(1)支持关系数据库（关系数据结构）从用户观点看，数据库由表构成，并且只有表这一种结构。(2)支持选择、投影、连接运算，且不要求定义物理存取路径当然并不要求关系系统的选择、投影、连接运算和关系代数的相应运算完全一样，而只要求有等价的这三种运算功能就行。几点解释·为什么关系系统除了要支持关系数据结构外，还必须支持选择、投影、连接运算呢？因为不支持这三种关系运算的系统，用户使用仍不方便，不能提高用户的生产率，而提高用户生产率正是关系系统主要目标之一。为什么要求这三种运算不能依赖于物理存取路径呢？因为依赖物理存取路径来实现关系运算就降低或丧失了数据的物理独立性。不依赖物理存取路径来实现关系运算就要求关系系统自动地选择路径。为此，系统要进行查询优化以获得较好的性能。这正是关系系统实施的关键技术。要求关系系统支持这三种最主要的运算而不是关系代数的全部运算功能，是因为它们是最有用的运算功能，能解决绝大部分的实际回题。4.1关系系统的分类依据各类系统支持关系模型的程度：s数据结构I完整性m数据操作1.1.表式系统这类系统仅支持关系(即表)数据结构，不支持集合级的操作。表式系统不能算关系系统。倒排表列(Invertedlist)系统就属于这一类。2.(最小)关系系统即前面定义的关系系统。它们仅支持关系数据结构和三种关系搡作。许多微机关系数据库系统如DbaseⅡ、FoxBASE、FoxPro等就属于（最小）关系系统。3.关系完备的系统这类系统支持关系数据结构和所有的关系代数操作(功能上与关系代数等价)。90年代初的许多关系数据库管理系统属于这一类。4.全关系系统这类系统支持关系模型的所有特征。即不仅是关系上完备的而且支持数据结构中域的概念，支持实体完整性和参照完整性。目前，大多数关系系统已不同程度上接近或达到了这个目标。4.2关系数据库系统的查询优化（1）关系查询优化的特点关系查询优化是影响RDBMS性能的关键因素。它减轻了用户选择存取路径的负担。用户只要提出‘干什么’，不必指出‘怎么干’。查询优化更优“用户程序”的优化。(2)查询优化的实现:1.将查询转化成某种内部表示,通常是语法树2.根据一定的等价变换把语法树转换成标准优化形式3.选择底层的操作算法,对于语法树中的每一个操作需要根据存储路径,数据的存储分布等信息来选择具体的执行算法4.生成查询计划..通常这样的方案有多个,需要对每个执行计划计算代价,从中选择代价最小的一个.（3）关系数据库查询优化的总目标选择有效的策略，基于代价的优化算法，求得给定关系表达式的值。即通过对多个执行方案分析，需要对每个执行计划计算代价，从中选择代价最小的一个查询算法。在集中式数据库中，查询的执行开销主要包括：总代价=I/O代价+CPU代价在多用户环境下：总代价=I/O代价+CPU代价+内存代价4.3一个基于代价分析的查询优化实例见word文档4.4查询优化的一般准则（l）选择运算应尽可能先做。在优化策略中这是最重要、最基本的一条。它常常可使执行时节约几个数量级，因为选择运算一般使计算的中间结果大大变小。（2）在执行连接前对关系适当地预处理。预处理方法主要有两种，在连接属性上建立索引和对关系排序，然后执行连接。第一种称为索引连接方法，第二种称为排序合并（SORT-MERGE）连接方法一个例子例如STUDENTSC这样的自然连接，用索引连接方法的步骤是：1)在SC上建立Sno的索引2)对STUDENT中每一个元组,由Sno值通过SC的索引查找相应的SC元组3)把这些SC元组和STUDENT元组连接起来这样Student表和SC表均只要扫描一遍。处理时间只是两个关系大小的线性函数。用排序合并连接方法的步骤是：1)首先对Student表和SC表按连接属性Sno排序(图4.2)2)取Student表中第一个Sno,依次扫描SC表中具有相同Sno的元组，把它们连接起来:3)当扫描到Sno不相同的第一个SC元组时，返回Student表扫描它的下一个元组，再扫描SC表中具有相同Sno的元组，把它们连接起来。重复上述步骤直到Student表扫描完。这样Student表和SC表也只要扫描一遍。当然，执行时间要加上对两个表的排序时间。即使这样，使用预处理方法执行连接的时间一般仍大大减少。（3）把投影运算和选择运算同时进行。如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完戌所有的这些运算以避免重复扫描关系。（4）投影同双目运算结合把投影同其前或其后的双目运算结合起来，没有必要为了去掉某些字段而扫描一遍关系。（5）选择同某些笛卡尔积结合起来构成一个连接运算把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算，连接特别是等值连接运算要比同样关系上的笛卡尔积省很多时间（6）找出公共子表达式。如果重复出现的子表达式的查询结果不是很大的关系，并且从外存中读入这个关系比计算该子表达式的时间少得多，则先计算一次公共子表达式并把结果写入中间文件是合算的。当查询的是视图时，定义视图的表达式就是公共子表达式的情况。4.5关系代数等价变换规则优化策略大部分都涉及到代数表达式的变换，所以，关系代数表达式的优化是查询优化的基本课题。而研究关系代数表达式的优化，必须研究关系表达式的等价变换规则。定义：两个查询表达式E1和E2是等价的，如果其查询的结果是相同的，可记为：E1≡E2利用这个等价定义，我们可利用前面讨论的“等价变换规则”，非常方便地描述查询表达式。常用的等价变化规则：1）连接、笛卡尔积交换律设E1和E2是关系代数表达式，F是连接运算的条件，则有：E1×E2≡E2×E1E1E2≡E2E1E1E2≡E2ElFF（2）连接、笛卡尔积的结合律设E1，E2，E3是关系代数表达式，Fl和F2是连接运算的条件，则有：(E1×E2)×E3≡El×(E2×E3)(E1E2)E3≡E1(E2E3)(E1E2)E3≡E1(E2E3)F1F2F1F2（3）投影的串接定律∏A1,A2,...,An(∏B1,B2,...,Bm(E))≡∏A1,A2,...,An(E)这里,E是关系代数表达式,Ai(i=1,2,...,n),Bj(j=l,2,...,m)是属性名且{A1,A2,...,An}构成{Bl，B2，...，Bm}的子集。（4）选择的串接定律бF1（бF2（E））≡бF1∧F2(E)这里，E是关系代数表达式，Fl，F2是选择条件。选择的串接律说明选择条件可以合并。这样一次就可检查全部条件。（5）选择与投影的交换律бF(∏A1,A2,...,An(E))≡∏A1,A2,...,An(бF(E))这里，选择条件F只涉及属性A1,...,An。若F中有不属于Al,...,An的属性:B1，…,Bm则有更一般的规则：∏A1,A2,...,An(бF(E))≡∏A1,A2,...,An(бF(∏A1,A2,...,An，B1,B2,...,Bm(E))（6）选择与笛卡尔积的交换律如果F中涉及的属性都是El中的属性,则бF(El×E2)≡бF(El)×E2如果F=F1∧F2，并且F1只涉及E1中的属性，F2只涉及E2中的属性，则由上面的等价变换规则1,4,6可推出：бF(E1×E2)≡бF1(El)×бF2(E2)若F1只涉及E1中的属性，F2涉及E1和E2两者的属性，则仍有бF(El×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）投影与笛卡尔积的交换设E1和E2是两个关系表达式，A1，...，An是E1的属性，B1，...，Bm是E2的属性，则A1,A2,…,An,B1,B2,…,Bm(E1×E2)≡A1,A2,…,An(E1)×B1,B2,…,Bm(E2)（l0）投影与并的交换设E1和E2有相同的属性名，则A1,A2,...,An(E1∪E2)≡A1,A2,...,An(E1)∪A1,A2,...,An(E2)4.6关系代数表达式的优化算法我们可以应用前面讨论的变换法则来优化关系表达式。使优化后的表达式能遵循4.2.3中的一般原则。例如把选择和投影尽可能地早做(即把它们移到表达式语法树的下部)。以下给出查询关系表达式的优化算法。算法：关系表达式的优化。输入：一个关系表达式的语法树。输出：计算该表达式的程序。方法：1.利用规则(4)把形如F1∧F2...∧Fn(E)变换为F1(F2(...(Fn(E))...))2.对每一个选择，利用规则(4)～（8）尽可能把它移到树的叶端。对每一个投影利用规则(3)，(9)，(l0)，(5)中的一般形式尽可能把它移向树的叶端。1.注意，法则(3)使一些投影消失，而一般形式的规则(5)把一个投影分裂为两个，其中一个有可能被移向树的叶端。2.利用规则(3)～(5)把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时执行，或在一次扫描中全部完成，尽管这种变换以乎违背‘投影尽可能早做’的原则，但这样做效率更高。3.把上述得到的语法树的内节点分组。每一双目运算(×，，∪，-)和它所有的直接祖先为一组(这些直接祖先是、运算)。如果其后代直到叶子全是单目运算则也将它们并入该组，但当双目运算是笛卡尔积(×)，而且其后的选择不能与它结合为等值连接时除外。把这些单目运算单独分为一组。6．生成一个程序，每组结点的计算是程序中的一步。各步的顺序是任意的，只要保证任何一组的计算不会在它的后代组之前计算。查询优化的一般步骤：及一个例子见word