第四章关系系统的查询优化.ppt

2、第二种方法 ①计算自然连接 读取总块数= 2100块 读数据时间=2100/20=105秒 中间结果大小=10000 （减少1000倍） 写中间结果时间=10000/10/20=50秒? ②选择操作 读取中间文件块，执行选择运算，花费时间50秒? ③投影操作? 把第二步的结果投影输出? 总时间＝(105＋50＋50)秒＝205秒=3.4分? 关系系统的查询优化 查询优化问题的提出（续） 3、第三种方法 Q3=πSname(Student ?SC.Cno=‘2’(SC)) ①选择操作 读SC表总块数= 10000/100=100块 读数据时间=100/20=5秒? 中间结果大小=50条（满足条件的元组只有50个），不 必使用中间文件。 ②自然连接操作 读Student表总块数= 1000/10=100块（只需读一遍该表） 读数据时间=100/20=5秒? ③ 投影操作 把连接结果投影输出。 总时间＝5＋5秒＝10秒 关系系统的查询优化 查询优化问题的提出（续） 四、关系代数的优化规则 关系代数优化策略是通过对关系代数表达式的等价变换来提高查询效率。 关系代数表达式等价 指把相同的关系代入两个关系代数表达式所得到的结果是相同的。 两个关系表达式E1和E2是等价的，记为E1 ≡E2。 关系系统的查询优化 关系代数的优化规则（续） 1、常用的等价变换规则 设E1、E2是关系代数表达式，F是条件表达式。 （1）连接、笛卡尔积交换律 E1×E2 ≡ E2×E1 E1 E2 ≡ E2 E1 E1 E2 ≡ E2 E1 （2）连接、笛卡尔积的结合律 (E1×E2 ) ×E3≡ E1×(E2 ×E3 ) (E1 E2 ) E3 ≡ E1 (E2 E3 ) (E1 E2 ) E3 ≡ E1 (E2 E3 ) 关系系统的查询优化 F F F1 F1 F2 F2 常用的等价变换规则（续） （3）投影的级联（串接定律） 假设： 1) E是关系代数表达式 2) Ai(i=1，2，…，n), Bj(j=l，2，…，m)是属性名 3) {A1, A2, …, An}是{Bl，B2，…，Bm}的子集 。 则： （4）选择的级联（串接定律） 选择的串接律说明选择条件可以合并。 关系系统的查询优化 关系代数等价变换规则（续） （5）选择与投影的交换律 假设: 选择条件F只涉及属性A1，…，An 假设: F中有不属于A1, …,An的属性B1,…,Bm 关系系统的查询优化 关系代数等价变换规则（续） （6）选择与笛卡尔积的交换律 假设：F中涉及的属性都是E1中的属性，则 假设：F=F1∧F2，并且F1只涉及E1中的属性，F2只涉及E2中的属性，则由上面的等价变换规则1，4，6可推出 假设： F=F1∧F2，F1只涉及E1中的属性，F2涉及E1和E2两者的属性，则 关系系统的查询优化 ?F ( E1 ×E2) ≡ ?F1 ∧ F2(E1 ×E2) ≡ ?F2 ( ?F1 (E1 ×E2)) ≡ ?F2 ( ?F1 (E1 )×E2) ?F ( E1 ×E2) ≡ ?F1 ∧ F2(E1 ×E2) ≡ ?F1 ( ?F2 (E1 ×E2)) ≡ ?F1 ( ?F2 (E2 )×E1) ≡?F1 (E1) ×?F2 (E2) 关系代数等价变换规则（续） （7）选择与并的分配律 假设：E=E1∪E2，E1，E2有相同的属性名 ?（8）选择与差运算的分配律 假设：E1与E2有相同的属性名 （9）选择对自然连接的分配律 假设：F只涉及E1和E2的公共属性 ?F(E1 E2) ≡ ?F(E1) ?F(E2) 关系系统的查询优化 关系代数等价变换规则（续） （10）投影与笛卡尔