关系查询和查询优化.ppt

关系查询和查询优化
第一页，讲稿共二十四页哦
关系数据库系统的查询处理
查询分析
查询检查
查询优化
查询执行
词法分析
语法分析
语义转换
符号名转换
安全性检查
完整性检查
查询树
代数优化
物理优化等
1 (E2 E3)
F F F F
第十一页，讲稿共二十四页哦
3. 投影的串接定律
π A1,A2, ,An(π B1,B2, ,Bm(E))≡ π A1,A2, ,An (E)
假设：
1) E是关系代数表达式
2) Ai(i=1，2，…，n), Bj(j=l，2，…，m)是属性名
3) {A1, A2, …, An}构成{Bl，B2，…，Bm}的子集
第十二页，讲稿共二十四页哦
4. 选择的串接定律
бF1 （ б F2（E））≡ бF1∧ F2(E)
选择的串接律说明 选择条件可以合并
这样一次就可检查全部条件。
5. 选择与投影的交换律
(1)假设: 选择条件F只涉及属性A1，…，An
бF (πA1,A2, ,An(E))≡ πA1,A2, ,An(бF(E))
(2)假设: F中有不属于A1, …,An的属性B1,…,Bm
π A1,A2, ,An ( бF (E))≡ πA1,A2, ,An(бF (πA1,A2, ,An,B1,B2, ,Bm(E)))
第十三页，讲稿共二十四页哦
6. 选择与笛卡尔积的交换律
(1) 假设：F中涉及的属性都是E1中的属性
бF (E1×E2)≡бF (E1)×E2 
(2) 假设：F=F1∧F2，并且F1只涉及E1中的属性，
F2只涉及E2中的属性
则由上面的等价变换规则1，4，6可推出：
бF(E1×E2) ≡б F1(E1)×бF2 (E2) 
(3) 假设： F=F1∧F2，并且 F1只涉及E1中的属性，
F2涉及E1和E2两者的属性
бF(E1×E2)≡б F2(бF1(E1)×E2)
它使部分选择在笛卡尔积前先做
第十四页，讲稿共二十四页哦
7. 选择与并的分配律
假设：E=E1∪E2，E1，E2有相同的属性名
бF(E1∪E2)≡ бF(E1)∪ бF(E2)
 8. 选择与差运算的分配律
假设：E1与E2有相同的属性名
бF(E1-E2)≡ бF(E1) - бF(E2)
9. 选择对自然连接的分配律
бF(E1 E2)≡ бF(E1) бF(E2)
  F只涉及E1与E2的公共属性
第十五页，讲稿共二十四页哦
10. 投影与笛卡尔积的分配
假设：E1和E2是两个关系表达式，
A1，…，An是E1的属性，
B1，…，Bm是E2的属性
π A1,A2, …,An,B1,B2, …,Bm （E1×E2)≡
π A1,A2, …,An（E1)× π B1,B2, …,Bm(E2)
l1. 投影与并的分配
假设：E1和E2 有相同的属性名
πA1,A2, …,An(E1∪E2)≡πA1,A2, …,An(E1)∪πA1,A2, …,An(E2)
第十六页，讲稿共二十四页哦
查询树的启发式优化
启发式规则的代数优化,是对关系代数表达式的查询树进行优化,其典型的规则有:
选择运算应尽可能先做  
目的：减小中间关系
投影运算和选择运算同时做
目的：避免重复扫描关系
把投影运算与其前面或后面的双目运算结合
目的：减少扫描关系的遍数
第十七页，讲稿共二十四页哦
某些选择运算＋在其前面执行的笛卡尔积===> 连接运算
例：= (Student×SC)
 
  Student SC
提取公共子表达式
第十八页，讲稿共二十四页哦
关系代数表达式的优化算法
算法：关系表达式的优化。
输入：一个关系表达式的查询树。
输出：优化的查询树。
方法：
(1) 分解选择运算
利用规则4把形如бF1 ∧F2 ∧ … ∧ Fn (E)变换为
бF1 (бF2(… (бFn(E))… ))
(2) 通过交换选择运算，将其尽可能移到叶端
对每一个选择，利用规则4～8尽可能把它移到树的叶端。
(3) 通过交换投影运算，将其尽可能移到叶端