1、1/921.1.分布式查询优化概述分布式查询优化概述2.2.分布式查询优化基础知识分布式查询优化基础知识3.3.分布式查询分类和层次结构分布式查询分类和层次结构4.4.基于关系代数等价变换的查询优化处理基于关系代数等价变换的查询优化处理5.5.基于半连接算法的查询优化处理基于半连接算法的查询优化处理6.6.基于直接连接算法的查询优化处理基于直接连接算法的查询优化处理7.7.直接连接操作的常用策略直接连接操作的常用策略分布式数据库中的查询处理和优化分布式数据库中的查询处理和优化 第第3章章2/92查询处理问题 集中式 查询转换为代数表达式 从所有等价表达式中选择最优的代数表达式 分布式 除了集中
2、式问题外，还有 站点之间交换数据的操作 选择最优的执行站点(分布）数据被传送的方式1.1 分布式查询优化的目标分布式查询优化的目标1 1 分布式查询优化概述分布式查询优化概述3/921.1 分布式查询优化的目标分布式查询优化的目标1 1 分布式查询优化概述分布式查询优化概述目标目标总代价最小总代价最小响应时间最短响应时间最短集中式集中式分布式分布式CPU代价（相对固定）代价（相对固定）I/O代价（优化的目标）代价（优化的目标）CPU代价代价I/O代价（访问磁盘）代价（访问磁盘）通讯代价通讯代价数据的分布和冗余增加了查询的并行处理数据的分布和冗余增加了查询的并行处理的可能性，从而可以缩减查询处理
3、的响应的可能性，从而可以缩减查询处理的响应时间时间主要标准主要标准辅助标准辅助标准4/921.2 分布式查询优化准则和代价分析分布式查询优化准则和代价分析1 1 分布式查询优化概述分布式查询优化概述准则：准则：使得使得通讯费用最低通讯费用最低和和响应时间最短响应时间最短，即以最小的总代价，即以最小的总代价，在最短的响应时间内获得需要的数据。在最短的响应时间内获得需要的数据。1.通讯费用与所传输的通讯费用与所传输的数据量数据量和和通信次数通信次数有关有关2.响应时间和通信时间有关，也与局部处理时间有关响应时间和通信时间有关，也与局部处理时间有关查询代价分析查询代价分析1.远程通讯网络远程通讯网络
4、 局部处理时间可以忽略不计，局部处理时间可以忽略不计，减少通讯代价减少通讯代价是主要目标是主要目标2.高速局域网高速局域网 传输时间比局部处理时间要短很多，以响应时间作为优化传输时间比局部处理时间要短很多，以响应时间作为优化目标，目标，局部处理时间局部处理时间是关键是关键5/92 例子 S(s#,sname,age,sex)104 元组 Site A C(c#,cname,teacher)105 元组 Site B SC(s#,c#,grade)106 元组 Site A 每个元组长度100bit,通讯传输速度 104 bit/sec,通讯延迟 1secS,SCCSite ASite B1.3
5、 分布式查询策略的重要性分布式查询策略的重要性1 1 分布式查询优化概述分布式查询优化概述6/92查询:所有选修maths 课的男生学号和姓名.SELECT s#,sname FROM S,C,SC WHERE S.s#=SC.s#AND C.c#=SC.c#AND sex=男 AND cname=maths;1.3 分布式查询策略的重要性分布式查询策略的重要性1 1 分布式查询优化概述分布式查询优化概述7/92 代价公式 QC=I/O 代价+CPU 代价+通讯代价 通讯代价 TC=传输延迟时间C0 +(传输数据量X/数据传输速率C1)=传输次数*1+传输的bit数*104。1.3 分布式查询
6、策略的重要性分布式查询策略的重要性1 1 分布式查询优化概述分布式查询优化概述8/921.3 分布式查询策略的重要性分布式查询策略的重要性1 1 分布式查询优化概述分布式查询优化概述策略策略1:A 传C B 把关系 C 传输到 A 地,在 A 地处理查询 T1=1+(105*100/104)S,SC 通信1次 C 103 秒 16.7 分钟 A 传S,SC B 把关系 S 和SC 传输到 B 地,在 B 地处理查询 T2=2+(104+105)*100/104 S,SC 通信2次 C 10100 秒 28小时 A 问105 B 先在A地求出男学生的成绩元组有105 再根据C#的值询问B地,核实
7、是否C=MATHS S,SC 答105 C T3(2*105*1)=2*105 秒 2.3 天策略策略2:策略策略3:六种查询策略六种查询策略S,SCCAB9/921.3 分布式查询策略的重要性分布式查询策略的重要性1 1 分布式查询优化概述分布式查询优化概述 A 问10 B 先在B地求出 MATHS的元组,有 10个 再根据C#的值询问 A 地的S，SC的连接，S,SC 答10 C 核实是否为选修MATHS的男生 T4 (2*10*1)=20 秒 A 传输105 B 先在A地求出男生选课元组，有105个 再把结果传输到 B 地,在 B 地执行查询，S,SC 通信1次 C T5=1+(105*
8、100)/104 1000 秒 16.7 分 A 传输10 B 先在B地求出为 MATHS 的元组，有 10个 再把结果传输到 A 地 ,在 A 地执行查询，S,SC 通信 1次 C T6=1+(10*100)/104 1 秒策略策略 4：策略策略 5：策略策略 6：六种查询策略六种查询策略S,SCCAB10/92相关表述记号相关表述记号 设关系模式为设关系模式为R(A1,A2,An)。它的一个关系设为。它的一个关系设为R。tR表示表示t是是R的一个的一个元组元组。则表示元组则表示元组t中相应于属性中相应于属性Ai的一个的一个分量分量。若若A=Ai1,Ai2,Aik，其中，其中Ai1,Ai2,
9、Aik是是A1,A2,An中的一部分，中的一部分，则则A称为属性列或域列。称为属性列或域列。tA=(tAi1,tAi2,tAik)表示元组表示元组 t 在属性在属性 列列A上诸分量的集合。则上诸分量的集合。则 表示表示A1,A2,An中去掉中去掉 Ai1,Ai2,Aik 后剩余的属性组。后剩余的属性组。A关系代数知识回顾关系代数知识回顾2 2 分布式查询优化中的基础知识分布式查询优化中的基础知识11/92 R为为n目关系，目关系，S为为m目关系。目关系。trR，tsS。trts 称为元组的称为元组的连接连接。它是一个它是一个(n+m)列的元组，前列的元组，前n个分量为个分量为R中的一个中的一个
10、n元组，后元组，后m个分量个分量 为为S中的一个中的一个m元组。元组。相关表述记号相关表述记号 给定一个关系给定一个关系R(X,Z)，X和和Z为属性组。我们定义，当为属性组。我们定义，当tX=x时，时，x在在R中中 的的象集象集（Images Set）为：）为：Zx=tZ|tR,tX=x 它表示它表示R中属性组中属性组X上值为上值为x的诸元组在的诸元组在Z上分量的集合。上分量的集合。2.1 关系代数知识回顾关系代数知识回顾2 2 分布式查询优化中的基础知识分布式查询优化中的基础知识12/92传统的集合运算传统的集合运算 并运算并运算c1b2a2c2b2a1c1b1a1CBAc1b2a2c2b3
11、a1c2b2a1CBAR1R2c1b1a1c1b2a2c2b3a1c2b2a1CBAR1R2 设关系设关系R和关系和关系S具有相同的目具有相同的目n（即两个关系都有（即两个关系都有n个属性），且相应个属性），且相应的属性取自同一个域，则关系的属性取自同一个域，则关系R与关系与关系S的并由属于的并由属于R或属于或属于S的元组组成。的元组组成。其结果关系仍为其结果关系仍为n目关系。记作：目关系。记作：2.1 关系代数知识回顾关系代数知识回顾2 2 分布式查询优化中的基础知识分布式查询优化中的基础知识13/92 差运算差运算c1b2a2c2b2a1c1b1a1CBAc1b2a2c2b3a1c2b2a
12、1CBAR1R2c1b1a1CBAR1R2设关系设关系R R和关系和关系S S具有相同的目具有相同的目n n，且相应的属性取自同一个域，则关系，且相应的属性取自同一个域，则关系R R与关系与关系S S的差由属于的差由属于R R而不属于而不属于S S的所有元组组成。其结果关系仍为的所有元组组成。其结果关系仍为n n目关系。记作：目关系。记作：传统的集合运算传统的集合运算2.1 关系代数知识回顾关系代数知识回顾2 2 分布式查询优化中的基础知识分布式查询优化中的基础知识14/92 交运算交运算c1b2a2c2b2a1c1b1a1CBAc1b2a2c2b3a1c2b2a1CBAR1R2ABCa1b2
13、c2a2b2c1R1R2 设关系设关系R R和关系和关系S S具有相同的目具有相同的目n n，且相应的属性取自同一个域，且相应的属性取自同一个域，则关系则关系R R与关系与关系S S的交由既属于的交由既属于R R又属于又属于S S的元组组成。其结果关系仍的元组组成。其结果关系仍为为n n目关系。记作：目关系。记作：传统的集合运算传统的集合运算2.1 关系代数知识回顾关系代数知识回顾2 2 分布式查询优化中的基础知识分布式查询优化中的基础知识15/92 两个分别为两个分别为n n目和目和m m目的关系目的关系R R和和S S的广义笛卡尔积是一个的广义笛卡尔积是一个(n+m)(n+m)列的元组列的
14、元组的集合。元组的前的集合。元组的前n n列是关系列是关系R R的一个元组，后的一个元组，后m m列是关系列是关系S S的一个元组。若的一个元组。若R R有有k1k1个元组，个元组，S S有有k2k2个元组，则关系个元组，则关系R R和关系和关系S S的广义笛卡尔积有的广义笛卡尔积有k1k1k2k2个元组。记作：个元组。记作：R1R2c1b1a1c1b1a1c1b1a1CBAc1b2a2c2b3a1c2b2a1CBA.c2b3a1c2b2a1.c2b2a1c2b2a1c1b2a2c2b2a1c1b1a1CBAc1b2a2c2b3a1c2b2a1CBAR1R2 广义笛卡尔积广义笛卡尔积2.1 关
15、系代数知识回顾关系代数知识回顾2 2 分布式查询优化中的基础知识分布式查询优化中的基础知识16/92专门的关系运算专门的关系运算学号 学生姓名 所属系名 学生年龄 S#SN SD SA S1 A CS 20 S2 B CS 21 S3 C MA 19 S4 D CI 19 S5 E MA 20 S6 F CS 22S(S#,SN,SD,SA)2.1 关系代数知识回顾关系代数知识回顾2 2 分布式查询优化中的基础知识分布式查询优化中的基础知识17/92选择运算是从关系中选取使公式为真的元组。这是从行的角度进行的运算。选择运算是从关系中选取使公式为真的元组。这是从行的角度进行的运算。在关系在关系R
16、中选择满足给定条件的元组，记做：中选择满足给定条件的元组，记做：是一个公式，表示形式为由逻辑运算符是一个公式，表示形式为由逻辑运算符连接各算术表达式组成连接各算术表达式组成。算术表达式的基本形式为算术表达式的基本形式为：。例例1 求计算机科学系求计算机科学系CS的学生的学生学号 学生姓名 所属系名 学生年龄 S#SN SD SA S1 A CS 20 S2 B CS 21 S3 C MA 19 S4 D CI 19 S5 E MA 20 S6 F CS 22(a)(S)(S)S#SN SD SA S1 A CS 20 S2 B CS 21 S6 F CS 22 选择运算选择运算18/92 在关
17、系在关系R中选择满足给定条件的元组，记做：中选择满足给定条件的元组，记做：例例2 求计算机科学系求计算机科学系CS，年龄不超过，年龄不超过21岁的学生。岁的学生。(S)S#SN SD SA S1 A CS 20 S2 B CS 21 选择运算选择运算(S)S#SN SD SA S1 A CS 20 S2 B CS 21 S6 F CS 22学号 学生姓名 所属系名 学生年龄 S#SN SD SA S1 A CS 20 S2 B CS 21 S3 C MA 19 S4 D CI 19 S5 E MA 20 S6 F CS 22(S)19/92 投影运算投影运算 这是从列的角度进行的运算这是从列的
18、角度进行的运算。例例 即求得学生关系即求得学生关系S在学生姓名和所在系这两个属性上的投影结果。在学生姓名和所在系这两个属性上的投影结果。学号 学生姓名 所属系名 学生年龄 S#SN SD SA S1 A CS 20 S2 B CS 21 S3 C MA 19 S4 D CI 19 S5 E MA 20 S6 F CS 22(a)(S)关系关系R上的投影是从上的投影是从R中选择若干属性列组成新的关系。记做：中选择若干属性列组成新的关系。记做：投影之后不仅取消了某些列投影之后不仅取消了某些列，还可能取消某些元组。还可能取消某些元组。SA(S)SA20211922 SN SD A CS B CSC
19、MAD CIE MAF CS20/92 连接运算（连接运算（连接）连接）连接运算是从两个关系的笛卡尔积中选取属性间满足一定条件的元组。连接运算是从两个关系的笛卡尔积中选取属性间满足一定条件的元组。记做记做:R S.其中，其中，F是条件表达式，它涉及到对两个关系中的属性的比较。是条件表达式，它涉及到对两个关系中的属性的比较。F例例4 设关系设关系R、S如下图：如下图：R S CE21/92 等值等值连连接接例例5 设关系设关系R、S如下图：如下图：连接运算中有两种最为重要也最为常用的连接，连接运算中有两种最为重要也最为常用的连接，为为“”的连接运算称为等值连接的连接运算称为等值连接:22/92
20、自然连接自然连接A B C Ea1 b1 5 3 a1 b2 6 7a2 b3 8 10a2 b3 8 2R S A R.B C S.B Ea1 b1 5 b1 3 a1 b2 6 b2 7a2 b3 8 b3 10a2 b3 8 b3 2R S R.B=S.B 另一种是自然连接。自然连接是一种特殊的等值连接，它要求两个另一种是自然连接。自然连接是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性组，并且要在结果中把重复的关系中进行比较的分量必须是相同的属性组，并且要在结果中把重复的属性去掉。属性去掉。例例6 关系关系R、S的自然连结：的自然连结：R S 23/92 半连接半连
21、接 在在R R、S S自然连接后仅保留对自然连接后仅保留对R R的属性的投影，记为：的属性的投影，记为：R R S 例例7 关系关系R、S的半连接：的半连接：A B C Ea1 b1 5 3 a1 b2 6 7a2 b3 8 10a2 b3 8 2R S A B C a1 b1 5 a1 b2 6 a2 b3 8 R S24/92左外连接左外连接:对对R中任意元组，若中任意元组，若S中找不到匹配的元组，中找不到匹配的元组，则则S用空元组与之对应。用空元组与之对应。R的信息在左外连接的结果中都得到保留。的信息在左外连接的结果中都得到保留。左外连接左外连接 在在R R、S S自然连接时对不匹配的元
22、组用空值来匹配。有左外连接、右外自然连接时对不匹配的元组用空值来匹配。有左外连接、右外连接和全外连接之分连接和全外连接之分 例例8 关系关系EMP、SAL的左外连结：的左外连结：SALEMP上海上海邓平邓平长春长春李宏李宏大连大连王小王小北京北京张丽张丽CITYENAME3000赵刚赵刚5000王小王小6000张丽张丽SALARYENAME50006000SALARY上海上海邓平邓平长春长春李宏李宏大连大连王小王小北京北京张丽张丽CITYENAMEEMPSAL25/92右外连结右外连结:对对S中任意元组，若中任意元组，若R中找不到匹配的元组，中找不到匹配的元组，则则R用空元组与之对应。用空元组
23、与之对应。S的信息在右外连接的结果中都得到保留。的信息在右外连接的结果中都得到保留。右外连接右外连接例例9 关系关系EMP、SAL的右外连结：的右外连结：SALEMP上海上海邓平邓平长春长春李宏李宏大连大连王小王小北京北京张丽张丽CITYENAME3000赵刚赵刚5000王小王小6000张丽张丽SALARYENAMEENAMECITYSALARY张丽张丽北京北京6000王小王小大连大连5000赵刚赵刚NULL3000EMPSAL26/92全外连接全外连接:对对R或或S中所有不匹配的元组，均用空元组分中所有不匹配的元组，均用空元组分别匹配。别匹配。R、S的信息在全外连接的结果中都得到保留。的信息
24、在全外连接的结果中都得到保留。全外连接全外连接例例10 关系关系EMP、SAL的全外连结：的全外连结：SALEMP上海上海邓平邓平长春长春李宏李宏大连大连王小王小北京北京张丽张丽CITYENAME3000赵刚赵刚5000王小王小6000张丽张丽SALARYENAMEENAMECITYSALARY张丽张丽北京北京6000王小王小大连大连5000李宏李宏长春长春NULL邓平邓平上海上海NULL赵刚赵刚3000EMPSAL27/92c1b2a1c3b2a2c6b6a4c3b2a1c6b4a3c7b3a2c2b1a1CBARc3c1c2Cd2d1d1Db2b2b1BS例例 11 除运算除运算 给定关系
25、给定关系R(X,Y)和和S(Y,Z)，其中，其中X,Y,Z为属性组。为属性组。R中的中的Y与与S中的中的Y可以有不同的属性名，但必须出自相同的域集。可以有不同的属性名，但必须出自相同的域集。R与与S的除运算得到一个新的除运算得到一个新的关系的关系P(X)，P是是R中满足下列条件的元组在中满足下列条件的元组在X属性列上的投影：元组在属性列上的投影：元组在X上上分量值分量值x的象集的象集Yx包含包含S在在Y上投影的集合。记作：上投影的集合。记作：其中其中Yx为为x在在R中的象集，中的象集，x=tX。ZXY28/92 除运算除运算c1b2a1c3b2a2c6b6a4c3b2a1c6b4a3c7b3a
26、2c2b1a1CBAc3c1c2Cd2d1d1Db2b2b1BRSa1的象集为：的象集为：a2的象集为：的象集为：a3的象集为：的象集为：a4的象集为：的象集为：（b1,c2），（），（b2,c3），（），（b2,c1）（b3,c7），（），（b2,c3）（b4,c6）（b6,c6）S在在B、C上的投影上的投影（b1,c2），（），（b2,c3），（），（b2,c1）29/92学号 课程号 学习成绩 S#C#GRADE S1 C2 A S2 C2 C S3 C2 B .学号 课程号 学习成绩 S#C#GRADE S1 C1 A S1 C2 A S1 C3 A S1 C5 B S2 C1 B S
27、2 C2 C S2 C4 C S3 C2 B .SC 关系代数表达式关系代数表达式 设教学数据库中有三个关系：设教学数据库中有三个关系：学生关系学生关系S（S#，SNAME，SD，AGE）课程关系课程关系C（C#，CN,CP#）学习关系学习关系SC（S#，C#，GRADE）例1 检索学习课程号为检索学习课程号为C2的学生学号与成绩的学生学号与成绩S#,GRADE(C#=C2(SC)C#=C2(SC)30/92学号 课程号 学习成绩 S#C#GRADE S1 C1 A S1 C2 A S1 C3 A S1 C5 B S2 C1 B S2 C2 C .SC学号 学生姓名 所属系名 学生年龄 S#S
28、NAME SD SA S1 A CS 20 S2 B CS 21 S3 C MA 19 S4 D CI 19 S5 E MA 20.SS SC C#=C2()S SC 例2 检索学习课程号为检索学习课程号为C2的学生学号和姓名的学生学号和姓名学号 学生姓名 所属系名 学生年龄 课程号 学习成绩 S#SNAME SD SA C#GRADE S1 A CS 20 C1 A S1 A CS 20 C2 A S1 A CS 20 C3 A S1 A CS 20 C5 A S2 B CS 21 C1 B S2 B CS 21 C2 C .S#SNAME S1 A S2 BS#,SNAME(S C#=C2
29、 SC)S#,SNAME(C#=C2(S SC )31/92例3 求选修求选修数据库原理数据库原理这门课程的学生名和所在系。这门课程的学生名和所在系。（S、C、SC）学号 课程号 学习成绩 S#C#GRADE S1 C1 A S1 C2 A S1 C3 A S1 C5 B S2 C1 B S2 C2 C .SC学号 学生姓名 所属系名 学生年龄 S#SNAME SD SA S1 A CS 20 S2 B CS 21 S3 C MA 19 S4 D CI 19 S5 E MA 20.S例4 检索学习课程号为检索学习课程号为C2或或C3的学生学号和所在系的学生学号和所在系SN,SD(CN=数据库原
30、理(C)S SC S#,SD(s S#(C#=C2C#=C3(SC)32/92例5 求至少选修求至少选修C2和和C3这两门课程的学生名。这两门课程的学生名。C#C2C3KSN(S (S#,C#(SC)K)SN(S (S#,C#(SC)C#(C#=C2C#=C3(C)33/92K C#(S#=S2(SC)（S、C、SC）例7 求选修全部课程的学生名。求选修全部课程的学生名。例8 求至少选修了学生编号为求至少选修了学生编号为S2 所选课程的学生名。所选课程的学生名。S#(SC)S#(C#=C2(SC)例6 求不学求不学C2这门课程的学生名。这门课程的学生名。S#(S)S#(C#=C2(SC)SN(
31、S (C#,S#(SC)C)SN(S (C#,S#(SC)C#(S#=S2(SC)34/92 SQL与代数的等价描述 E1 SELECT sname FROM S,SC WHERE S.s#=SC.s#and SC.c#=c03;代数描述 sname(s.s#=SC.s#and SC.c#=c03(SSC)2.1 用关系代数和用关系代数和SQLSQL语句表示一个查询语句表示一个查询2 2 分布式查询优化中的基础知识分布式查询优化中的基础知识关系代数基本操作：关系代数基本操作：并（并（）、交（）、交（）、笛卡尔积（）、笛卡尔积（）、选择（）、选择（）、投影（）、投影（）关系代数导出操作：关系代数
32、导出操作：差（）、除（差（）、除（）、）、连接（连接（）、自然连接（）、自然连接（）、半连接（）、半连接（）35/92 E2 SELECT sname FROM S WHERE S.s#in (SELECT SC.s#FROM SC WHER c#=c03);代数描述 sname(s.s#=SC.s#(S SC.c#=c03 SC)E3 SELECT sname FROM S,(SELECT SC.s#FROM SC WHER c#=c03)SCC WHERE S.s#=SCC.s#;代数描述 sname(S SC.c#=c03 SC)36/922.2 查询树查询树2 2 分布式查询优化中的基
33、础知识分布式查询优化中的基础知识snames.s#=sc.s#c#=c03 S SCsname s.s#=sc.s#S c#=c03SCsname S c#=c03SC(a)对于E1的查询树(b)对于E2的查询树(c)对于E3的查询树节点表示节点表示一个一元一个一元或二元操或二元操作符作符叶子表示叶子表示已知关系已知关系树根表示树根表示查询结果查询结果37/92 一元操作：只涉及一个操作对象 (SL),(PJ)二元操作：涉及两个操作对象(UN),（）,(DF),(CP),（），(JN),(SJ),2.3 等价变换规则的概念和术语等价变换规则的概念和术语2 2 分布式查询优化中的基础知识分布式查
34、询优化中的基础知识38/92等价变换规则 空值的变换 R =R R =R =R=-R=R -=R R =R =()=()=自身操作的等价R R=R R R=R R R=R 一元操作F1(F2(R)=F1and F2(R)(R)=(R)A1,An(B1,Bm(R)=A1,An(R)有条件:A必须是B的属性2.3 等价变换规则的概念和术语等价变换规则的概念和术语2 2 分布式查询优化中的基础知识分布式查询优化中的基础知识39/92 交换律1(2(R)=2(1(R)条件:1 2 是 选择操作 时总成立 1 2 是 投影操作时要求其属性集合相等 1 与 2 是投影和选择操作时:A1,An(F(R)=F
35、(A1,An(R)的条件是 F中的属性是 A1,.An 的子集R S=S R R S=S RR S=S R R S=S RR S S R R -S S-R2.3 等价变换规则的概念和术语等价变换规则的概念和术语2 2 分布式查询优化中的基础知识分布式查询优化中的基础知识40/92 结合律 R B(S B T)=(R B S)B T)B:二元操作（JN）,（CP）,（UN）,等总成立（SJ）有问题2.3 等价变换规则的概念和术语等价变换规则的概念和术语2 2 分布式查询优化中的基础知识分布式查询优化中的基础知识41/92 分配率U(R B S)=U(R)B U(S)U:一元操作 F(R S)其中
36、F=F1 and F2,若F1有R属性,F2有S属性,则 F(RS)=F1(R)F2(S)若F1只有R属性,F2有R与S属性,则 F(R S)=F2(F1(R)S)F(R S)=F(R)F(S)F(R -S)=F(R)-F(S)F(R S)=F(R)F(S)2.3 等价变换规则的概念和术语等价变换规则的概念和术语2 2 分布式查询优化中的基础知识分布式查询优化中的基础知识42/92 B1,Bm,C1,Ck(R S)=B1,Bm(R)C1,Ck(S)B1,Bm 是R属性,C1,Ck是S属性 B1,Bm,C1,Ck(R S)=B1,Bm(R)C1,Ck(S)B1,Bm,C1,Ck(R -S)=B1
37、,Bm(R)-C1,Ck(S)B1,Bm,C1,Ck(R S)=B1,Bm(R)C1,Ck(S)PJB1,Bm(R S)=B1,Bm(B1,Bm,C1,Ck(R)C1,Ck(S)2.3 等价变换规则的概念和术语等价变换规则的概念和术语2 2 分布式查询优化中的基础知识分布式查询优化中的基础知识43/92 局部查询：只涉及本地.单个站点的数据,优化同集中式 选择和投影早做，中间结果大大减少 连接前进行预处理（属性排序、属性索引）同时执行一串投影和选择操作 远程查询：也只涉及单个站点的数据,但还要远程通讯,选择站点 选择查询应用最近的冗余分配站点 全局查询：涉及多个站点数据,优化复杂3.1 分布式
38、查询分类分布式查询分类3 3 分布式查询的分类与层次结构分布式查询的分类与层次结构44/92全局查询 具体化 对查询进行分解，确定查询使用的物理副本，落实查询对象 非冗余具体化，所有要访问对象只有一个副本 冗余具体化，多个副本，研究如何选择副本，使通信代价最小 确定操作执行的顺序 确定二元操作连接和并操作的顺序 先执行所有连接操作，再执行并操作 先执行部分并操作，再执行连接操作 选择和投影尽可能早进行 确定操作执行的方法 把若干个操作连接起来在一次数据库访问中 连接方法在查询优化中起着重要作用 确定执行的站点 执行站点不一定是发出查询的站点 考虑通讯费用和执行效率3.1 分布式查询分类分布式查
39、询分类3 3 分布式查询优化概述分布式查询优化概述45/92查询分解数据本地化全局优化局部优化分布关系上的查询表达分布关系上的代数表达分段关系查询表达带有通讯操作的段查询优化优化的局部查询表达全局模式段模式段的统计数据局部模式控制站点本地站点分布查询的层次46/92 查询分解 将查询问题（SQL）转换成一个定义在全局关系上的关系代数表达式 需要从全局概念模式中获得转换所需要的信息 数据本地化 具体化全局关系上的查询，落实到合适的片段上的查询 即将全局关系上的关系代数表达式变换为相应片段上的关系代数表达式 全局优化 输入的是分片查询，优化目标是寻找一个近于最优的执行策略（操作次序）输出是一个优化
40、的、片段上的关系代数查询 局部优化 输入是局部模式 它由该站点上的DBMS进行优化3.2 分布式查询处理的层次结构分布式查询处理的层次结构3 3 分布式查询优化概述分布式查询优化概述47/92基本原理1.查询问题关系代数表达式2.分析得到查询树3.进行全局到片段的变换得到基于片段的查询树4.利用关系代数等价变换规则的优化算法，尽可能先执行选择和投影操作优化算法1.连接和合并尽可能上提（树根方向）2.选择和投影操作尽可能下移（叶子方向）4.1 基本原理和实现方法基本原理和实现方法4 4 基于关系代数等价变换的查询优化处理基于关系代数等价变换的查询优化处理48/92 实现步骤和方法 转换一：查询问
41、题关系代数表达式 转换二：关系代数表达式查询树 转换三：全局查询树分拆成片段查询树 优化：利用关系代数等价变换规则的优化算法，优化查询树，进而优化查询4.1 基本原理和实现方法基本原理和实现方法4 4 基于关系代数等价变换的查询优化处理基于关系代数等价变换的查询优化处理49/924.2 查询优化处理举例查询优化处理举例4 4 基于关系代数等价变换的查询优化处理基于关系代数等价变换的查询优化处理全局关系全局关系S(S#,SNAME,AGE,SEX)和和SC(S#,C#,GRADE)被水平分片被水平分片hh S SCS1:SEX=M男学生全体男学生全体S2:SEX=F女学生全体女学生全体SC1：C
42、#=20课程号课程号20课程号课程号20查询问题：查找至少有一门功课成绩在查询问题：查找至少有一门功课成绩在90分以上的男生姓名分以上的男生姓名SNAME(SEX=M and GRADE90(S.S#=SC.C#(SSC)50/924.2 查询优化处理举例查询优化处理举例4 4 基于关系代数等价变换的查询优化处理基于关系代数等价变换的查询优化处理SNAMES.S#=SC.S#S.S#=SC.S#S#,SNAMES#,SNAME GRADE90 GRADE90SNAME SEX=M S SC SEX=M U S1SEX=M S2SEX=F U SC1C#C20 SC1C#C20(a)全局关系上的
43、查询树全局关系上的查询树(b)对应片段上的查询树对应片段上的查询树 变换变换51/924.2 查询优化处理举例查询优化处理举例4 4 基于关系代数等价变换的查询优化处理基于关系代数等价变换的查询优化处理SNAMES.S#=SC.S#S.S#=SC.S#S#,SNAMES#,SNAME GRADE90SNAME SEX=MU SC1C#C20（c）把投影和选择下移后）把投影和选择下移后的查询树的查询树(d)一个简化一个简化的查询树的查询树产生矛盾去掉一支产生矛盾去掉一支S#,SNAME GRADE90 S2SEX=F SEX=M SC1C#C20 SC2C#C20 S1SEX=M SC2C#C2
44、0 S1SEX=MUUGRADE90GRADE9052/924.2 查询优化处理举例查询优化处理举例4 4 基于关系代数等价变换的查询优化处理基于关系代数等价变换的查询优化处理水平分片的查询优化的基本思想：水平分片的查询优化的基本思想：1.尽量把选择条件下移到分片的限定关系处尽量把选择条件下移到分片的限定关系处2.再把分片的限定关系与选择条件进行比较再把分片的限定关系与选择条件进行比较3.去掉它们之间存在矛盾的相应片断去掉它们之间存在矛盾的相应片断4.如果最后剩下一个水平片断，则重构全局关系的操作中，如果最后剩下一个水平片断，则重构全局关系的操作中，就可去掉就可去掉“并并”操作（至少可以减少操
45、作（至少可以减少“并并”操作的次数）操作的次数）53/924.2 查询优化处理举例查询优化处理举例4 4 基于关系代数等价变换的查询优化处理基于关系代数等价变换的查询优化处理全局关系全局关系EMP(EMP#,ENAME,SALARY,DEPT#,DNAME)垂直分片：垂直分片：E1(EMP#,DEPT#,DNAME)EMP2(EMP#,ENAME,SALARY)v SE1E2:查询问题：雇员的姓名和工资情况查询问题：雇员的姓名和工资情况ENAME,SALARY(EMP)54/924.2 查询优化处理举例查询优化处理举例4 4 基于关系代数等价变换的查询优化处理基于关系代数等价变换的查询优化处理
46、ENAME,SALARYENAMEEMP#,DEPT#,EMP#,ENAME,DEPTNAMESALARYENAME,SALARYEMP#,ENAME,SALARYENAME,SALARY EMPE2:EMP#,ENAME,SALARY去掉无关的片去掉无关的片段段 移植到片段上移植到片段上去掉连接去掉连接E1：E2：E1.EMP#=E2.EMP#55/924.2 查询优化处理举例查询优化处理举例4 4 基于关系代数等价变换的查询优化处理基于关系代数等价变换的查询优化处理垂直分片的查询优化的基本思想：垂直分片的查询优化的基本思想：1.把垂直分片所用到的属性集，与查询条件中的投影操作把垂直分片所用
47、到的属性集，与查询条件中的投影操作所涉及的属性相比较，去掉无关的垂直片断所涉及的属性相比较，去掉无关的垂直片断2.如果最后只剩下一个垂直片断与查询有关时，去掉重构如果最后只剩下一个垂直片断与查询有关时，去掉重构全局关系的全局关系的“连接连接”操作（至少可以减少操作（至少可以减少“连接连接”操作操作的次数）的次数）56/92 假定有两个关系R,S,在属性R.A=S.B上做半连接操作，可表示为：RA=B S=R(R A=B S)=R A=B(B(S)SA=B R=S(S A=B R)=S A=B(A(R)用半连接表示连接操作 RA=BS=(RA=B S)A=BS=（R A=B(B(S)A=BS R
48、A=BS=(SA=B R)A=BR=(S A=B(A(R)A=BR5.1 半连接操作半连接操作5 5 基于半连接算法的查询优化处理基于半连接算法的查询优化处理57/92例子1:R S AB 2a10 b25c30d25w 3x10 y15z32x A(R)=2,10,25,30R SSR=A C10 y25 wA=AA=AA CSR10 b25c AB58/92例子2：半连接简化 RSTRSTB=BC=CA=AR,S,T的循环连接图对R的充分简化R=R TS=S RT=T S减少一个元组59/92R=R TS=S RT=T S减两个元组R=R T=减少三个元组一般：简化程序长度随着关系的元组数
49、目增长线性增长。对R的另一个简化程序：R=R S T=T R S=S T （练习）60/925.2 半连接表示连接的代价估算半连接表示连接的代价估算5 5 基于半连接算法的查询优化处理基于半连接算法的查询优化处理RS网络网络 站点站点1 站点站点2 (1)(1)B B(S)(S)(3)R=R(3)R=RA=BA=BB B(S)(2)(S)(2)B B(S)(S)(4)R=R(4)R=RA=BA=B B B(S)(5)R(S)(5)RA=BA=BS SRA=BS=(RA=B S)A=BS=（R A=B(B(S)A=BS61/92 关系的概貌 Card(R)片段关系R的元组数目 Size(A)属性
50、A的大小(即字节数)Size(R)片段关系的大小,属性大小之和 Val(AR)属性A在R中出现的不同值的个数5.2 半连接表示连接的代价估算半连接表示连接的代价估算5 5 基于半连接算法的查询优化处理基于半连接算法的查询优化处理62/92 代数操作对关系概貌的影响 选择操作 S=F（R）Card(S)=*Card(R)Size(S)=Size(R)Val(BS)是Val(BR),Card(S),Card(R)的函数 并操作 T=RS Card(T)Card(R)+Card(S)Size(T)=Size(R)=Size(S)Val(AT)Val(AR)+Val(AS)5.2 半连接表示连接的代价
