《数据库管理及应用》课程电子教案（PPT课件）4.01 Optimitation of Query 查询优化

3.08 optimization of Query 查询优化 2 159

159 §3.08 optimization of Query 查询优化

、 Putting the questions (问题的提出) 一个用户查询，系统实现时 均使用一个与之相应的关系代数表达式去求解。 同一查询等价的关系代数表达式的不同，就会 出现不同的求解路线。 例：有一SEQUEL语言书写的查询： SELECT C#.GRADE FROM S,SC WHERE S.S#=SC.S#AND S.NAME=CHAN 160

160 一、Putting the questions (问题的提出) 一个用户查询,系统实现时 均使用一个与之相应的关系代数表达式去求解。 同一查询等价的关系代数表达式的不同，就会 出现不同的求解路线。 例：有一SEQUEL语言书写的查询： SELECT C#,GRADE FROM S，SC WHERE S.S#=SC.S# AND S.NAME=‘CHAN’

查询问题： 假定姓名唯一，则 S.NAME=CHAN 可以确定唯一的学号S.S# 用S.S#扫描$C关系匹配：S.S#=SC.S#并投 影其C#,GRADE 用户查询：‘CHAN所选课程课号和相应成绩。 161

161 查询问题： 假定姓名唯一,则: S.NAME=‘CHAN’ 可以确定唯一的学号S.S# 用S.S#扫描SC关系匹配： S.S# =SC.S#并投 影其C#，GRADE 用户查询：‘CHAN’所选课程课号和相应成绩

实际解释过程： 由：S.S#=SC.S# 被操作关系：S,SC,知 先自然连接，产生如下关系： S# NAME AGE SEX C# GRADE 然后选择：NAME=CHEN,投影C#, GRADE

实际解释过程： 由： S.S#=SC.S# 被操作关系：S，SC，知： 先自然连接，产生如下关系： S# NAME AGE SEX C# GRADE 然后选择：NAME =CHEN ，投影C#，GRADE

系统可用多种等价的关系 代数表达式，实现该操作： T1=11C#,GRADE (òS.S#=SC.S#NAME=CHAN(SxSC)） T2=Π6#， GRADE NAME-CHAN (S ☒ sc)) T3=Πc*, GRADE (8 NAME=CHAN(s) 运算复杂性比较 162

162 系统可用多种等价的关系 代数表达式，实现该操作： T1=C#，GRADE（S.S#=SC.S#NAME=‘CHAN’(SSC)) T2=C#，GRADE （NAME=CHAN(S SC)) T3=C#，GRADE （ NAME=CHAN(s) SC) 运算复杂性比较

● 二、优化的一般策略 1、提前执行选择运算 2、合并乘积与其后的连接为连接运算 3、在一次扫描中，同时执行一连串的选择 和投影 4、提前对文件做予处理，如建立倒排文件 5、存储公共表达式 163

163 二、优化的一般策略 1、提前执行选择运算 2、合并乘积与其后的连接 为连接运算 3、在一次扫描中，同时执行一连串的选择 和投影 4、提前对文件做予处理，如建立倒排文件 5、存储公共表达式

三、关系代数表达式的 等价代换规则： 1、投影串结合： Π，2.，。A(B1.。,w(E)三ⅡA,A2,。。A(E） 相连的两次投影，必然有： {A1,...AN}C[B1,...,BM} 内层投影无意义 2、选择串结合： ⑧1(82(E))≡⑧1F2(E 两次选择操作在一次扫描中完成

164 三、关系代数表达式的 等价代换规则： 1、投影串结合： A1,A2。。。AN(B1。。。,BM (E))   A1,A2,。。。AN(E) 相连的两次投影，必然有： {A1,…,AN} {B1,…,BM} 内层投影无意义 2、选择串结合： F1（ F2（E）） F1F2 （E） 两次选择操作在一次扫描中完成

3、选择与投影交换 若选择公式F中只涉及A1,,AN则： Π A1.A2,AN(G(E)）三C（LA1A2AN(E) 规则上先选择、先投影，结果同 实现上是一次扫描中完成，且不受上述条 件限制 4、选择和乘积交换 有如下几种情况： 165

165 3、选择与投影交换 若选择公式F中只涉及A1,…,AN 则：  A1,A2,…,AN(F（E））  F（ A1,A2,…,AN(E)） 规则上先选择、先投影，结果同 实现上是一次扫描中完成，且不受上述条 件限制 4、选择和乘积交换 有如下几种情况：

公式F中只涉及E1或E2属性 δ-(E1×E2)≡δ(E1)×E2 δ(E1×E2)≡E1×δ=(E2) F=F1入F2,且F1只涉及E1,F2只涉及E2属性 δ(E1×E2)≡⑧1(E1)×2(E2) 若F1涉及E1、E2,而F2只涉及E2属性 ⑧(E1×E2)≡d-1(E1×⑧2(E2)) 166

166 公式F中只涉及E1或E2属性 F（E1E2） F（E1） E2 F（E1E2） E1F（E2） F=F1F2，且F1只涉及E1，F2只涉及E2属性 F（E1E2） F1（E1） F2（E2） 若F1涉及E1、E2，而F2只涉及E2属性 F（E1E2） F1（E1 F2（E2））

5、选择与合并交换 E1、E2属性相同： δ(E1UE2)≡ δ(E1)Uδp(E2〉 6、选择与求差交换 δ(E1-E2)≡δ(E1)-δ(E2)≡δ(E1)-E2 7、投影与合并交换 若E1、E2同类 ΠAIAN(EIUE2)≡ΠAIAN(E1)UA1ANCE2〉 16

167 5、选择与合并交换 E1、E2属性相同： F（E1E2） F（E1） F（E2） 6、选择与求差交换 F（E1-E2） F（E1）- F（E2） F（E1）- E2 7、投影与合并交换 若E1、E2同类  A1,,…,AN（E1E2）  A1,,…,AN（E1）   A1,,…,AN（E2）