分布式数据库系统及其应用.

Presentation on theme: "分布式数据库系统及其应用."— Presentation transcript:

1 分布式数据库系统及其应用

2 第3章 分布式数据库中的查询处理和优化 分布式查询优化概述 分布式查询优化基础知识 分布式查询分类和层次结构
基于关系代数等价变换的查询优化处理 基于半连接算法的查询优化处理 基于直接连接算法的查询优化处理 直接连接操作的常用策略

3 查询处理问题 集中式 分布式 查询转换为代数表达式 从所有等价表达式中选择最优的代数表达式 除了集中式问题外，还有 站点之间交换数据的操作
1.1 分布式查询优化的目标 1 分布式查询优化概述 查询处理问题 集中式 查询转换为代数表达式 从所有等价表达式中选择最优的代数表达式 分布式 除了集中式问题外，还有 站点之间交换数据的操作 选择最优的执行站点(分布） 数据被传送的方式

4 1 分布式查询优化概述 1.1 分布式查询优化的目标 CPU代价（相对固定） 集中式 I/O代价（可变的，优化的目标） 总代价最小
主要标准 辅助标准 I/O代价（访问磁盘） 分布式 目标 通讯代价 响应时间最短 数据的分布和冗余增加了查询的并行处理的可能性，从而可以缩减查询处理的响应时间

5 1 分布式查询优化概述 1.2 分布式查询优化准则和代价分析 准则：
使得通讯费用最低和响应时间最短，即以最小的总代价，在最短的响应时间内获得需要的数据。 通讯费用与所传输的数据量和通信次数有关 响应时间和通信时间有关，也与局部处理时间有关 查询代价分析 远程通讯网络 局部处理时间可以忽略不计，减少通讯代价是主要目标 高速局域网 传输时间比局部处理时间要短很多，以响应时间作为优化目标，局部处理时间是关键

6 例子 S(s#, sname, age, sex) 104 元组 Site A
1.3 分布式查询策略的重要性 1 分布式查询优化概述 例子 S(s#, sname, age, sex) 元组 Site A C(c#, cname, teacher) 元组 Site B SC(s#, c#, grade) 元组 Site A 每个元组长度100Bit, 通讯传输速度 104 bit/sec, 通讯延迟 1sec S, SC C Site A Site B

7 查询: 所有选修maths 课的男生学号和姓名. SELECT s#, sname FROM S, C, SC
1.3 分布式查询策略的重要性 1 分布式查询优化概述 查询: 所有选修maths 课的男生学号和姓名. SELECT s#, sname FROM S, C, SC WHERE S.s#=SC.s# AND C.c#=SC.c# AND sex=‘男’ AND cname=‘maths’;

8 代价公式 QC = I/O 代价 + CPU 代价 + 通讯代价 通讯代价 TC = 传输延迟时间C0
1.3 分布式查询策略的重要性 1 分布式查询优化概述 代价公式 QC = I/O 代价 + CPU 代价 + 通讯代价 通讯代价 TC = 传输延迟时间C0 + (传输数据量X * 数据传输速率C1)

9 六种查询策略 策略 1 : 3 1.3 分布式查询策略的重要性 1 分布式查询优化概述 S, SC C A B A 传 C B 把关系 C
传输到 地 ,在 地处理查询 ○ T1 = 1 + (10**5 * 100 / 10**4) S , SC 通信 次 ≈ 10**3 秒 16.7 分钟 ,S C B 和 B 在 T2 = 2+(10**4+10**6) * 100 / 10**4 2 10100 28 小时 问 10**5 B 先在 地求出男学生的成绩元组有 10**5 再根据 C# 的值询问 ,核实是否C=‘MATHS’ 答 10**5 C T3 (2 * 10**5 *1)=2*10**5 2.3 天 3

10 六种查询策略 策略 4： 1.3 分布式查询策略的重要性 1 分布式查询优化概述 S, SC C A B A 问 10 B 先在 地求出 ‘
MATHS ’的元组,有 个 ○ 再根据 C# 的值询问 地的 S ， SC 的连接， , 答 C 核实是否为选修 ’ 的男生 T4 ≈ (2 * 10 * 1) = 20 秒 传输 10**5 地求出男生选课元组，有 再把结果传输到 地 在 地执行查询， 通信 1 次 T5 = 1 + (10**5 * 100) / 10**4 1000 16.7 分 地求出为 ’的元组，有 T6 = 1 + (10 * 100) / 10**4 策略 4： 策略 5： 策略 6：

11 2 分布式查询优化中的基础知识 2.1 关系代数知识回顾 相关表述记号
⒈ 设关系模式为R(A1, A2, …, An)。它的一个关系设为R。 t∈R表示t是R的一个元组。t[Ai]则表示元组t中相应于属性Ai的一个分量 。 ⒉ 若A={Ai1, Ai2, …, Aik}，其中Ai1, Ai2, …, Aik是A1, A2, …, An中的一部分， 则A称为属性列或域列。 t[A]=(t[Ai1], t[Ai2], …, t[Aik])表示元组 t 在属性 列A上诸分量的集合。则 表示{A1, A2, …, An}中去掉 {Ai1, Ai2, …, Aik} 后剩余的属性组。 A

12 2 分布式查询优化中的基础知识 2.1 关系代数知识回顾 ⌒ 相关表述记号
⒊ R为n目关系，S为m目关系。tr∈R ，ts∈S。 trts 称为元组的连接。 它是一个(n+m)列的元组，前n个分量为R中的一个n元组，后m个分量 为S中的一个m元组。 ⌒ ⒋ 给定一个关系R(X,Z)，X和Z为属性组。我们定义，当t[X]=x时，x在R中 的象集（Images Set）为： Zx={ t[Z]|t∈R, t[X]=x } 它表示R中属性组X上值为x的诸元组在Z上分量的集合。

13 2 分布式查询优化中的基础知识 2.1 关系代数知识回顾 传统的集合运算 并运算
设关系R和关系S具有相同的目n（即两个关系都有n个属性），且相应 的属性取自同一个域，则关系R与关系S的并由属于R或属于S的元组组成。 其结果关系仍为n目关系。记作： R∪S={ t | t∈R∨t∈S } c1 b2 a2 c2 a1 b1 C B A b3 R1 R2 c1 b1 a1 b2 a2 c2 b3 C B A R1∪R2

14 2 分布式查询优化中的基础知识 2.1 关系代数知识回顾 ∈ 传统的集合运算 差运算
设关系R和关系S具有相同的目n，且相应的属性取自同一个域，则关系R与关系S的差由属于R而不属于S的所有元组组成。其结果关系仍为n目关系。记作： R－S={t|t∈R∧t S} ∈ c1 b2 a2 c2 a1 b1 C B A b3 R1 R2 c1 b1 a1 C B A R1－R2

15 2 分布式查询优化中的基础知识 2.1 关系代数知识回顾 传统的集合运算 交运算 设关系R和关系S具有相同的目n，且相应的属性取自同一个域，
则关系R与关系S的交由既属于R又属于S的元组组成。其结果关系仍 为n目关系。记作： R∩S={t|t∈R∧t∈S} R1∩R2 c1 b2 a2 c2 a1 b1 C B A b3 R1 R2 A B C a1 b2 c2 a2 c1

16 2 分布式查询优化中的基础知识 2.1 关系代数知识回顾 广义笛卡尔积
两个分别为n目和m目的关系R和S的广义笛卡尔积是一个(n+m)列的元组 的集合。元组的前n列是关系R的一个元组，后m列是关系S的一个元组。若 R有k1个元组，S有k2个元组，则关系R和关系S的广义笛卡尔积有 k1×k2个元组。记作： R1×R2 c1 b1 a1 C B A b2 a2 c2 b3 .. c1 b2 a2 c2 a1 b1 C B A b3 R1 R2

17 2 分布式查询优化中的基础知识 2.1 关系代数知识回顾 专门的关系运算 S(S#,SN,SD,SA) 学号 学生姓名 所属系名 学生年龄
学号 学生姓名 所属系名 学生年龄 S# SN SD SA S A CS S B CS S C MA S D CI S E MA S F CS

18 σF (R) ={ t | t ∈R Λ F(t)=‘真’ }
选择运算 在关系R中选择满足给定条件的元组，记做： σF (R) ={ t | t ∈R Λ F(t)=‘真’ } F是一个公式，表示形式为由逻辑运算符（∧,∨,٦)连接各算术表达式组成。 算术表达式的基本形式为：XθY. θ ={>, ≥ ,<, ≤ ,=, ≠} 。 选择运算是从关系中选取使公式为真的元组。这是从行的角度进行的运算。 例1 求计算机科学系CS的学生 σ SD=‘CS’ (S) 学号 学生姓名 所属系名 学生年龄 S# SN SD SA S A CS S B CS S C MA S D CI S E MA S F CS (a) (S) σ SD=‘CS’ (S) (S’) S# SN SD SA S A CS S B CS S F CS

19 σ SD=‘CS’ ∧SA≤21 (S) σF (R) ={ t | t ∈R Λ F(t)=‘真’ } σ SD=‘CS’ (S)
选择运算 在关系R中选择满足给定条件的元组，记做： σF (R) ={ t | t ∈R Λ F(t)=‘真’ } 例2 求计算机科学系CS，年龄不超过21岁的学生。 σ SD=‘CS’ ∧SA≤21 (S) (S’) S# SN SD SA S A CS S B CS S F CS σ SD=‘CS’ (S) 学号 学生姓名 所属系名 学生年龄 S# SN SD SA S A CS S B CS S C MA S D CI S E MA S F CS (S) (S’) S# SN SD SA S A CS S B CS

20 πA (R) ={ t[A] | t ∈R} 投影运算 关系R上的投影是从R中选择若干属性列组成新的关系。记做：
投影之后不仅取消了某些列，还可能取消某些元组。 这是从列的角度进行的运算。 例3 πSN,SD (S) 即求得学生关系S在学生姓名和所在系这两个属性上的投影结果。 学号 学生姓名 所属系名 学生年龄 S# SN SD SA S A CS S B CS S C MA S D CI S E MA S F CS (a) (S) πSN,SD (S) πSA (S) SA 20 21 19 22 SN SD A CS B CS C MA D CI E MA F CS

21 ∞ F 连接运算（θ连接） 连接运算是从两个关系的笛卡尔积中选取属性间满足一定条件的元组。
记做: R S. 其中，F是条件表达式，它涉及到对两个关系中的属性的比较。 ∞ F 例4 设关系R、S如下图： R S ∞ C<E R S ∞ C<E R S 2 b5 b3 10 7 b2 3 b1 E B 10 b3 8 a2 6 b2 a1 7 5 b1 E S.B C R.B A 12 b4 a2 8 b3 6 b2 a1 5 b1 C B A

22 连接运算中有两种最为重要也最为常用的连接，
等值连接 连接运算中有两种最为重要也最为常用的连接， θ为“＝”的连接运算称为等值连接: 例5 设关系R、S如下图： 2 b5 b3 10 7 b2 3 b1 E B S R A R.B C S.B E a1 b b a1 b b a2 b b a2 b b R S ∞ R.B=S.B A B C a1 b1 5 a1 b2 6 a2 b3 8 a2 b4 12

23 另一种是自然连接。自然连接是一种特殊的等值连接，它要求两个 关系中进行比较的分量必须是相同的属性组，并且要在结果中把重复的 属性去掉。
例6 关系R、S的自然连结： R S ∞ A R.B C S.B E a1 b b a1 b b a2 b b a2 b b R S ∞ R.B=S.B A B C E a1 b a1 b a2 b a2 b R S ∞

24 半连接 在R、S自然连接后仅保留对R的属性的投影，记为：R ∝ S 例7 关系R、S的半连接： A B C E a1 b a1 b a2 b a2 b R S ∞ 2 b5 b3 10 7 b2 3 b1 E B S R 12 b4 a2 8 b3 6 b2 a1 5 b1 C B A A B C a1 b a1 b a2 b R ∝ S

25 在R、S自然连接时对不匹配的元组用空值来匹配。有左外连接、右外连接和全外连接之分
则S用空元组与之对应。R的信息在左外连接的结果中都得到保留。 例8 关系EMP、SAL的左外连结： SAL EMP 上海 邓平 长春 李宏 大连 王小 北京 张丽 CITY ENAME 3000 赵刚 5000 6000 SALARY NULL 5000 6000 SALARY 上海 邓平 长春 李宏 大连 王小 北京 张丽 CITY ENAME EMP SAL

26 右外连结: 对S中任意元组，若R中找不到匹配的元组， 则R用空元组与之对应。S的信息在右外连接的结果中都得到保留。
例9 关系EMP、SAL的右外连结： SAL EMP 上海 邓平 长春 李宏 大连 王小 北京 张丽 CITY ENAME 3000 赵刚 5000 6000 SALARY EMP SAL ENAME CITY SALARY 张丽 北京 6000 王小 大连 5000 赵刚 NULL 3000

27 全外连接: 对R或S中所有不匹配的元组，均用空元组分 别匹配。R、S的信息在全外连接的结果中都得到保留。
例10 关系EMP、SAL的全外连结： EMP SAL SAL EMP 上海 邓平 长春 李宏 大连 王小 北京 张丽 CITY ENAME 3000 赵刚 5000 6000 SALARY ENAME CITY SALARY 张丽 北京 6000 王小 大连 5000 李宏 长春 NULL 邓平 上海 赵刚 3000

28 除运算 给定关系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上投影的集合。记作： R÷S = { tｒ[X] | tｒ∈R ∧ Yx ΠY(S) } 其中Yx为x在R中的象集，x=tｒ[X]。 c1 b2 a1 c3 a2 c6 b6 a4 b4 a3 c7 b3 c2 b1 C B A R d2 d1 D S 例 11 Z X Y

29 除运算 R÷S = { tｒ[X] | tｒ∈R ∧ Yx ΠY(S) } a1的象集为： a2的象集为： a3的象集为： a4的象集为： {（b1,c2），（b2,c3），（b2,c1）} {（b3,c7），（b2,c3）} {（b4,c6）} {（b6,c6）} c1 b2 a1 c3 a2 c6 b6 a4 b4 a3 c7 b3 c2 b1 C B A d2 d1 D R S S在B、C上的投影 R÷S＝{ a1} {（b1,c2），（b2,c3），（b2,c1）}

30 πS# ,GRADE(σ C# =‘C2’ (SC))
关系代数表达式 设教学数据库中有三个关系： 学生关系S（S#，SNAME，SD， AGE ） 课程关系C（C#，CN, CP#） 学习关系SC（S#，C#，GRADE） 例1 检索学习课程号为C2的学生学号与成绩 σ C# =‘C2’ (SC) 学号 课程号 学习成绩 S# C# GRADE S C A S C A S C A S C B S C B S C C S C C S C B SC 学号 课程号 学习成绩 S# C# GRADE S C A S C C S C B πS# ,GRADE(σ C# =‘C2’ (SC))

31 ＝ πS# ,SNAME(S ∞ C# =‘C2’ SC) πS# ,SNAME(σ C# =‘C2’ ( S ∞ SC ))
学号 课程号 学习成绩 S# C# GRADE S C A S C A S C A S C B S C B S C C SC 学号 学生姓名 所属系名 学生年龄 S# SNAME SD SA S A CS S B CS S C MA S D CI S E MA S S SC ∞ σ C# =‘C2’( ) S SC ∞ 学号 学生姓名 所属系名 学生年龄 课程号 学习成绩 S# SNAME SD SA C# GRADE S A CS C A S A CS C A S A CS C A S A CS C A S B CS C B S B CS C C S# SNAME S A S B ＝ πS# ,SNAME(σ C# =‘C2’ ( S ∞ SC )) πS# ,SNAME(S ∞ C# =‘C2’ SC)

32 πSN ,SD( (σCN=‘数据库原理’(C)) )
例3 求选修《数据库原理》这门课程的学生名和所在系。 （ S、C、SC ） πSN ,SD( (σCN=‘数据库原理’(C)) ) S ∞ SC ∞ 例4 检索学习课程号为C2或C3的学生学号和所在系 学号 学生姓名 所属系名 学生年龄 S# SNAME SD SA S A CS S B CS S C MA S D CI S E MA S 学号 课程号 学习成绩 S# C# GRADE S C A S C A S C A S C B S C B S C C SC πS# ,SD( s ∞ πS# (σC# =‘C2’∨C#=‘C3’(SC)) )

33 πSN( S ∞ (πS#, C# (SC) ÷K))
例5 求至少选修C2和C3这两门课程的学生名。 C# C2 C3 K πSN( S ∞ (πS#, C# (SC) ÷K)) πSN( S ∞ (πS#, C# (SC) ÷ πC# (σC# =‘C2’∨C#=‘C3’(C)))

34 × √ πS#(SC)－πS# (σC# =‘C2’ (SC)) πS#(S)－πS# (σC# =‘C2’ (SC))
例7 求选修全部课程的学生名。 πSN ( S ∞ (πC#,S# (SC) ÷ C) ) 例8 求至少选修了学生编号为S2 所选课程的学生名。 K ＝πC# (σS#=‘S2’(SC)) πSN ( S ∞ (πC#,S# (SC) ÷ πC# (σS#=‘S2’(SC))))

35 sname(s.s#=SC.s# and SC.c#=‘c03’(S×SC))
2.1 用关系代数和SQL语句表示一个查询 2 分布式查询优化中的基础知识 关系代数基本操作： 并（∪）、交（∩）、笛卡尔积（ × ）、选择（ ）、投影（ ） 关系代数导出操作： 差（－）、除（÷）、 θ连接（ ∞ θ ）、自然连接（∞）、半连接（∝） 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’(S×SC))

36 sname(s.s#=SC.s# (S ×  SC.c#=‘c03’ SC))
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)

37 sname  s.s# = sc.s# s.s# = sc.s#c# =‘c03’ 2 分布式查询优化中的基础知识 2.2 查询树
叶子表示已知关系 节点表示一个一元或二元操作符 树根表示查询结果 2.2 查询树 2 分布式查询优化中的基础知识 sname s.s# = sc.s#c# =‘c03’  S SC  s.s# = sc.s# S c#=‘c03’ SC ∞ S  c# =‘c03’ (a)对于E1的查询树 (b)对于E2的查询树 (c)对于E3的查询树

38 一元操作：只涉及一个操作对象 二元操作：涉及两个操作对象  (SL),  (PJ)
2.3 等价变换规则的概念和术语 2 分布式查询优化中的基础知识 一元操作：只涉及一个操作对象  (SL),  (PJ) 二元操作：涉及两个操作对象 ∪ (UN), ∩（） , － (DF), × (CP), ∞θ（），∞ (JN), ∝ (SJ),

39 R  Ø = R R  Ø = Ø R ∞ Ø = Ø Ø ∝ R = Ø
2.3 等价变换规则的概念和术语 2 分布式查询优化中的基础知识 等价变换规则 空值的变换 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的属性

40 交换率 2 分布式查询优化中的基础知识 2.3 等价变换规则的概念和术语 1 (2 (R)) = 2 (1 (R)) 条件:
1 2 是 选择操作 时总成立 1 2 是 投影操作 时要求其属性集合相等 1 与 2 是投影和选择操作时:  A1,…An( F(R)) =  F ( A1,…An (R)) 的条件是 F中的属性是 A1, …. An 的子集 R ∞ S = S ∞ R R × S = S × R R  S = S  R R  S = S  R R ∝ S  S ∝ R R - S  S - R

41 结合率 R B ( S B T ) = (R B S) B T) B: 二元操作 ∞（JN）, ×（CP）, ∪（UN）, 等总成立
2.3 等价变换规则的概念和术语 2 分布式查询优化中的基础知识 结合率 R B ( S B T ) = (R B S) B T) B: 二元操作 ∞（JN）, ×（CP）, ∪（UN）, 等总成立 ∝（SJ） 有问题

42 分配率 2 分布式查询优化中的基础知识 2.3 等价变换规则的概念和术语 U (R B S) = U (R) B U (S) U:一元操作
SLF(R × S) 其中F = F1 and F2, 若F1有R属性, F2有S属性, 则  F(R × S) =  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)

43 2.3 等价变换规则的概念和术语 2 分布式查询优化中的基础知识  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,…,Bm (R) -  C1,…Ck (S)  B1,…,Bm,C1,…Ck (R ∞ S) =  B1,…,Bm (R) ∞  C1,…Ck (S)  B1,…,Bm (R ∝ S) = B1,…,Bm ( B1,…,Bm,C1,…Ck (R) ∝  C1,…Ck (S))

44 定义: 限定关系  F[R: QR] [ F(R) : F and QR]  A[R: QR] [ A(R) : QR]
2.3 等价变换规则的概念和术语 2 分布式查询优化中的基础知识 限定关系 定义: R: QR 称为 R的限定关系, 其中QR表示R中数据具有的特征。 逻辑片段就是一个限定关系  city=‘london’(Supplier) 的限定关系: [Supplier:  city=‘london’]  F[R: QR] [ F(R) : F and QR]  A[R: QR] [ A(R) : QR] [R: QR] × [S: QS] [R × S : QR and QS] [R: QR] [S: QS] [R - S : QR ] [R: QR]  [S: QS] [R  S : QR or QS] [R: QR]  [S: QS] [R  S : QR and QS]

45 局部查询：只涉及本地. 单个站点的数据, 优化同集中式
3.1 分布式查询分类 3 分布式查询的分类与层次结构 局部查询：只涉及本地. 单个站点的数据, 优化同集中式 选择和投影早做，中间结果大大减少 连接前进行预处理（属性排序、属性索引） 同时执行一串投影和选择操作 远程查询：也只涉及单个站点的数据, 但要远程通讯, 选择站点 选择查询应用最近的冗余分配站点 全局查询：涉及多个站点数据, 优化复杂

46 3 分布式查询优化概述 3.1 分布式查询分类 全局查询 具体化 确定操作执行的顺序 确定操作执行的方法 确定执行的站点
对查询进行分解，确定查询使用的物理副本，落实查询对象 非冗余具体化，所有要访问对象只有一个副本 冗余具体化，多个副本，研究如何如何选择副本，使通信代价最小 确定操作执行的顺序 确定二元操作连接和并操作的顺序 先执行所有连接操作，再执行并操作 先执行部分并操作，再执行连接操作 选择和投影尽可能早进行 确定操作执行的方法 把若干个操作连接起来在一次数据库访问中，确定可用的访问路径 连接方法在查询优化中起着重要作用 确定执行的站点 执行站点不一定是发出查询的站点 考虑通讯费用和执行效率

47 分布查询的层次 分布关系上的查询表达 全局模式 查询分解 分布关系上的代数表达 控制站点 数据本地化 段模式 分段关系查询表达 段的统计数据
全局优化 带有通讯操作的段查询优化 本地站点 局部模式 局部优化 优化的局部查询表达

48 3 分布式查询优化概述 3.2 分布式查询处理的层次结构 查询分解 数据本地化 全局优化 局部优化
将查询问题（SQL）转换成一个定义在全局关系上的关系代数表达式 需要从全局概念模式中获得转换所需要的信息 数据本地化 具体化全局关系上的查询，落实到合适的片段上的查询 即将全局关系上的关系代数表达式变换为相应片段上的关系代数表达式 全局优化 输入的是分片查询，优化目标是寻找一个近于最优的执行策略（操作次序） 输出是一个优化的、片段上的关系代数查询 局部优化 输入是局部模式 它由该站点上的DBMS进行优化

49

50 基本原理 优化算法 4 基于关系代数等价变换的查询优化处理 4.1 基本原理和实现方法 查询问题——〉关系代数表达式 分析得到查询树
进行全局到片段的变换得到基于片段的查询树 利用关系代数等价变换规则的优化算法，尽可能先执行选择和投影操作 优化算法 连接和合并尽可能上提（树根方向） 选择和投影操作尽可能下移（叶子方向）

51 实现步骤和方法 转换一：查询问题——〉关系代数表达式 转换二：关系代数表达式——〉查询树 转换三：全局查询树分拆成片段查询树
4.1 基本原理和实现方法 4 基于关系代数等价变换的查询优化处理 实现步骤和方法 转换一：查询问题——〉关系代数表达式 转换二：关系代数表达式——〉查询树 转换三：全局查询树分拆成片段查询树 优化：利用关系代数等价变换规则的优化算法，优化查询树，进而优化查询

52 S(S#, SNAME, AGE, SEX)和SC(S#, C#, GRADE)被水平分片
4.2 查询优化处理举例 4 基于关系代数等价变换的查询优化处理 全局关系 S(S#, SNAME, AGE, SEX)和SC(S#, C#, GRADE)被水平分片 h S SC S1: SEX=‘M’ 男学生全体 S2: SEX=‘F’ 女学生全体 SC1：C#<=20 课程号<=20 SC2：C# >20 课程号>20 查询问题：查找至少有一门功课成绩在90分以上的男生姓名 SNAME(SEX=‘M’ and GRADE>90(S.S #=SC.S# (S×SC)))

53   4 基于关系代数等价变换的查询优化处理 4.2 查询优化处理举例 变换 ∞ S SNAME S.S#=SC.S# S#, SNAME
GRADE>90 SEX=‘M’ S SC U S1 [SEX=‘M’] S2 [SEX=‘F’] SC1 [C#‘C20’] [C#>’C20’] (a)全局关系上的查询树 (b)对应片段上的查询树 变换 ∞

54    U ∞ 4 基于关系代数等价变换的查询优化处理 4.2 查询优化处理举例 SNAME S.S#=SC.S# SEX=‘M’ S1
S#, SNAME  GRADE>90 SEX=‘M’ U SC1 [C#‘C20’ （c）把投影和选择下移后的查询树 (d)一个简化的查询树 产生矛盾去掉一支 S2 [SEX=‘F’] [C#‘C20’] SC2 [C#‘C20’] S1 [SEX=‘M’] [C#‘C20’ GRADE>90] ∞ 

55 4.2 查询优化处理举例 4 基于关系代数等价变换的查询优化处理 水平分片的查询优化的基本思想： 尽量把选择条件下移到分片的限定关系处 再把分片的限定关系与选择条件进行比较 去掉它们之间存在矛盾的相应片断 如果最后剩下一个水平片断，则重构全局关系的操作中，就可去掉“并”操作（至少可以减少“并”操作的次数）

56 EMP(EMP#, ENAME, SALARY,DEPT#,DNAME) 垂直分片：E1 (EMP#,DEPT#,DNAME)
4.2 查询优化处理举例 4 基于关系代数等价变换的查询优化处理 全局关系 EMP(EMP#, ENAME, SALARY,DEPT#,DNAME) 垂直分片：E1 (EMP#,DEPT#,DNAME) EMP2(EMP#, ENAME, SALARY) v S E1 E2: 查询问题：雇员的姓名和工资情况 ENAME,SALARY(EMP)

57  ∞ 4 基于关系代数等价变换的查询优化处理 4.2 查询优化处理举例 ENAME, SALARY ENAME EMP#,DEPT#,
EMP#,ENAME, DEPTNAME SALARY EMP E2: EMP#,ENAME, 去掉无关的片段 移植到片段上 去掉连接 E1： E2： E1.EMP#=E2.EMP# ∞

58 4.2 查询优化处理举例 4 基于关系代数等价变换的查询优化处理 垂直分片的查询优化的基本思想： 把垂直分片所用到的属性集，与查询条件中的投影操作所涉及的属性相比较，去掉无关的垂直片断 如果最后只剩下一个垂直片断与查询有关时，去掉重构全局关系的“连接”操作（至少可以减少“连接”操作的次数）

59 假定有两个关系R,S,在属性R.A=S.B上做半连接操作，可表示为：
5.1 半连接操作 5 基于半连接算法的查询优化处理 假定有两个关系R,S,在属性R.A=S.B上做半连接操作，可表示为： R∝A=B S= R( R ∞A=B S)=R ∞A=B (B (S)) S∝A=B R= S( S ∞A=B R)=S ∞A=B (A (R)) 用半连接表示连接操作 R∞A=BS= ( R∝A=B S)∞A=BS = （R ∞A=B (B (S)) ∞A=BS S∞A=BR = ( S∝A=B R)∞A=BR =(S ∞A=B (A (R) )∞A=BR

60 例子1: R ∝ S  A (R) = [2,10,25,30] A C R 2 a 10 b 25 c 30 d S 25 w 3 x
10 y 15 z 32 x R ∝ S A=A  A (R) = [2,10,25,30] A B A C 10 y 25 w 10 b 25 c S∝R = A=A

61 例子2：半连接简化 R S T R,S,T的循环连接图 S T R 对R的充分简化 T’=T ∝ S’ R’=R ∝ T S’=S ∝ R’
C=C B=B T R A=A 对R的充分简化 T’=T ∝ S’ R’=R ∝ T S’=S ∝ R’ 减少一个元组

62 一般：简化程序长度随着关系的元组数目增长线性增长。 对R的另一个简化程序：
R’’=R’ ∝ T’ T’’=T’ ∝ S’’ S’’=S’ ∝ R’’ 减两个元组 R’’’=R’’ ∝T’’ =  减少三个元组 一般：简化程序长度随着关系的元组数目增长线性增长。 对R的另一个简化程序： R’=R ∝ S T’ = T ∝ R’ S’ = S ∝ T’ （练习）

63 5.2 半连接表示连接的代价估算 5 基于半连接算法的查询优化处理 站点 站点2 R 网络 S (1)  B(S) (3) R’= R∝A=BB(S) (2) B(S) (4) R’= R∝A=B B(S) (5) R’∞A=BS

64 关系的概貌 5 基于半连接算法的查询优化处理 5.2 半连接表示连接的代价估算 Card(R) 片段关系R的元组数目
Size(A) 属性A的大小(即字节数) Size(R) 片段关系的大小, 属性大小之和 Val(A[R]) 属性A在R中出现的不同值的个数

65 代数操作对关系概貌的影响 选择操作 S= F（R） Card(S)= ρ *Card(R) Size(S)=Size(R)
5.2 半连接表示连接的代价估算 5 基于半连接算法的查询优化处理 代数操作对关系概貌的影响 选择操作 S= F（R） Card(S)= ρ *Card(R) Size(S)=Size(R) Val(B[S])是Val(B[R]), Card(S), Card(R)的函数 并操作 T=R∪S Card(T)  Card(R)+Card(S) Size(T)=Size(R)=Size(S) Val(A[T])  Val(A[R])+Val([AS])

66 设c=Val(B[S]), m=Val(B[R]), r=Card(S), n=Card(R)
c=(n,m,r)=r, 当r<m/2 c=(n,m,r)=(r+m)/3, 当m/2 ≤r < 2m c=(n,m,r)=m, 当r ≥2m

67 ρ =Val(A[S])/Val(Dom(A))
5.2 半连接表示连接的代价估算 5 基于半连接算法的查询优化处理 代数操作对关系概貌的影响 连接操作 T=R∞S Card(T) =(Card(R)*Card(S))/Val(A[R]) Size(T) = Size(R)+Size(S) Val(A[T])  Min(Val(A[R]), Val(B[S])) A 是连接属性 Val(A[T])  Val(A[R])+Val(B[S]) A不是连接属性 半连接 T=R∝S ρ =Val(A[S])/Val(Dom(A)) Card(T) = ρ *Card(R) Size(T) = 第一个操作数Size（R） Val(A[T]) = ρ *Val(A[R])

68 代价公式：T=C0+C1*X 采用半连接的总代价 比较T半R 与T半S, 取最优者 5 基于半连接算法的查询优化处理
5.2 半连接表示连接的代价估算 5 基于半连接算法的查询优化处理 代价公式：T=C0+C1*X 在站点2上做投影B (S) 把B (S)传到站点1上，代价为： C0+C1* size (B)* val( B[S]) 在站点1上计算半连接，R’=R ∝A=B S 把R’从站点1传到站点2的代价为： C0+C1* size (R’)* card( R’) 在站点2上执行连接操作：R’ ∞A=BS 采用半连接的总代价 T半R= 2C0+C1* (size (R’)* card( R’) +size (B)* val( B[S])) T半S= 2C0+C1* (size (S’)* card( S’) +size (A)* val( A[R])) 比较T半R 与T半S, 取最优者

69 基本原理 采用半连接优化算法的步骤 5 基于半连接算法的查询优化处理 5.3 半连接算法优化原理和步骤 通常有两次传输
但是传输的数据量和传输整个关系相比，要远远少 一般有：T半<<T全 半连接的得益：当card（R）>>card（R’），可减少站点间的数据传输量 半连接的损失：传输B (S) =C0+C1* size (B)* val( B[S]) 基本原理是在传到另一个站点做连接前，消除与连接无关的数据，减少做连接操作的数据量，从而减小传输代价 采用半连接优化算法的步骤 计算每种半连接方案的代价，并从中选择一种最佳方案 选择传输代价最小的站点，计算采用全连接的方案的代价 比较两种方案，确定最优方案

70 基础 循环 后优化 5 基于半连接算法的查询优化处理 5.3 半连接算法优化原理和步骤 SDD-1半连接算法
给定一个优化图G, 对G中出现的关系已经施加了全部本地简化。 循环 a) 给出所有可能的半连接∝ b) 在有益∝中选择得益最大或者费用最低的∝，若没有这样的∝ ，则中止循环 c) 重新求取受影响的∝的得益与费用，Goto a) 后优化 选出要求较少传输的site来收集全部关系，在此执行∝

71 Statistical information: 1. cardinality.
Features Algo Timing Objective Function  Optim. Factors Networks Semi- joins Statistics Fragments Distri. INGRES Dynamic Response Time, Total cost Msg. Size, Processing cost General Or broadcast No 1 Horizontal R* Static Total Cost # of msg Msg size I/O, &CPU General or local 2 SDD-1 Size Yes 1,3 4,5 AHY Response time,total cost # of msg &Msg. Size 5 Statistical information: 1. cardinality. 2. number of unique values per attribute. 3. join selectivity. 4. size of projection on each join attribute 5. attribute size and tuple size

72 四种基于直接连接的优化算法 （考虑关系分段）
6.1 概述 6 基于直接连接算法的查询优化处理 半连接算法和直接连接算法区别 取决于数据传输和局部处理的相对费用 如果传输费用是主要的，采用半连接，SDD-1 如果本地费用是主要的，采用直接连接,System R* 四种基于直接连接的优化算法 （考虑关系分段） 利用站点依赖信息的算法 分片与复制算法 站点依赖和数据复制结合算法 Hash划分算法

73 站 点 S1 S2 R2 F21 F22 6 基于直接连接算法的查询优化处理 6.2 利用站点依赖信息的算法 关 系 R1 F11 F12
站 点 关 系 S S2 F F12 F F22 R1 R2 ∞ ∞ ∪

74 站点依赖 设关系Ri分片Fi1和Fi2, Rj分片Fj1和Fj2 关系Ri和Rj在属性A上满足条件
6.2 利用站点依赖信息的算法 6 基于直接连接算法的查询优化处理 站点依赖 设关系Ri分片Fi1和Fi2, Rj分片Fj1和Fj2 关系Ri和Rj在属性A上满足条件 Fis ∞ A Fjt=  , 其中s  t, 则称Ri和Rj在属性A上站点依赖 也就是说: Ri ∞ A Rj =U (Fis ∞ A Fjs), 对于包含着两个关系的片段的每个站点s都成立 此时关系的连接操作无站点间数据传输

75 Ri Rj 6 基于直接连接算法的查询优化处理 6.2 利用站点依赖信息的算法 ∞ Ri Rj 本地连接 Fi1 Fi2 Fi3 Fj1
A 本地连接 Ri Fi1 Fi2 Fi3 Fj1 Fj2 Fj3 Rj f(A) f(A) Result

76 推论 6 基于直接连接算法的查询优化处理 6.2 利用站点依赖信息的算法
若Ri和Rj在属性A上站点依赖，则Ri和Rj在任何包含A的属性集B上也站点依赖。 若Ri和Rj在属性A上站点依赖，另一属性（或属性组）B函数决定A，且A  ，则Ri和Rj在B上也站点依赖。 若Ri和Rj在属性A上站点依赖，且若Rj和Rk在属性B上站点依赖，则（Ri ∞ ARj ∞ B Rk）=（Fis ∞ A Fjs ∞ B Fks) 查询Ri ∞ A Rj ∞ B Rk的连接操作能够以无数据传输的方式处理。

77 6 基于直接连接算法的查询优化处理 6.2 利用站点依赖信息的算法 算法描述
Placement_Dependency (Q, P, S)，其中： R={R1,R2,R3,…,Rn}是查询Q引用的一组关系 P是站点依赖信息 S是一个连接操作可以无数据传输的执行的最大关系集合 开始时S是空集。算法结束时，若S=R,则Q可以无数据传输执行 算法步骤 初始化S= ， R={R1,R2,R3,…,Rn} 若能找到一对关系Ri和Rj在属性A上站点依赖，且Ri ∞ CRj 包含在Q中，其中C包含A,那么把Ri和Rj放到S中，否则算法终止，返回空集S。 只要存在R中而不在S中的关系Rk满足下面的特性，就把其放入S中：有S中的关系比如Rj ，与Rk在属性B上有站点依赖关系，且Rj ∞ BRk在Q中或者可以由Q导出，根据推论3，则Rk可被包含在S中。

78 6.3 分片和复制算法 6 基于直接连接算法的查询优化处理 站 点 关 系 S S2 F F12 R R2 R1 R2

79 查询引用的某个关系的所有片段分布在这些站点上,其余被引用的关系复制到每一个选定的站点
6.3 分片和复制算法 6 基于直接连接算法的查询优化处理 查询引用的某个关系的所有片段分布在这些站点上,其余被引用的关系复制到每一个选定的站点 R1 ∞ R2 = Ui (F1i ∞ R2) 算法可应用到涉及两个或两个以上的关系的查询 其中一个关系保持分片状态 其他关系可先连接起来，再被复制到各个站点 在各个站点上，其他关系副本与相应的第一个关系的片断连接

80 6.3 分片和复制算法 6 基于直接连接算法的查询优化处理 R1 R2 R1 ∞ 本地连接 R11 R12 R13 R2 R21 R22 f
partition Result union

81 如何确定保持分片关系的关系，以使得查询具有最短的时间
6.3 分片和复制算法 6 基于直接连接算法的查询优化处理 如何确定保持分片关系的关系，以使得查询具有最短的时间 估算各种策略的响应时间，选择时间最短的策略，S1站点上响应时间(完成时间，FT(Q,S1,R1)）包括三部分，以P.70图为例： F22到S1的数据传输时间 F22和F21进行合并形成S1上的R2副本的时间 F11和S1上的R2副本之间连接的时间 比较Max{FT(Q,S1,R1), FT(Q,S2 ,,R1)}, Max{FT(Q,S1,R2), FT(Q,S2 ,,R2)}，找出响应时间小的保持分片关系 算法忽略了把结果传送到要求答案的用户站点的代价，和将部分结果组装成最终结果的代价，认为它们不大重要，或者采用其他算法时这些部分没有太大差别。

82 6.3 分片和复制算法 6 基于直接连接算法的查询优化处理 Fragmentation_and_replicate(Q, R, S) For 每个保持分片状态的关系Ri For 每个包含关系Ri的一个片段的站点Sj 计算在站点Sj执行子查询的完成时间 FT(Q, Sj, Ri) 计算关系Ri保持分片状态下的响应时间 Ti = maxj (FT(Q, Sj, Ri)) 选择Rk = mini (Ti)为保持分片状态的关系

83 6.3 分片和复制算法 6 基于直接连接算法的查询优化处理 R1 R2 R1 ∞ 本地连接 F11 R2 F21 F12 R2 F22
partition Result union

84 6.3 分片和复制算法 6 基于直接连接算法的查询优化处理 举例 已知R1分段F11和F12的大小为: |F11|=|F12|=50 R2分段F21和F22的大小为: |F21|= |F22|=200 设 数据通讯C0=0, C1=1, 本地连接Cost=J(x1, x2)=5*(x1+x2) 并操作Cost = U(x1, x2) = 2*(x1+x2) 令R1保持分片状态, 则: 站点S1的完成时间 FT(Q, S1, R1) = 200+2*( )+5*(50+300)=2550 同理: FT(Q, S2, R1) = 100+2*( )+5*(50+300)=2450 因此, 查询响应时间在R1保持分片状态为 2550.

85 6.3 分片和复制算法 6 基于直接连接算法的查询优化处理 令R2保持分片状态, 则: 站点S1的完成时间 FT(Q, S1, R2) = 50+2*(50+50)+5*( )=1250 同理: FT(Q, S2, R2) = 50+2*(50+50)+5*( )=1750 因此, 查询响应时间在R2保持分片状态为 1750. 因为: R1保持分片状态的响应时间>R2保持分片状态的响应时间 所以: 选择R2保持分片计算查询

86 6.4 站点依赖和数据复制结合 6 基于直接连接算法的查询优化处理 S1 S2 F11 F12 F21 F22 R3 站 点 R1 关 系 R2 R3 设R1和R2在属性A上站点依赖, 查询R1 ∞A R2 ∞B R3

87 6.4 站点依赖和数据复制结合 6 基于直接连接算法的查询优化处理 设R1和R2在属性A上站点依赖, 查询R1 ∞ R2 ∞ R3 第一个连接因为站点依赖，无传输处理 第二个连接因为存在R3的副本,也没有传输处理 另外一个保证查询无传输的方法是R1和R2连接执行后，形成一个关系R4，它有两个片断： 一个由F11 ∞ F21给出 一个由F12 ∞ F22给出 最后由R4和R3的副本连接得到最后的结果

88 6.4 站点依赖和数据复制结合 6 基于直接连接算法的查询优化处理 连接依赖定义： 如果Ri 和Rj 在属性A上站点依赖 或者关系Ri复制在关系Rj各片断的站点上 或者关系Rj复制在关系 Ri各片断的站点上

89 利用Hash函数对分片关系上的连接属性作站点依赖计算, 再据此分片, 以获取站点依赖的连接算法
6 基于直接连接算法的查询优化处理 利用Hash函数对分片关系上的连接属性作站点依赖计算, 再据此分片, 以获取站点依赖的连接算法 例如, 运用Hash函数 1 若a 是奇数 0 若a 是偶数 对R中每个元组, h(a)为1送入站点S1, h(a)为0送入站点S2. 于是片段关系R被划分为Ro和Re R1 ∞ R2 = (R1o ∞ R2o) U (R1e ∞ R2e) h(a) =

90 h(a) = 6 基于直接连接算法的查询优化处理 6.5 Hash划分算法
利用Hash函数对分片关系上的连接属性作站点依赖计算, 再据此分片, 以获取站点依赖的JN算法 例如, 运用Hash函数 1 若a 是奇数 0 若a 是偶数 片断F11按属性A的值为奇和偶数划分成F11o和F11e，片断F12划分成F12o和F12e 站点S2上F12’=F11e∪F12e，站点S1上F11’=F11o∪F12o 显然A ( F11 ’ )和A(F12’)没有公共值,前面是奇数值后面是偶数值 F12’∞ F11’是空集，这说明R1和R2在新组成的片断下在属性A上站点依赖。 R1 ∞ R2 = （F11’∞ F21’） U （F12’∞ F22’） h(a) =

91 考察三个关系R1，R2和R3 ,它们在两个站点上，有两种情况：
6.5 Hash划分算法 6 基于直接连接算法的查询优化处理 考察三个关系R1，R2和R3 ,它们在两个站点上，有两种情况： 在同一属性A上连接，R1∞A R2 ∞AR3 在三个关系的片断上应用Hash函数 使用新组建的片断，三个关系在属性A上将满足站点依赖 经这种划分和数据传送之后，两个站点上的片断在属性A上的连接就可以并行进行，合并执行结果给出答案 在不同属性上连接， R1∞A R2 ∞BR3

92 两种情况： 在同一属性A上连接，R1∞A R2 ∞AR3 在不同属性上连接， R1∞A R2 ∞BR3 6 基于直接连接算法的查询优化处理
6.5 Hash划分算法 6 基于直接连接算法的查询优化处理 两种情况： 在同一属性A上连接，R1∞A R2 ∞AR3 在不同属性上连接， R1∞A R2 ∞BR3 在属性A上应用同样的Hash函数，在属性B上也应用同样的Hash函数，可能得不到希望的站点依赖 因R1中属性A的值是奇数的发往S1，R3中属性B是奇数的元组发往S1.但R2中某些元组可能在A上有奇数值，而在B上有偶数值 解决方法是允许这些元组在两个站点上都存在。

93 若R1与R2在A上有相同的Hash函数, R2与R3在属性B上有相同的Hash函数
6 基于直接连接算法的查询优化处理 R1 ∞ A R2 ∞ B R3 若R1与R2在A上有相同的Hash函数, R2与R3在属性B上有相同的Hash函数 S1 S2 F011(A) Fe12(A) F021(A)U F021(B) F031(B) Fe32(B) Fe22(A)U Fe22(B)

94 站点 S1 S2 关系 R1 F11 F12 R2 F21 F22 6 基于直接连接算法的查询优化处理 6.6 算法比较 站点依赖算法
无数据传递 可利用索引做本地连接 每个站点连接数据总量是R，两个片段 分片和复制算法 数据传输总量是R 数据传送后,可能要重新创建索引 每个站点的连接数据量是(3/2)R,一个全关系和一个片断 Hash划分算法 数据传送量是R 索引方面, 比片段复制算法更低 每个站点的连接数据量同站点依赖 假定每个片段的大小是R大小的一半R/2

95 7 直接连接操作的常用策略 7.1 直接连接操作一般常用策略 两个关系在同一个站点， 嵌套循环法 排序扫描法
R∞S，称外层关系为R,内层关系为S 嵌套循环法 顺序扫描外层关系R，对于R的每一元组扫描内层关系S 查找在连接属性上一致的元组，组合起来构成结果的一部分 需要扫描一次关系R和Card（R）次关系S 排序扫描法 先把两个关系按照连接属性进行排序 然后按照连接属性值的顺序扫描这两个关系，使匹配的元组成为结果的一部分 对两个关系都扫描一次，但增加了排序代价

96 7 直接连接操作的常用策略 7.1 直接连接操作一般常用策略 两个关系在不同站点，关系R和关系S 两种传输方式 三种选择连接站点的方法
整体传输 如果传输S,则保存S（被多次扫描，传输量少） 如果传输R，则S可直接使用一次来到的R元组，不保存R(但传输量大） 按需传输 只传输需要连接的元组，一次一个元组，无需临时存储器 每次提取都要交换一次信息，传输代价高，只在高速局域网中才是合理的 三种选择连接站点的方法 R站点 S站点 其他站点

97 7 直接连接操作的常用策略 7.2 利用并行性的直接连接操作策略 一个操作内的并行一般是不可行的 多个操作间的并行是可行的 流水线并行
在查询表达式中，一个操作A的输出元组作为第二个操作B的输入 在第一个操作尚未产生全部的输出元组集合之前，第二个操作就可以在它的输入上进行工作 可以在不同的站点上运行A和B，在A产生部分结果元组的同时，B来使用它们 独立的并行 查询表达式中，那些相互之间没有依赖关系的操作可以并行地执行

98 有很多策略，其中一个是两种并行方法结合使用：
7.2 利用并行性的直接连接操作策略 7 直接连接操作的常用策略 例子：R1∞ R2∞ R3∞ R4 有很多策略，其中一个是两种并行方法结合使用： 把R1送到S2并在S2上计算R1∞ R2，同时把R3送到S4上计算R3∞ R4 在站点S2上计算R1∞ R2的过程中，就可以把已经计算出来的元组送到站点S1，而不必等到整个连接计算完成 同样，在站点S4上计算R3∞ R4的过程中，就可以把已经计算出来的元组送到站点S1，而不必等到整个连接计算完成。 一旦（R1∞ R2）和（ R3∞ R4）的元组到达站点S1,在S1上就可以开始计算（R1∞ R2）∞（ R3∞ R4 ）。 也就是说，站点S1上最终连接的结果的计算可以同S2上R1∞ R2 的计算以及S4上的R3∞ R4计算并行地进行。

99 练习1 8 6 2 5 3 4 1 C B A 9 D 7 F E S R T 有关系R，S，T，如图所示 计算连接R ∞ S ∞ T
计算半连接R∝S，S∝R，S∝T，T∝S，R∝T，T∝R 8 6 2 5 3 4 1 C B A 9 D 7 F E S R T

100 练习2 在如下R, S的概貌上计算R ∞A=B S Size(R)=50, Card(R)=100, Val(A[R])=50, Size(A)=3 Size(S)=5, Card(S)=50, Val(B[S])=50, Size(B)=3 R ∝A=B S 的选择度 ρ = 0.2 S ∝A=B R 的选择度 ρ = 0.8 C0=0,C1=1 问: 1. 使用 ∝简化程序在R的站点执行∞ 2. 使用 ∝简化程序在S的站点执行∞ 3. 使用直接连接在R站点执行∞ 4. 使用直接连接在S站点执行∞ 那种方案较优? 站点 站点2 R 网络 S

101 分布式查询优化概述（目标、准则和代价估算） 基础知识 关系代数回顾 等价变换规则 分布式查询分类和层次结构 基于关系代数等价变换的查询优化
总 结 分布式查询优化概述（目标、准则和代价估算） 基础知识 关系代数回顾 等价变换规则 分布式查询分类和层次结构 基于关系代数等价变换的查询优化 基于半连接算法的查询优化处理 基于直接连接算法的查询优化处理（四类算法）