三 分布式查詢處理

1、三 分布式查詢處理查詢處理問題 集中式 查詢轉(zhuǎn)換為代數(shù)表達(dá)式 從所有等價(jià)表達(dá)式中選擇最優(yōu)的代數(shù)表達(dá)式 分布式 除了集中式問題外，還有 站點(diǎn)之間交換數(shù)據(jù)的操作 選擇最優(yōu)的執(zhí)行站點(diǎn) 數(shù)據(jù)被傳送的方式分布查詢分類 局部查詢只涉及本地. 單個(gè)站點(diǎn)的數(shù)據(jù), 優(yōu)化同集中式 遠(yuǎn)程查詢也只涉及單個(gè)站點(diǎn)的數(shù)據(jù), 但要遠(yuǎn)程通訊, 選擇站點(diǎn) 全局查詢涉及多個(gè)站點(diǎn)數(shù)據(jù), 優(yōu)化復(fù)雜LDBMS.LDBMSDBDB本地模式.全局模式本地模式全局模式全局模式全局模式用戶用戶用戶用戶site1site2site3查詢處理優(yōu)化目標(biāo) 總代價(jià)最小 集中式 CPU , I/O 代價(jià) 分布式 CPU, I/O 通訊代價(jià) 時(shí)間代價(jià) 響應(yīng)時(shí)

2、間分布式查詢策略的重要性 例子 S(s#, sname, age, sex) 104 元組 Site A C(c#, cname, teacher) 105 元組 Site B SC(s#, c#, grade) 106 元組 Site A 每個(gè)元組長(zhǎng)度100Bit, 通訊傳輸速度 104 bit/sec, 通訊延遲 1secS, SCCSite ASite B查詢: 所有選修maths 課的男生學(xué)號(hào)和姓名. SELECT s#, sname FROM S, C, SC WHERE S.s#=SC.s# AND C.c#=SC.c# AND sex=男 AND name=maths;查詢代價(jià)估

3、算方法 代價(jià)公式 QC = I/O 代價(jià) + CPU 代價(jià) + 通訊代價(jià) 通訊代價(jià) TC = 傳輸延遲時(shí)間C0 + (傳輸數(shù)據(jù)量X * 數(shù)據(jù)傳輸速率C1)6種策略CS, SCS, SCC(C)S, SC(S)CSC(S), SCCS, SC(C)T1=1+(105*100/104)=16.7分鐘T2=2+ (104 +105)*100/104=2.8小時(shí)T32*105*1=4.7天T4 2*10*1=20秒T5=1+(105*100/104)=16.7分鐘T6=1+(10*100/104)=1秒1212基礎(chǔ)知識(shí) SQL與代數(shù)的等價(jià)描述 SELECT sname FROM S, SC WHERE

4、 S.s#=SC.s# and SC.c#=c03; 代數(shù)描述 sname(s.s#=SC.s# and SC.c#=c03(S SC) SELECT sname FROM S WHERE S.s# in ( SELECT SC.s# FROM SC WHER c#=c03); 代數(shù)描述 sname(s.s#=SC.s# (S SC.c#=c03 SC) SELECT sname FROM S , ( SELECT SC.s# FROM SC WHER c#=c03) SCC WHERE S.s# = SCC.s# ; 代數(shù)描述 sname(S SC.c#=c03 SC)查詢樹SSCs.s#=

5、SC.s# and SC.c#=c03snameSSCs.s#=SC.s# snameSSCs.s#=SC.s#snamec#=c03c#=c03代數(shù)操作符 一目操作 (SL), (PJ) 二目操作 (UN), , - (DF), X (CP), (JN), (SJ), 等價(jià)變換規(guī)則 空值的變換 R = R R = R SJ = SJ R = - R = R - = R R JN = R X = () = () = 自身操作的等價(jià)R R = R R R = R R JN R = R 一目操作F1 (F2(R) = F1 and F2(R) A1,An(B1,Bm(R) = A1,An(R) 有

6、條件等價(jià)變換規(guī)則-續(xù) 交換率1 (2 (R) = 2 (1 (R)條件: 1 2 是 SL 時(shí)總成立 1 2 是 PJ 時(shí)要求其屬性集合相等 1 與 2 是 PJ 和 SL時(shí): PJA1,An(SLF(R) = SLF (PJA1,An (R) 的條件是 F中的屬性是 A1, . An 的子集等價(jià)變換規(guī)則-續(xù)R JN S = S JN R R CP S = S CP RR S = S R R S = S RR SJ S S SJ R R - S S - R 結(jié)合率 R B ( S B T ) = (R B S) B T)B: 二目操作JN, CP, UN, 等總成立SJ 有問題等價(jià)變換規(guī)則-續(xù)

7、 分配率U (R B S) = U (R) B U (S) U:一目操作 SLF(R CP S) 其中F = F1 and F2, 若F1有R屬性, F2有S屬性, 則 SLF(R CP S) = SLF1 (R) CP SLF2 (S) 若F1只有R屬性, F2有R與S屬性, 則 SLF(R CP S) = SLF2 (SLF1 (R) CP S) SLF(R S) = SLF(R) SLF (S) SLF(R - S) = SLF(R) - SLF (S) SLF(R JN S) = SLF(R) JN SLF (S)等價(jià)變換規(guī)則-續(xù) PJB1,Bm,C1,Ck (R CP S) = PJ

8、B1,Bm (R) CP PJC1,Ck (S) B1,Bm 是R屬性, C1,Ck是S屬性 PJB1,Bm,C1,Ck (R S) = PJB1,Bm (R) PJC1,Ck (S) PJB1,Bm,C1,Ck (R - S) = PJB1,Bm (R) - PJC1,Ck (S) PJB1,Bm,C1,Ck (R JN S) = PJB1,Bm (R) JN PJC1,Ck (S) PJB1,Bm (R SJ S) = PJB1,Bm (PJB1,Bm,C1,Ck (R) SJ PJC1,Ck (S) 限定關(guān)系 定義: R: QR 稱為 R的限定關(guān)系, 其中QR表示查詢邏輯片段就是一個(gè)限定

9、關(guān)系 SL city=london(Supplier) 的限定關(guān)系: Supplier:Slcity=london SLFR: QR SLF(R) : F and QR PJAR: QR PJA(R) : QR R: QR CP S: QS R CP S : QR and QS R: QR - S: QS R - S : QR R: QR S: QS R S : QR or QS限定關(guān)系-續(xù) R: QR S: QS R S : QR and QSR: QR S: QS R: QR - (R: QR - S: QS ) R: QR - (R - S: QR) R- (R-S) : QR R S:

10、 QR R: QR JN S: QS R JN S : QR and QS and FR: QR JN S: QS SLF( R: QR CP S: QS) SLFR CP S: QR and QS SLF (R CP S) : QR and QS and F R JN S: QR and QS and F 限定關(guān)系-續(xù) R: QR SJ S: QS R SJ S : QR and QS and FR: QR SJ S: QS PJA(R) ( R: QR CP S: QS ) PJA(R)R JN S: QR and QS AND F PJA(R) (R CP S) : QR and QS

11、and F R SJ S: QR and QS and F 查詢查詢計(jì)劃全局關(guān)系上的代數(shù)查詢樹分解分片關(guān)系上的代數(shù)查詢樹 本地化優(yōu)化查詢處理的層次結(jié)構(gòu)分解 技術(shù)同集中式方法 代數(shù)轉(zhuǎn)換 消除冗余操作 代數(shù)重寫 SELECT sname FROM S WHERE S.s# in ( SELECT SC.s# FROM SC WHER c#=c03); 代數(shù)描述 sname(s.s#=SC.s# (S SC.c#=c03 SC) SELECT sname FROM S , ( SELECT SC.s# FROM SC WHER c#=c03) SCC WHERE S.s# = SCC.s# ; 代數(shù)

12、描述 sname(S SC.c#=c03 SC)代數(shù)轉(zhuǎn)換舉例SSCs.s#=SC.s# and SC.c#=c03snameSSCs.s#=SC.s# snameSSCs.s#=SC.s#snamec#=c03c#=c03對(duì)應(yīng)的查詢樹描述消除冗余例子: 條件矛盾或蘊(yùn)含(E.sal=2000) (E.sal5000) False(E.sal5000) (E.sal3000) E.sal100; 代數(shù)描述 SLSUM(QTY)100(s#, p# GB SUM(QTY) (Supply)S#,p#GBum(QTY)SLsum(QTY)100UNSupply1Supply2Q3:UNSLsum(QTY)100SLsum(QTY)100S#,p#GBum(QTY)S#,p#GBum(QTY)Supply1Supply2分組操作盡量下推至片段上集合函數(shù)變換 Min(S) = Min(Min(S1), , Min(Sn) Count(S) = Sum(Count(S1), Count(Sn) Max(S) = Max(Max(S