第9章 关系数据库的查询优化.ppt

An Introduction to Database System 一、问题的提出 一个用户查询，系统实现时均使用一个与之相应的关系代数表达式去求解。同一查询等价的关系代数表达式不同，就会出现不同的求解路线。 例：求选修了课程2的学生姓名 ? SELECT Student.Sname FROM Student, SC WHERE Student.Sno=SC.Sno AND SC.Cno=2; 等价的关系代数表达式如下： Ｑ1＝ ПＳname(бStudent.Sno=SC.Sno ∧SC.Cno=2 (Student×SC))? Ｑ2＝ ПＳname(бSC.Cno= 2 (Student SC)) Ｑ3＝ ПSname(Student бSC.Cno= 2 (SC))? 二、 查询优化的一般准则 选择运算应尽可能先做 ? 目的：减小中间关系 在执行连接操作前对关系适当进行预处理 在连接属性上建立索引——索引连接方法 按连接属性排序——排序合并连接方法? 投影运算和选择运算同时做 目的：避免重复扫描关系 将投影运算与其前面或后面的双目运算结合 目的：减少扫描关系的遍数 某些选择运算＋在其前面执行的笛卡尔积 === 连接运算 例：бStudent.Sno=SC.Sno (Student×SC) ? ? Student SC 提取公共子表达式 三、关系代数等价变换规则 设E1、E2等是关系代数表达式，F是条件表达式 1、连接、笛卡尔积交换律 E1× E2≡ E2×E1 E1 E2≡E2 E1 E1 F E2≡E2 F E1 ? 2. 连接、笛卡尔积的结合律 (E1×E2) × E3 ≡ E1 × (E2×E3) (E1 E2) E3 ≡ E1 (E2 E3) (E1 E2) E3 ≡ E1 (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. 投影与笛卡尔积的交换 假设：E1和E2是两个关系表达式， A1，…，An是E1的属性， B1，…，Bm是E2的属性 π A1,A2, …,An,B1,B2, …,Bm （E1