查询树的优化优秀PPT.ppt

《查询树的优化优秀PPT.ppt》由会员分享，可在线阅读，更多相关《查询树的优化优秀PPT.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、查询树的优化你现在浏览的是第一页，共40页等价的概念：n若关系表达式f（E1，E2，En）的结果与关系表达式g（E1，E2，En）的结果是同一个关系，那么称这两个表达式等价。n若关系表达式E1和E2是等价的可以记为：你现在浏览的是第二页，共40页等价变换规则1.连接、笛卡儿积交换率连接、笛卡儿积交换率设设E1和和E2是关系代数表达式，是关系代数表达式，F是连接运算的条是连接运算的条件，则有：件，则有：你现在浏览的是第三页，共40页笛卡尔积自然连接你现在浏览的是第四页，共40页2.连接、笛卡尔积的结合率连接、笛卡尔积的结合率 设设E1，E2，E3是关系代数表达式，是关系代数表达式，F1和和F2是

2、连是连接运算的条件，则有：接运算的条件，则有：你现在浏览的是第五页，共40页你现在浏览的是第六页，共40页3.投影的串接定律 这里，这里，E是关系代数表达式，是关系代数表达式，Ai（i=1，2，n），），Bj（j=1，2，m）是属性名且）是属性名且A1，A2，An 是是B1，B2，Bm 的子集。的子集。你现在浏览的是第七页，共40页求所有的学生姓名：你现在浏览的是第八页，共40页4.选择的串接定律E是关系代数表达式，是关系代数表达式，F1和和F2是选择是选择条件。选择的串接定律说明选择条件可以条件。选择的串接定律说明选择条件可以合并，这样一次就可以检查全部的条件。合并，这样一次就可以检查全部的

3、条件。你现在浏览的是第九页，共40页求IS系年龄大于岁的学生：你现在浏览的是第十页，共40页5.选择与投影的交换率 此时，条件此时，条件F只涉及属性组只涉及属性组A。若条件中有不属于。若条件中有不属于A的属性组的属性组B，那么有更一般的规则：，那么有更一般的规则：你现在浏览的是第十一页，共40页你现在浏览的是第十二页，共40页6.选择与笛卡尔积的交换 （1）F只涉及只涉及E1的属性。的属性。（2）F=F1 F2，且，且F1只涉及只涉及E1的属性，的属性，F2只涉只涉及及E2的属性。的属性。（3）F=F1 F2，且，且F1只涉及只涉及E1的属性，而的属性，而F2涉涉及及E1和和E2的属性。的属性

4、。你现在浏览的是第十三页，共40页(1)实例：实例：95001这个学生可能的选课情况：这个学生可能的选课情况：（2）证明：）证明：你现在浏览的是第十四页，共40页7.选择与并的分配率设设E=E1 E2，E1和和E2有相同的属性名，则：有相同的属性名，则：注：先做选择可以减少读取写入的数据，因此减少磁盘注：先做选择可以减少读取写入的数据，因此减少磁盘IO量，量，从而提高了效率。从而提高了效率。你现在浏览的是第十五页，共40页设设S1是计科是计科041的学生关系表，的学生关系表，S2是计科是计科042的学生关系表：的学生关系表：你现在浏览的是第十六页，共40页8.选择与差运算的分配率设设E1和和E

5、2有相同的属性名，则：有相同的属性名，则：注：先做选择可以减少读取写入的数据，因此减少磁盘注：先做选择可以减少读取写入的数据，因此减少磁盘IO量，从量，从而提高了效率。而提高了效率。你现在浏览的是第十七页，共40页设设S1是计科是计科041的学生关系表，的学生关系表，S3是计科专业的学生关系表：是计科专业的学生关系表：你现在浏览的是第十八页，共40页9.选择对自然连接的分配率F只涉及只涉及E1和和E2的公共属性。的公共属性。注：先做选择可以减少做笛卡儿积的数据，结果关系的数据量也注：先做选择可以减少做笛卡儿积的数据，结果关系的数据量也同步减少，因此减少磁盘同步减少，因此减少磁盘IO量，提高了效

6、率。量，提高了效率。你现在浏览的是第十九页，共40页查找查找95001这位学生的选课记录：这位学生的选课记录：你现在浏览的是第二十页，共40页10.投影于笛卡尔积的分配律 设设E1和和E2是两个关系表达式，是两个关系表达式，A是是E1的属性组，的属性组，B是是E2的属性组。则：的属性组。则：注：先做投影可以减少读取写入的数据，因此减少磁盘注：先做投影可以减少读取写入的数据，因此减少磁盘IO量，从而提高了效率。量，从而提高了效率。你现在浏览的是第二十一页，共40页查找所有学生可能的选课对：你现在浏览的是第二十二页，共40页11.投影与并的分配律设设E1和和E2有相同的属性名，则：有相同的属性名，

7、则：注：先做投影可以减少读取写入的数据，因此减少磁盘注：先做投影可以减少读取写入的数据，因此减少磁盘IO量，从量，从而提高了效率。而提高了效率。你现在浏览的是第二十三页，共40页设设S1是计科是计科041的学生关系表，的学生关系表，S2是计科是计科042的学生关系表：的学生关系表：查找计科查找计科041、042的大于岁的学生：的大于岁的学生：你现在浏览的是第二十四页，共40页优化规则：n选择运算尽可能先做。选择运算尽可能先做。n投影运算和选择运算同时进行。投影运算和选择运算同时进行。n把投影运算同其前后的把投影运算同其前后的 双目运算结合执行。双目运算结合执行。n选择运算和笛卡儿积运算结合成连

8、接运算。选择运算和笛卡儿积运算结合成连接运算。n找出公共子表达式，避免重复运算。找出公共子表达式，避免重复运算。你现在浏览的是第二十五页，共40页优化算法：1.利用规则利用规则4分解选择运算。分解选择运算。2.利用规则利用规则49把选择运算尽量移到叶端。把选择运算尽量移到叶端。3.利用规则利用规则3，5，10，11把投影运算尽量移到叶端。把投影运算尽量移到叶端。4.利用规则利用规则35把选择和投影的串接合并成单个选择、把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影的形式。使尽可能单个投影或一个选择后跟一个投影的形式。使尽可能多的选择和投影同时执行。多的选择和投影同时执行。5.

9、分组。双目运算和他的直系祖先为一组；双目运算后分组。双目运算和他的直系祖先为一组；双目运算后代直道叶子全是单目运算时并入改组。笛卡儿积的后代直道叶子全是单目运算时并入改组。笛卡儿积的后代中若不是与之可以合并的自然连接的等值选择时，代中若不是与之可以合并的自然连接的等值选择时，其后代单独分为一组。其后代单独分为一组。你现在浏览的是第二十六页，共40页优化实例例：对课本第二章例例：对课本第二章例9的关系代数表达式（如下）的关系代数表达式（如下）进行优化。进行优化。其中，其中，C是课程表，是课程表，S是学生表，是学生表，SC是学生选是学生选课表。课表。在优化规则中没有对自然连接的直接优化，我在优化规

10、则中没有对自然连接的直接优化，我们把自然连接分解为笛卡儿积和选择。们把自然连接分解为笛卡儿积和选择。你现在浏览的是第二十七页，共40页分解后的关系代数表达式SCSC你现在浏览的是第二十八页，共40页第一步：利用规则第一步：利用规则4分解选择运算分解选择运算SCSC你现在浏览的是第二十九页，共40页第二步：尽量下放选择运算第二步：尽量下放选择运算SCSC你现在浏览的是第三十页，共40页SCSC第二步（第二步（2）：下放完成后：）：下放完成后：你现在浏览的是第三十一页，共40页第三步：尽量下放投影运算第三步：尽量下放投影运算SCSCE你现在浏览的是第三十二页，共40页第三步：尽量下放投影运算第三步

11、：尽量下放投影运算SCSC你现在浏览的是第三十三页，共40页第三步（第三步（2）：第一次下放后：）：第一次下放后：SCSC你现在浏览的是第三十四页，共40页第三步（第三步（3）：第二次下放：）：第二次下放：SCSC你现在浏览的是第三十五页，共40页第三步（第三步（3）：第二次下放：）：第二次下放：SCSC你现在浏览的是第三十六页，共40页第三步（第三步（4）：第二次下放后：）：第二次下放后：SCSC你现在浏览的是第三十七页，共40页SCSC第四步：尽量把选择和投影靠在一起第四步：尽量把选择和投影靠在一起你现在浏览的是第三十八页，共40页第五步：分组第五步：分组SCSC你现在浏览的是第三十九页，共40页作业：n第三版：第三版：P166第第4题。题。n第四版：第四版：P275第第2题。题。即优化表达式：即优化表达式：你现在浏览的是第四十页，共40页