【正文】 片的基本類型和方法 水平分片，垂直分片，混合分片 A 水平分片：對全關系進行選擇操作，把具有相同性質的元組進行分組，構成若干不相交的子集。 總結：數(shù)據(jù)庫片段及位置分配的設計所需要 的參數(shù)均從 應用需求中得來，總結這些參數(shù)可用如下三個表表達： A 頻率表：各站點每一應用激活的次數(shù) B 劃分表：各實體的潛在水平分片規(guī)則 C 極化表：給定站點發(fā)出一給定應用訪問一給定片段的 概率 需 求 分 析 全 局 概 念 模 型 全 局 邏 輯 模 型 分 片 設 計 系 統(tǒng) 實 現(xiàn) 試 運 行 及 維 護 分 布 設 計 局 部 邏 輯 設 計 物 理 設 計 頻率表 劃分表 極化表 分布式數(shù)據(jù)庫設計的一個例子 訂票系統(tǒng)維護分布在三個網(wǎng)絡站點（與機場 1， 2， 3處于同一地理區(qū)域）上的數(shù)據(jù)庫。 （ 6）重構局部模式 本節(jié)要點 1. 理解分布式數(shù)據(jù)庫系統(tǒng)的基本概念及特征，總結分布式數(shù)據(jù)庫分片設計方法。 查詢本地化 ?把一個全局關系上的查詢，轉化為對片段的局部查詢。 b. 對于垂直分片，注意消去不提供連接運算后所需要屬性的分支。若對于 i ≠ j ,有： Ri[A] ∩ Sj[A] = φ ,則稱關系 R和 S在屬性 A上站點依賴。 一個全局事務在執(zhí)行時分解為由若干與相應站點有關的操作序列組成的“子事務”。 begin transaction select BALANCE into FROM_AMOUNT from ACCOUNT_TABLE where ACCOUNT_NO = FROM_ACC。 ① 協(xié)調者： ●寫 “ 開始事務 ” 日志； ●向各個參與者發(fā)出 “ 準備 ” 命令； ●進入等待狀態(tài)。 ● 參與者進入“撤消”或“提交”狀態(tài)。 本節(jié)重點 167。 T2: Read(y)。 算法：對主副本加鎖；執(zhí)行更新操作；開鎖 3）分布式加鎖算法：鎖的管理由各個站點調度器參與、協(xié)調，本地調度器負責本站數(shù)據(jù)加鎖。 ● 撤消并恢復占用資源較少的事務。 4）在事務結束之前，不對數(shù)據(jù)庫進行物理操作。 （ 3）每個站點都開辟一個緩沖區(qū)，用于保存其它站點發(fā)來的讀 / 寫操作。 2）各站點進行表決，并把表決結果回送源站點。 。 3. 寫階段：如果驗證獲得通過，則提交該事務，否則重新啟動事務。 例站點 i上緩沖區(qū)隊列情況如下： 站點 1 站點 2 ? 站點 n R11 R12 R13 W11 R21 R22 R23 R24 W21 W22 … Rn1 Rn2 Wn2 讀隊列 寫隊列 站點 i 上處理緩沖區(qū)隊列上的操作算法： 重復執(zhí)行如下步驟，直到?jīng)]有滿足執(zhí)行條件的 Rij 和 Wij ，或者至少出現(xiàn)一個讀 /寫隊列為空， 此時 RT/WT=0： 1）令： RT = min(Rij), WT = min(Wij) i：站點序號； j：讀 /寫操作的序號 2）按下列原則處理緩沖區(qū)內(nèi)各個站點讀 /寫隊列： * 掃描讀隊列若各隊列存在若干個 Rij WT,則，按時標順序 逐一執(zhí)行 Rij，并使 Rij出隊列 * 掃描寫隊列若各隊列存在若干個 Wij RT,則，按時標順序 逐一執(zhí)行 Wij，并使 Wij出隊列 五 并發(fā)控制的樂觀方法 驗證 讀 /計算 寫 /提交 悲觀法事務的執(zhí)行過程 讀 /計算 驗證 寫 /提交 樂觀法事務的執(zhí)行過程 樂觀方法的特點： 1） 任何事務在寫一個數(shù)據(jù)項之前，必須首先讀該數(shù)據(jù)項。 若 TS WTM(x)， 則， 拒絕該操作；并使發(fā)出該操作的事務用新時標重新啟動； 否則， 執(zhí)行讀操作，且使： RTM(x) = max（ RTM(x), TS） 2）設 TS是對數(shù)據(jù)對象 x進行寫操作的當前時標。 四 并發(fā)控制的時標技術 1. 時標 :唯一識別一個事務，并用于對事務進行排序的標識符。 ● 遵守鎖的相容性規(guī)則 ● 遵守兩段鎖協(xié)議（ Two Phase Locking2PL) ● 持有 X鎖的事務，必須到結束事務才能開鎖。 Write(y)。 2 局部調度：每個站點上的調度稱為局部調度 3 全局調度：數(shù)據(jù)庫系統(tǒng)全局事務的調度。 兩階段提交協(xié)議的特點： ● 參與者有權單方面撤消事務。 Case2:不可以提交子事務： ※ 參與者寫 “ 撤消 ” 日志； ※ 向協(xié)調者發(fā) “ 建議撤消 ” 消息； ※ 參與者進入 “ 撤消 ” 狀態(tài)。 create AGENT。 全局應用事務： read(AMOUNT, FROM_ACC, TO_ACC)。 * 如果 R和 S在屬性 A上站點依賴， S和 T在屬性 B上站點依賴，則： R S = (Ri Si T ∪ i Ti） 使用站點依賴算法實現(xiàn)直接連接運算的優(yōu)點 : 1）無數(shù)據(jù)傳送 2）可進行并行計算 3）可利用本地索引 在查詢優(yōu)化過程中，可以判斷什么時候使用站點依賴算法（ P87） 分片和復制算法 當查詢不能在無數(shù)據(jù)傳送方式下處理，可采用分片和復制算法， 算法的原理： 選擇一組站點，將查詢中的某一個關系的所有片段分布到這些 站點上，然后把查詢中的其余關系復制到每一個選定的站點上。 設：關系 R和 S在 屬性 =： R A=B S =π R ( R A=B S ) (π B (S)) =R A=B S A=B R =π S ( S A=B R ) (π A (R)) =S A=B 或者 : 利用半連接運算實現(xiàn)連接運算 S= R A=B (R A=B S) A=B S (S A=B R) A=B R 或者 : S= R A=B 令： tuple(R) 表示關系 R的元組數(shù) size(B) 表示屬性 B的數(shù)據(jù)長度 現(xiàn)假設，用戶希望在站點 2上得到 R 與 S自然連接 的結果 R S 網(wǎng)絡 站點 1 站點 2 R S 網(wǎng)絡 站點 1 站點 2 (1)πB(S) (2)傳送 πB(S) (3)R′=R πB(S) B (4)傳送 R′ (5)R′ S B 總代價： T半 = 2C0 + C1 *[size(B) * tuple(πB(S)) + size(R′) * tuple(R′) ] 采用半連接操作優(yōu)化的原理：兩個關系進行連接操作之前，去掉無用的無組，減少數(shù)據(jù)傳輸量。其重點在連接運算和并運算的優(yōu)化 局部優(yōu)化： ?由確定的片段所在站點執(zhí)行 二、分布式查詢處理的代價 QC估算： QC=I/