查询树的优化精选PPT.ppt

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

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

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

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

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

5、先做选择可以减少读取写入的数据，因此减少磁盘IO量，量，从而提高了效率。从而提高了效率。第17页，此课件共40页哦设设S1是计科是计科041的学生关系表，的学生关系表，S3是计科专业的学生关系表：是计科专业的学生关系表：第18页，此课件共40页哦9.选择对自然连接的分配率F只涉及只涉及E1和和E2的公共属性。的公共属性。注：先做选择可以减少做笛卡儿积的数据，结果关系的数据量也注：先做选择可以减少做笛卡儿积的数据，结果关系的数据量也同步减少，因此减少磁盘同步减少，因此减少磁盘IO量，提高了效率。量，提高了效率。第19页，此课件共40页哦查找查找95001这位学生的选课记录：这位学生的选课记录：第

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

7、高了效率。第23页，此课件共40页哦设设S1是计科是计科041的学生关系表，的学生关系表，S2是计科是计科042的学生关系表：的学生关系表：查找计科查找计科041、042的大于岁的学生：的大于岁的学生：第24页，此课件共40页哦优化规则：n选择运算尽可能先做。选择运算尽可能先做。n投影运算和选择运算同时进行。投影运算和选择运算同时进行。n把投影运算同其前后的把投影运算同其前后的 双目运算结合执行。双目运算结合执行。n选择运算和笛卡儿积运算结合成连接运算。选择运算和笛卡儿积运算结合成连接运算。n找出公共子表达式，避免重复运算。找出公共子表达式，避免重复运算。第25页，此课件共40页哦优化算法：1

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

9、目运算时并入改组。笛卡儿积的后代中若不是与之可以合并的自然连接的等值选择时，其后代若不是与之可以合并的自然连接的等值选择时，其后代单独分为一组。单独分为一组。第26页，此课件共40页哦优化实例例：对课本第二章例例：对课本第二章例9的关系代数表达式（如下）进的关系代数表达式（如下）进行优化。行优化。其中，其中，C是课程表，是课程表，S是学生表，是学生表，SC是学生选课是学生选课表。表。在优化规则中没有对自然连接的直接优化，我在优化规则中没有对自然连接的直接优化，我们把自然连接分解为笛卡儿积和选择。们把自然连接分解为笛卡儿积和选择。第27页，此课件共40页哦分解后的关系代数表达式SCSC第28页，

10、此课件共40页哦第一步：利用规则第一步：利用规则4分解选择运算分解选择运算SCSC第29页，此课件共40页哦第二步：尽量下放选择运算第二步：尽量下放选择运算SCSC第30页，此课件共40页哦SCSC第二步（第二步（2）：下放完成后：）：下放完成后：第31页，此课件共40页哦第三步：尽量下放投影运算第三步：尽量下放投影运算SCSCE第32页，此课件共40页哦第三步：尽量下放投影运算第三步：尽量下放投影运算SCSC第33页，此课件共40页哦第三步（第三步（2）：第一次下放后：）：第一次下放后：SCSC第34页，此课件共40页哦第三步（第三步（3）：第二次下放：）：第二次下放：SCSC第35页，此课件共40页哦第三步（第三步（3）：第二次下放：）：第二次下放：SCSC第36页，此课件共40页哦第三步（第三步（4）：第二次下放后：）：第二次下放后：SCSC第37页，此课件共40页哦SCSC第四步：尽量把选择和投影靠在一起第四步：尽量把选择和投影靠在一起第38页，此课件共40页哦第五步：分组第五步：分组SCSC第39页，此课件共40页哦作业：n第三版：第三版：P166第第4题。题。n第四版：第四版：P275第第2题。题。即优化表达式：即优化表达式：第40页，此课件共40页哦