【正文】 半 R= 2C0+C1* (size (R’)* card( R’) +size (B)* val( B[S])) – T半 S= 2C0+C1* (size (S’)* card( S’) +size (A)* val( A[R])) ? 比較 T半 R 與 T半 S, 取最優(yōu)者 半連接表示連接的代價估算 5 基于半連接算法的查詢優(yōu)化處理 ? 基本原理 1. 通常有兩次傳輸 2. 但是傳輸?shù)臄?shù)據(jù)量和傳輸整個關(guān)系相比，要遠(yuǎn)遠(yuǎn)少 3. 一般有： T半 T全 4. 半連接的得益：當(dāng) card（ R） card（ R’），可減少站點(diǎn)間的數(shù)據(jù)傳輸量 5. 半連接的損失：傳輸 ?B (S) =C0+C1* size (B)* val( B[S]) 6. 基本原理是在傳到另一個站點(diǎn)做連接前，消除與連接無關(guān)的數(shù)據(jù)，減少做連接操作的數(shù)據(jù)量，從而減小傳輸代價 ? 采用半連接優(yōu)化算法的步驟 – 計(jì)算每種半連接方案的代價，并從中選擇一種最佳方案 – 選擇傳輸代價最小的站點(diǎn)，計(jì)算采用全連接的方案的代價 – 比較兩種方案，確定最優(yōu)方案 半連接算法優(yōu)化原理和步驟 5 基于半連接算法的查詢優(yōu)化處理 SDD1半連接算法 ? 基礎(chǔ) 給定一個優(yōu)化圖 G, 對 G中出現(xiàn)的關(guān)系已經(jīng)施加了全部本地簡化。 ? 循環(huán) a) 給出所有可能的半連接 ∝ b) 在有益 ∝ 中選擇得益最大或者費(fèi)用最低的 ∝ ，若沒有這樣的 ∝ ，則中止循環(huán) c) 重新求取受影響的 ∝ 的得益與費(fèi)用， Goto a) ? 后優(yōu)化 選出要求較少傳輸?shù)?site來收集全部關(guān)系，在此執(zhí)行 ∝ 半連接算法優(yōu)化原理和步驟 5 基于半連接算法的查詢優(yōu)化處理 ? 半連接算法和直接連接算法區(qū)別 – 取決于數(shù)據(jù)傳輸和局部處理的相對費(fèi)用 – 如果傳輸費(fèi)用是主要的，采用半連接， SDD1 – 如果本地費(fèi)用是主要的，采用直接連接 ,System R* ? 四種基于直接連接的優(yōu)化算法 （考慮關(guān)系分段） – 利用站點(diǎn)依賴信息的算法 – 分片與復(fù)制算法 – 站點(diǎn)依賴和數(shù)據(jù)復(fù)制結(jié)合算法 – Hash劃分算法 概述 6 基于直接連接算法的查詢優(yōu)化處理 利用站點(diǎn)依賴信息的算法 6 基于直接連接算法的查詢優(yōu)化處理 站 點(diǎn) 關(guān) 系 S1 S2 F11 F12 F21 F22 R1 R2 ∪ ∞ ∞ ? 站點(diǎn)依賴 設(shè)關(guān)系 Ri分片 Fi1和 Fi2, Rj分片 Fj1和 Fj2 關(guān)系 Ri和 Rj在屬性 A上滿足條件 Fis ∞ A Fjt= ? , 其中 s ? t, 則稱 Ri和 Rj在屬性 A上站點(diǎn)依賴 也就是說 : Ri ∞ A Rj =U (Fis ∞ A Fjs), 對于包含著兩個關(guān)系的片段的每個站點(diǎn) s都成立 此時關(guān)系的連接操作無站點(diǎn)間數(shù)據(jù)傳輸 利用站點(diǎn)依賴信息的算法 6 基于直接連接算法的查詢優(yōu)化處理 Ri Fj1 Fj2 Fj3 Fi1 Fi2 Fi3 Rj 本地連接 Result A f(A) f(A) Ri Rj 利用站點(diǎn)依賴信息的算法 6 基于直接連接算法的查詢優(yōu)化處理 ∞ ? 推論 – 若 Ri和 Rj在屬性 A上站點(diǎn)依賴，則 Ri和 Rj在任何包含 A的屬性集 B上也站點(diǎn)依賴。 – 若 Ri和 Rj在屬性 A上站點(diǎn)依賴，另一屬性（或?qū)傩越M） B函數(shù)決定 A，且 A ? ?，則 Ri和 Rj在 B上也站點(diǎn)依賴。 – 若 Ri和 Rj在屬性 A上站點(diǎn)依賴，且若 Rj和 Rk在屬性 B上站點(diǎn)依賴，則（ Ri ∞ ARj ∞ B Rk） =（ Fis ∞ A Fjs ∞ B Fks) – 查詢 Ri ∞ A Rj ∞ B Rk的連接操作能夠以無數(shù)據(jù)傳輸?shù)姆绞教幚怼? 利用站點(diǎn)依賴信息的算法 6 基于直接連接算法的查詢優(yōu)化處理 ? 算法描述 – Placement_Dependency (Q, P, S)，其中： ? R={R1,R2,R3,…,Rn} 是查詢 Q引用的一組關(guān)系 ? P是站點(diǎn)依賴信息 ? 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上站點(diǎn)依賴，且 Ri ∞ CRj 包含在 Q中，其中 C包含 A,那么把 Ri和 Rj放到 S中，否則算法終止，返回空集 S。 ? 只要存在 R中而不在 S中的關(guān)系 Rk滿足下面的特性，就把其放入 S中：有 S中的關(guān)系比如 Rj ，與 Rk在屬性 B上有站點(diǎn)依賴關(guān)系，且 Rj ∞ BRk在 Q中或者可以由 Q導(dǎo)出，根據(jù)推論 3，則 Rk可被包含在 S中。 利用站點(diǎn)依賴信息的算法 6 基于直接連接算法的查詢優(yōu)化處理 分片和復(fù)制算法 6 基于直接連接算法的查詢優(yōu)化處理 站 點(diǎn) 關(guān) 系 S1 S2 F11 F12 R2 R2 R1 R2 ? 查詢引用的某個關(guān)系的所有片段分布在這些站點(diǎn)上 ,其余被引用的關(guān)系復(fù)制到每一個選定的站點(diǎn) R1 ∞ R2 = Ui (F1i ∞ R2) ? 算法可應(yīng)用到涉及兩個或兩個以上的關(guān)系的查詢 – 其中一個關(guān)系保持分片狀態(tài) – 其他關(guān)系可先連接起來，再被復(fù)制到各個站點(diǎn) – 在各個站點(diǎn)上，其他關(guān)系副本與相應(yīng)的第一個關(guān)系的片斷連接 分片和復(fù)制算法 6 基于直接連接算法的查詢優(yōu)化處理 R1 R2 R2 R2 R11 R12 R13 R21 R22 本地連接 Result f partition union R1 R2 分片和復(fù)制算法 6 基于直接連接算法的查詢優(yōu)化處理 ∞ ? 如何確定保持分片關(guān)系的關(guān)系，以使得查詢具有最短的時間 ? 估算各種策略的響應(yīng)時間，選擇時間最短的策略， S1站點(diǎn)上響應(yīng)時間 (完成時間， FT(Q,S1,R1)）包括三部分，以 圖為例： – 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é)果傳送到要求答案的用戶站點(diǎn)的代價，和將部分結(jié)果組裝成最終結(jié)果的代價，認(rèn)為它們不大重要，或者采用其他算法時這些部分沒有太大差別。 分片和復(fù)制算法 6 基于直接連接算法的查詢優(yōu)化處理 Fragmentation_and_replicate(Q, R, S) For 每個保持分片狀態(tài)的關(guān)系 Ri For 每個包含關(guān)系 Ri的一個片段的站點(diǎn) Sj 計(jì)算在站點(diǎn) Sj執(zhí)行子查詢的完成時間 FT(Q, Sj, Ri) 計(jì)算關(guān)系 Ri保持分片狀態(tài)下的響應(yīng)時間 Ti = maxj (FT(Q, Sj, Ri)) 選擇 Rk = mini (Ti)為保持分片狀態(tài)的關(guān)系 分片和復(fù)制算法 6 基于直接連接算法的查詢優(yōu)化處理 R1 R2 R2 R2 F11 F13 F21 F22 本地連接 Result f partition union R1 R2 F12 分片和復(fù)制算法 6 基于直接連接算法的查詢優(yōu)化處理 ∞ 舉例 已知 R1分段 F11和 F12的大小為 : |F11|=|F12|=50 R2分段 F21和 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) , 則 : 站點(diǎn) S1的完成時間 FT(Q, S1, R1) = 200+2*(100+200)+5*(50+300)=2550 同理 : FT(Q, S2, R1) = 100+2*(100+200)+5*(50+300)=2450 因此 , 查詢響應(yīng)時間在 R1保持分片狀態(tài)為 2550. 分片和復(fù)制算法 6 基于直接連接算法的查詢優(yōu)化處理 令 R2保持分片狀態(tài) , 則 : 站點(diǎn) S1的完成時間 FT(Q, S1, R2) = 50+2*(50+50)+5*(100+100)=1250 同理 : FT(Q, S2, R2) = 50+2*(50+50)+5*(200+100)=1750 因此 , 查詢響應(yīng)時間在 R2保持分片狀態(tài)為 1750. 因?yàn)?: R1保持分片狀態(tài)的響應(yīng)時間 R2保持分片狀態(tài)的響應(yīng)時間 所以 : 選擇 R2保持分片計(jì)算查詢 分片和復(fù)制算法 6 基于直接連接算法的查詢優(yōu)化處理 站 點(diǎn) 關(guān) 系 R1 R2 R3 S1 S2 F11 F12 F21 F22 R3 R3 設(shè) R1和 R2在屬性 A上站點(diǎn)依賴 , 查詢 R1 ∞A R2 ∞B R3 站點(diǎn)依賴和數(shù)據(jù)復(fù)制結(jié)合 6 基于直接連接算法的查詢優(yōu)化處理 設(shè) R1和 R2在屬性 A上站點(diǎn)依賴 , 查詢 R1 ∞ R2 ∞ R3 ?第一個連接因?yàn)檎军c(diǎn)依賴，無傳輸處理 ?第二個連接因?yàn)榇嬖?R3的副本 ,也沒有傳輸處理 ?另外一個保證查詢無傳輸?shù)姆椒ㄊ?R1和 R2連接執(zhí)行后，形成一個關(guān)系 R4，它有兩個片斷： ?一個由 F11 ∞ F21給出 ?一個由 F12 ∞ F22給出 ?最后由 R4和 R3的副本連接得到最后的結(jié)果 站點(diǎn)依賴和數(shù)據(jù)復(fù)制結(jié)合 6 基于直接連接算法的查詢優(yōu)化處理 連接依賴定義： ?如果 Ri 和 Rj 在屬性 A上站點(diǎn)依賴 ?或者關(guān)系 Ri復(fù)制在關(guān)系 Rj各片斷的站點(diǎn)上 ?或者關(guān)系 Rj復(fù)制在關(guān)系 Ri各片斷的站點(diǎn)上 站點(diǎn)依賴和數(shù)據(jù)復(fù)制結(jié)合 6 基于直接連接算法的查詢優(yōu)化處理 ? 利用 Hash函數(shù)對分片關(guān)系上的連接屬性作站點(diǎn)依賴計(jì)算 , 再據(jù)此分片 , 以獲取站點(diǎn)依賴的連接算法 ? 例如 , 運(yùn)用 Hash函數(shù) 1 若 a 是奇數(shù) 0 若 a 是偶數(shù) 對 R中每個元組 , h(a)為 1送入站點(diǎn) S1, h(a)為 0送入站點(diǎn) S2. 于是片段關(guān)系 R被劃分為 Ro和 Re ? R1 ∞ R2 = (R1o ∞ R2o) U (R1e ∞ R2e) h(a) = Hash劃分算法 6 基于直接連接算法的查詢優(yōu)化處理 ? 利用 Hash函數(shù)對分片關(guān)系上的連接屬性作站點(diǎn)依賴計(jì)算 , 再據(jù)此分片 , 以獲取站點(diǎn)依賴的 JN算法 ? 例如 , 運(yùn)用 Hash函數(shù) 1 若 a 是奇數(shù) 0 若 a 是偶數(shù) ? 片斷 F11按屬性 A的值為奇和偶數(shù)劃分成 F11o和 F11e，片斷 F12劃分成 F12o和 F12e ? 站點(diǎn) S2上 F12’=F11e∪ F12e，站點(diǎn) S1上 F11’=F11o∪ F12o ? 顯然 ?A ( F11 ’ )和 ?A