崔明义
（ mycui369@126.com)
计算机应用技术 2007级研究生
1,分布式查询优化概述
2.分布式查询优化基础知识
3.分布式查询分类和层次结构
4.基于关系代数等价变换的查询优化处理
5.基于半连接算法的查询优化处理
6.基于直接连接算法的查询优化处理
7.直接连接操作的常用策略分布式数据库中的查询处理和优化第 3章查询处理问题
集中式
– 查询转换为代数表达式
– 从所有等价表达式中选择最优的代数表达式
分布式
– 除了集中式问题外，还有
– 站点之间交换数据的操作
– 选择最优的执行站点 (分布）
– 数据被传送的方式
1.1 分布式查询优化的目标
1 分布式查询优化概述
1.1 分布式查询优化的目标
1 分布式查询优化概述目标总代价最小响应时间最短集中式分布式
CPU代价（相对固定）
I/O代价（可变的，优化的目标）
CPU代价
I/O代价（访问磁盘）
通讯代价数据的分布和冗余增加了查询的并行处理的可能性，从而可以缩减查询处理的响应时间主要标准辅助标准
1.2 分布式查询优化准则和代价分析
1 分布式查询优化概述准则：
使得通讯费用最低和响应时间最短，即以最小的总代价，在最短的响应时间内获得需要的数据。
1,通讯费用与所传输的数据量和通信次数有关
2,响应时间和通信时间有关，也与局部处理时间有关查询代价分析
1,远程通讯网络局部处理时间可以忽略不计，减少通讯代价是主要目标
2,高速局域网传输时间比局部处理时间要短很多，以响应时间作为优化目标，局部处理时间是关键
例子
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,
通讯延迟 1sec
S,SC CSite A
Site B
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’;
1.3 分布式查询策略的重要性
1 分布式查询优化概述
代价公式
QC = I/O 代价 + CPU 代价 + 通讯代价
通讯代价
TC = 传输延迟时间 C0
+ (传输数据量 X * 数据传输速率 C1)
1.3 分布式查询策略的重要性
1 分布式查询优化概述
1.3 分布式查询策略的重要性
1 分布式查询优化概述策略 1:
A 传 C B 把关系 C 传输到 A 地,在 A 地处理查询
○ ○ T1 = 1 + (10**5 * 100 / 10**4)
S,SC 通信 1次 C ≈ 10**3 秒 ≈ 16.7 分钟
A 传 S,SC B 把关系 S 和 SC 传输到 B 地,在 B 地处理查询
○ ○ T2 = (2+10**4+10**5) * 100 / 10**4
S,SC 通信 2次 C ≈ 10100 秒 ≈ 28小时
A 问 10**5 B 先在 A地求出男学生的成绩元组有 10**5
○ ○ 再根据 C#的值询问 B地,核实是否 C=‘MATHS’
S,SC 答 10**5 C T3 ≈ (2 * 10**5 *1)=2*10**5 秒 ≈ 2.3 天策略 2:
策略 3:
六种查询策略
S,SC CA B
1.3 分布式查询策略的重要性
1 分布式查询优化概述
A 问 10 B 先在 B地求出 ‘MATHS’的元组,有 10个
○ ○ 再根据 C#的值询问 A 地的 S,SC的连接，
S,SC 答 10 C 核实是否为选修 ‘MATHS’的男生
T4 ≈ (2 * 10 * 1) = 20 秒
A 传输 10**5 B 先在 A地求出男生选课元组，有 10**5个
○ ○ 再把结果传输到 B 地,在 B 地执行查询，
S,SC 通信 1次 C T5 = 1 + (10**5 * 100) / 10**4
≈ 1000 秒 ≈ 16.7 分
A 传输 10 B 先在 B地求出为 ‘ MATHS’的元组，有 10个
○ ○ 再把结果传输到 A地,在 A地执行查询，
S,SC 通信 1次 C T6 = 1 + (10 * 100) / 10**4 ≈ 1 秒策略 4：
策略 5：
策略 6：
六种查询策略
S,SC CA B
相关表述记号
⒈ 设关系模式为 R(A1,A2,…,An) 。它的一个关系设为 R。
t∈ R表示 t是 R的一个 元组 。 t[Ai]则表示元组 t中相应于属性 Ai的一个 分量 。
⒉ 若 A={Ai1,Ai2,…,A ik}，其中 Ai1,Ai2,…,A ik是 A1,A2,…,An 中的一部分，
则 A称为属性列或域列。 t[A]=(t[Ai1],t[Ai2],…,t[A ik])表示元组 t 在属性列 A上诸分量的集合。则 表示 {A1,A2,…,An} 中去掉
{Ai1,Ai2,…,A ik} 后剩余的属性组。
A
2.1 关系代数知识回顾
2 分布式查询优化中的基础知识
⒊ 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上分量的集合。
2.1 关系代数知识回顾
2 分布式查询优化中的基础知识传统的集合运算
并运算
c1b2a2
c2b2a1
c1b1a1
CBA
c1b2a2
c2b3a1
c2b2a1
CBAR1 R2
c1b1a1
c1b2a2
c2b3a1
c2b2a1
CBA
R1∪ R2
设关系 R和关系 S具有相同的目 n（即两个关系都有 n个属性），且相应的属性取自同一个域，则关系 R与关系 S的并由属于 R或属于 S的元组组成。
其结果关系仍为 n目关系。记作,R∪ S={ t | t∈ R∨ t∈ S }
2.1 关系代数知识回顾
2 分布式查询优化中的基础知识
差运算
c1b2a2
c2b2a1
c1b1a1
CBA
c1b2a2
c2b3a1
c2b2a1
CBAR1 R2
c1b1a1
CBA
R1－ R2
设关系 R和关系 S具有相同的目 n，且相应的属性取自同一个域，则关系 R与关系 S
的差由属于 R而不属于 S的所有元组组成。其结果关系仍为 n目关系。记作：
R－ S={t|t∈R∧t S}∈
传统的集合运算
2.1 关系代数知识回顾
2 分布式查询优化中的基础知识
交运算
c1b2a2
c2b2a1
c1b1a1
CBA
c1b2a2
c2b3a1
c2b2a1
CBAR1 R2 A B C
a1 b2 c2
a2 b2 c1
R1∩R2
设关系 R和关系 S具有相同的目 n，且相应的属性取自同一个域，
则关系 R与关系 S的交由既属于 R又属于 S的元组组成。其结果关系仍为 n目关系。记作,R∩S={t|t∈R∧t∈S}
传统的集合运算
2.1 关系代数知识回顾
2 分布式查询优化中的基础知识两个分别为 n目和 m目的关系 R和 S的广义笛卡尔积是一个 (n+m)列的元组的集合。元组的前 n列是关系 R的一个元组，后 m列是关系 S的一个元组。若
R有 k1个元组,S有 k2个元组，则关系 R和关系 S的广义笛卡尔积有
k1× k2个元组。记作：
R1× R2
c1b1a1
c1b1a1
c1b1a1
CBA
c1b2a2
c2b3a1
c2b2a1
CBA
......
c2b3a1
c2b2a1
......
c2b2a1
c2b2a1c1b2a2
c2b2a1
c1b1a1
CBA
c1b2a2
c2b3a1
c2b2a1
CBAR1 R2
广义笛卡尔积
2.1 关系代数知识回顾
2 分布式查询优化中的基础知识专门的关系运算学号 学生姓名 所属系名 学生年龄
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(S#,SN,SD,SA)
2.1 关系代数知识回顾
2 分布式查询优化中的基础知识选择运算是从关系中选取使公式为真的元组。这是从行的角度进行的运算。
在关系 R中选择满足给定条件的元组，记做：
σF (R) ={ t | t ∈ R Λ F(t)=‘真 ’ }
F是一个公式，表示形式为由逻辑运算符 （ ∧,∨,?)连接各算术表达式组成 。
算术表达式的基本形式为,XθY,θ ={>,≥,<,≤,=,≠} 。
例 1 求计算机科学系 CS的学生
σ SD=‘CS’ (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)
(S’)
S# SN SD SA
S1 A CS 20
S2 B CS 21
S6 F CS 22
σ SD=‘CS’ (S)
选择运算在关系 R中选择满足给定条件的元组，记做：
σF (R) ={ t | t ∈ R Λ F(t)=‘真 ’ }
例 2 求计算机科学系 CS，年龄不超过 21岁的学生。
σ SD=‘CS’ ∧ SA≤21 (S)
(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
σ SD=‘CS’ (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
(S)
投影运算这是从列的角度进行的运算 。
例 3 πSN,SD (S) 即求得学生关系 S在学生姓名和所在系这两个属性上的投影结果。
πSN,SD (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中选择若干属性列组成新的关系。记做：
πA (R) ={ t[A] | t ∈ R}
投影之后不仅取消了某些列,还可能取消某些元组。
πSA (S)
SA
20
21
19
22
SN SD
A CS
B CS
C MA
D CI
E MA
F CS
连接运算（ θ 连接）
连接运算是从两个关系的笛卡尔积中选取属性间满足一定条件的元组。
记做,R S,其中,F是条件表达式，它涉及到对两个关系中的属性的比较。∞ F
S
2b5
2b3
10b3
7b2
3b1
EB
12b4a2
8b3a2
6b2a1
5b1a1
CBA
R
R S∞
C<E
10b38b3a2
10b36b2a1
7b26b2a1
10b35b1a1
7b25b1a1
ES.BCR.BA
例 4 设关系 R,S如下图,R S∞
C<E
等值 连接例 5 设关系 R,S如下图：
2b5
2b3
10b3
7b2
3b1
EBS
12b4a2
8b3a2
6b2a1
5b1a1
CBA
R
A R.B C S.B E
a1 b1 5 b1 3
a1 b2 6 b2 7
a2 b3 8 b3 10
a2 b3 8 b3 2
R S∞ R.
B=S.B
连接运算中有两种最为重要也最为常用的连接，
θ为,＝,的连接运算称为等值连接,
自然连接
A B C E
a1 b1 5 3
a1 b2 6 7
a2 b3 8 10
a2 b3 8 2
R S∞
A R.B C S.B E
a1 b1 5 b1 3
a1 b2 6 b2 7
a2 b3 8 b3 10
a2 b3 8 b3 2
R S∞ R.
B=S.B
另一种是自然连接。自然连接是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性组，并且要在结果中把重复的属性去掉。
例 6 关系 R,S的自然连结,R S∞
半连接在 R,S自然连接后仅保留对 R的属性的投影，记为,R ∝ S
例 7 关系 R,S的半连接：
A B C E
a1 b1 5 3
a1 b2 6 7
a2 b3 8 10
a2 b3 8 2
R S∞
A B C
a1 b1 5
a1 b2 6
a2 b3 8
R ∝ S2b5
2b3
10b3
7b2
3b1
EBS
12b4a2
8b3a2
6b2a1
5b1a1
CBAR
左外连接,对 R中任意元组，若 S中找不到匹配的元组，
则 S用空元组与之对应。 R的信息在左外连接的结果中都得到保留。
左外连接在 R,S自然连接时对不匹配的元组用空值来匹配。有左外连接、右外连接和全外连接之分例 8 关系 EMP,SAL的左外连结：
SALEMP
上海邓平长春李宏大连王小北京张丽
CITYENAME
3000赵刚
5000王小
6000张丽
SALARYENAME
NULL
NULL
5000
6000
SALARY
上海邓平长春李宏大连王小北京张丽
CITYENAME
EMP SAL
右外连结,对 S中任意元组，若 R中找不到匹配的元组，
则 R用空元组与之对应。 S的信息在右外连接的结果中都得到保留。
右外连接例 9 关系 EMP,SAL的右外连结：
SALEMP
上海邓平长春李宏大连王小北京张丽
CITYENAME
3000赵刚
5000王小
6000张丽
SALARYENAME
ENAME CITY SALARY
张丽 北京 6000
王小 大连 5000
赵刚 NULL 3000
EMP SAL
全外连接,对 R或 S中所有不匹配的元组，均用空元组分别匹配。 R,S的信息在全外连接的结果中都得到保留。
全外连接例 10 关系 EMP,SAL的全外连结：
SALEMP
上海邓平长春李宏大连王小北京张丽
CITYENAME
3000赵刚
5000王小
6000张丽
SALARYENAME
ENAME CITY SALARY
张丽 北京 6000
王小 大连 5000
李宏 长春 NULL
邓平 上海 NULL
赵刚 NULL 3000
EMP SAL
c1b2a1
c3b2a2
c6b6a4
c3b2a1
c6b4a3
c7b3a2
c2b1a1
CBA
R
c3
c1
c2
C
d2
d1
d1
D
b2
b2
b1
B
S例 11
除运算给定关系 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]。
Z
X
Y
除运算
c1b2a1
c3b2a2
c6b6a4
c3b2a1
c6b4a3
c7b3a2
c2b1a1
CBA
c3
c1
c2
C
d2
d1
d1
D
b2
b2
b1
B
R S
a1的象集为：
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） }
R÷ S = { tｒ [X] | tｒ ∈ R ∧ Yx?ΠY(S) }
R÷ S＝ { a1}
学号 课程号 学习成绩
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
S2 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)
学号 课程号 学习成绩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 20S2 B CS 21
S3 C MA 19S4 D CI 19
S5 E MA 20..,.,.,.
S
S SC∞
σ C# =‘C2’( )S SC∞
例 2 检索学习课程号为 C2的学生学号和姓名学号 学生姓名 所属系名 学生年龄 课程号 学习成绩
S# SNAME SD SA C# GRADES1 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 B
＝ πS#,SNAME(S ∞ C# =‘C2’ SC)πS#,SNAME(σ C# =‘C2’ ( S ∞ SC ))
例 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 SAS1 A CS 20
S2 B CS 21S3 C MA 19
S4 D CI 19S5 E MA 20
..,.,.,.
S
例 4 检索学习课程号为 C2或 C3的学生学号和所在系
πSN,SD( (σCN=‘数据库原理 ’ (C)) )S ∞ SC ∞
πS#,SD( s ∞πS# (σC# =‘C2’∨ C#=‘C3’(SC)) )
例 5 求至少选修 C2和 C3这两门课程的学生名。
C#
C2
C3
K
πSN( S ∞ (πS#,C# (SC) ÷ K))
πSN( S ∞ (πS#,C# (SC) ÷
πC# (σC# =‘C2’∨ C#=‘C3’(C)))
K ＝ π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 ( S ∞ (πC#,S# (SC) ÷ C) )
πSN ( S ∞ (πC#,S# (SC) ÷ πC# (σS#=‘S2’(SC))))
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))
2.1 用关系代数和 SQL语句表示一个查询
2 分布式查询优化中的基础知识关系代数基本操作：
并（ ∪ ）、交（ ∩）、笛卡尔积（ × ）、选择（?）、投影（?）
关系代数到处操作：
差（－）、除（ ÷ ）,θ 连接（ ∞ θ ）、自然连接（ ∞）、半连接（ ∝ ）
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)
2.2 查询树
2 分布式查询优化中的基础知识
sname
s.s# = sc.s#?c# =‘c03’
S SC
sname
s.s# = sc.s#
S?c#=‘c03’
SC
sname
∞
S?c# =‘c03’
SC
(a)对于 E1的查询树
(b)对于 E2的查询树
(c)对于 E3的查询树节点表示一个一元或二元操作符叶子表示已知关系树根表示查询结果
一元操作：只涉及一个操作对象
(SL),? (PJ)
二元操作：涉及两个操作对象
∪ (UN),∩（）,－ (DF),× (CP),
∞θ（）,∞ (JN),∝ (SJ),
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的属性
2.3 等价变换规则的概念和术语
2 分布式查询优化中的基础知识
交换率
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
2.3 等价变换规则的概念和术语
2 分布式查询优化中的基础知识
结合率
R B ( S B T ) = (R B S) B T)
B,二元操作
∞（ JN）,× （ CP）,∪ （ UN）,?等总成立
∝ （ SJ） 有问题
2.3 等价变换规则的概念和术语
2 分布式查询优化中的基础知识
分配率
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)
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)
–? PJB1,…,Bm (R ∝ S)
=?B1,…,Bm (? B1,…,Bm,C1,…Ck (R) ∝? C1,…Ck (S))
2.3 等价变换规则的概念和术语
2 分布式查询优化中的基础知识限定关系
定义,
R,QR 称为 R的限定关系,其中 QR表示查询逻辑片段就是一个限定关系
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]
2.3 等价变换规则的概念和术语
2 分布式查询优化中的基础知识
局部查询：只涉及本地,单个站点的数据,优化同集中式
选择和投影早做，中间结果大大减少
连接前进行预处理（属性排序、属性索引）
同时执行一串投影和选择操作
远程查询：也只涉及单个站点的数据,但要远程通讯,选择站点
选择查询应用最近的冗余分配站点
全局查询：涉及多个站点数据,优化复杂
3.1 分布式查询分类
3 分布式查询的分类与层次结构全局查询
具体化
– 对查询进行分解，确定查询使用的物理副本，落实查询对象
– 非冗余具体化，所有要访问对象只有一个副本
– 冗余具体化，多个副本，研究如何如何选择副本，使通信代价最小
确定操作执行的顺序
– 确定二元操作连接和并操作的顺序
先执行所有连接操作，再执行并操作
先执行部分并操作，再执行连接操作
– 选择和投影尽可能早进行
确定操作执行的方法
– 把若干个操作连接起来在一次数据库访问中，确定可用的访问路径
– 连接方法在查询优化中起着重要作用
确定执行的站点
– 执行站点不一定是发出查询的站点
– 考虑通讯费用和执行效率
3.1 分布式查询分类
3 分布式查询优化概述查询分解数据本地化全局优化局部优化分布关系上的查询表达分布关系上的代数表达分段关系查询表达带有通讯操作的段查询优化优化的局部查询表达全局模式段模式段的统计数据局部模式控制站点本地站点分布查询的层次
查询分解
– 将查询问题（ SQL）转换成一个定义在全局关系上的关系代数表达式
– 需要从全局概念模式中获得转换所需要的信息
数据本地化
– 具体化全局关系上的查询，落实到合适的片段上的查询
– 即将全局关系上的关系代数表达式变换为相应片段上的关系代数表达式
全局优化
– 输入的是分片查询，优化目标是寻找一个近于最优的执行策略（操作次序）
– 输出是一个优化的、片段上的关系代数查询
局部优化
– 输入是局部模式
– 它由该站点上的 DBMS进行优化
3.2 分布式查询处理的层次结构
3 分布式查询优化概述
基本原理
1,查询问题 ——〉 关系代数表达式
2,分析得到查询树
3,进行全局到片段的变换得到基于片段的查询树
4,利用关系代数等价变换规则的优化算法，尽可能先执行选择和投影操作
优化算法
1,连接和合并尽可能上提（树根方向）
2,选择和投影操作尽可能下移（叶子方向）
4.1 基本原理和实现方法
4 基于关系代数等价变换的查询优化处理
实现步骤和方法
– 转换一：查询问题 ——〉 关系代数表达式
– 转换二：关系代数表达式 ——〉 查询树
– 转换三：全局查询树分拆成片段查询树
– 优化：利用关系代数等价变换规则的优化算法，优化查询树，进而优化查询
4.1 基本原理和实现方法
4 基于关系代数等价变换的查询优化处理
4.2 查询优化处理举例
4 基于关系代数等价变换的查询优化处理全局关系
S(S#,SNAME,AGE,SEX)和 SC(S#,C#,GRADE)被水平分片
h 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.C# (S× SC)))
4.2 查询优化处理举例
4 基于关系代数等价变换的查询优化处理
SNAME
S.S#=SC.S# S.S#=SC.S#
S#,SNAME?S#,SNAME?GRADE>90?GRADE>90
SNAME
SEX=‘M’
S
SC?SEX=‘M’
U
S1[SEX=‘M’] S2[SEX=‘F’]
U
SC1[C#?‘C20’] SC1[C#>’C20’]
(a)全局关系上的查询树
(b)对应片段上的查询树变换∞
∞
4.2 查询优化处理举例
4 基于关系代数等价变换的查询优化处理
SNAME
S.S#=SC.S# S.S#=SC.S#
S#,SNAME
S#,SNAME
GRADE>90
SNAME
SEX=‘M’
U
SC1
[C#?‘C20’
（ c）把投影和选择下移后 的查询树 (d)一个简化 的查询树产生矛盾去掉一支
S#,SNAME?GRADE>90
S2[SEX=‘F’]
SEX=‘M’ SC1
[C#?‘C20’]
SC2
[C#?‘C20’]
S1[SEX=‘M’]
SC2
[C#?‘C20’
S1[SEX=‘M’]
U U
GRADE>90] GRADE>90]
∞ ∞
4.2 查询优化处理举例
4 基于关系代数等价变换的查询优化处理水平分片的查询优化的基本思想：
1,尽量把选择条件下移到分片的限定关系处
2,再把分片的限定关系与选择条件进行比较
3,去掉它们之间存在矛盾的相应片断
4,如果最后剩下一个水平片断，则重构全局关系的操作中，
就可去掉“并”操作（至少可以减少“并”操作的次数）
4.2 查询优化处理举例
4 基于关系代数等价变换的查询优化处理全局关系
EMP(EMP#,ENAME,SALARY,DEPT#,DNAME)
垂直分片,E1 (EMP#,DEPT#,DNAME)
EMP2(EMP#,ENAME,SALARY)
v
S
E1 E2,
查询问题：雇员的姓名和工资情况
ENAME,SALARY(EMP)
4.2 查询优化处理举例
4 基于关系代数等价变换的查询优化处理
ENAME,SALARY? ENAME?
EMP#,DEPT#,? EMP#,ENAME,?
DEPTNAM
E
SALARY
ENAME,SALARY?
EMP#,ENAME,?
SALARY
ENAME,SALARY?
EMP
E2,EMP#,ENAME,SALARY
去掉无关的片段移植到片段上去掉连接
E1,E2：
E1.EMP#=E2.EMP#∞
∞
4.2 查询优化处理举例
4 基于关系代数等价变换的查询优化处理垂直分片的查询优化的基本思想：
1,把垂直分片所用到的属性集，与查询条件中的投影操作所涉及的属性相比较，去掉无关的垂直片断
2,如果最后只剩下一个垂直片断与查询有关时，去掉重构全局关系的“连接”操作（至少可以减少“连接”操作的次数）
假定有两个关系 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
– R∞A=BS = ( S∝ A=B R)∞A=BR
=(S ∞A=B (?A (R) )∞A=BR
5.1 半连接操作
5 基于半连接算法的查询优化处理例子 1,R ∝ S
A B
2 a
10 b
25 c
30 d 25 w
3 x
10 y
15 z
32 x
A (R) = [2,10,25,30]
R ∝ S
S∝ R =
A C
10 y
25 w
A=A
A=A
A C
SR
10 b
25 c
A B
例子 2：半连接简化
R S T
R
S
T
B=B C=C
A=A
R,S,T的循环连接图对 R的充分简化
R’=R ∝ T
S’=S ∝ R’
T’=T ∝ S’
减少一个元组
R’’=R’ ∝ T’
S’’=S’ ∝ R’’
T’’=T’ ∝ S’’
减两个元组
R’’’=R’’ ∝ T’’ =? 减少三个元组一般：简化程序长度随着关系的元组数目增长线性增长。
对 R的另一个简化程序：
R’=R ∝ S T’ = T ∝ R’ S’ = S ∝ T’ （练习）
5.2 半连接表示连接的代价估算
5 基于半连接算法的查询优化处理
R S网络站点 1 站点 2
(1)? B(S)
(3) R’= R∝ A=B?B(S) (2)?B(S)
(4) R’= R∝ A=B?B(S) (5) R’∞ A=BS
关系的概貌
– Card(R) 片段关系 R的元组数目
– Size(A) 属性 A的大小 (即字节数 )
– Size(R) 片段关系的大小,属性大小之和
– Val(A[R]) 属性 A在 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])
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])
5.2 半连接表示连接的代价估算
5 基于半连接算法的查询优化处理
代价公式,T=C0+C1*X
1,在站点 2上做投影?B (S)
2,把?B (S)传到站点 1上，代价为：
– C0+C1* size (B)* val( B[S])
3,在站点 1上计算半连接,R’=R ∝ A=B S
4,把 R’从站点 1传到站点 2的代价为：
– C0+C1* size (R’)* card( R’)
5,在站点 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,取最优者
5.2 半连接表示连接的代价估算
5 基于半连接算法的查询优化处理
基本原理
1,通常有两次传输
2,但是传输的数据量和传输整个关系相比，要远远少
3,一般有,T半 <<T全
4,半连接的得益：当 card（ R） >>card（ R’），可减少站点间的数据传输量
5,半连接的损失：传输?B (S) =C0+C1* size (B)* val( B[S])
6,基本原理是在传到另一个站点做连接前，消除与连接无关的数据，减少做连接操作的数据量，从而减小传输代价
采用半连接优化算法的步骤
– 计算每种半连接方案的代价，并从中选择一种最佳方案
– 选择传输代价最小的站点，计算采用全连接的方案的代价
– 比较两种方案，确定最优方案
5.3 半连接算法优化原理和步骤
5 基于半连接算法的查询优化处理
SDD-1半连接算法
基础给定一个优化图 G,对 G中出现的关系已经施加了全部本地简化。
循环
a) 给出所有可能的半连接 ∝
b) 在有益 ∝ 中选择得益最大或者费用最低的 ∝,若没有这样的 ∝,则中止循环
c) 重新求取受影响的 ∝ 的得益与费用,Goto a)
后优化选出要求较少传输的 site来收集全部关系，在此执行 ∝
5.3 半连接算法优化原理和步骤
5 基于半连接算法的查询优化处理
半连接算法和直接连接算法区别
– 取决于数据传输和局部处理的相对费用
– 如果传输费用是主要的，采用半连接,SDD-1
– 如果本地费用是主要的，采用直接连接,System R*
四种基于直接连接的优化算法 （考虑关系分段）
– 利用站点依赖信息的算法
– 分片与复制算法
– 站点依赖和数据复制结合算法
– Hash划分算法
6.1 概述
6 基于直接连接算法的查询优化处理
6.2 利用站点依赖信息的算法
6 基于直接连接算法的查询优化处理站 点关系
S1 S2
F11 F12
F21 F22
R1
R2
∪
∞ ∞
站点依赖设关系 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都成立此时关系的连接操作无站点间数据传输
6.2 利用站点依赖信息的算法
6 基于直接连接算法的查询优化处理
Ri Fj1
Fj2
Fj3
Fi1
Fi2
Fi3
Rj
本地连接
Result
A
f(A) f(A)
Ri Rj
6.2 利用站点依赖信息的算法
6 基于直接连接算法的查询优化处理
∞
推论
– 若 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的连接操作能够以无数据传输的方式处理。
6.2 利用站点依赖信息的算法
6 基于直接连接算法的查询优化处理
算法描述
– 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中。
6.2 利用站点依赖信息的算法
6 基于直接连接算法的查询优化处理
6.3 分片和复制算法
6 基于直接连接算法的查询优化处理站 点关系
S1 S2
F11 F12
R2 R2
R1
R2
查询引用的某个关系的所有片段分布在这些站点上,其余被引用的关系复制到每一个选定的站点
R1 ∞ R2 = Ui (F1i ∞ R2)
算法可应用到涉及两个或两个以上的关系的查询
– 其中一个关系保持分片状态
– 其他关系可先连接起来，再被复制到各个站点
– 在各个站点上，其他关系副本与相应的第一个关系的片断连接
6.3 分片和复制算法
6 基于直接连接算法的查询优化处理
R1 R
2
R2
R2
R11
R12
R13
R21
R22
本地连接
Result
f
partition
union
R1 R2
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)}，找出响应时间小的保持分片关系
算法忽略了把结果传送到要求答案的用户站点的代价，和将部分结果组装成最终结果的代价，认为它们不大重要，
或者采用其他算法时这些部分没有太大差别。
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)为保持分片状态的关系
6.3 分片和复制算法
6 基于直接连接算法的查询优化处理
R1 R
2
R2
R2
F11
F13
F21
F22
本地连接
Result
f
partition
union
R1 R2
F12
6.3 分片和复制算法
6 基于直接连接算法的查询优化处理
∞
举例已知 R1分段 F11和 F12的大小为,|F11|=|F12|=50
R2分段 F21和 F22的大小为,|F21|= 100 |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*(100+200)+5*(50+300)=2550
同理,FT(Q,S2,R1) = 100+2*(100+200)+5*(50+300)=2450
因此,查询响应时间在 R1保持分片状态为 2550.
6.3 分片和复制算法
6 基于直接连接算法的查询优化处理令 R2保持分片状态,则,站点 S1的完成时间
FT(Q,S1,R2) = 50+2*(50+50)+5*(100+100)=1250
同理,
FT(Q,S2,R2) = 50+2*(50+50)+5*(200+100)=1750
因此,查询响应时间在 R2保持分片状态为 1750.
因为,
R1保持分片状态的响应时间 >R2保持分片状态的响应时间所以,选择 R2保持分片计算查询
6.3 分片和复制算法
6 基于直接连接算法的查询优化处理站 点关系
R1
R2
R3
S1 S2
F11 F12
F21 F22
R3 R3
设 R1和 R2在属性 A上站点依赖,查询 R1 ∞A R2 ∞B R3
6.4 站点依赖和数据复制结合
6 基于直接连接算法的查询优化处理设 R1和 R2在属性 A上站点依赖,查询 R1 ∞ R2 ∞ R3
第一个连接因为站点依赖，无传输处理
第二个连接因为存在 R3的副本,也没有传输处理
另外一个保证查询无传输的方法是 R1和 R2连接执行后，
形成一个关系 R4，它有两个片断：
一个由 F11 ∞ F21给出
一个由 F12 ∞ F22给出
最后由 R4和 R3的副本连接得到最后的结果
6.4 站点依赖和数据复制结合
6 基于直接连接算法的查询优化处理连接依赖定义：
如果 Ri 和 Rj 在属性 A上站点依赖
或者关系 Ri复制在关系 Rj各片断的站点上
或者关系 Rj复制在关系 Ri各片断的站点上
6.4 站点依赖和数据复制结合
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) =
6.5 Hash划分算法
6 基于直接连接算法的查询优化处理
利用 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) =
6.5 Hash划分算法
6 基于直接连接算法的查询优化处理
考察三个关系 R1,R2和 R3,它们在两个站点上，有两种情况：
– 在同一属性 A上连接,R1∞A R2∞AR3
在三个关系的片断上应用 Hash函数
使用新组建的片断，三个关系在属性 A上将满足站点依赖
经这种划分和数据传送之后，两个站点上的片断在属性 A上的连接就可以并行进行，合并执行结果给出答案
– 在不同属性上连接,R1∞A R2∞BR3
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上有偶数值
解决方法是允许这些元组在两个站点上都存在。
6.5 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)
6.5 Hash划分算法
6 基于直接连接算法的查询优化处理
站点依赖算法
– 无数据传递
– 可利用索引做本地连接
– 每个站点连接数据总量是 R，两个片段
分片和复制算法
– 数据传输总量是 R
– 数据传送后,可能要重新创建索引
– 每个站点的连接数据量是 (3/2)R,一个全关系和一个片断
Hash划分算法
– 数据传送量是 R
– 索引方面,比片段复制算法更低
– 每个站点的连接数据量同站点依赖
6.6 算法比较
6 基于直接连接算法的查询优化处理站点
S1 S2
关系 R1 F11 F12
R2 F21 F22
假定每个片段的大小是 R大小的一半 R/2
两个关系在同一个站点，
– R∞S，称外层关系为 R,内层关系为 S
– 嵌套循环法
顺序扫描外层关系 R，对于 R的每一元组扫描内层关系 S
查找在连接属性上一致的元组，组合起来构成结果的一部分
需要扫描一次关系 R和 Card（ R）次关系 S
– 排序扫描法
先把两个关系按照连接属性进行排序
然后按照连接属性值的顺序扫描这两个关系，使匹配的元组成为结果的一部分
对两个关系都扫描一次，但增加了排序代价
7.1 直接连接操作一般常用策略
7 直接连接操作的常用策略
两个关系在不同站点，关系 R和关系 S
– 两种传输方式
整体传输
– 如果传输 S,则保存 S（被多次扫描，传输量少）
– 如果传输 R，则 S可直接使用一次来到的 R元组，不保存 R(但传输量大）
按需传输
– 只传输需要连接的元组，一次一个元组，无需临时存储器
– 每次提取都要交换一次信息，传输代价高，只在高速局域网中才是合理的
– 三种选择连接站点的方法
R站点
S站点
其他站点
7.1 直接连接操作一般常用策略
7 直接连接操作的常用策略
一个操作内的并行一般是不可行的
多个操作间的并行是可行的
– 流水线并行
在查询表达式中，一个操作 A的输出元组作为第二个操作 B的输入
在第一个操作尚未产生全部的输出元组集合之前，第二个操作就可以在它的输入上进行工作
可以在不同的站点上运行 A和 B，在 A产生部分结果元组的同时,B来使用它们
– 独立的并行
查询表达式中，那些相互之间没有依赖关系的操作可以并行地执行
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计算并行地进行。
7.2 利用并行性的直接连接操作策略
7 直接连接操作的常用策略练习 1
有关系 R,S,T，如图所示
1,计算连接 R ∞ S ∞ T
2,计算机半连接 R∝ S,S∝ R,S∝ T,T∝ S,R∝ T,T∝ R
862
535
643
861
635
532
CBA
485
614
695
386
953
653
DCB
983
658
878
966
FED
SR T
练习 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站点执行 ∞
那种方案较优? R
S网络站点 1 站点 2
总 结
分布式查询优化概述（目标、准则和代价估算）
基础知识
关系代数回顾
等价变换规则
分布式查询分类和层次结构
基于关系代数等价变换的查询优化
基于半连接算法的查询优化处理
基于直接连接算法的查询优化处理（四类算法）
（ mycui369@126.com)
计算机应用技术 2007级研究生
1,分布式查询优化概述
2.分布式查询优化基础知识
3.分布式查询分类和层次结构
4.基于关系代数等价变换的查询优化处理
5.基于半连接算法的查询优化处理
6.基于直接连接算法的查询优化处理
7.直接连接操作的常用策略分布式数据库中的查询处理和优化第 3章查询处理问题
集中式
– 查询转换为代数表达式
– 从所有等价表达式中选择最优的代数表达式
分布式
– 除了集中式问题外，还有
– 站点之间交换数据的操作
– 选择最优的执行站点 (分布）
– 数据被传送的方式
1.1 分布式查询优化的目标
1 分布式查询优化概述
1.1 分布式查询优化的目标
1 分布式查询优化概述目标总代价最小响应时间最短集中式分布式
CPU代价（相对固定）
I/O代价（可变的，优化的目标）
CPU代价
I/O代价（访问磁盘）
通讯代价数据的分布和冗余增加了查询的并行处理的可能性，从而可以缩减查询处理的响应时间主要标准辅助标准
1.2 分布式查询优化准则和代价分析
1 分布式查询优化概述准则：
使得通讯费用最低和响应时间最短，即以最小的总代价，在最短的响应时间内获得需要的数据。
1,通讯费用与所传输的数据量和通信次数有关
2,响应时间和通信时间有关，也与局部处理时间有关查询代价分析
1,远程通讯网络局部处理时间可以忽略不计，减少通讯代价是主要目标
2,高速局域网传输时间比局部处理时间要短很多，以响应时间作为优化目标，局部处理时间是关键
例子
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,
通讯延迟 1sec
S,SC CSite A
Site B
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’;
1.3 分布式查询策略的重要性
1 分布式查询优化概述
代价公式
QC = I/O 代价 + CPU 代价 + 通讯代价
通讯代价
TC = 传输延迟时间 C0
+ (传输数据量 X * 数据传输速率 C1)
1.3 分布式查询策略的重要性
1 分布式查询优化概述
1.3 分布式查询策略的重要性
1 分布式查询优化概述策略 1:
A 传 C B 把关系 C 传输到 A 地,在 A 地处理查询
○ ○ T1 = 1 + (10**5 * 100 / 10**4)
S,SC 通信 1次 C ≈ 10**3 秒 ≈ 16.7 分钟
A 传 S,SC B 把关系 S 和 SC 传输到 B 地,在 B 地处理查询
○ ○ T2 = (2+10**4+10**5) * 100 / 10**4
S,SC 通信 2次 C ≈ 10100 秒 ≈ 28小时
A 问 10**5 B 先在 A地求出男学生的成绩元组有 10**5
○ ○ 再根据 C#的值询问 B地,核实是否 C=‘MATHS’
S,SC 答 10**5 C T3 ≈ (2 * 10**5 *1)=2*10**5 秒 ≈ 2.3 天策略 2:
策略 3:
六种查询策略
S,SC CA B
1.3 分布式查询策略的重要性
1 分布式查询优化概述
A 问 10 B 先在 B地求出 ‘MATHS’的元组,有 10个
○ ○ 再根据 C#的值询问 A 地的 S,SC的连接，
S,SC 答 10 C 核实是否为选修 ‘MATHS’的男生
T4 ≈ (2 * 10 * 1) = 20 秒
A 传输 10**5 B 先在 A地求出男生选课元组，有 10**5个
○ ○ 再把结果传输到 B 地,在 B 地执行查询，
S,SC 通信 1次 C T5 = 1 + (10**5 * 100) / 10**4
≈ 1000 秒 ≈ 16.7 分
A 传输 10 B 先在 B地求出为 ‘ MATHS’的元组，有 10个
○ ○ 再把结果传输到 A地,在 A地执行查询，
S,SC 通信 1次 C T6 = 1 + (10 * 100) / 10**4 ≈ 1 秒策略 4：
策略 5：
策略 6：
六种查询策略
S,SC CA B
相关表述记号
⒈ 设关系模式为 R(A1,A2,…,An) 。它的一个关系设为 R。
t∈ R表示 t是 R的一个 元组 。 t[Ai]则表示元组 t中相应于属性 Ai的一个 分量 。
⒉ 若 A={Ai1,Ai2,…,A ik}，其中 Ai1,Ai2,…,A ik是 A1,A2,…,An 中的一部分，
则 A称为属性列或域列。 t[A]=(t[Ai1],t[Ai2],…,t[A ik])表示元组 t 在属性列 A上诸分量的集合。则 表示 {A1,A2,…,An} 中去掉
{Ai1,Ai2,…,A ik} 后剩余的属性组。
A
2.1 关系代数知识回顾
2 分布式查询优化中的基础知识
⒊ 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上分量的集合。
2.1 关系代数知识回顾
2 分布式查询优化中的基础知识传统的集合运算
并运算
c1b2a2
c2b2a1
c1b1a1
CBA
c1b2a2
c2b3a1
c2b2a1
CBAR1 R2
c1b1a1
c1b2a2
c2b3a1
c2b2a1
CBA
R1∪ R2
设关系 R和关系 S具有相同的目 n（即两个关系都有 n个属性），且相应的属性取自同一个域，则关系 R与关系 S的并由属于 R或属于 S的元组组成。
其结果关系仍为 n目关系。记作,R∪ S={ t | t∈ R∨ t∈ S }
2.1 关系代数知识回顾
2 分布式查询优化中的基础知识
差运算
c1b2a2
c2b2a1
c1b1a1
CBA
c1b2a2
c2b3a1
c2b2a1
CBAR1 R2
c1b1a1
CBA
R1－ R2
设关系 R和关系 S具有相同的目 n，且相应的属性取自同一个域，则关系 R与关系 S
的差由属于 R而不属于 S的所有元组组成。其结果关系仍为 n目关系。记作：
R－ S={t|t∈R∧t S}∈
传统的集合运算
2.1 关系代数知识回顾
2 分布式查询优化中的基础知识
交运算
c1b2a2
c2b2a1
c1b1a1
CBA
c1b2a2
c2b3a1
c2b2a1
CBAR1 R2 A B C
a1 b2 c2
a2 b2 c1
R1∩R2
设关系 R和关系 S具有相同的目 n，且相应的属性取自同一个域，
则关系 R与关系 S的交由既属于 R又属于 S的元组组成。其结果关系仍为 n目关系。记作,R∩S={t|t∈R∧t∈S}
传统的集合运算
2.1 关系代数知识回顾
2 分布式查询优化中的基础知识两个分别为 n目和 m目的关系 R和 S的广义笛卡尔积是一个 (n+m)列的元组的集合。元组的前 n列是关系 R的一个元组，后 m列是关系 S的一个元组。若
R有 k1个元组,S有 k2个元组，则关系 R和关系 S的广义笛卡尔积有
k1× k2个元组。记作：
R1× R2
c1b1a1
c1b1a1
c1b1a1
CBA
c1b2a2
c2b3a1
c2b2a1
CBA
......
c2b3a1
c2b2a1
......
c2b2a1
c2b2a1c1b2a2
c2b2a1
c1b1a1
CBA
c1b2a2
c2b3a1
c2b2a1
CBAR1 R2
广义笛卡尔积
2.1 关系代数知识回顾
2 分布式查询优化中的基础知识专门的关系运算学号 学生姓名 所属系名 学生年龄
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(S#,SN,SD,SA)
2.1 关系代数知识回顾
2 分布式查询优化中的基础知识选择运算是从关系中选取使公式为真的元组。这是从行的角度进行的运算。
在关系 R中选择满足给定条件的元组，记做：
σF (R) ={ t | t ∈ R Λ F(t)=‘真 ’ }
F是一个公式，表示形式为由逻辑运算符 （ ∧,∨,?)连接各算术表达式组成 。
算术表达式的基本形式为,XθY,θ ={>,≥,<,≤,=,≠} 。
例 1 求计算机科学系 CS的学生
σ SD=‘CS’ (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)
(S’)
S# SN SD SA
S1 A CS 20
S2 B CS 21
S6 F CS 22
σ SD=‘CS’ (S)
选择运算在关系 R中选择满足给定条件的元组，记做：
σF (R) ={ t | t ∈ R Λ F(t)=‘真 ’ }
例 2 求计算机科学系 CS，年龄不超过 21岁的学生。
σ SD=‘CS’ ∧ SA≤21 (S)
(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
σ SD=‘CS’ (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
(S)
投影运算这是从列的角度进行的运算 。
例 3 πSN,SD (S) 即求得学生关系 S在学生姓名和所在系这两个属性上的投影结果。
πSN,SD (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中选择若干属性列组成新的关系。记做：
πA (R) ={ t[A] | t ∈ R}
投影之后不仅取消了某些列,还可能取消某些元组。
πSA (S)
SA
20
21
19
22
SN SD
A CS
B CS
C MA
D CI
E MA
F CS
连接运算（ θ 连接）
连接运算是从两个关系的笛卡尔积中选取属性间满足一定条件的元组。
记做,R S,其中,F是条件表达式，它涉及到对两个关系中的属性的比较。∞ F
S
2b5
2b3
10b3
7b2
3b1
EB
12b4a2
8b3a2
6b2a1
5b1a1
CBA
R
R S∞
C<E
10b38b3a2
10b36b2a1
7b26b2a1
10b35b1a1
7b25b1a1
ES.BCR.BA
例 4 设关系 R,S如下图,R S∞
C<E
等值 连接例 5 设关系 R,S如下图：
2b5
2b3
10b3
7b2
3b1
EBS
12b4a2
8b3a2
6b2a1
5b1a1
CBA
R
A R.B C S.B E
a1 b1 5 b1 3
a1 b2 6 b2 7
a2 b3 8 b3 10
a2 b3 8 b3 2
R S∞ R.
B=S.B
连接运算中有两种最为重要也最为常用的连接，
θ为,＝,的连接运算称为等值连接,
自然连接
A B C E
a1 b1 5 3
a1 b2 6 7
a2 b3 8 10
a2 b3 8 2
R S∞
A R.B C S.B E
a1 b1 5 b1 3
a1 b2 6 b2 7
a2 b3 8 b3 10
a2 b3 8 b3 2
R S∞ R.
B=S.B
另一种是自然连接。自然连接是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性组，并且要在结果中把重复的属性去掉。
例 6 关系 R,S的自然连结,R S∞
半连接在 R,S自然连接后仅保留对 R的属性的投影，记为,R ∝ S
例 7 关系 R,S的半连接：
A B C E
a1 b1 5 3
a1 b2 6 7
a2 b3 8 10
a2 b3 8 2
R S∞
A B C
a1 b1 5
a1 b2 6
a2 b3 8
R ∝ S2b5
2b3
10b3
7b2
3b1
EBS
12b4a2
8b3a2
6b2a1
5b1a1
CBAR
左外连接,对 R中任意元组，若 S中找不到匹配的元组，
则 S用空元组与之对应。 R的信息在左外连接的结果中都得到保留。
左外连接在 R,S自然连接时对不匹配的元组用空值来匹配。有左外连接、右外连接和全外连接之分例 8 关系 EMP,SAL的左外连结：
SALEMP
上海邓平长春李宏大连王小北京张丽
CITYENAME
3000赵刚
5000王小
6000张丽
SALARYENAME
NULL
NULL
5000
6000
SALARY
上海邓平长春李宏大连王小北京张丽
CITYENAME
EMP SAL
右外连结,对 S中任意元组，若 R中找不到匹配的元组，
则 R用空元组与之对应。 S的信息在右外连接的结果中都得到保留。
右外连接例 9 关系 EMP,SAL的右外连结：
SALEMP
上海邓平长春李宏大连王小北京张丽
CITYENAME
3000赵刚
5000王小
6000张丽
SALARYENAME
ENAME CITY SALARY
张丽 北京 6000
王小 大连 5000
赵刚 NULL 3000
EMP SAL
全外连接,对 R或 S中所有不匹配的元组，均用空元组分别匹配。 R,S的信息在全外连接的结果中都得到保留。
全外连接例 10 关系 EMP,SAL的全外连结：
SALEMP
上海邓平长春李宏大连王小北京张丽
CITYENAME
3000赵刚
5000王小
6000张丽
SALARYENAME
ENAME CITY SALARY
张丽 北京 6000
王小 大连 5000
李宏 长春 NULL
邓平 上海 NULL
赵刚 NULL 3000
EMP SAL
c1b2a1
c3b2a2
c6b6a4
c3b2a1
c6b4a3
c7b3a2
c2b1a1
CBA
R
c3
c1
c2
C
d2
d1
d1
D
b2
b2
b1
B
S例 11
除运算给定关系 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]。
Z
X
Y
除运算
c1b2a1
c3b2a2
c6b6a4
c3b2a1
c6b4a3
c7b3a2
c2b1a1
CBA
c3
c1
c2
C
d2
d1
d1
D
b2
b2
b1
B
R S
a1的象集为：
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） }
R÷ S = { tｒ [X] | tｒ ∈ R ∧ Yx?ΠY(S) }
R÷ S＝ { a1}
学号 课程号 学习成绩
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
S2 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)
学号 课程号 学习成绩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 20S2 B CS 21
S3 C MA 19S4 D CI 19
S5 E MA 20..,.,.,.
S
S SC∞
σ C# =‘C2’( )S SC∞
例 2 检索学习课程号为 C2的学生学号和姓名学号 学生姓名 所属系名 学生年龄 课程号 学习成绩
S# SNAME SD SA C# GRADES1 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 B
＝ πS#,SNAME(S ∞ C# =‘C2’ SC)πS#,SNAME(σ C# =‘C2’ ( S ∞ SC ))
例 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 SAS1 A CS 20
S2 B CS 21S3 C MA 19
S4 D CI 19S5 E MA 20
..,.,.,.
S
例 4 检索学习课程号为 C2或 C3的学生学号和所在系
πSN,SD( (σCN=‘数据库原理 ’ (C)) )S ∞ SC ∞
πS#,SD( s ∞πS# (σC# =‘C2’∨ C#=‘C3’(SC)) )
例 5 求至少选修 C2和 C3这两门课程的学生名。
C#
C2
C3
K
πSN( S ∞ (πS#,C# (SC) ÷ K))
πSN( S ∞ (πS#,C# (SC) ÷
πC# (σC# =‘C2’∨ C#=‘C3’(C)))
K ＝ π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 ( S ∞ (πC#,S# (SC) ÷ C) )
πSN ( S ∞ (πC#,S# (SC) ÷ πC# (σS#=‘S2’(SC))))
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))
2.1 用关系代数和 SQL语句表示一个查询
2 分布式查询优化中的基础知识关系代数基本操作：
并（ ∪ ）、交（ ∩）、笛卡尔积（ × ）、选择（?）、投影（?）
关系代数到处操作：
差（－）、除（ ÷ ）,θ 连接（ ∞ θ ）、自然连接（ ∞）、半连接（ ∝ ）
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)
2.2 查询树
2 分布式查询优化中的基础知识
sname
s.s# = sc.s#?c# =‘c03’
S SC
sname
s.s# = sc.s#
S?c#=‘c03’
SC
sname
∞
S?c# =‘c03’
SC
(a)对于 E1的查询树
(b)对于 E2的查询树
(c)对于 E3的查询树节点表示一个一元或二元操作符叶子表示已知关系树根表示查询结果
一元操作：只涉及一个操作对象
(SL),? (PJ)
二元操作：涉及两个操作对象
∪ (UN),∩（）,－ (DF),× (CP),
∞θ（）,∞ (JN),∝ (SJ),
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的属性
2.3 等价变换规则的概念和术语
2 分布式查询优化中的基础知识
交换率
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
2.3 等价变换规则的概念和术语
2 分布式查询优化中的基础知识
结合率
R B ( S B T ) = (R B S) B T)
B,二元操作
∞（ JN）,× （ CP）,∪ （ UN）,?等总成立
∝ （ SJ） 有问题
2.3 等价变换规则的概念和术语
2 分布式查询优化中的基础知识
分配率
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)
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)
–? PJB1,…,Bm (R ∝ S)
=?B1,…,Bm (? B1,…,Bm,C1,…Ck (R) ∝? C1,…Ck (S))
2.3 等价变换规则的概念和术语
2 分布式查询优化中的基础知识限定关系
定义,
R,QR 称为 R的限定关系,其中 QR表示查询逻辑片段就是一个限定关系
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]
2.3 等价变换规则的概念和术语
2 分布式查询优化中的基础知识
局部查询：只涉及本地,单个站点的数据,优化同集中式
选择和投影早做，中间结果大大减少
连接前进行预处理（属性排序、属性索引）
同时执行一串投影和选择操作
远程查询：也只涉及单个站点的数据,但要远程通讯,选择站点
选择查询应用最近的冗余分配站点
全局查询：涉及多个站点数据,优化复杂
3.1 分布式查询分类
3 分布式查询的分类与层次结构全局查询
具体化
– 对查询进行分解，确定查询使用的物理副本，落实查询对象
– 非冗余具体化，所有要访问对象只有一个副本
– 冗余具体化，多个副本，研究如何如何选择副本，使通信代价最小
确定操作执行的顺序
– 确定二元操作连接和并操作的顺序
先执行所有连接操作，再执行并操作
先执行部分并操作，再执行连接操作
– 选择和投影尽可能早进行
确定操作执行的方法
– 把若干个操作连接起来在一次数据库访问中，确定可用的访问路径
– 连接方法在查询优化中起着重要作用
确定执行的站点
– 执行站点不一定是发出查询的站点
– 考虑通讯费用和执行效率
3.1 分布式查询分类
3 分布式查询优化概述查询分解数据本地化全局优化局部优化分布关系上的查询表达分布关系上的代数表达分段关系查询表达带有通讯操作的段查询优化优化的局部查询表达全局模式段模式段的统计数据局部模式控制站点本地站点分布查询的层次
查询分解
– 将查询问题（ SQL）转换成一个定义在全局关系上的关系代数表达式
– 需要从全局概念模式中获得转换所需要的信息
数据本地化
– 具体化全局关系上的查询，落实到合适的片段上的查询
– 即将全局关系上的关系代数表达式变换为相应片段上的关系代数表达式
全局优化
– 输入的是分片查询，优化目标是寻找一个近于最优的执行策略（操作次序）
– 输出是一个优化的、片段上的关系代数查询
局部优化
– 输入是局部模式
– 它由该站点上的 DBMS进行优化
3.2 分布式查询处理的层次结构
3 分布式查询优化概述
基本原理
1,查询问题 ——〉 关系代数表达式
2,分析得到查询树
3,进行全局到片段的变换得到基于片段的查询树
4,利用关系代数等价变换规则的优化算法，尽可能先执行选择和投影操作
优化算法
1,连接和合并尽可能上提（树根方向）
2,选择和投影操作尽可能下移（叶子方向）
4.1 基本原理和实现方法
4 基于关系代数等价变换的查询优化处理
实现步骤和方法
– 转换一：查询问题 ——〉 关系代数表达式
– 转换二：关系代数表达式 ——〉 查询树
– 转换三：全局查询树分拆成片段查询树
– 优化：利用关系代数等价变换规则的优化算法，优化查询树，进而优化查询
4.1 基本原理和实现方法
4 基于关系代数等价变换的查询优化处理
4.2 查询优化处理举例
4 基于关系代数等价变换的查询优化处理全局关系
S(S#,SNAME,AGE,SEX)和 SC(S#,C#,GRADE)被水平分片
h 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.C# (S× SC)))
4.2 查询优化处理举例
4 基于关系代数等价变换的查询优化处理
SNAME
S.S#=SC.S# S.S#=SC.S#
S#,SNAME?S#,SNAME?GRADE>90?GRADE>90
SNAME
SEX=‘M’
S
SC?SEX=‘M’
U
S1[SEX=‘M’] S2[SEX=‘F’]
U
SC1[C#?‘C20’] SC1[C#>’C20’]
(a)全局关系上的查询树
(b)对应片段上的查询树变换∞
∞
4.2 查询优化处理举例
4 基于关系代数等价变换的查询优化处理
SNAME
S.S#=SC.S# S.S#=SC.S#
S#,SNAME
S#,SNAME
GRADE>90
SNAME
SEX=‘M’
U
SC1
[C#?‘C20’
（ c）把投影和选择下移后 的查询树 (d)一个简化 的查询树产生矛盾去掉一支
S#,SNAME?GRADE>90
S2[SEX=‘F’]
SEX=‘M’ SC1
[C#?‘C20’]
SC2
[C#?‘C20’]
S1[SEX=‘M’]
SC2
[C#?‘C20’
S1[SEX=‘M’]
U U
GRADE>90] GRADE>90]
∞ ∞
4.2 查询优化处理举例
4 基于关系代数等价变换的查询优化处理水平分片的查询优化的基本思想：
1,尽量把选择条件下移到分片的限定关系处
2,再把分片的限定关系与选择条件进行比较
3,去掉它们之间存在矛盾的相应片断
4,如果最后剩下一个水平片断，则重构全局关系的操作中，
就可去掉“并”操作（至少可以减少“并”操作的次数）
4.2 查询优化处理举例
4 基于关系代数等价变换的查询优化处理全局关系
EMP(EMP#,ENAME,SALARY,DEPT#,DNAME)
垂直分片,E1 (EMP#,DEPT#,DNAME)
EMP2(EMP#,ENAME,SALARY)
v
S
E1 E2,
查询问题：雇员的姓名和工资情况
ENAME,SALARY(EMP)
4.2 查询优化处理举例
4 基于关系代数等价变换的查询优化处理
ENAME,SALARY? ENAME?
EMP#,DEPT#,? EMP#,ENAME,?
DEPTNAM
E
SALARY
ENAME,SALARY?
EMP#,ENAME,?
SALARY
ENAME,SALARY?
EMP
E2,EMP#,ENAME,SALARY
去掉无关的片段移植到片段上去掉连接
E1,E2：
E1.EMP#=E2.EMP#∞
∞
4.2 查询优化处理举例
4 基于关系代数等价变换的查询优化处理垂直分片的查询优化的基本思想：
1,把垂直分片所用到的属性集，与查询条件中的投影操作所涉及的属性相比较，去掉无关的垂直片断
2,如果最后只剩下一个垂直片断与查询有关时，去掉重构全局关系的“连接”操作（至少可以减少“连接”操作的次数）
假定有两个关系 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
– R∞A=BS = ( S∝ A=B R)∞A=BR
=(S ∞A=B (?A (R) )∞A=BR
5.1 半连接操作
5 基于半连接算法的查询优化处理例子 1,R ∝ S
A B
2 a
10 b
25 c
30 d 25 w
3 x
10 y
15 z
32 x
A (R) = [2,10,25,30]
R ∝ S
S∝ R =
A C
10 y
25 w
A=A
A=A
A C
SR
10 b
25 c
A B
例子 2：半连接简化
R S T
R
S
T
B=B C=C
A=A
R,S,T的循环连接图对 R的充分简化
R’=R ∝ T
S’=S ∝ R’
T’=T ∝ S’
减少一个元组
R’’=R’ ∝ T’
S’’=S’ ∝ R’’
T’’=T’ ∝ S’’
减两个元组
R’’’=R’’ ∝ T’’ =? 减少三个元组一般：简化程序长度随着关系的元组数目增长线性增长。
对 R的另一个简化程序：
R’=R ∝ S T’ = T ∝ R’ S’ = S ∝ T’ （练习）
5.2 半连接表示连接的代价估算
5 基于半连接算法的查询优化处理
R S网络站点 1 站点 2
(1)? B(S)
(3) R’= R∝ A=B?B(S) (2)?B(S)
(4) R’= R∝ A=B?B(S) (5) R’∞ A=BS
关系的概貌
– Card(R) 片段关系 R的元组数目
– Size(A) 属性 A的大小 (即字节数 )
– Size(R) 片段关系的大小,属性大小之和
– Val(A[R]) 属性 A在 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])
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])
5.2 半连接表示连接的代价估算
5 基于半连接算法的查询优化处理
代价公式,T=C0+C1*X
1,在站点 2上做投影?B (S)
2,把?B (S)传到站点 1上，代价为：
– C0+C1* size (B)* val( B[S])
3,在站点 1上计算半连接,R’=R ∝ A=B S
4,把 R’从站点 1传到站点 2的代价为：
– C0+C1* size (R’)* card( R’)
5,在站点 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,取最优者
5.2 半连接表示连接的代价估算
5 基于半连接算法的查询优化处理
基本原理
1,通常有两次传输
2,但是传输的数据量和传输整个关系相比，要远远少
3,一般有,T半 <<T全
4,半连接的得益：当 card（ R） >>card（ R’），可减少站点间的数据传输量
5,半连接的损失：传输?B (S) =C0+C1* size (B)* val( B[S])
6,基本原理是在传到另一个站点做连接前，消除与连接无关的数据，减少做连接操作的数据量，从而减小传输代价
采用半连接优化算法的步骤
– 计算每种半连接方案的代价，并从中选择一种最佳方案
– 选择传输代价最小的站点，计算采用全连接的方案的代价
– 比较两种方案，确定最优方案
5.3 半连接算法优化原理和步骤
5 基于半连接算法的查询优化处理
SDD-1半连接算法
基础给定一个优化图 G,对 G中出现的关系已经施加了全部本地简化。
循环
a) 给出所有可能的半连接 ∝
b) 在有益 ∝ 中选择得益最大或者费用最低的 ∝,若没有这样的 ∝,则中止循环
c) 重新求取受影响的 ∝ 的得益与费用,Goto a)
后优化选出要求较少传输的 site来收集全部关系，在此执行 ∝
5.3 半连接算法优化原理和步骤
5 基于半连接算法的查询优化处理
半连接算法和直接连接算法区别
– 取决于数据传输和局部处理的相对费用
– 如果传输费用是主要的，采用半连接,SDD-1
– 如果本地费用是主要的，采用直接连接,System R*
四种基于直接连接的优化算法 （考虑关系分段）
– 利用站点依赖信息的算法
– 分片与复制算法
– 站点依赖和数据复制结合算法
– Hash划分算法
6.1 概述
6 基于直接连接算法的查询优化处理
6.2 利用站点依赖信息的算法
6 基于直接连接算法的查询优化处理站 点关系
S1 S2
F11 F12
F21 F22
R1
R2
∪
∞ ∞
站点依赖设关系 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都成立此时关系的连接操作无站点间数据传输
6.2 利用站点依赖信息的算法
6 基于直接连接算法的查询优化处理
Ri Fj1
Fj2
Fj3
Fi1
Fi2
Fi3
Rj
本地连接
Result
A
f(A) f(A)
Ri Rj
6.2 利用站点依赖信息的算法
6 基于直接连接算法的查询优化处理
∞
推论
– 若 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的连接操作能够以无数据传输的方式处理。
6.2 利用站点依赖信息的算法
6 基于直接连接算法的查询优化处理
算法描述
– 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中。
6.2 利用站点依赖信息的算法
6 基于直接连接算法的查询优化处理
6.3 分片和复制算法
6 基于直接连接算法的查询优化处理站 点关系
S1 S2
F11 F12
R2 R2
R1
R2
查询引用的某个关系的所有片段分布在这些站点上,其余被引用的关系复制到每一个选定的站点
R1 ∞ R2 = Ui (F1i ∞ R2)
算法可应用到涉及两个或两个以上的关系的查询
– 其中一个关系保持分片状态
– 其他关系可先连接起来，再被复制到各个站点
– 在各个站点上，其他关系副本与相应的第一个关系的片断连接
6.3 分片和复制算法
6 基于直接连接算法的查询优化处理
R1 R
2
R2
R2
R11
R12
R13
R21
R22
本地连接
Result
f
partition
union
R1 R2
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)}，找出响应时间小的保持分片关系
算法忽略了把结果传送到要求答案的用户站点的代价，和将部分结果组装成最终结果的代价，认为它们不大重要，
或者采用其他算法时这些部分没有太大差别。
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)为保持分片状态的关系
6.3 分片和复制算法
6 基于直接连接算法的查询优化处理
R1 R
2
R2
R2
F11
F13
F21
F22
本地连接
Result
f
partition
union
R1 R2
F12
6.3 分片和复制算法
6 基于直接连接算法的查询优化处理
∞
举例已知 R1分段 F11和 F12的大小为,|F11|=|F12|=50
R2分段 F21和 F22的大小为,|F21|= 100 |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*(100+200)+5*(50+300)=2550
同理,FT(Q,S2,R1) = 100+2*(100+200)+5*(50+300)=2450
因此,查询响应时间在 R1保持分片状态为 2550.
6.3 分片和复制算法
6 基于直接连接算法的查询优化处理令 R2保持分片状态,则,站点 S1的完成时间
FT(Q,S1,R2) = 50+2*(50+50)+5*(100+100)=1250
同理,
FT(Q,S2,R2) = 50+2*(50+50)+5*(200+100)=1750
因此,查询响应时间在 R2保持分片状态为 1750.
因为,
R1保持分片状态的响应时间 >R2保持分片状态的响应时间所以,选择 R2保持分片计算查询
6.3 分片和复制算法
6 基于直接连接算法的查询优化处理站 点关系
R1
R2
R3
S1 S2
F11 F12
F21 F22
R3 R3
设 R1和 R2在属性 A上站点依赖,查询 R1 ∞A R2 ∞B R3
6.4 站点依赖和数据复制结合
6 基于直接连接算法的查询优化处理设 R1和 R2在属性 A上站点依赖,查询 R1 ∞ R2 ∞ R3
第一个连接因为站点依赖，无传输处理
第二个连接因为存在 R3的副本,也没有传输处理
另外一个保证查询无传输的方法是 R1和 R2连接执行后，
形成一个关系 R4，它有两个片断：
一个由 F11 ∞ F21给出
一个由 F12 ∞ F22给出
最后由 R4和 R3的副本连接得到最后的结果
6.4 站点依赖和数据复制结合
6 基于直接连接算法的查询优化处理连接依赖定义：
如果 Ri 和 Rj 在属性 A上站点依赖
或者关系 Ri复制在关系 Rj各片断的站点上
或者关系 Rj复制在关系 Ri各片断的站点上
6.4 站点依赖和数据复制结合
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) =
6.5 Hash划分算法
6 基于直接连接算法的查询优化处理
利用 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) =
6.5 Hash划分算法
6 基于直接连接算法的查询优化处理
考察三个关系 R1,R2和 R3,它们在两个站点上，有两种情况：
– 在同一属性 A上连接,R1∞A R2∞AR3
在三个关系的片断上应用 Hash函数
使用新组建的片断，三个关系在属性 A上将满足站点依赖
经这种划分和数据传送之后，两个站点上的片断在属性 A上的连接就可以并行进行，合并执行结果给出答案
– 在不同属性上连接,R1∞A R2∞BR3
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上有偶数值
解决方法是允许这些元组在两个站点上都存在。
6.5 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)
6.5 Hash划分算法
6 基于直接连接算法的查询优化处理
站点依赖算法
– 无数据传递
– 可利用索引做本地连接
– 每个站点连接数据总量是 R，两个片段
分片和复制算法
– 数据传输总量是 R
– 数据传送后,可能要重新创建索引
– 每个站点的连接数据量是 (3/2)R,一个全关系和一个片断
Hash划分算法
– 数据传送量是 R
– 索引方面,比片段复制算法更低
– 每个站点的连接数据量同站点依赖
6.6 算法比较
6 基于直接连接算法的查询优化处理站点
S1 S2
关系 R1 F11 F12
R2 F21 F22
假定每个片段的大小是 R大小的一半 R/2
两个关系在同一个站点，
– R∞S，称外层关系为 R,内层关系为 S
– 嵌套循环法
顺序扫描外层关系 R，对于 R的每一元组扫描内层关系 S
查找在连接属性上一致的元组，组合起来构成结果的一部分
需要扫描一次关系 R和 Card（ R）次关系 S
– 排序扫描法
先把两个关系按照连接属性进行排序
然后按照连接属性值的顺序扫描这两个关系，使匹配的元组成为结果的一部分
对两个关系都扫描一次，但增加了排序代价
7.1 直接连接操作一般常用策略
7 直接连接操作的常用策略
两个关系在不同站点，关系 R和关系 S
– 两种传输方式
整体传输
– 如果传输 S,则保存 S（被多次扫描，传输量少）
– 如果传输 R，则 S可直接使用一次来到的 R元组，不保存 R(但传输量大）
按需传输
– 只传输需要连接的元组，一次一个元组，无需临时存储器
– 每次提取都要交换一次信息，传输代价高，只在高速局域网中才是合理的
– 三种选择连接站点的方法
R站点
S站点
其他站点
7.1 直接连接操作一般常用策略
7 直接连接操作的常用策略
一个操作内的并行一般是不可行的
多个操作间的并行是可行的
– 流水线并行
在查询表达式中，一个操作 A的输出元组作为第二个操作 B的输入
在第一个操作尚未产生全部的输出元组集合之前，第二个操作就可以在它的输入上进行工作
可以在不同的站点上运行 A和 B，在 A产生部分结果元组的同时,B来使用它们
– 独立的并行
查询表达式中，那些相互之间没有依赖关系的操作可以并行地执行
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计算并行地进行。
7.2 利用并行性的直接连接操作策略
7 直接连接操作的常用策略练习 1
有关系 R,S,T，如图所示
1,计算连接 R ∞ S ∞ T
2,计算机半连接 R∝ S,S∝ R,S∝ T,T∝ S,R∝ T,T∝ R
862
535
643
861
635
532
CBA
485
614
695
386
953
653
DCB
983
658
878
966
FED
SR T
练习 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站点执行 ∞
那种方案较优? R
S网络站点 1 站点 2
总 结
分布式查询优化概述（目标、准则和代价估算）
基础知识
关系代数回顾
等价变换规则
分布式查询分类和层次结构
基于关系代数等价变换的查询优化
基于半连接算法的查询优化处理
基于直接连接算法的查询优化处理（四类算法）
