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

第八章物 ?問題的?啟發(fā)式關(guān)系代數(shù)優(yōu)化?啟發(fā)式關(guān)系演算優(yōu)化?基于復(fù)雜性估計(jì)的查詢優(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í)行過程計(jì)算S和SC的笛卡兒①使用一個(gè)內(nèi)存緩沖區(qū)BS讀入某個(gè)關(guān)系(如S)的未處理元組②使用另一個(gè)內(nèi)存緩沖區(qū)BSC讀入另一個(gè)關(guān)系(如SC)的未處理元組③把BS中的每個(gè)元組和BSC中每個(gè)元組相連接，并送入出緩沖區(qū)④如果BO已滿則寫到一個(gè)臨時(shí)文件⑤重復(fù)步驟②～④，直至SC中元組全部處理完⑥重復(fù)步驟①～⑥，直至S中元組全部處理完S中有1000個(gè)學(xué)生S中有1000個(gè)學(xué)生記SC中有10000個(gè)選課SC中選修C2課程的記錄為50Q1的時(shí)間開銷設(shè)BS能裝50個(gè)S的元組，BSC能裝100個(gè)SC的元組，每個(gè)磁盤塊能裝10個(gè)S的元組或100個(gè)SC的元組。每個(gè)(1)計(jì)算S和SC 時(shí)間開銷：105秒（讀）＋100000秒（寫(2)時(shí)間開銷：100000秒（讀(3)時(shí)間開銷：0忽略CPU時(shí)間，Q需要的處理時(shí)間大 問題的提Q2=ΠSN(σSC.C#="C2"(1)

S.S#=SC.S# (3)把第2S中有1000個(gè)學(xué)生記SCS中有1000個(gè)學(xué)生記SC中有10000個(gè)選課SC中選修C2課程的記錄為50Q2的時(shí)間開銷設(shè)BS能裝50個(gè)S的元組，BSC能裝100個(gè)SC的元組，每個(gè)磁盤塊能裝10個(gè)S的元組或100個(gè)SC的元組。每個(gè)(1)設(shè)自然連接的結(jié)果為1000個(gè)元組時(shí)間開銷：105秒（讀）＋10秒（寫(2)時(shí)間開銷：10秒（讀(3)時(shí)間開銷：0忽略CPU時(shí)間，Q2需要的處理時(shí)間大約125問題的提Q3=ΠSN((σSC.C#="C2"(1)對SC

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

啟發(fā)式關(guān)系代數(shù)優(yōu)化館數(shù)據(jù)庫關(guān)系借閱登記關(guān)系:Loa(Cn，Nc，Da)設(shè)由已借出書的信息構(gòu)成的視圖LBI定義如下CREATEVIEWASSELECT FROMWHEREBoo.Nc=Loa.NcSELECTFROMWHEREDa<2/1/1994CREATEVIEWASSELECTFROMCREATEVIEWASSELECTFROMWHEREBoo.Nc=Loa.Nc書目關(guān)系:書目關(guān)系:關(guān)系:借閱者關(guān)系:借閱登記關(guān)系:SELECTTiFROMWHERE個(gè)直接定義在基關(guān)系上的等價(jià)查詢并變換為等價(jià)的ΠTi(C1(ΠL(C2其中–C1 C2Boo.Nc=Loa.Nc ”書目關(guān)系:書目關(guān)系:關(guān)系:借閱者關(guān)系:借閱登記關(guān)系:Q的優(yōu)化過

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

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

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