1、第四章第四章4.14.1分布式数据库查询优化概述分布式数据库查询优化概述对于全局查询，如果子查询在不同的局部数对于全局查询，如果子查询在不同的局部数据库中没有相交，很显然可以使用局部数据据库中没有相交，很显然可以使用局部数据库的名称代替全局名称，也就是只要从局部库的名称代替全局名称，也就是只要从局部数据库中查询数据就行了，这就相当于缩小数据库中查询数据就行了，这就相当于缩小了查询范围，从而提高了优化效率。如果子了查询范围，从而提高了优化效率。如果子查询在不同的局部数据库中有相交，经过合查询在不同的局部数据库中有相交，经过合理的优化，可以减少中间结果，提高查询效理的优化，可以减少中间结果，提高查
2、询效率。率。4.14.1分布式数据库查询优化概述分布式数据库查询优化概述分布式数据库查询优化有二个标准：分布式数据库查询优化有二个标准：1.1.以查询总代价最小为标准以查询总代价最小为标准2.2.以查询的响应时间最短为标准以查询的响应时间最短为标准4.2 4.2 查询优化的基本概念查询优化的基本概念关系代数等价变化规则关系代数等价变化规则查询树查询树数据库参数数据库参数关系运算的特征参数关系运算的特征参数4.2.14.2.1关系代数等价变化规则关系代数等价变化规则关系代数有九种常见操作符：其中关系代数有九种常见操作符：其中2个一元个一元操作符，操作符，7个二元操作符。一元运算个二元操作符。一元
3、运算:选择选择()，投影，投影()；二元运算；二元运算:并并()，交，交()，差，差(-)，除，除()，笛卡儿积，笛卡儿积(x)，连接，连接()，半连接，半连接()。4.2.14.2.1关系代数等价变化规则关系代数等价变化规则设设R、S、T为关系，为关系，U、U1、U2为一元运算为一元运算符，符，B、B1、B2为二元运算符，则关系代数为二元运算符，则关系代数等价规则为：等价规则为：（1）U1U2R=U2U1R；（2）UR=UUR；（3）(UR)B(US)=U(RBS)；（4）RB(SBT)=(RBS)BT；（5）U(RBS)=(UR)B(US)。4.2.14.2.1关系代数等价变化规则关系代数
4、等价变化规则1.连接、笛卡儿积的交换律连接、笛卡儿积的交换律设设E1、E2是关系代数表达式，是关系代数表达式，F是连接是连接运算的条件，则以下等价公式成立：运算的条件，则以下等价公式成立：（1）E1E2=E2E1；（2）E1E2=E2E1；（3）E1FE2=E2FE1。4.2.14.2.1关系代数等价变化规则关系代数等价变化规则2.连接、笛卡儿积的结合律连接、笛卡儿积的结合律设设E1，E2、E3是关系代数表达式，是关系代数表达式，F1、F2是是连接条件，连接条件，F1只涉及到只涉及到E1和和E2的属性，的属性，F2只只涉及涉及E2和和E3的属性。则以下等价公式成立：的属性。则以下等价公式成立：
5、（1）(E1E2)E3=E1(E2E3)；（2）(E1F1E2)F2E3=E1F1(E2F2E3)；（3）(E1E2)E3=E1(E2E3)。4.2.14.2.1关系代数等价变化规则关系代数等价变化规则3.投影的串接投影的串接设设E是一个关系代数表达式，是一个关系代数表达式，A1、A2、An、B1、B2、Bm是是E中的某些中的某些属性名，属性名，AiB1、B2、Bm（i=1,2.,n），则以下等价公式），则以下等价公式成立：成立：A1、A2、An(B1、B2、Bm(E)=A1、A2、An(E)。4.2.14.2.1关系代数等价变化规则关系代数等价变化规则4.选择运算串接选择运算串接 设设E是一
6、个关系代数表达式，是一个关系代数表达式，F1和和F2是选择运算的条件。则以下等价公式成是选择运算的条件。则以下等价公式成立：立：F1(F2（E）)=(F1F2)(E)；由于由于F1F2F2F1，因此选择的交换，因此选择的交换律也成立，即：律也成立，即：F1(F2（E）)=F2(F1（E）)。4.2.14.2.1关系代数等价变化规则关系代数等价变化规则5.选择运算与投影运算的交换律选择运算与投影运算的交换律设设F只涉及只涉及L中属性，则以下等价公式成中属性，则以下等价公式成立：立：L(F(E)=F(L(E)；如果条件如果条件F还涉及不在还涉及不在L中的属性集中的属性集L1，那么下式成立：那么下式
7、成立：L(F(E)=L(F(LL1(E)。4.2.14.2.1关系代数等价变化规则关系代数等价变化规则6.选择运算与笛卡儿积的分配律选择运算与笛卡儿积的分配律（1）设）设F中涉及的属性都是中涉及的属性都是E1的属性则有以下等价的属性则有以下等价公式成立：公式成立：F(E1E2)=F(E1)E2；（2）如果）如果F=F1F2，且，且F1只涉及只涉及E1的属性，的属性，F2只涉只涉及及E2的属性，则有以下等价公式成立：的属性，则有以下等价公式成立：F(E1E2)=F1(E1)F2（E2）；）；（3）如果）如果F=F1F2，且，且F1只涉及只涉及E1的属性，的属性，F2涉及涉及E1和和E2的属性，则
8、有以下等价公式成立：的属性，则有以下等价公式成立：F(E1E2)=F2（F1(E1)E2）。）。4.2.14.2.1关系代数等价变化规则关系代数等价变化规则7.选择对并的分配律选择对并的分配律假设假设E1和和E2具有相同的属性名，或具有相同的属性名，或者者E1和和E2表达的关系的属性有对应表达的关系的属性有对应性，则有以下等价公式成立：性，则有以下等价公式成立：F(E1E2)=F(E1)F（E2）。）。4.2.14.2.1关系代数等价变化规则关系代数等价变化规则8.选择对集合差的选择对集合差的分配律分配律假设假设E1和和E2具有相同的属性名，或具有相同的属性名，或者者E1和和E2表达的关系的属
9、性有对应表达的关系的属性有对应性，则有以下等价公式成立：性，则有以下等价公式成立：F(E1E2)=F(E1)F(E2）。）。4.2.14.2.1关系代数等价变化规则关系代数等价变化规则9.选择对自然连接的分配律选择对自然连接的分配律假设假设F只涉及表达式只涉及表达式E1和和E2的公共属的公共属性，且包含连接属性，则有以下等性，且包含连接属性，则有以下等价公式成立：价公式成立：F(E1E2)=F(E1)F(E2）。）。4.2.14.2.1关系代数等价变化规则关系代数等价变化规则10.投影对笛卡儿积的分配律投影对笛卡儿积的分配律假假L1是是E1的属性集的属性集L2是是E2的属性的属性集，则有以下等
10、价公式成立：集，则有以下等价公式成立：L1L2(E1E2)=L1(E1)L2（E2）。）。4.2.14.2.1关系代数等价变化规则关系代数等价变化规则11.投影对并的分配律投影对并的分配律假设假设E1和和E2具有相同的属性名或具有相同的属性名或者者E1和和E2表达的关系的属性有对应表达的关系的属性有对应性，则有以下等价公式成立：性，则有以下等价公式成立：L(E1E2)=L(E1)L（E2）。）。4.2.14.2.1关系代数等价变化规则关系代数等价变化规则12.选择与连接操作的结合选择与连接操作的结合设设E1、E2、E3是关系代数表达式，是关系代数表达式，F、F1、F2是条件，则有以下等价公是条
11、件，则有以下等价公式成立：式成立：F(E1E2)=E1FE2；F1(E1F2E2)=E1F1F2E2。4.2.14.2.1关系代数等价变化规则关系代数等价变化规则13.并和交的交换律并和交的交换律假设假设E1和和E2具有相同的属性名或具有相同的属性名或者者E1和和E2表达的关系的属性有对应表达的关系的属性有对应性，则有以下等价公式成立：性，则有以下等价公式成立：E1E2=E2E1；E1E2=E2E1。4.2.14.2.1关系代数等价变化规则关系代数等价变化规则14.并和交的结合律并和交的结合律假设假设E1、E2、E3具有相同的属性名，具有相同的属性名，或者或者E1、E2、E3表达的关系的属性表
12、达的关系的属性有对应性，则有以下等价公式成立：有对应性，则有以下等价公式成立：(E1E2)E3=E1(E2)E3)；(E1E2)E3=E1(E2)E3)。4.2.24.2.2查询树查询树所谓查询树，是指一个查询的关系代数表达式，所谓查询树，是指一个查询的关系代数表达式，按其运算的先后顺序用树状结构来加以表示。按其运算的先后顺序用树状结构来加以表示。查询树定义如下：查询树定义如下：ROOT:=TT:=R/T/TBT/UTU:=F/LB:=/其中其中R是关系，是关系，F是选择条件，是选择条件，L是的属性集。是的属性集。4.2.24.2.2查询树查询树关系代数的操作关系代数的操作、和和与查询树的对应
13、关与查询树的对应关系如下：系如下：关系代数操作关系代数操作查询树查询树 关系代数操作关系代数操作查询树查询树4.2.24.2.2查询树查询树关系代数的操作关系代数的操作、和和与查询树的对应关与查询树的对应关系如下：系如下：关系代数操作关系代数操作查询树查询树 关系代数操作关系代数操作查询树查询树4.2.24.2.2查询树查询树例例4.3设有一个学生关系设有一个学生关系STUDENT（SNO,SNAME,BIRTH,SORE,DNO,COLLEGE），其中），其中SNO为学生学号，为学生学号，SNAME为为学生姓名，学生姓名，BIRTH为生日，为生日，SORE为所选课程总为所选课程总成绩，成绩，
14、DNO为学生所在学院编号，为学生所在学院编号，COLLEGE为为学院名称。有一学生选课关系表学院名称。有一学生选课关系表COURSE（CNO,CNAME,CSORE,SNO），其中），其中CNO为课程代码，为课程代码，CNAME为课程名称，为课程名称，CSORE课程成绩，课程成绩，SNO为选课学生学号。要求查找所有为选课学生学号。要求查找所有选修了选修了“分布式数据库原理分布式数据库原理”课程的学号及姓名。课程的学号及姓名。4.2.24.2.2查询树查询树可以用下面的关系代数表达式表示查询：可以用下面的关系代数表达式表示查询：QQ：SNO,SNAMESNO,SNAME CNAME=”CNAME
15、=”分布式数据库原理分布式数据库原理分布式数据库原理分布式数据库原理”(STUDENTCOURSE)(STUDENTCOURSE)对应于这个表达式，可用下图所示的查询树表示：对应于这个表达式，可用下图所示的查询树表示：对应于这个表达式，可用下图所示的查询树表示：对应于这个表达式，可用下图所示的查询树表示：4.2.3 4.2.3 数据库参数数据库参数对于一个给定的关系对于一个给定的关系R，常用的数据库参数，常用的数据库参数包括：包括：（1）关系的基数：指关系）关系的基数：指关系R包含的元组个数，包含的元组个数，记为记为Card(R)；（2）属性的长度：指关系）属性的长度：指关系R中属性中属性A的
16、取值的取值所占用的平均字节数，记为所占用的平均字节数，记为Length(A)；（3）元组的长度：指关系）元组的长度：指关系R中每个元组占用中每个元组占用的平均字节数，记为的平均字节数，记为Length(R)，这里有，这里有Length(R)=Length(Ai)；4.2.3 4.2.3 数据库参数数据库参数（4）关系的大小：指关系）关系的大小：指关系R中所有元组包含中所有元组包含的字节数，记为的字节数，记为Size(R)，这里有，这里有Size(R)=Card(R)*Length(R)；（5）关系的块数：指包含关系）关系的块数：指包含关系R中所有元组中所有元组所需的内存块的数量，记为所需的内存
17、块的数量，记为Block(R)；（6）属性不同值：指关系）属性不同值：指关系R中属性中属性A在所有在所有元组中不同属性值的个数，记为元组中不同属性值的个数，记为Val(R,A)；4.2.3 4.2.3 数据库参数数据库参数（7）属性的值域：指关系）属性的值域：指关系R中属性中属性A的取值的取值范围，记为范围，记为Dom(A)；（8）属性）属性A的最大值和最小值：指关系的最大值和最小值：指关系R中中属性属性A的所有元组取得的最大值和最小值，的所有元组取得的最大值和最小值，记为记为Max(A)和和Min(A)。4.2.44.2.4关系运算的特征参数关系运算的特征参数令令S表示对关系表示对关系R执行
18、一元运算的结果，令执行一元运算的结果，令T表示对两个关系表示对两个关系R和和S进行某种二元运算的结进行某种二元运算的结果。果。1.选择运算选择运算()1）基数）基数Card(S)=Card(R)=1/Val(R,A)2）元组的长度）元组的长度Length(S)=Length(R)4.2.44.2.4关系运算的特征参数关系运算的特征参数3）属性不同值）属性不同值在选择运算中，对结果关系中属性不同值的在选择运算中，对结果关系中属性不同值的估计可以分为属性估计可以分为属性B属于选择谓词和不属于属于选择谓词和不属于选择谓词两种情况考虑。选择谓词两种情况考虑。当属性当属性B属于选择谓词时，如果选择条件中
19、属于选择谓词时，如果选择条件中有条件等式有条件等式B=X（X为属性值），则其不同为属性值），则其不同值的数量为：值的数量为：Val(S,B)=1；4.2.44.2.4关系运算的特征参数关系运算的特征参数当属性当属性B属于选择谓词时，如果选择条件中属于选择谓词时，如果选择条件中属性属性B的条件为不等式；或的条件为不等式；或B与选择谓词相关与选择谓词相关且为关键词，则在属性均匀分布的假设下，且为关键词，则在属性均匀分布的假设下，不同值的数量与选择率成正比，即有：不同值的数量与选择率成正比，即有：Val(S,B)=Val(R,B)；当属性当属性B不属于选择谓词时，假设不属于选择谓词时，假设B是均匀分
20、是均匀分布的，在这种情况下对结果关系中属性布的，在这种情况下对结果关系中属性B不不同值的近似值估计方法如下：同值的近似值估计方法如下：4.2.44.2.4关系运算的特征参数关系运算的特征参数 当当Card(S)Val(R,B)/2时，时，Val(S,B)=Card(S)；当当Val(R,B)/2Card(S)2 Val(R,B)时，时，Val(S,B)=（Card(S)+Val(R,B)/3;当当Card(S)2Val(R,B)时时,Val(S,B)=Val(R,B)。4.2.44.2.4关系运算的特征参数关系运算的特征参数2.投影运算投影运算()1）基数）基数投影运算影响操作数的基数，对于一
21、个关系投影运算影响操作数的基数，对于一个关系R进行投进行投影运算后，在所得的结果关系影运算后，在所得的结果关系S中，可能出现重复的中，可能出现重复的元组，而根据关系的性质，这些重复的元组应被删除。元组，而根据关系的性质，这些重复的元组应被删除。所以，投影运算会影响操作数的基数，即通常所以，投影运算会影响操作数的基数，即通常Card(S)不等于不等于Card(R)，但是，要对这个影响做出估，但是，要对这个影响做出估算是困难的，一般可用下列三条准则：算是困难的，一般可用下列三条准则：（1）如果投影只涉及单个属性）如果投影只涉及单个属性A，则令，则令Card(S)=Val(R,A)；4.2.44.2
22、.4关系运算的特征参数关系运算的特征参数2.投影运算投影运算()1）基数）基数 （2）如果所有投影属性的不同值）如果所有投影属性的不同值VAL(R,Ai)乘积乘积即：即：VAL(R,A1)VAL(R,A2)VAL(R,An)Card(R)，其中其中Attr(S)是投影结果中的属性，是投影结果中的属性，AiAttr(S)，则令，则令Card(S)=VAL(R,A1)VAL(R,A2)VAL(R，An)；（3）如果投影包含）如果投影包含R的一个关键字，则令的一个关键字，则令Card(S)=Card(R)；4.2.44.2.4关系运算的特征参数关系运算的特征参数2.投影运算投影运算()2）元组的长度
23、）元组的长度 投影结果的长度被缩短成投影属性长度之和投影结果的长度被缩短成投影属性长度之和,即：即：Length(S)=Length(Ai)，其中，其中Ai为投影属性。为投影属性。3）属性不同值）属性不同值投影属性的不同值的数量和操作数关系中不同值投影属性的不同值的数量和操作数关系中不同值的数量相同，即：的数量相同，即：Val(S,A)=Val(R,A)。4.2.44.2.4关系运算的特征参数关系运算的特征参数3.并运算并运算1）基数）基数Card(T)Card(R)+Card(S)。2）元组的长度）元组的长度Length(T)=Length(R)=Length(S)，这是因为并运算，这是因为
24、并运算只能运用于具有相同属性模式的关系。只能运用于具有相同属性模式的关系。3）属性的不同值）属性的不同值Val(T,A)Val(R,A)+Val(S,A)。4.2.44.2.4关系运算的特征参数关系运算的特征参数4.差运算差运算1）基数）基数Max（0，Card(R)-Card(S)）Card(T)Card(R)；2）元组的长度）元组的长度Length(T)=Length(R)=Length(S)；同样，差运算只能运用于具有相同属性模式的关系。同样，差运算只能运用于具有相同属性模式的关系。3）属性不同值）属性不同值Val(T,A)Val(R,A)4.2.44.2.4关系运算的特征参数关系运算的
25、特征参数5.笛卡尔积运算笛卡尔积运算1）基数）基数Card(T)=Card(R)Card(S)。2）元组的长度）元组的长度Length(T)=Length(R)+Length(S)。3）属性的不同值）属性的不同值属性的不同值与操作数关系相应属性的不同值相等，属性的不同值与操作数关系相应属性的不同值相等，即：即：当当AAttr(R)时，时，Val(T,A)=Val(R,A)；当；当AAttr(S)时，时，Val(T,A)=Val(S,A)。4.2.44.2.4关系运算的特征参数关系运算的特征参数6.连接运算连接运算1）基数）基数对于关系对于关系R和和S，假设满足以下条件，假设满足以下条件:（1）
26、对于具有相同属性）对于具有相同属性A的两个关系的两个关系R和和S，且，且Val(R,A)Val(S,A)，即，即R中属性中属性A的每个取值都在的每个取值都在S中中出现；出现；（2）对于不是关系）对于不是关系R与关系与关系S连接属性的属性连接属性的属性B，在，在连接后不会丢失属性值；连接后不会丢失属性值；（3）属性的不同值均匀的分布在关系）属性的不同值均匀的分布在关系R和和S中。中。4.2.44.2.4关系运算的特征参数关系运算的特征参数基于以上的假设，自然连接基数近似估计为：基于以上的假设，自然连接基数近似估计为：基于以上的假设，自然连接基数近似估计为：基于以上的假设，自然连接基数近似估计为：
27、Card(T)=Card(R)Card(S)/Max(Val(R,A),ValS,A)Card(T)=Card(R)Card(S)/Max(Val(R,A),ValS,A)。2)2)元组的长度元组的长度元组的长度元组的长度Length(T)=Length(R)+Length(S)-Length(A)Length(T)=Length(R)+Length(S)-Length(A)。3 3）属性不同值）属性不同值）属性不同值）属性不同值如果如果如果如果A A是一个连接属性，则有：是一个连接属性，则有：是一个连接属性，则有：是一个连接属性，则有：Val(T,A)=min(Val(R,A),Val(T,
28、A)=min(Val(R,A),Val(S,A)Val(S,A)；如果如果如果如果A A为关系为关系为关系为关系R R中不是用于连接的属性，则有：中不是用于连接的属性，则有：中不是用于连接的属性，则有：中不是用于连接的属性，则有：Val(T,A)Val(R,A)Val(T,A)Val(R,A)；如果如果如果如果A A为关系为关系为关系为关系S S中不是用于连接的属性，则有：中不是用于连接的属性，则有：中不是用于连接的属性，则有：中不是用于连接的属性，则有：Val(T,A)Val(S,A)Val(T,A)Val(S,A)。4.2.44.2.4关系运算的特征参数关系运算的特征参数7.半连接运算半连
29、接运算1）基数）基数 令令表示半连接运算的选择率，它用于度量表示半连接运算的选择率，它用于度量R中元组选择到结果关系中元组选择到结果关系T的比例，并可由下的比例，并可由下式估算：式估算：=Val(S,A)/Val(dom(A)其中其中Val（dom(A)）表示在属性）表示在属性A的域值集的域值集合中不同值的数目。给定合中不同值的数目。给定，便可确定便可确定Card(T)的值为：的值为：Card(T)=Card(R)；4.2.44.2.4关系运算的特征参数关系运算的特征参数2）元组的长度）元组的长度 半连接运算结果的长度和它的第一个操作数半连接运算结果的长度和它的第一个操作数的长度相同，即：的长
30、度相同，即：Length(T)=Length(R)。3）属性不同值）属性不同值如果属性如果属性A不属于半连接属性，假设该属性不属于半连接属性，假设该属性独立于半连接属性且均匀分布假设成立，则独立于半连接属性且均匀分布假设成立，则属性不同值的数量如下：属性不同值的数量如下：4.2.44.2.4关系运算的特征参数关系运算的特征参数当当Card(T)Val(R,A)/2时，时，Val(T,A)=Card(T)；当当Val(R,A)/2Card(T)600 OR score600score600）（college=”计算机计算机”score600)和和STUDENT12(SORE600)两个数据模式，
31、最终形两个数据模式，最终形成成STUDENT11(SORE600)、STUDENT12(SORE600)、STUDENT2(SNO,DNO,COLLEGE)三个局部数据模式三个局部数据模式。4.84.8综合应用案例分析综合应用案例分析要求查找所有选修了要求查找所有选修了”分布式数据原理分布式数据原理”课程且学生所有课程总成绩课程且学生所有课程总成绩600的学的学号及姓名。即查询为：号及姓名。即查询为：SELSECT SNO,SNAME FORM STUDENT,COURSE WHERE COURSE.CNAME=”分布式数据库原分布式数据库原理理”AND STUDENT.SORE600 AND STUDENT.SNO=COURSE.SNO4.84.8综合应用案例分析综合应用案例分析（1）将查询问题转换成关系代数）将查询问题转换成关系代数表达表达式：式：SNO,SNAMECNAME=”分布式数据库原理分布式数据库原理”AND SORE600(STUDENTCOURSE)4.84.8综合应用案例分析综合应用案例分析（2）将关系代数表达式变换到查询）将关系代数表达式变换到查询树树4.84.8综合应用案例分析综合应用案例分析（3）从全局查询到片段查询的变换）从全局查询到片段查询的变换4.84.8综合应用案例分析综合应用案例分析优化后的查询树如图优化后的查询树如图4-25所所示：示：
