查询树的优化精选文档.ppt

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

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

2、的条件，则有：本讲稿第五页，共四十页本讲稿第六页，共四十页3.投影的串接定律 这里，这里，E是关系代数表达式，是关系代数表达式，Ai（i=1，2，n），），Bj（j=1，2，m）是属性名且）是属性名且A1，A2，An 是是B1，B2，Bm 的子集。的子集。本讲稿第七页，共四十页求所有的学生姓名：本讲稿第八页，共四十页4.选择的串接定律E是关系代数表达式，是关系代数表达式，F1和和F2是选择条是选择条件。选择的串接定律说明选择条件可以合件。选择的串接定律说明选择条件可以合并，这样一次就可以检查全部的条件。并，这样一次就可以检查全部的条件。本讲稿第九页，共四十页求IS系年龄大于岁的学生：本讲稿第十

3、页，共四十页5.选择与投影的交换率 此时，条件此时，条件F只涉及属性组只涉及属性组A。若条件中有不属于。若条件中有不属于A的属性组的属性组B，那么有更一般的规则：，那么有更一般的规则：本讲稿第十一页，共四十页本讲稿第十二页，共四十页6.选择与笛卡尔积的交换 （1）F只涉及只涉及E1的属性。的属性。（2）F=F1 F2，且，且F1只涉及只涉及E1的属性，的属性，F2只涉及只涉及E2的属性。的属性。（3）F=F1 F2，且，且F1只涉及只涉及E1的属性，而的属性，而F2涉涉及及E1和和E2的属性。的属性。本讲稿第十三页，共四十页(1)实例：实例：95001这个学生可能的选课情况：这个学生可能的选课

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

5、此减少磁盘IO量，从而提量，从而提高了效率。高了效率。本讲稿第十七页，共四十页设设S1是计科是计科041的学生关系表，的学生关系表，S3是计科专业的学生关系表：是计科专业的学生关系表：本讲稿第十八页，共四十页9.选择对自然连接的分配率F只涉及只涉及E1和和E2的公共属性。的公共属性。注：先做选择可以减少做笛卡儿积的数据，结果关系的数据量也注：先做选择可以减少做笛卡儿积的数据，结果关系的数据量也同步减少，因此减少磁盘同步减少，因此减少磁盘IO量，提高了效率。量，提高了效率。本讲稿第十九页，共四十页查找查找95001这位学生的选课记录：这位学生的选课记录：本讲稿第二十页，共四十页10.投影于笛卡尔

6、积的分配律 设设E1和和E2是两个关系表达式，是两个关系表达式，A是是E1的属性组，的属性组，B是是E2的属性组。则：的属性组。则：注：先做投影可以减少读取写入的数据，因此减少磁盘注：先做投影可以减少读取写入的数据，因此减少磁盘IO量，从量，从而提高了效率。而提高了效率。本讲稿第二十一页，共四十页查找所有学生可能的选课对：本讲稿第二十二页，共四十页11.投影与并的分配律设设E1和和E2有相同的属性名，则：有相同的属性名，则：注：先做投影可以减少读取写入的数据，因此减少磁盘注：先做投影可以减少读取写入的数据，因此减少磁盘IO量，量，从而提高了效率。从而提高了效率。本讲稿第二十三页，共四十页设设S

7、1是计科是计科041的学生关系表，的学生关系表，S2是计科是计科042的学生关系表：的学生关系表：查找计科查找计科041、042的大于岁的学生：的大于岁的学生：本讲稿第二十四页，共四十页优化规则：n选择运算尽可能先做。选择运算尽可能先做。n投影运算和选择运算同时进行。投影运算和选择运算同时进行。n把投影运算同其前后的把投影运算同其前后的 双目运算结合执行。双目运算结合执行。n选择运算和笛卡儿积运算结合成连接运算。选择运算和笛卡儿积运算结合成连接运算。n找出公共子表达式，避免重复运算。找出公共子表达式，避免重复运算。本讲稿第二十五页，共四十页优化算法：1.利用规则利用规则4分解选择运算。分解选择

8、运算。2.利用规则利用规则49把选择运算尽量移到叶端。把选择运算尽量移到叶端。3.利用规则利用规则3，5，10，11把投影运算尽量移到叶端。把投影运算尽量移到叶端。4.利用规则利用规则35把选择和投影的串接合并成单个选择、单把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影的形式。使尽可能多个投影或一个选择后跟一个投影的形式。使尽可能多的选择和投影同时执行。的选择和投影同时执行。5.分组。双目运算和他的直系祖先为一组；双目运算分组。双目运算和他的直系祖先为一组；双目运算后代直道叶子全是单目运算时并入改组。笛卡儿积后代直道叶子全是单目运算时并入改组。笛卡儿积的后代中若不是与之可以合

9、并的自然连接的等值选的后代中若不是与之可以合并的自然连接的等值选择时，其后代单独分为一组。择时，其后代单独分为一组。本讲稿第二十六页，共四十页优化实例例：对课本第二章例例：对课本第二章例9的关系代数表达式（如下）的关系代数表达式（如下）进行优化。进行优化。其中，其中，C是课程表，是课程表，S是学生表，是学生表，SC是学生选是学生选课表。课表。在优化规则中没有对自然连接的直接优化，我在优化规则中没有对自然连接的直接优化，我们把自然连接分解为笛卡儿积和选择。们把自然连接分解为笛卡儿积和选择。本讲稿第二十七页，共四十页分解后的关系代数表达式SCSC本讲稿第二十八页，共四十页第一步：利用规则第一步：利

10、用规则4分解选择运算分解选择运算SCSC本讲稿第二十九页，共四十页第二步：尽量下放选择运算第二步：尽量下放选择运算SCSC本讲稿第三十页，共四十页SCSC第二步（第二步（2）：下放完成后：）：下放完成后：本讲稿第三十一页，共四十页第三步：尽量下放投影运算第三步：尽量下放投影运算SCSCE本讲稿第三十二页，共四十页第三步：尽量下放投影运算第三步：尽量下放投影运算SCSC本讲稿第三十三页，共四十页第三步（第三步（2）：第一次下放后：）：第一次下放后：SCSC本讲稿第三十四页，共四十页第三步（第三步（3）：第二次下放：）：第二次下放：SCSC本讲稿第三十五页，共四十页第三步（第三步（3）：第二次下放：）：第二次下放：SCSC本讲稿第三十六页，共四十页第三步（第三步（4）：第二次下放后：）：第二次下放后：SCSC本讲稿第三十七页，共四十页SCSC第四步：尽量把选择和投影靠在一起第四步：尽量把选择和投影靠在一起本讲稿第三十八页，共四十页第五步：分组第五步：分组SCSC本讲稿第三十九页，共四十页作业：n第三版：第三版：P166第第4题。题。n第四版：第四版：P275第第2题。题。即优化表达式：即优化表达式：本讲稿第四十页，共四十页