数据库-db-chapter计算机科学技术学院

第八章物 •问题的•启发式关系代数优化•启发式关系演算优化•基于复杂性估计的查询优化问题的提––SELECTDISTINCTFROMS,WHERES.S#=SC.S#ANDQ1=ΠSN(σ(S.S#=SC.S#)∧(SC.C#="C2")Q2=ΠSN(σSC.C#="C2" S.S#=SC.S#Q3=ΠSN((σSC.C#="C2" 问题的提Q1=ΠSN(σ(S.S#=SC.S#)∧(SC.C#="C2")Q1的执行过程计算S和SC的笛卡儿①使用一个内存缓冲区BS读入某个关系(如S)的未处理元组②使用另一个内存缓冲区BSC读入另一个关系(如SC)的未处理元组③把BS中的每个元组和BSC中每个元组相连接，并送入出缓冲区④如果BO已满则写到一个临时文件⑤重复步骤②～④，直至SC中元组全部处理完⑥重复步骤①～⑥，直至S中元组全部处理完S中有1000个学生S中有1000个学生记SC中有10000个选课SC中选修C2课程的记录为50Q1的时间开销设BS能装50个S的元组，BSC能装100个SC的元组，每个磁盘块能装10个S的元组或100个SC的元组。每个(1)计算S和SC 时间开销：105秒（读）＋100000秒（写(2)时间开销：100000秒（读(3)时间开销：0忽略CPU时间，Q需要的处理时间大 问题的提Q2=ΠSN(σSC.C#="C2"(1)

S.S#=SC.S# (3)把第2S中有1000个学生记SCS中有1000个学生记SC中有10000个选课SC中选修C2课程的记录为50Q2的时间开销设BS能装50个S的元组，BSC能装100个SC的元组，每个磁盘块能装10个S的元组或100个SC的元组。每个(1)设自然连接的结果为1000个元组时间开销：105秒（读）＋10秒（写(2)时间开销：10秒（读(3)时间开销：0忽略CPU时间，Q2需要的处理时间大约125问题的提Q3=ΠSN((σSC.C#="C2"(1)对SC

S表，把读入的S元组和内存中的SC元组作连(3)把第2问题的提S中有1000个学生记S中有1000个学生记SC中有10000个选课SC中选修C2课程的记录为50每个磁盘块能装10个S的元组或100个SC的元组。每个(1)对SC时间开销：5秒（读(2)时间开销：5秒（读(3)时间开销：0若SC表的C#字段有索引，Q3的处理时间将进一步减问题的提•问题的•启发式关系代数优化•启发式关系演算优化•基于复杂性估计的查询优化启发式关系代数启发式关系代数关系代数等价变换 设E1和E2是两个关系代数表达式。如果E1和E2表示相同的关系，则称E1和E2等价，记作启发式关系代数关系代数等价变换规律（12类1.c1AND...ANDcn(E)≡c1(c2(...(cn2.c1(c2(E))≡c2(c1(E)3.ΠL1(ΠL2(...(ΠLn(E))...))≡ΠL1其中E是关系代数表达式，Li是投影属性集合，而且L2...Ln启发式关系代数关系代数等价变换规律（12类4ΠL(C(E))≡C(ΠL(E)其中，E是关系代数表达式，L是投影属性集合，C选择条件，C只涉及L中的属性ΠL(C(E)≡ΠL(CΠLB1Bm(E)C还涉及L以外的属性B1、...、5 其中，E1和E2是关系代数表达式，C是连接条6.其中，E1和E2是关系代数表达式启发式关系代数关系代数等价变换规律（12类7.(1)(2)

C2E3≡ C1

C2(3)(E1∪E2)∪E3≡(4)(E1∩E2)∩E3≡8.(1)C1 C2E2)≡(C1 C2其中，C1是选择条件，C2是连接条件，E1和E2(2)C1 C2E2)≡(C11 C2(C12式，C1=C11∧C12，C11仅涉及E1的属性，C12仅涉及E2的属性(3)用×代替上边两个等价式中 C2，就可以得到选择与乘积的分配启发式关系代数关系代数等价变换规律（12类9.投影、连接 (1)ΠL CE2)≡(ΠL1 C(ΠL2其中C是连接条件，E1和E2是关系代数表达式，L=L1∪L2是投影属性集合，L1仅涉及E1的属性，L2仅(2)ΠL CE2)≡ΠL((ΠL1 C(ΠL2其中，C是连接条件，E1和E2是关系代数表达式，C涉E1的属性A1、...、Ai、...、Ak和E2的属性B1、...、Bj、...、Bp，L{Ai,...,Ak,Bj,...,Bp}，L1={A1，...，Ai，...，Ak}，L2={B1，...,Bj，...，Bp}(3)用×代替上边两个等价式中的 启发式关系代数关系代数等价变换规律（12类10.(1)C(E1∪E2)≡(C(E1))∪(C(2)C(E1∩E2)≡(C(E1))∩(C(3)C(E1－E2)≡(C(E1))－(C11.(1)ΠL(E1∪E2)≡(ΠL(E1))∪(ΠL(2)ΠL(E1∩E2)≡(ΠL(E1))∩(ΠL(3)ΠL(E1－E2)≡(ΠL(E1))－(ΠL12.除了上述规律以外，还有很多其他等价变换规律。例如，使用DMra启发式关系代数启发式代数优化给定一个关系代数表达式，可以应用一组启发式规则对其进行等价变换，产生一个具有需要注意，这些规则不能保证一定产生最优启发式代数优化规则14.ΠL(C(E))≡C(ΠL(E)ΠL(CE≡ΠL(CΠLB1Bm(E8.选择、连接和笛卡儿乘积的分C1 C2E2)≡(C1

C2C1 C2E2)≡(C11 C2(C1210.选择与集合操作的分C(E1∪E2)≡(C(E1))∪(CC(E1∩E2)≡(C(E1))∩(CC(E1－E2)≡(C(E1))－(C启发式代数优化规则2把某些选择操作与邻接 乘积相 规则3同时执行相同关系上的多个选择和投规则 启发式代数优化规则5如果一个反复出现的公共表达式的结果不是一个很大的关系，而且从外存读入它的时间小于计算它的时间，可以只计算这个表达式一次并其在一个查询树中，叶子结点表示关系，内结点表示关系代数操查询树以自底向上的方式执行：当一个内结点的操作分量可用时，这个内结点所表示的操作启动执行，执行结束后用结果关系代替这个内结点。构造查询的内部表示是查询处理的第一步。给定一个用高级语言定义的查询，需要两步来构造该查询第一步把用高级语言定义的查询转换为关系代数表达第二步把关系代数表达式转换为查询SELECTFROMWHERE可以按照如下方法把这个查询转换为关系代数使用FROM从句中的关系R1,R2,...,RnCΠlist(C(R1×R2×...×Rn))从关系代数表达式到查询树的转SELECTFROMWHEREP=15AND代×代×ΠA(P=15ANDN=“User”输入：关系代数表达输出：计算输入关系代数表达式的程方法(1)使用规律1把每个选择操作C1ANDANDCn(E)变换为：C1(...(Cn(E))...(2)使用规律2,4,8和10，把查询树上的每个选择操作移到尽可能靠 点(3)使用规律3、4、9和11(4使用规律1、3和4(5)使用规律7重新安 (6)组 (8)

启发式关系代数优化馆数据库关系借阅登记关系:Loa(Cn，Nc，Da)设由已借出书的信息构成的视图LBI定义如下CREATEVIEWASSELECT FROMWHEREBoo.Nc=Loa.NcSELECTFROMWHEREDa<2/1/1994CREATEVIEWASSELECTFROMCREATEVIEWASSELECTFROMWHEREBoo.Nc=Loa.Nc书目关系:书目关系:关系:借阅者关系:借阅登记关系:SELECTTiFROMWHERE个直接定义在基关系上的等价查询并变换为等价的ΠTi(C1(ΠL(C2其中–C1 C2Boo.Nc=Loa.Nc ”书目关系:书目关系:关系:借阅者关系:借阅登记关系:Q的优化过

书目关系:关系:借阅者关系:借阅登记关系:移动选择操作和合并投影操作后的查Q的优化过

书目关系:关系:借阅者关系:借阅登记关系:经过投影移动合并等处理后的查书目关系:关系:Q的优化过

借阅者关系:借阅登记关系:最后的结果查询合并选择和笛卡儿积形成连接•问题的•启发式关系代数优化•启发式关系演算优化•基于复杂性估计的查询优化介绍实现QUEL查询语言所使用的启发式QUEL查询类似于关系演算，所以称Wang-Youssefi算法是启发式关系演算优使用超图表示QUEL设Q=R (1)当i≠j时，Si和Sj没有相同属性(2)对于1≤i≤n，R与Si具有至少一个相同属性下面是计算QFOR每个元组r∈RFORi=1TOn计算Ti 计算 Tn，结果加入ENDFOR超图消解超图消解•问题的•启发式关系代数优化•启发式关系演算优化•算法1.4基于复杂性估计考虑各