A=B
S
分布式数据库
35 半连接的传输代价: T半=2*c0+c1*(Size(B)*Val(S[B]) +Size(R)*Card(R’))
S1
Gender = ‘M’ G > 90
∪
S2
∪
SC1
SC2
分布式数据库
将选择条件与水平分片条件结合， 去掉矛盾的分支
sname
29
Sex = ‘M’
∪ Grade > 90
S1 Grade > 90 SC1
SC2
分布式数据库
例：垂直分片的优化 Emp(Eno, name, sal, dno,dname)
+ 通信代价
2）响应时间 = 局部处理时间 + 通信时间 （与并行处理程度有关） 总代价与响应时间可以不一致
分布式数据库
查询优化的准则及代价估算
9
以最小的总代价、在最短的时间内获得需要 的数据
通信网络的类型影响通信费用，最终影响查 询优化的方法 •远程通信网：以减小通信代价为主 •高速局域网：以减小局部处理时间为主
分布式数据库 策略4：先在B站点找出‘Maths’元组（假设最多 有10门），再根据Cno向A站点核查S和SC6 的连接，选‘Maths’的是否是男生。 站点B 站点A 通信20次
C S, SC （问答各10次） T4 = 2 * 10 *1秒 = 20秒 策略5：先在A站点找出男生选课成绩（最多 100000个元组），再把结果传到B站点,在B 站点执行查询。 站点B 站点A 通信1次 S, SC （传100000个元组） C T5 = 1 + 100000 *100/10000 16.7 (分)
③ 计算R’=R∝A=B S’
④传输 R’
⑤
计算R’ ∞
A=B
S
分布式数据库
传输代价：T=c0+c1*X
34
① 在Site2上计算S’=πB (S)
② 将S’从Site2传输到Site1: T1=c0+c1*Size(B)*Val(S[B]) ③在Site1上计算R’=R∝A=B S’ ④ 将R’从Site1传输到Site2: T2=c0+c1*Size(R)*Card(R’) ⑤ 在Site2上计算R’ ∞
12
E1= E2=
sn (s.sno =sc.sno o = ‘c1’(S SC)
)
sn (s.sno =sc.sno(S(o =‘c1’(SC)) )) E3= sn ( S (o = ‘c1’(SC) ) )
查询树
分布式数据库
sn
–
–
分布式数据库
例 S(Sno, Sn, Age, Gender) SC(Sno, Cno, G)
分片模式
25
‘ S1 M’ 用户查询：
S h ‘F’ S2
SC h Cno > 20 Cno 20 SC1 SC2
SELECT distinct Sn
FROM S, SC WHERE S.Sno = SC.Sno and Gender = ‘M’ and G > 90
二元运算结合律
18
R B1( S B2 T) ( R B1 S ) B2 T B1 、B2不为 ‘’, ‘’, ‘∝ ’
• 一元运算对）B （U（S））
F( R S ) F( R ) S
F只涉及R的属性
F( R S ) F1( R ) F2( S ) F = F1F2 , 且F1、F2分别只涉及R、S的属性
3
AND Cn = ‘Maths’
分布式数据库
代价估算： T = 传输延迟时间 + 传输数据量 / 数据传输速率
4
= 传输次数 * 1 + 传输的bit数 / 10000 策略1：把关系C传到A站点；在A站点进行处理。 站点B 站点A 通信一次
（传C) C S, SC T1 = 1 + 100000 *100 / 10000 16.7 （分）
o = ‘c1’ S SC
sn
sn
13
s.sno =sc.sno s.sno =sc.sno

S S
o = ‘c1
SC
o = ‘c1’
SC
（E1查询树）
（E2查询树）
（E3查询树）
分布式数据库
关系运算的等价变换规则
等价的定义 • 关系代数表达式E1与E2是等价的，如果用相同的 关系代入两个关系表达式的相应关系时，所得得 结果相同。记作： E1 E2 关系代数运算 • 一元运算：选择（σ ），投影（π ） • 二元运算：并（∪ ），交（∩ ），差（），除 （÷），笛卡儿积（），连接（∞），半连接 （∝）
– 关系数据库一般采用SQL作为接口语言
Select Sn from s,sc Where s.Sno=sc.Sno and Cno=‘c1’
分布式数据库
关系代数表达式
– 关系模型有三类查询语言 – 用关系代数表达式可以方便地表示查询要求 – 关系代数表达式可以表示出各操作的执行顺序， 可以利用等价变换，实现查询优化
•
一元运算幂等律
16
U(U(R)) U(R)
A( B( R ) ) A(R)
其中， A B
F1( F2( R ) ) F1 F2( R )
•
一元运算交换律
U1(U2(R)) U2(U1(R))
若U1、U2都是选择运算()，上式成立；
若U1、U2 都是投影运算( )，要求投影涉及相同的属性。
分布式数据库
假设：每个元组的长度为100 bit; 通信系统传 输速率为10000bit / 秒；通信延迟时间为1秒。 查询选修‘Maths’课的男生的学号和姓名
SELECT Sno, Sn FROM S, SC, C WHERE S.Sno = SC.Sno AND o = o AND Sex = ‘M’
14
分布式数据库
等价变换规则 • 与空值有关的规则
15
R ∪φ R
Rφ φ
R ∩φ φ
R ∞ φ φ
R-φ R
R ∝φ φ
φ -Rφ
φ ∝ R φ
R ∞ φ φ σ F(φ ) φ
•
π Aφ φ
R-Rφ
自身操作的变换规则
R∩ RR R∞RR
R∪ R R
分布式数据库
分布式数据库
F( R ∪ S ) F( R ) ∪ F( S ) F( R S ) F( R ) F( S ) F( R ∞ S ) F( R ) ∞ S F只涉及R的属性
19
F( R ∞ S ) F1( R ) ∞ F2( S )
F = F1F2 , 且F1、F2分别只涉及R、S的属性 A, B( R S ) A(R) B(S) A、B分别只涉及R、S的属性 A( R ∪ S ) A(R) ∪ A(S)
分布式数据库
3.3查询的分类与处理步骤
查询的分类
20
局部查询查询
只涉及本地站点的数据
优化策略与集中式数据库类似 1.先做选择和投影 2.选择合适的连接策略，按连接属性建索引 3.将一些操作组合起来，减少扫描次数 4.找出公共表达式
远程查询
只涉及远程站点的数据 优化策略与局部查询类似 有多个副本时，选择通信代价较低的站点
G > 90
分布式数据库
27
sn Gender = ‘M’ G > 90 sn
s.sno =sc.sno

S
SC S SC
Gender = ‘M’ G > 90 S SC
分布式数据库
将全局查询树转换为基于片段的查询树 sn
28
sn
Gender = ‘M’ G > 90 S SC
分布式数据库
若U1、U2 分别是选择和投影运算时： F ( A(R) ) A( F ( R ) ) 当 F中的属性仅涉及A 时 A( F ( R ) ) F ( A(R) ) 成立。
•
17
永真
二元运算交换律
RBSSBR
B 不为 ‘’, ‘’, ‘∝ ’
分布式数据库
•
22
分布式数据库
3.4 基于关系代数等价变换的优化算法
思路
用户查询 关系代数 表达式
23
查询树
基于片段 的查询树
优化的 查询树
分布式数据库
24
优化策略
–
将连接、并运算向根部移动，选择、投影 移动到叶子 将选择条件与水平分片条件结合，去掉矛 盾的分支 将投影属性与垂直分片属性比较，去掉无 关的分支
分布式数据库
查询优化的准则及代价估算
10
查询代价
QC = I/O代价 + CPU代价+ 通信代价
通信代价估算
C(X) = C0 + C1 * X
C0: 一次通信的延迟时间
C1：数据传输率（单位：秒 / bit）
X：传输的数据量（单位：bit)
分布式数据库
3.2查询优化基础
查询表达式
11
SQL语言
分布式数据库
转成关系代数表达式： Sn ( Gender = ‘M’ G > 90( S.Sno=SC.Sno( S SC ) ) 将关系代数表达式转 换成查询树并优化 sn
26
Gender = ‘M’
G > 90
s.sno =sc.sno S SC
sn
Gender = ‘M’
30
分片模式
Emp V Emp2(Eno, name, sal)