數(shù)據(jù)庫-db-chapter計算機科學技術學院

第八章物 ?問題的?啟發(fā)式關系代數(shù)優(yōu)化?啟發(fā)式關系演算優(yōu)化?基于復雜性估計的查詢優(yōu)化問題的提––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的執(zhí)行過程計算S和SC的笛卡兒①使用一個內(nèi)存緩沖區(qū)BS讀入某個關系(如S)的未處理元組②使用另一個內(nèi)存緩沖區(qū)BSC讀入另一個關系(如SC)的未處理元組③把BS中的每個元組和BSC中每個元組相連接，并送入出緩沖區(qū)④如果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元組和內(nèi)存中的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的處理時間將進一步減問題的提?問題的?啟發(fā)式關系代數(shù)優(yōu)化?啟發(fā)式關系演算優(yōu)化?基于復雜性估計的查詢優(yōu)化啟發(fā)式關系代數(shù)啟發(fā)式關系代數(shù)關系代數(shù)等價變換 設E1和E2是兩個關系代數(shù)表達式。如果E1和E2表示相同的關系，則稱E1和E2等價，記作啟發(fā)式關系代數(shù)關系代數(shù)等價變換規(guī)律（12類1.c1AND...ANDcn(E)≡c1(c2(...(cn2.c1(c2(E))≡c2(c1(E)3.ΠL1(ΠL2(...(ΠLn(E))...))≡ΠL1其中E是關系代數(shù)表達式，Li是投影屬性集合，而且L2...Ln啟發(fā)式關系代數(shù)關系代數(shù)等價變換規(guī)律（12類4ΠL(C(E))≡C(ΠL(E)其中，E是關系代數(shù)表達式，L是投影屬性集合，C選擇條件，C只涉及L中的屬性ΠL(C(E)≡ΠL(CΠLB1Bm(E)C還涉及L以外的屬性B1、...、5 其中，E1和E2是關系代數(shù)表達式，C是連接條6.其中，E1和E2是關系代數(shù)表達式啟發(fā)式關系代數(shù)關系代數(shù)等價變換規(guī)律（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，就可以得到選擇與乘積的分配啟發(fā)式關系代數(shù)關系代數(shù)等價變換規(guī)律（12類9.投影、連接 (1)ΠL CE2)≡(ΠL1 C(ΠL2其中C是連接條件，E1和E2是關系代數(shù)表達式，L=L1∪L2是投影屬性集合，L1僅涉及E1的屬性，L2僅(2)ΠL CE2)≡ΠL((ΠL1 C(ΠL2其中，C是連接條件，E1和E2是關系代數(shù)表達式，C涉E1的屬性A1、...、Ai、...、Ak和E2的屬性B1、...、Bj、...、Bp，L{Ai,...,Ak,Bj,...,Bp}，L1={A1，...，Ai，...，Ak}，L2={B1，...,Bj，...，Bp}(3)用×代替上邊兩個等價式中的 啟發(fā)式關系代數(shù)關系代數(shù)等價變換規(guī)律（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.除了上述規(guī)律以外，還有很多其他等價變換規(guī)律。例如，使用DMra啟發(fā)式關系代數(shù)啟發(fā)式代數(shù)優(yōu)化給定一個關系代數(shù)表達式，可以應用一組啟發(fā)式規(guī)則對其進行等價變換，產(chǎn)生一個具有需要注意，這些規(guī)則不能保證一定產(chǎn)生最優(yōu)啟發(fā)式代數(shù)優(yōu)化規(guī)則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啟發(fā)式代數(shù)優(yōu)化規(guī)則2把某些選擇操作與鄰接 乘積相 規(guī)則3同時執(zhí)行相同關系上的多個選擇和投規(guī)則 啟發(fā)式代數(shù)優(yōu)化規(guī)則5如果一個反復出現(xiàn)的公共表達式的結果不是一個很大的關系，而且從外存讀入它的時間小于計算它的時間，可以只計算這個表達式一次并其在一個查詢樹中，葉子結點表示關系，內(nèi)結點表示關系代數(shù)操查詢樹以自底向上的方式執(zhí)行：當一個內(nèi)結點的操作分量可用時，這個內(nèi)結點所表示的操作啟動執(zhí)行，執(zhí)行結束后用結果關系代替這個內(nèi)結點。構造查詢的內(nèi)部表示是查詢處理的第一步。給定一個用高級語言定義的查詢，需要兩步來構造該查詢第一步把用高級語言定義的查詢轉換為關系代數(shù)表達第二步把關系代數(shù)表達式轉換為查詢SELECTFROMWHERE可以按照如下方法把這個查詢轉換為關系代數(shù)使用FROM從句中的關系R1,R2,...,RnCΠl(fā)ist(C(R1×R2×...×Rn))從關系代數(shù)表達式到查詢樹的轉SELECTFROMWHEREP=15AND代×代×ΠA(P=15ANDN=“User”輸入：關系代數(shù)表達輸出：計算輸入關系代數(shù)表達式的程方法(1)使用規(guī)律1把每個選擇操作C1ANDANDCn(E)變換為：C1(...(Cn(E))...(2)使用規(guī)律2,4,8和10，把查詢樹上的每個選擇操作移到盡可能靠 點(3)使用規(guī)律3、4、9和11(4使用規(guī)律1、3和4(5)使用規(guī)律7重新安 (6)組 (8)

啟發(fā)式關系代數(shù)優(yōu)化館數(shù)據(jù)庫關系借閱登記關系: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的優(yōu)化過

書目關系:關系:借閱者關系:借閱登記關系:移動選擇操作和合并投影操作后的查Q的優(yōu)化過

書目關系:關系:借閱者關系:借閱登記關系:經(jīng)過投影移動合并等處理后的查書目關系:關系:Q的優(yōu)化過

借閱者關系:借閱登記關系:最后的結果查詢合并選擇和笛卡兒積形成連接?問題的?啟發(fā)式關系代數(shù)優(yōu)化?啟發(fā)式關系演算優(yōu)化?基于復雜性估計的查詢優(yōu)化介紹實現(xiàn)QUEL查詢語言所使用的啟發(fā)式QUEL查詢類似于關系演算，所以稱Wang-Youssefi算法是啟發(fā)式關系演算優(yōu)使用超圖表示QUEL設Q=R (1)當i≠j時，Si和Sj沒有相同屬性(2)對于1≤i≤n，R與Si具有至少一個相同屬性下面是計算QFOR每個元組r∈RFORi=1TOn計算Ti 計算 Tn，結果加入ENDFOR超圖消解超圖消解?問題的?啟發(fā)式關系代數(shù)優(yōu)化?啟發(fā)式關系演算優(yōu)化?算法1.4基于復雜性估計考慮各