3章_分布式數(shù)據(jù)庫中的查詢處理和優(yōu)化_

1、分布式數(shù)據(jù)庫系統(tǒng)及其應(yīng)用,,分布式查詢優(yōu)化概述分布式查詢優(yōu)化基礎(chǔ)知識分布式查詢分類和層次結(jié)構(gòu)基于關(guān)系代數(shù)等價變換的查詢優(yōu)化處理基于半連接算法的查詢優(yōu)化處理基于直接連接算法的查詢優(yōu)化處理直接連接操作的常用策略,,,分布式數(shù)據(jù)庫中的查詢處理和優(yōu)化,第3章,查詢處理問題,集中式查詢轉(zhuǎn)換為代數(shù)表達(dá)式從所有等價表達(dá)式中選擇最優(yōu)的代數(shù)表達(dá)式分布式除了集中式問題外，還有站點之間交換數(shù)據(jù)的操作選擇最優(yōu)的執(zhí)行站點(分布）數(shù)據(jù)被傳

2、送的方式,,,,目標(biāo),總代價最小,響應(yīng)時間最短,集中式,分布式,,CPU代價（相對固定）,I/O代價（可變的，優(yōu)化的目標(biāo)）,CPU代價,I/O代價（訪問磁盤）,通訊代價,數(shù)據(jù)的分布和冗余增加了查詢的并行處理的可能性，從而可以縮減查詢處理的響應(yīng)時間,主要標(biāo)準(zhǔn)輔助標(biāo)準(zhǔn),準(zhǔn)則： 使得通訊費用最低和響應(yīng)時間最短，即以最小的總代價，在最短的響應(yīng)時間內(nèi)獲得需要的數(shù)據(jù)。通訊費用與所傳輸?shù)臄?shù)據(jù)量和通信次數(shù)有關(guān)響應(yīng)時間和通信時間有關(guān)

3、，也與局部處理時間有關(guān)查詢代價分析遠(yuǎn)程通訊網(wǎng)絡(luò) 局部處理時間可以忽略不計，減少通訊代價是主要目標(biāo)高速局域網(wǎng) 傳輸時間比局部處理時間要短很多，以響應(yīng)時間作為優(yōu)化目標(biāo)，局部處理時間是關(guān)鍵,例子 S(s#, sname, age, sex) 104 元組 Site A C(c#, cname, teacher) 105 元組 Site B SC(s#, c#,

4、grade) 106 元組 Site A 每個元組長度100Bit, 通訊傳輸速度 104 bit/sec, 通訊延遲 1sec,查詢: 所有選修maths 課的男生學(xué)號和姓名. SELECT s#, sname FROM S, C, SC WHERE S.s#=SC.s# AND C

5、.c#=SC.c# AND sex=‘男’ AND cname=‘maths’;,代價公式 QC = I/O 代價 + CPU 代價 + 通訊代價 通訊代價 TC = 傳輸延遲時間C0 + (傳輸數(shù)據(jù)量X * 數(shù)據(jù)傳輸速率C1),六種查詢策略,六種查詢策略,相關(guān)表述記號,⒈ 設(shè)關(guān)系模式為R(A1, A2, …

6、, An)。它的一個關(guān)系設(shè)為R。 t∈R表示t是R的一個元組。t[Ai]則表示元組t中相應(yīng)于屬性Ai的一個分量 。,,,⒉ 若A={Ai1, Ai2, …, Aik}，其中Ai1, Ai2, …, Aik是A1, A2, …, An中的一部分， 則A稱為屬性列或域列。 t[A]=(t[Ai1], t[Ai2], …, t[Aik])表示元組 t 在屬性 列A上諸分量的集合。則 表示{

7、A1, A2, …, An}中去掉 {Ai1, Ai2, …, Aik} 后剩余的屬性組。,,相關(guān)表述記號,⒋ 給定一個關(guān)系R(X,Z)，X和Z為屬性組。我們定義，當(dāng)t[X]=x時，x在R中 的象集（Images Set）為： Zx={ t[Z]|t∈R, t[X]=x } 它表示R中屬性組X上值為x的諸元組在Z上分量的集合。,,,傳統(tǒng)的集合運算,并運算,設(shè)關(guān)系R和關(guān)系S具有相同的目n（即

8、兩個關(guān)系都有n個屬性），且相應(yīng)的屬性取自同一個域，則關(guān)系R與關(guān)系S的并由屬于R或?qū)儆赟的元組組成。其結(jié)果關(guān)系仍為n目關(guān)系。記作： R∪S={ t | t∈R∨t∈S },差運算,,傳統(tǒng)的集合運算,交運算,R1∩R2,設(shè)關(guān)系R和關(guān)系S具有相同的目n，且相應(yīng)的屬性取自同一個域，則關(guān)系R與關(guān)系S的交由既屬于R又屬于S的元組組成。其結(jié)果關(guān)系仍為n目關(guān)系。記作： R∩S={t|t∈R∧t∈S},傳統(tǒng)的集合運算,兩個分別為n目和m目的關(guān)

9、系R和S的廣義笛卡爾積是一個(n+m)列的元組的集合。元組的前n列是關(guān)系R的一個元組，后m列是關(guān)系S的一個元組。若R有k1個元組，S有k2個元組，則關(guān)系R和關(guān)系S的廣義笛卡爾積有k1×k2個元組。記作：,廣義笛卡爾積,專門的關(guān)系運算,S(S#,SN,SD,SA),選擇運算是從關(guān)系中選取使公式為真的元組。這是從行的角度進(jìn)行的運算。,在關(guān)系R中選擇滿足給定條件的元組，記做：

10、 σF (R) ={ t | t ∈R Λ F(t)=‘真’ }F是一個公式，表示形式為由邏輯運算符（∧,∨,?)連接各算術(shù)表達(dá)式組成。算術(shù)表達(dá)式的基本形式為：XθY. θ ={>, ≥ ,<, ≤ ,=, ≠} 。,例1 求計算機(jī)科學(xué)系CS的學(xué)生,σ SD=‘CS’ (S),,,,,σ SD=‘CS’ (S),選擇運算,在關(guān)系R中選擇滿足給定條件的元組，記做：

11、 σF (R) ={ t | t ∈R Λ F(t)=‘真’ },例2 求計算機(jī)科學(xué)系CS，年齡不超過21歲的學(xué)生。,σ SD=‘CS’ ∧SA≤21 (S),選擇運算,,投影運算,,這是從列的角度進(jìn)行的運算。,例3 πSN,SD (S) 即求得學(xué)生關(guān)系S在學(xué)生姓名和所在系這兩個屬性上的投影結(jié)果。,πSN,SD (S),關(guān)系R上的投影是從R中選擇若干屬性列組成新的關(guān)系。記做：

12、 πA (R) ={ t[A] | t ∈R}投影之后不僅取消了某些列，還可能取消某些元組。,,連接運算（θ連接）,S,R,R S,∞ C<E,,,等值連接,例5 設(shè)關(guān)系R、S如下圖：,,,,12,b4,a2,8,b3,a2,6,b2,a1,5,b1,a1,C,B,A,,,,,,,,,,,R,,連接運算中有兩種最為重要也最為常用的連接，,θ為“＝”的連接運算稱為等值連接:,自然

13、連接,另一種是自然連接。自然連接是一種特殊的等值連接，它要求兩個關(guān)系中進(jìn)行比較的分量必須是相同的屬性組，并且要在結(jié)果中把重復(fù)的屬性去掉。,半連接,在R、S自然連接后僅保留對R的屬性的投影，記為：R ∝ S,例7 關(guān)系R、S的半連接：,,,,R,左外連接: 對R中任意元組，若S中找不到匹配的元組，則S用空元組與之對應(yīng)。R的信息在左外連接的結(jié)果中都得到保留。,左外連接,在R、S自然連接時對不匹配的元

14、組用空值來匹配。有左外連接、右外連接和全外連接之分,例8 關(guān)系EMP、SAL的左外連結(jié)：,,,,,,,,,,,右外連結(jié): 對S中任意元組，若R中找不到匹配的元組，則R用空元組與之對應(yīng)。S的信息在右外連接的結(jié)果中都得到保留。,右外連接,例9 關(guān)系EMP、SAL的右外連結(jié)：,,,,,,,,,,,全外連接: 對R或S中所有不匹配的元組，均用空元組分別匹配。R、S的信息

15、在全外連接的結(jié)果中都得到保留。,全外連接,例10 關(guān)系EMP、SAL的全外連結(jié)：,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,除運算,給定關(guān)系R(X,Y)和S(Y,Z)，其中X, Y, Z為屬性組。R中的Y與S中的Y可以有不同的屬性名，但必須出自相同的域集。R與S的除運算得到一個新的關(guān)系P(X)，P是R中滿足下列條件的元組在X屬性列上的投影：元組在X上分量值x的象集Yx包含S在Y上投影的集合。記作

16、： R÷S = { tｒ[X] | tｒ∈R ∧ Yx ?ΠY(S) } 其中Yx為x在R中的象集，x=tｒ[X]。,Z,X,除運算,S在B、C上的投影,{（b1,c2），（b2,c3），（b2,c1）},R÷S = { tｒ[X] | tｒ∈R ∧ Yx ?ΠY(S) },R÷S＝{ a1},,,,,,,關(guān)系代數(shù)表達(dá)式,設(shè)教學(xué)數(shù)據(jù)庫中有三個關(guān)系：

17、學(xué)生關(guān)系S（S#，SNAME，SD， AGE ） 課程關(guān)系C（C#，CN, CP#） 學(xué)習(xí)關(guān)系SC（S#，C#，GRADE）,例1 檢索學(xué)習(xí)課程號為C2的學(xué)生學(xué)號與成績,,,,πS# ,GRADE(σ C# =‘C2’ (SC)),σ C# =‘C2’ (SC),,,例2 檢索學(xué)習(xí)課程號為C2的學(xué)生學(xué)號和姓名,,,＝,πS# ,SNAME(S

18、∞ C# =‘C2’ SC),πS# ,SNAME(σ C# =‘C2’ ( S ∞ SC )),例3 求選修《數(shù)據(jù)庫原理》這門課程的學(xué)生名和所在系。,,（ S、C、SC ）,例4 檢索學(xué)習(xí)課程號為C2或C3的學(xué)生學(xué)號和所在系,πSN ,SD( (σCN=‘?dāng)?shù)據(jù)庫原理’(C)) ),S ∞ SC ∞,πS# ,SD( s ∞ πS# (σC# =‘C2’∨C#=‘C3’(SC))

19、 ),例5 求至少選修C2和C3這兩門課程的學(xué)生名。,πSN( S ∞ (πS#, C# (SC) ÷K)),πSN( S ∞ (πS#, C# (SC) ÷ πC# (σC# =‘C2’∨C#=‘C3’(C))),K ＝πC# (σS#=‘S2’(SC)),,（ S、C、SC ）,例7 求選修全部課程的學(xué)生名。,例8 求至少選修了學(xué)生編號為S2 所選課程的學(xué)生名。,πS#(SC)－πS#

20、(σC# =‘C2’ (SC)),例6 求不學(xué)C2這門課程的學(xué)生名。,πS#(S)－πS# (σC# =‘C2’ (SC)),×√,,πSN ( S ∞ (πC#,S# (SC) ÷ C) ),πSN ( S ∞ (πC#,S# (SC) ÷ πC# (σS#=‘S2’(SC)))),SQL與代數(shù)的等價描述E1SELECT sname FROM S, SC WHERE S.s#

21、=SC.s# and SC.c#=‘c03’;代數(shù)描述 ?sname(?s.s#=SC.s# and SC.c#=‘c03’(S×SC)),關(guān)系代數(shù)基本操作：并（∪）、交（∩）、笛卡爾積（ × ）、選擇（ ?）、投影（ ?）關(guān)系代數(shù)到處操作：差（－）、除（÷）、 θ連接（ ∞ θ ）、自然連接（∞）、半連接（∝）,E2SELECT sname FROM S WHERE

22、 S.s# in ( SELECT SC.s# FROM SC WHER c#=‘c03’);代數(shù)描述 ?sname(?s.s#=SC.s# (S × ? SC.c#=‘c03’ SC))E3SELECT sname FROM S , ( SELECT SC.s# FROM SC WHER c#=‘c03’)

23、 SCC WHERE S.s# = SCC.s# ;代數(shù)描述 ?sname(S ∞ ? SC.c#=‘c03’ SC),節(jié)點表示一個一元或二元操作符,葉子表示已知關(guān)系,樹根表示查詢結(jié)果,一元操作：只涉及一個操作對象 ? (SL), ? (PJ)二元操作：涉及兩個操作對象∪ (UN), ∩（） , － (DF), × (CP), ∞θ（），∞ (JN), ∝ (SJ),,等價

24、變換規(guī)則,空值的變換 R ? Ø = R R ? Ø = Ø R ∞ Ø = Ø Ø ∝ R = ØØ - R = Ø R - Ø = R R ∞θ Ø = Ø R × Ø = Ø? (Ø) = Ø ? (

25、Ø) = Ø 自身操作的等價R ? R = R R ? R = R R ∞ R = R一元操作?F1 (?F2(R)) = ?F1and F2(R) ? ? (R) = ?(R) ?A1,…,An(?B1,…,Bm(R)) = ?A1,…,An(R),有條件:A必須是B的屬性,交換率?1 (?2 (R)) = ?2 (?1 (R))條件:?1 ?2 是

26、 選擇操作 時總成立?1 ?2 是 投影操作 時要求其屬性集合相等?1 與 ?2 是投影和選擇操作時: ? A1,…An(? F(R)) = ? F (? A1,…An (R)) 的條件是 F中的屬性是 A1, …. An 的子集R ∞ S = S ∞ R R × S = S × RR ? S = S ? R R ? S = S ? RR ∝ S

27、? S ∝ R R - S ? S - R,結(jié)合率 R B ( S B T ) = (R B S) B T)B: 二元操作∞（JN）, ×（CP）, ∪（UN）, ?等總成立∝（SJ） 有問題,分配率U (R B S) = U (R) B U (S) U:一元操作SLF(R × S) 其中F = F1 and F2, 若F1有R屬性, F2有

28、S屬性, 則 ? F(R S) = ? F1 (R) × ? F2 (S) 若F1只有R屬性, F2有R與S屬性, 則 ? F(R × S) = ? F2 (? F1 (R) × S)? F(R ? S) = ? F(R) ? ? F (S)? F(R - S) = ? F(R) - ? F (S)? F(R ∞ S) = ? F(R) ∞ ? F (S),? B1,…

29、,Bm,C1,…Ck (R × S) = ? B1,…,Bm (R) × ? C1,…Ck (S) B1,…,Bm 是R屬性, C1,…Ck是S屬性? B1,…,Bm,C1,…Ck (R ? S) = ? B1,…,Bm (R) ? ? C1,…Ck (S) ? B1,…,Bm,C1,…Ck (R - S)

30、 = ? B1,…,Bm (R) - ? C1,…Ck (S) ? B1,…,Bm,C1,…Ck (R ∞ S) = ? B1,…,Bm (R) ∞ ? C1,…Ck (S) ? PJB1,…,Bm (R ∝ S) = ?B1,…,Bm (? B1,…,Bm,C1,…Ck (R) ∝ ? C1,…Ck (S)),限定關(guān)系,定義: R: QR 稱為 R的限定關(guān)系,

31、其中QR表示查詢邏輯片段就是一個限定關(guān)系 ? city=‘london’(Supplier) 的限定關(guān)系: [Supplier: ? city=‘london’]? F[R: QR] [? F(R) : F and QR]? A[R: QR] [? A(R) : QR][R: QR] × [S: QS] [R × S : QR an

32、d QS][R: QR] - [S: QS] [R - S : QR ][R: QR] ? [S: QS] [R ? S : QR or QS][R: QR] ? [S: QS] [R ? S : QR and QS],,,,,,,局部查詢：只涉及本地. 單個站點的數(shù)據(jù), 優(yōu)化同集中式選擇和投影早做，中間結(jié)果大大減少連接前進(jìn)行預(yù)處理（屬性排

33、序、屬性索引）同時執(zhí)行一串投影和選擇操作遠(yuǎn)程查詢：也只涉及單個站點的數(shù)據(jù), 但要遠(yuǎn)程通訊, 選擇站點選擇查詢應(yīng)用最近的冗余分配站點全局查詢：涉及多個站點數(shù)據(jù), 優(yōu)化復(fù)雜,全局查詢具體化對查詢進(jìn)行分解，確定查詢使用的物理副本，落實查詢對象非冗余具體化，所有要訪問對象只有一個副本冗余具體化，多個副本，研究如何如何選擇副本，使通信代價最小確定操作執(zhí)行的順序確定二元操作連接和并操作的順序先執(zhí)行所有連接操作，再執(zhí)行并操作先

34、執(zhí)行部分并操作，再執(zhí)行連接操作選擇和投影盡可能早進(jìn)行確定操作執(zhí)行的方法把若干個操作連接起來在一次數(shù)據(jù)庫訪問中，確定可用的訪問路徑連接方法在查詢優(yōu)化中起著重要作用確定執(zhí)行的站點執(zhí)行站點不一定是發(fā)出查詢的站點考慮通訊費用和執(zhí)行效率,查詢分解,數(shù)據(jù)本地化,全局優(yōu)化,局部優(yōu)化,分布關(guān)系上的查詢表達(dá),分布關(guān)系上的代數(shù)表達(dá),分段關(guān)系查詢表達(dá),帶有通訊操作的段查詢優(yōu)化,優(yōu)化的局部查詢表達(dá),,,,,,,,,全局模式,段模式,段的統(tǒng)計數(shù)據(jù),

35、局部模式,,,,,,控制站點,,本地站點,分布查詢的層次,查詢分解將查詢問題（SQL）轉(zhuǎn)換成一個定義在全局關(guān)系上的關(guān)系代數(shù)表達(dá)式需要從全局概念模式中獲得轉(zhuǎn)換所需要的信息數(shù)據(jù)本地化具體化全局關(guān)系上的查詢，落實到合適的片段上的查詢即將全局關(guān)系上的關(guān)系代數(shù)表達(dá)式變換為相應(yīng)片段上的關(guān)系代數(shù)表達(dá)式全局優(yōu)化輸入的是分片查詢，優(yōu)化目標(biāo)是尋找一個近于最優(yōu)的執(zhí)行策略（操作次序）輸出是一個優(yōu)化的、片段上的關(guān)系代數(shù)查詢局部優(yōu)化輸入是局部模

36、式它由該站點上的DBMS進(jìn)行優(yōu)化,基本原理查詢問題——〉關(guān)系代數(shù)表達(dá)式分析得到查詢樹進(jìn)行全局到片段的變換得到基于片段的查詢樹利用關(guān)系代數(shù)等價變換規(guī)則的優(yōu)化算法，盡可能先執(zhí)行選擇和投影操作優(yōu)化算法連接和合并盡可能上提（樹根方向）選擇和投影操作盡可能下移（葉子方向）,實現(xiàn)步驟和方法轉(zhuǎn)換一：查詢問題——〉關(guān)系代數(shù)表達(dá)式轉(zhuǎn)換二：關(guān)系代數(shù)表達(dá)式——〉查詢樹轉(zhuǎn)換三：全局查詢樹分拆成片段查詢樹優(yōu)化：利用關(guān)系代數(shù)等價變換規(guī)則的優(yōu)

37、化算法，優(yōu)化查詢樹，進(jìn)而優(yōu)化查詢,全局關(guān)系S(S#, SNAME, AGE, SEX)和SC(S#, C#, GRADE)被水平分片,查詢問題：查找至少有一門功課成績在90分以上的男生姓名?SNAME(?SEX=‘M’ and GRADE>90(?S.S #=SC.C# (S×SC))),?,水平分片的查詢優(yōu)化的基本思想：盡量把選擇條件下移到分片的限定關(guān)系處再把分片的限定關(guān)系與選擇條件進(jìn)行比較去掉它們之間存在矛

38、盾的相應(yīng)片斷如果最后剩下一個水平片斷，則重構(gòu)全局關(guān)系的操作中，就可去掉“并”操作（至少可以減少“并”操作的次數(shù)）,全局關(guān)系EMP(EMP#, ENAME, SALARY,DEPT#,DNAME)垂直分片：E1 (EMP#,DEPT#,DNAME)EMP2(EMP#, ENAME, SALARY),查詢問題：雇員的姓名和工資情況?ENAME,SALARY(EMP),垂直分片的查詢優(yōu)化的基本思想：把垂直分片所用到的屬性集，與查詢

39、條件中的投影操作所涉及的屬性相比較，去掉無關(guān)的垂直片斷如果最后只剩下一個垂直片斷與查詢有關(guān)時，去掉重構(gòu)全局關(guān)系的“連接”操作（至少可以減少“連接”操作的次數(shù)）,假定有兩個關(guān)系R,S,在屬性R.A=S.B上做半連接操作，可表示為：R∝A=B S= ?R( R ∞A=B S)=R ∞A=B (?B (S))S∝A=B R= ?S( S ∞A=B R)=S ∞A=B (?A (R))用半連接表示連接操作R∞A=BS= ( R∝A=B

40、 S)∞A=BS= （R ∞A=B (?B (S)) ∞A=BSR∞A=BS = ( S∝A=B R)∞A=BR=(S ∞A=B (?A (R) )∞A=BR,例子1: R ∝ S,AB,,? A (R) = [2,10,25,30],,R ∝ S,S∝R =,A C10 y25 w,,,,,A=A,A=A,A C,S,R,AB,例子2：半連接簡化,R,S,T,R,S,T,,,,B=B,C=C,A=A,R,

41、S,T的循環(huán)連接圖,對R的充分簡化,R’=R ∝ T,S’=S ∝ R’,T’=T ∝ S’,減少一個元組,R’’=R’ ∝ T’,S’’=S’ ∝ R’’,T’’=T’ ∝ S’’,減兩個元組,R’’’=R’’ ∝T’’ = ? 減少三個元組,一般：簡化程序長度隨著關(guān)系的元組數(shù)目增長線性增長。對R的另一個簡化程序： R’=R ∝ S

42、T’ = T ∝ R’ S’ = S ∝ T’ （練習(xí)）,R,S,,網(wǎng)絡(luò),,站點1 站點2,(1) ? B(S),(3) R’= R∝A=B?B(S) (2) ?B(S)(4) R’= R∝A=B ?B(S) (5) R’∞A=BS,,,關(guān)系的概貌Card(R)

43、 片段關(guān)系R的元組數(shù)目Size(A) 屬性A的大小(即字節(jié)數(shù))Size(R) 片段關(guān)系的大小, 屬性大小之和Val(A[R]) 屬性A在R中出現(xiàn)的不同值的個數(shù),代數(shù)操作對關(guān)系概貌的影響選擇操作 S= ?F（R） Card(S)= ρ *Card(R) Size(S)=Size(R) Val(B[S])是Val(B[R]), Card(S), Card

44、(R)的函數(shù)并操作 T=R∪S Card(T) ? Card(R)+Card(S) Size(T)=Size(R)=Size(S) Val(A[T]) ? Val(A[R])+Val([AS]),代數(shù)操作對關(guān)系概貌的影響連接操作 T=R∞S Card(T) =(Card(R)*Card(S))/Val(A[R]) Size(T) = Size(R)+Size(S) –Size(A) V

45、al(A[T]) ? Min(Val(A[R]), Val(B[S])) A 是連接屬性 Val(A[T]) ? Val(A[R])+Val(B[S]) A不是連接屬性 半連接 T=R∝Sρ =Val(A[S])/Val(Dom(A)) Card(T) = ρ *Card(R) Size(T) = 第一個操作數(shù)Size（R） Val(A[T]) = ρ *Val(A[R]),代價公式：T=

46、C0+C1*X在站點2上做投影?B (S)把?B (S)傳到站點1上，代價為：C0+C1* size (B)* val( B[S])在站點1上計算半連接，R’=R ∝A=B S把R’從站點1傳到站點2的代價為：C0+C1* size (R’)* card( R’)在站點2上執(zhí)行連接操作：R’ ∞A=BS采用半連接的總代價T半R= 2C0+C1* (size (R’)* card( R’) +size (B)* val(

47、 B[S]))T半S= 2C0+C1* (size (S’)* card( S’) +size (A)* val( A[R]))比較T半R 與T半S, 取最優(yōu)者,基本原理通常有兩次傳輸?shù)莻鬏數(shù)臄?shù)據(jù)量和傳輸整個關(guān)系相比，要遠(yuǎn)遠(yuǎn)少一般有：T半>card（R’），可減少站點間的數(shù)據(jù)傳輸量半連接的損失：傳輸?B (S) =C0+C1* size (B)* val( B[S])基本原理是在傳到另一個站點做連接前，消除與連

48、接無關(guān)的數(shù)據(jù)，減少做連接操作的數(shù)據(jù)量，從而減小傳輸代價采用半連接優(yōu)化算法的步驟計算每種半連接方案的代價，并從中選擇一種最佳方案選擇傳輸代價最小的站點，計算采用全連接的方案的代價比較兩種方案，確定最優(yōu)方案,SDD-1半連接算法,基礎(chǔ) 給定一個優(yōu)化圖G, 對G中出現(xiàn)的關(guān)系已經(jīng)施加了全部本地簡化。循環(huán)a) 給出所有可能的半連接∝b) 在有益∝中選擇得益最大或者費用最低的∝，若沒有這樣的∝ ，則中止循環(huán)c)

49、 重新求取受影響的∝的得益與費用，Goto a)后優(yōu)化選出要求較少傳輸?shù)膕ite來收集全部關(guān)系，在此執(zhí)行∝,半連接算法和直接連接算法區(qū)別取決于數(shù)據(jù)傳輸和局部處理的相對費用如果傳輸費用是主要的，采用半連接，SDD-1如果本地費用是主要的，采用直接連接,System R*四種基于直接連接的優(yōu)化算法 （考慮關(guān)系分段）利用站點依賴信息的算法分片與復(fù)制算法站點依賴和數(shù)據(jù)復(fù)制結(jié)合算法Hash劃分算法,R1

50、 R2,,,,,∪,∞,∞,站點依賴設(shè)關(guān)系Ri分片F(xiàn)i1和Fi2, Rj分片F(xiàn)j1和Fj2關(guān)系Ri和Rj在屬性A上滿足條件 Fis ∞ A Fjt= ? , 其中s ≠ t, 則稱Ri和Rj在屬性A上站點依賴也就是說: Ri ∞ A Rj =U (Fis ∞ A Fjs), 對于包含著兩個關(guān)系的片段的每個站點s都成立此時關(guān)系的連接操作無站點間數(shù)據(jù)傳輸,Ri,,,,Rj,,,,,,,,

51、,,本地連接,Result,,,,,,A,f(A),,f(A),,Ri,Rj,∞,推論若Ri和Rj在屬性A上站點依賴，則Ri和Rj在任何包含A的屬性集B上也站點依賴。若Ri和Rj在屬性A上站點依賴，另一屬性（或?qū)傩越M）B函數(shù)決定A，且A ? ?，則Ri和Rj在B上也站點依賴。若Ri和Rj在屬性A上站點依賴，且若Rj和Rk在屬性B上站點依賴，則（Ri ∞ ARj ∞ B Rk）=U（Fis ∞ A Fjs ∞ B Fks)查詢Ri

52、 ∞ A Rj ∞ B Rk的連接操作能夠以無數(shù)據(jù)傳輸?shù)姆绞教幚怼?算法描述Placement_Dependency (Q, P, S)，其中：R={R1,R2,R3,…,Rn}是查詢Q引用的一組關(guān)系P是站點依賴信息S是一個連接操作可以無數(shù)據(jù)傳輸?shù)膱?zhí)行的最大關(guān)系集合開始時S是空集。算法結(jié)束時，若S=R,則Q可以無數(shù)據(jù)傳輸執(zhí)行算法步驟初始化S= ?， R={R1,R2,R3,…,Rn}若能找到一對關(guān)系Ri和Rj在屬性A上

53、站點依賴，且Ri ∞ CRj 包含在Q中，其中C包含A,那么把Ri和Rj放到S中，否則算法終止，返回空集S。只要存在R中而不在S中的關(guān)系Rk滿足下面的特性，就把其放入S中：有S中的關(guān)系比如Rj ，與Rk在屬性B上有站點依賴關(guān)系，且Rj ∞ BRk在Q中或者可以由Q導(dǎo)出，根據(jù)推論3，則Rk可被包含在S中。,查詢引用的某個關(guān)系的所有片段分布在這些站點上,其余被引用的關(guān)系復(fù)制到每一個選定的站點 R1 ∞ R2 = Ui (F1

54、i ∞ R2)算法可應(yīng)用到涉及兩個或兩個以上的關(guān)系的查詢其中一個關(guān)系保持分片狀態(tài)其他關(guān)系可先連接起來，再被復(fù)制到各個站點在各個站點上，其他關(guān)系副本與相應(yīng)的第一個關(guān)系的片斷連接,R1,,,,F21,F22,,,,,,,,,,本地連接,Result,fpartition,union,,,,,,,,,,,,R1,R2,∞,如何確定保持分片關(guān)系的關(guān)系，以使得查詢具有最短的時間估算各種策略的響應(yīng)時間，選擇時間最短的策略，S1站點上響應(yīng)

55、時間(完成時間，F(xiàn)T(Q,S1,R1)）包括三部分，以P.70圖為例：F22到S1的數(shù)據(jù)傳輸時間F22和F21進(jìn)行合并形成S1上的R2副本的時間F11和S1上的R2副本之間連接的時間比較Max{FT(Q,S1,R1), FT(Q,S2 ,,R1)}, Max{FT(Q,S1,R2), FT(Q,S2 ,,R2)}，找出響應(yīng)時間小的保持分片關(guān)系算法忽略了把結(jié)果傳送到要求答案的用戶站點的代價，和將部分結(jié)果組裝成最終結(jié)果的代價，認(rèn)為

56、它們不大重要，或者采用其他算法時這些部分沒有太大差別。,Fragmentation_and_replicate(Q, R, S) For 每個保持分片狀態(tài)的關(guān)系Ri For 每個包含關(guān)系Ri的一個片段的站點Sj 計算在站點Sj執(zhí)行子查詢的完成時間 FT(Q, Sj, Ri) 計算關(guān)系Ri保持分片狀態(tài)下的響應(yīng)時間

57、 Ti = maxj (FT(Q, Sj, Ri)) 選擇Rk = mini (Ti)為保持分片狀態(tài)的關(guān)系,R1,R2,R2,R2,,,,F11,F13,F21,F22,,,,,,,,,,本地連接,Result,fpartition,union,,,,,,,,,,,,R1,R2,F12,∞,舉例 已知R1分段F11和F12的大小為: |F11|=|F12|=50 R2分段F21和

58、F22的大小為: |F21|= 100 |F22|=200 設(shè) 數(shù)據(jù)通訊C0=0, C1=1, 本地連接Cost=J(x1, x2)=5*(x1+x2) 并操作Cost = U(x1, x2) = 2*(x1+x2) 令R1保持分片狀態(tài), 則: 站點S1的完成時間 FT(Q, S1, R1) = 200+2*(100+200)+5*(50+300)=255

59、0 同理: FT(Q, S2, R1) = 100+2*(100+200)+5*(50+300)=2450 因此, 查詢響應(yīng)時間在R1保持分片狀態(tài)為 2550.,令R2保持分片狀態(tài), 則: 站點S1的完成時間 FT(Q, S1, R2) = 50+2*(50+50)+5*(100+100)=1250 同理: FT(Q, S2, R2) = 50+2*(50+50)+5*(200+1

60、00)=1750 因此, 查詢響應(yīng)時間在R2保持分片狀態(tài)為 1750. 因為: R1保持分片狀態(tài)的響應(yīng)時間>R2保持分片狀態(tài)的響應(yīng)時間 所以: 選擇R2保持分片計算查詢,站 點,關(guān)系,R1,R2,R3,,,,設(shè)R1和R2在屬性A上站點依賴, 查詢R1 ∞A R2 ∞B R3,設(shè)R1和R2在屬性A上站點依賴, 查詢R1 ∞ R

61、2 ∞ R3第一個連接因為站點依賴，無傳輸處理第二個連接因為存在R3的副本,也沒有傳輸處理另外一個保證查詢無傳輸?shù)姆椒ㄊ荝1和R2連接執(zhí)行后，形成一個關(guān)系R4，它有兩個片斷：一個由F11 ∞ F21給出一個由F12 ∞ F22給出最后由R4和R3的副本連接得到最后的結(jié)果,連接依賴定義：如果Ri 和Rj 在屬性A上站點依賴或者關(guān)系Ri復(fù)制在關(guān)系Rj各片斷的站點上或者關(guān)系Rj復(fù)制在關(guān)系 Ri各片斷的站點上,利用Has

62、h函數(shù)對分片關(guān)系上的連接屬性作站點依賴計算, 再據(jù)此分片, 以獲取站點依賴的連接算法例如, 運用Hash函數(shù) 1 若a 是奇數(shù) 0 若a 是偶數(shù) 對R中每個元組, h(a)為1送入站點S1, h(a)為0送入站點S2. 于是片段關(guān)系R被劃分為Ro和ReR1 ∞ R2 = (R1o ∞ R2o) U (R1

63、e ∞ R2e),h(a),=,,利用Hash函數(shù)對分片關(guān)系上的連接屬性作站點依賴計算, 再據(jù)此分片, 以獲取站點依賴的JN算法例如, 運用Hash函數(shù) 1 若a 是奇數(shù) 0 若a 是偶數(shù)片斷F11按屬性A的值為奇和偶數(shù)劃分成F11o和F11e，片斷F12劃分成F12o和F12e站點S2上F12’=F11e∪F12e，站點S1

64、上F11’=F11o∪F12o顯然?A ( F11 ’ )和?A(F12’)沒有公共值,前面是奇數(shù)值后面是偶數(shù)值F12’∞ F11’是空集，這說明R1和R2在新組成的片斷下在屬性A上站點依賴。R1 ∞ R2 = （F11’∞ F21’） U （F12’∞ F22’）,h(a),=,,考察三個關(guān)系R1，R2和R3 ,它們在兩個站點上，有兩種情況：在同一屬性A上連接，R1∞A R2 ∞AR3在三個關(guān)系的片斷上應(yīng)用Hash函數(shù)

65、使用新組建的片斷，三個關(guān)系在屬性A上將滿足站點依賴經(jīng)這種劃分和數(shù)據(jù)傳送之后，兩個站點上的片斷在屬性A上的連接就可以并行進(jìn)行，合并執(zhí)行結(jié)果給出答案在不同屬性上連接， R1∞A R2 ∞BR3,兩種情況：在同一屬性A上連接，R1∞A R2 ∞AR3在不同屬性上連接， R1∞A R2 ∞BR3在屬性A上應(yīng)用同樣的Hash函數(shù)，在屬性B上也應(yīng)用同樣的Hash函數(shù)，可能得不到希望的站點依賴因R1中屬性A的值是奇數(shù)的發(fā)往S1，R3中屬

66、性B是奇數(shù)的元組發(fā)往S1.但R2中某些元組可能在A上有奇數(shù)值，而在B上有偶數(shù)值解決方法是允許這些元組在兩個站點上都存在。,R1 ∞ A R2 ∞ B R3 若R1與R2在A上有相同的Hash函數(shù), R2與R3在屬性B上有相同的Hash函數(shù),,站點依賴算法無數(shù)據(jù)傳遞可利用索引做本地連接每個站點連接數(shù)據(jù)總量是R，兩個片段分片和復(fù)制算法數(shù)據(jù)傳輸總量是R數(shù)據(jù)傳送后,可能要重新創(chuàng)建索引每個站點的連接數(shù)據(jù)量是(3/2)R

67、,一個全關(guān)系和一個片斷Hash劃分算法數(shù)據(jù)傳送量是R索引方面, 比片段復(fù)制算法更低每個站點的連接數(shù)據(jù)量同站點依賴,假定每個片段的大小是R大小的一半R/2,兩個關(guān)系在同一個站點，R∞S，稱外層關(guān)系為R,內(nèi)層關(guān)系為S嵌套循環(huán)法順序掃描外層關(guān)系R，對于R的每一元組掃描內(nèi)層關(guān)系S查找在連接屬性上一致的元組，組合起來構(gòu)成結(jié)果的一部分需要掃描一次關(guān)系R和Card（R）次關(guān)系S排序掃描法先把兩個關(guān)系按照連接屬性進(jìn)行排序然后按照

68、連接屬性值的順序掃描這兩個關(guān)系，使匹配的元組成為結(jié)果的一部分對兩個關(guān)系都掃描一次，但增加了排序代價,兩個關(guān)系在不同站點，關(guān)系R和關(guān)系S兩種傳輸方式整體傳輸如果傳輸S,則保存S（被多次掃描，傳輸量少）如果傳輸R，則S可直接使用一次來到的R元組，不保存R(但傳輸量大）按需傳輸只傳輸需要連接的元組，一次一個元組，無需臨時存儲器每次提取都要交換一次信息，傳輸代價高，只在高速局域網(wǎng)中才是合理的三種選擇連接站點的方法R站點S站

69、點其他站點,一個操作內(nèi)的并行一般是不可行的多個操作間的并行是可行的流水線并行在查詢表達(dá)式中，一個操作A的輸出元組作為第二個操作B的輸入在第一個操作尚未產(chǎn)生全部的輸出元組集合之前，第二個操作就可以在它的輸入上進(jìn)行工作可以在不同的站點上運行A和B，在A產(chǎn)生部分結(jié)果元組的同時，B來使用它們獨立的并行查詢表達(dá)式中，那些相互之間沒有依賴關(guān)系的操作可以并行地執(zhí)行,例子：R1∞ R2∞ R3∞ R4有很多策略，其中一個是兩種并行方法

70、結(jié)合使用：把R1送到S2并在S2上計算R1∞ R2，同時把R3送到S4上計算R3∞ R4 在站點S2上計算R1∞ R2的過程中，就可以把已經(jīng)計算出來的元組送到站點S1，而不必等到整個連接計算完成同樣，在站點S4上計算R3∞ R4的過程中，就可以把已經(jīng)計算出來的元組送到站點S1，而不必等到整個連接計算完成。一旦（R1∞ R2）和（ R3∞ R4）的元組到達(dá)站點S1,在S1上就可以開始計算（R1∞ R2）∞（ R3∞ R4 ）。也