查询树的优化

第七讲查询树的优化王晓辉华北电力大学计算机系等价的概念：若关系表达式f（E1，E2，…，En）的结果与关系表达式g（E1，E2，…，En）的结果是同一个关系，那么称这两个表达式等价。若关系表达式E1和E2是等价的可以记为：12EE等价变换规则1.连接、笛卡儿积交换率设E1和E2是关系代数表达式，F是连接运算的条件，则有：1221EEEE1221EEEE1221FFEEEE笛卡尔积{()()}rsrsRStttRtS{()()}srrsSRtttRtS自然连接..()RASBRSRS2.连接、笛卡尔积的结合率设E1，E2，E3是关系代数表达式，F1和F2是连接运算的条件，则有：123123()()EEEEEE123123()()EEEEEE1212123123()()FFFFEEEEEE(){()()()}rstrstRSTttttRtStT(){()()()}rstrstRSTttttRtStT3.投影的串接定律121212,,,,,,,,,(())()nmnAAABBBAAAEE这里，E是关系代数表达式，Ai（i=1，2，…，n），Bj（j=1，2，…，m）是属性名且{A1，A2，…An}是{B1，B2，…，Bm}的子集。,(())()SnameSnameSageSnameSS求所有的学生姓名：4.选择的串接定律1212(())()FFFFEEE是关系代数表达式，F1和F2是选择条件。选择的串接定律说明选择条件可以合并，这样一次就可以检查全部的条件。''19''19(())()SdeptISSageSdeptISSageSS求IS系年龄大于１９岁的学生：5.选择与投影的交换率此时，条件F只涉及属性组A。若条件中有不属于A的属性组B，那么有更一般的规则：1212,,,,,,(())(())nnFAAAAAAFEE12121212,,,,,,,,,,,,,(())((()))nnnmAAAFAAAFAAABBBEE19,,19(())(())SageSnameSageSnameSageSageSE1919,(())((()))SnameSageSnameSageSnameSageSE6.选择与笛卡尔积的交换122112121212()1()()()23(())FFFFFFEEEEEEEE（）（）（）（1）F只涉及E1的属性。（2）F=F1∧F2，且F1只涉及E1的属性，F2只涉及E2的属性。（3）F=F1∧F2，且F1只涉及E1的属性，而F2涉及E1和E2的属性。'95001''95001'()()SnoSnoSCSC(1)实例：95001这个学生可能的选课情况：（2）证明：122121121212121212()()(())(())()()FFFFFFFFFEEEEEEEEEE7.选择与并的分配率设E=E1∪E2，E1和E2有相同的属性名，则：1212()()()FFFEEEE注：先做选择可以减少读取写入的数据，因此减少磁盘IO量，从而提高了效率。设S1是计科041的学生关系表，S2是计科042的学生关系表：1912191192()()()SageSageSageSSSS8.选择与差运算的分配率设E1和E2有相同的属性名，则：1212()()()FFFEEEE注：先做选择可以减少读取写入的数据，因此减少磁盘IO量，从而提高了效率。设S1是计科041的学生关系表，S3是计科专业的学生关系表：1931193191()()()SageSageSageSSSS9.选择对自然连接的分配率F只涉及E1和E2的公共属性。1212()()()FFFEEEE注：先做选择可以减少做笛卡儿积的数据，结果关系的数据量也同步减少，因此减少磁盘IO量，提高了效率。'95001''95001''95001'()()()SnoSnoSnoSSCSSC查找‘95001’这位学生的选课记录：10.投影于笛卡尔积的分配律设E1和E2是两个关系表达式，A是E1的属性组，B是E2的属性组。则：12121212,,,,,,,12,,,1,,,2()()()nmnmAAABBBAAABBBEEEE注：先做投影可以减少读取写入的数据，因此减少磁盘IO量，从而提高了效率。,()()()SnameCnameSnameCnameSCSC查找所有学生可能的选课对：11.投影与并的分配律设E1和E2有相同的属性名，则：121212,,,12,,,1,,,2()()()nnnAAAAAAAAAEEEE注：先做投影可以减少读取写入的数据，因此减少磁盘IO量，从而提高了效率。设S1是计科041的学生关系表，S2是计科042的学生关系表：1912191192()()()SageSageSageSSSS查找计科041、042的大于１９岁的学生：优化规则：选择运算尽可能先做。投影运算和选择运算同时进行。把投影运算同其前后的双目运算结合执行。选择运算和笛卡儿积运算结合成连接运算。找出公共子表达式，避免重复运算。优化算法：1.利用规则4分解选择运算。2.利用规则4~9把选择运算尽量移到叶端。3.利用规则3，5，10，11把投影运算尽量移到叶端。4.利用规则3~5把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影的形式。使尽可能多的选择和投影同时执行。5.分组。双目运算和他的直系祖先为一组；双目运算后代直道叶子全是单目运算时并入改组。笛卡儿积的后代中若不是与之可以合并的自然连接的等值选择时，其后代单独分为一组。优化实例例：对课本第二章例9的关系代数表达式（如下）进行优化。其中，C是课程表，S是学生表，SC是学生选课表。在优化规则中没有对自然连接的直接优化，我们把自然连接分解为笛卡儿积和选择。'5'(())SnameCpnoCSCS分解后的关系代数表达式'5'....(())SnameCpnoCCnoSCCnoSCSnoSSnoCSCSSname'5'....CpnoCCnoSCCnoSCSnoSSno××SCSC第一步：利用规则4分解选择运算Sname..SCSnoSSno××SCSC'5'Cpno..CCnoSCCno1212(())()FFFFEE1212()(())FFFFEE第二步：尽量下放选择运算Sname..SCSnoSSno××SCSC'5'Cpno..CCnoSCCno1212()()FFEEEESname..SCSnoSSno××SCSC'5'Cpno..CCnoSCCno第二步（2）：下放完成后：第三步：尽量下放投影运算Sname..SCSnoSSno××SCSC'5'Cpno..CCnoSCCno.....,.,(()((())SnameSCSnoSSnoSnameSCSnoSSnoSCSnoSSnoSnameEEE第三步：尽量下放投影运算Sname..SCSnoSSno××SCSC'5'Cpno..CCnoSCCno.,.,SCSnoSSnoSname12121212,,,,,,,12,,,1,,,2()()()nmnmAAABBBAAABBBEEEE第三步（2）：第一次下放后：..SCSnoSSno××SCSC'5'Cpno..CCnoSCCnoSname.,.SSnameSSno.SCSno第三步（3）：第二次下放：..SCSnoSSno××SCSC'5'Cpno..CCnoSCCnoSname.SCSno.......,.,.(()(((()))SCSnoCCnoSCCnoSCSnoCCnoSCCnoCCnoSCSnoSCCnoEE.,.SSnameSSno第三步（3）：第二次下放：..SCSnoSSno××SCSC'5'Cpno..CCnoSCCnoSname.SCSno.,.SSnameSSno.,.,.CCnoSCSnoSCCno12121212,,,,,,,12,,,1,,,2()()()nmnmAAABBBAAABBBEEEE第三步（4）：第二次下放后：..SCSnoSSno××SCSC'5'Cpno..CCnoSCCnoSname.SCSno.,.SCSnoSCCno.CCno.,.SSnameSSno..SCSnoSSno××SCSC'5'Cpno..CCnoSCCnoSname.SCSno.,.SCSnoSCCno.CCno第四步：尽量把选择和投影靠在一起.,.SSnameSSno第五步：分组..SCSnoSSno××SCSC'5'Cpno..CCnoSCCnoSname.SCSno.,.SCSnoSCCno.CCno.,.SSnameSSno作业：第三版：P166第4题。第四版：P275第2题。即优化表达式：''(()CnameSdeptISSSCC