分布式數(shù)據(jù)庫及相關(guān)問題課件

1、第六部分 分布式數(shù)據(jù)庫及相關(guān)技術(shù)的討論（第8-11章內(nèi)容）一 分布式數(shù)據(jù)庫概述產(chǎn)生和發(fā)展概念和分類體系結(jié)構(gòu)模式結(jié)構(gòu)及獨(dú)立性。二 分布式數(shù)據(jù)庫系統(tǒng)中存在的技術(shù)問題分布式DB的設(shè)計(jì)分布式DB的查詢分布式DB的事務(wù)管理及并發(fā)。第1頁，共85頁。一 分布式數(shù)據(jù)庫概述I 分布式數(shù)據(jù)庫的產(chǎn)生及發(fā)展a 經(jīng)濟(jì)的發(fā)展b 計(jì)算機(jī)硬件環(huán)境及網(wǎng)絡(luò)的發(fā)展發(fā)展歷程：產(chǎn)生于20世紀(jì)70年代末期，成長于80年代 第一個(gè)分布式數(shù)據(jù)庫系統(tǒng)SDD-1是美國計(jì)算機(jī)公司（CAA）于1976年-1978年設(shè)計(jì)，79年在DEC-10/20上實(shí)現(xiàn)。德國斯圖加特大學(xué)研制的porel系統(tǒng)美國IBM的R*和system R美國加大學(xué)伯克利分校的I

2、ngres法國INRA研制的SIRIUS-DELTA。第2頁，共85頁。1987年：C.J Date提出了完全的，真正的分布式DBS應(yīng)遵循的12條規(guī)則：本地自治性不依賴于中心站點(diǎn)可連續(xù)操作位置獨(dú)立性數(shù)據(jù)分片獨(dú)立性數(shù)據(jù)復(fù)制獨(dú)立性分布式查詢獨(dú)立性分布式事務(wù)管理硬件獨(dú)立性操作系統(tǒng)獨(dú)立性網(wǎng)絡(luò)獨(dú)立性DBMS獨(dú)立性第3頁，共85頁。II 分布式數(shù)據(jù)庫系統(tǒng)的定義及分類1 分布式數(shù)據(jù)庫的定義： 分布式數(shù)據(jù)庫是一個(gè)數(shù)據(jù)集合，這些數(shù)據(jù)分布在由計(jì)算機(jī)網(wǎng)絡(luò)連接起來的若干節(jié)點(diǎn)上，每個(gè)節(jié)點(diǎn)可以管理本地的數(shù)據(jù)應(yīng)用，也可以參與全局?jǐn)?shù)據(jù)應(yīng)用。同時(shí)這些數(shù)據(jù)在邏輯上形成一個(gè)整體，由統(tǒng)一的數(shù)據(jù)庫管理系統(tǒng)進(jìn)行管理。（DDBMS）注：幾

3、個(gè)基本的概念站點(diǎn)：計(jì)算機(jī)連接的一個(gè)邏輯單位，稱為一個(gè)站點(diǎn)。本地（或稱：局部）用戶、本地應(yīng)用：一個(gè)用戶或應(yīng)用只訪問他所注冊的那個(gè)站點(diǎn)。全局用戶、全局應(yīng)用：一個(gè)用戶訪問涉及兩個(gè)或兩個(gè)以上的站點(diǎn)中的數(shù)據(jù)。全局?jǐn)?shù)據(jù)庫（GDB）、局部數(shù)據(jù)庫（LDB）：。第4頁，共85頁。2.分布式數(shù)據(jù)庫系統(tǒng)的基本特點(diǎn)：A 結(jié)構(gòu)特點(diǎn)：物理分布，邏輯相關(guān)。B 應(yīng)用特點(diǎn)：站點(diǎn)自治。第5頁，共85頁。多處理機(jī)系統(tǒng)C.數(shù)據(jù)分布透明性：數(shù)據(jù)的物理獨(dú)立性內(nèi)容更豐富，增加了數(shù)據(jù)分布透明性。-數(shù)據(jù)的邏輯分片、數(shù)據(jù)的物理位置分布、數(shù)據(jù)的復(fù)制，對用戶透明。D.集中與自治兼?zhèn)涞臄?shù)據(jù)庫系統(tǒng)控制機(jī)制.-兩個(gè)層次的數(shù)據(jù)共享：局部/全局?jǐn)?shù)據(jù)共享。第6

4、頁，共85頁。E.增加數(shù)據(jù)冗余度。-利用數(shù)據(jù)冗余提高系統(tǒng)可靠性、可用性和系統(tǒng)性能。F.事務(wù)管理的分布性。-分布環(huán)境下，維護(hù)事務(wù)的原子性、一致性、隔離性和持久性。第7頁，共85頁。3.分布式數(shù)據(jù)庫系統(tǒng)的模式結(jié)構(gòu)第8頁，共85頁。4.分布式數(shù)據(jù)庫系統(tǒng)的分類A 按局部DBMS的數(shù)據(jù)模型分類：-同構(gòu)型：數(shù)據(jù)模型相同 *同質(zhì)同構(gòu)：數(shù)據(jù)模型相同且局部DBMS相同。 *異質(zhì)同構(gòu)：數(shù)據(jù)模型相同外交部局部DBMS不同。 SDD-1和DDM 美國CCA公司 SYSTEM R* 美國IBM公司 POREL 德國斯圖加特大學(xué) -異構(gòu)型 ：數(shù)據(jù)模型不同 MULTIBASE 美國CCA1981研制 IMADAS:H 佛羅

5、里達(dá)大學(xué)1984研制 DDTS HONEYWELL公司1980年研制。第9頁，共85頁。B 按全局控制系統(tǒng)類型分類：-全局控制集中型DDBS DDBS的全局控制機(jī)制及數(shù)據(jù)字典位于一個(gè)中心站點(diǎn)，由中心站點(diǎn)完成全局事務(wù)的協(xié)調(diào)和局部數(shù)據(jù)庫的轉(zhuǎn)換等所有控制功能。-全局控制分散型DDBS DDBS的全局控制機(jī)制及數(shù)據(jù)字典分散在網(wǎng)絡(luò)的各個(gè)站點(diǎn)上，每個(gè)站點(diǎn)都能完成全局事務(wù)的協(xié)調(diào)和局部數(shù)據(jù)轉(zhuǎn)換。-全局控制可變型（主從型） 將站點(diǎn)分成兩組，一組都包含全局控制機(jī)制和數(shù)據(jù)字典，另一組為輔助站點(diǎn)，只包含自己的數(shù)據(jù)應(yīng)用。第10頁，共85頁。4.分布式數(shù)據(jù)庫管理系統(tǒng)的功能結(jié)構(gòu)：除了具有集中式DBMS具有的功能外，還要有如

6、下附加 的功能： * 數(shù)據(jù)跟蹤 * 分布式查詢處理能力 * 分布式事務(wù)管理的能力 * 復(fù)制數(shù)據(jù)的能力 * 安全性 * 分布式目錄管理第11頁，共85頁。二.分布式數(shù)據(jù)庫系統(tǒng)中存在的技術(shù)問題： 1 分布式數(shù)據(jù)庫系統(tǒng)的設(shè)計(jì) -全局模式的設(shè)計(jì) -數(shù)據(jù)分片，分布 2 分布式數(shù)據(jù)庫的查詢處理 3 分布式數(shù)據(jù)庫的事務(wù)管理及并發(fā)控制 4 分布式數(shù)據(jù)庫的可靠性 5 異構(gòu)數(shù)據(jù)庫的連接 6 安全性 7 目錄管理第12頁，共85頁。1.分布式數(shù)據(jù)庫設(shè)計(jì)一 方法：根據(jù)設(shè)計(jì)是基于現(xiàn)存的數(shù)據(jù)系統(tǒng)還是構(gòu)造一個(gè)全新的數(shù)據(jù)庫系統(tǒng)，有兩種方法創(chuàng)建分布式數(shù)據(jù)庫： 組合法：基于現(xiàn)有的系統(tǒng)，建立一個(gè)協(xié)調(diào)管理系統(tǒng)。 -采用自底向上的方式

7、構(gòu)建 重構(gòu)法：創(chuàng)建全新的數(shù)據(jù)庫系統(tǒng) -自頂向下的方式構(gòu)建二 分布式數(shù)據(jù)庫設(shè)計(jì)的內(nèi)容： 1. 數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)-需求分析 1）數(shù)據(jù)需求 2）應(yīng)用需求 應(yīng)用的原發(fā)站點(diǎn)：發(fā)出應(yīng)用請求的站點(diǎn) 應(yīng)用在站點(diǎn)被激活的頻率 應(yīng)用對數(shù)據(jù)對象訪問次數(shù)、類型和分布統(tǒng)計(jì)第13頁，共85頁。2. 數(shù)據(jù)庫設(shè)計(jì)（設(shè)計(jì)的核心任務(wù)） 全局模式設(shè)計(jì) 局部數(shù)據(jù)庫設(shè)計(jì) 數(shù)據(jù)分片設(shè)計(jì) 片段的位置分配設(shè)計(jì)三 分布式數(shù)據(jù)庫設(shè)計(jì)的目標(biāo)： 確保數(shù)據(jù)庫數(shù)據(jù)和應(yīng)用具有最大程度的本地性。 分布式數(shù)據(jù)的可用性和可靠性 工作負(fù)荷分布 存儲的能力和費(fèi)用第14頁，共85頁。四 自頂向下的方式構(gòu)建分布式數(shù)據(jù)庫需求分析全局概念模型全局邏輯模型分片設(shè)計(jì)系統(tǒng)實(shí)現(xiàn)試運(yùn)

8、行及維護(hù)分布設(shè)計(jì)局部邏輯設(shè)計(jì)物理設(shè)計(jì)1 設(shè)計(jì)的步驟：第15頁，共85頁。2 數(shù)據(jù)庫的分片設(shè)計(jì)（1）. 什么叫“片段”？ 指在分布式數(shù)據(jù)庫系統(tǒng)中，某一站點(diǎn)上存儲的數(shù)據(jù)集合。（2）.分片設(shè)計(jì)的目的？ 產(chǎn)生全局?jǐn)?shù)據(jù)的一個(gè)合理的劃分，從而使每個(gè)站點(diǎn)只獲得它所需要的數(shù)據(jù)，最大可能保證應(yīng)用的本地性。（3）分片應(yīng)遵循的一般規(guī)則：設(shè)：R = R1, R2, , Rn 1）完整性 即，tR, 則，必有t Ri ( i = 1,2, , n ) 2）可重構(gòu)性 即，R = Ri ( i = 1,2, , n ) 或R = Ri ( i = 1, , n ) 3）不相交性 即，Ri Rj = (i,j= 1, , n

9、,且i j） 或Ri Rj = 主碼屬性(i ,j= 1, , n,且i j）第16頁，共85頁。（4）分片的基本類型和方法 水平分片，垂直分片，混合分片A 水平分片：對全關(guān)系進(jìn)行選擇操作，把具有相同性質(zhì)的元組進(jìn)行分組，構(gòu)成若干不相交的子集。初級分片和導(dǎo)出分片 初級分片：以關(guān)系自身屬性性質(zhì)分組例1 S( S#, Sname, Age, Sex )define fragment S1 asselect * from S where Sex = M ；define fragment S2 asselect * from S where Sex = F；第17頁，共85頁。 導(dǎo)出分片：用其它關(guān)系的屬

10、性對某一全關(guān)系進(jìn)行分組例2 設(shè)：全局關(guān)系 SC( S#, C#, Grade ) S( S#, Sname, Age, Sex )設(shè)計(jì)需求：按S的“性別”屬性（Sex）去劃分SCDefine fragment SC1 as select SC.S#, C#, Grade from SC, S where SC.S# = S.S# and S.Sex = MDefine fragment SC2 as select SC.S#, C#, Grade from SC, S where SC.S# = S.S# and S.Sex = F第18頁，共85頁。 B 垂直分片：利用投影操作把全關(guān)系的屬性

11、分成若干組，目標(biāo)是把頻繁使用的屬性聚集在一起，且各片段只在鍵屬性下重疊。例3 設(shè)：全局關(guān)系EMP(E#,Name,Dept,Job,Sal,tel)Key = E# 垂直分片： EMP1(E#, Name, Sal, tel) EMP2(E#, Dept, Job)第19頁，共85頁。3 數(shù)據(jù)庫片段位置分配的設(shè)計(jì)兩種方式： 非冗余分配：一個(gè)片段映射到一個(gè)站點(diǎn) 冗余分配：一個(gè)片段映射到多個(gè)站點(diǎn)非冗余“最佳適應(yīng)”分配法： 計(jì)算：Bij = k( Fkj * Nki ) 即，計(jì)算所有的應(yīng)用在站點(diǎn)j上訪問片段i 的總次數(shù)。 對所有站點(diǎn)j確定j, 使得Bij = max( Bij )即，把片段Ri分配到

12、有最大訪問次數(shù)的站點(diǎn)j。i-片段序號j-站點(diǎn)序號k-應(yīng)用序號Fkj-應(yīng)用k在站點(diǎn)j上激活的頻率Rki-應(yīng)用k對片段i 進(jìn)行檢索訪問的次數(shù)(Read)Uki-應(yīng)用k對片段i 進(jìn)行更新訪問的次數(shù)Nki = Rki + Uki -應(yīng)用k對片段i進(jìn)行訪問的總次數(shù)第20頁，共85頁。冗余分配比較復(fù)雜，一般采用下列方法之一進(jìn)行估算：-所有得益站點(diǎn)法：-附加復(fù)制法（1）“所有得益站點(diǎn)”法對所有站點(diǎn)確定非冗余分配方案。從全部結(jié)點(diǎn)中選擇一組站點(diǎn)，使得給這組站點(diǎn)分配片段Ri的一個(gè)拷貝所得到的檢索效益，大于從其它站點(diǎn)對Ri實(shí)施更新的代價(jià)。把片段Ri拷貝分配給該組站點(diǎn)第21頁，共85頁。（2）附加拷貝法對所有站點(diǎn)確定

13、非冗余分配方案。計(jì)算把片段Ri分配給所有站點(diǎn)所能得到的總效益fi（以及一個(gè)站點(diǎn)分得Ri所得到的效益）從分得片段Ri能夠獲取最大益處的站點(diǎn)起，對各站點(diǎn)依次附加片段Ri的一個(gè)拷貝，直到增加片段Ri不能使系統(tǒng)得到明顯效益（或者說效益增大“接近”fi ）為止?？偨Y(jié)：數(shù)據(jù)庫片段及位置分配的設(shè)計(jì)所需要 的參數(shù)均從應(yīng)用需求中得來，總結(jié)這些參數(shù)可用如下三個(gè)表表達(dá)：A 頻率表：各站點(diǎn)每一應(yīng)用激活的次數(shù)B 劃分表：各實(shí)體的潛在水平分片規(guī)則C 極化表：給定站點(diǎn)發(fā)出一給定應(yīng)用訪問一給定片段的概率第22頁，共85頁。需求分析全局概念模型全局邏輯模型分片設(shè)計(jì)系統(tǒng)實(shí)現(xiàn)試運(yùn)行及維護(hù)分布設(shè)計(jì)局部邏輯設(shè)計(jì)物理設(shè)計(jì)頻率表劃分表極化

14、表第23頁，共85頁。分布式數(shù)據(jù)庫設(shè)計(jì)的一個(gè)例子訂票系統(tǒng)維護(hù)分布在三個(gè)網(wǎng)絡(luò)站點(diǎn)（與機(jī)場1，2，3處于同一地理區(qū)域）上的數(shù)據(jù)庫。數(shù)據(jù)庫存儲機(jī)場規(guī)程、班機(jī)起降和旅客訂票等數(shù)據(jù)。（1）概念設(shè)計(jì)-全局概念模式（E-R圖）第24頁，共85頁。（2）收集數(shù)據(jù)與其最相關(guān)的應(yīng)用知識-用操作模式表示a 訂票: 用于旅客預(yù)訂機(jī)票。第25頁，共85頁。b 登記: 用于旅客登機(jī)登記任務(wù)記錄。第26頁，共85頁。c 起飛應(yīng)用:查詢即將從一個(gè)機(jī)場起飛的30個(gè)班機(jī)信息。第27頁，共85頁。（3）在操作模式的基礎(chǔ)上，對每一實(shí)體估算應(yīng)用的定量數(shù)據(jù)，建立邏輯訪問表例“班機(jī)”實(shí)體邏輯訪問表第28頁，共85頁。（4）分布需求分析a.

15、 頻率表：調(diào)研并給出在三個(gè)站點(diǎn)上使用各個(gè)應(yīng)用的頻率（激活的次數(shù)）第29頁，共85頁。b.劃分表：分析各個(gè)實(shí)體各種可能的分片方式及其選擇性*基本劃分第30頁，共85頁。*導(dǎo)出劃分注釋表：第31頁，共85頁。c.極化表：調(diào)研并給出從一個(gè)站點(diǎn)發(fā)出一個(gè)應(yīng)用所需要訪問某片段的概率。第32頁，共85頁。（5）飛機(jī)訂票系統(tǒng)的分布式設(shè)計(jì)a.為各個(gè)實(shí)體選擇合適的分片,原則:滿足本地性，不造成應(yīng)用困難。對本例來予，各個(gè)實(shí)體采用水平分片： “機(jī)場” 由基于區(qū)域的基本水平分片（片段(F1F3)：機(jī)場1，機(jī)場2，機(jī)場3） “班機(jī)” 由基于起飛機(jī)場區(qū)域的導(dǎo)出水平分片（片段(A1A3) ：班機(jī)1，班機(jī)2，班機(jī)3） “旅客”

16、 由基于旅客訂票涉及的班機(jī)起飛機(jī)場所在區(qū)域的導(dǎo)出水平分片（片段(P1P7)：旅客1，旅客2，旅客3，旅客7）第33頁，共85頁。b.進(jìn)行片段的非冗余分配：1）站點(diǎn)1：機(jī)場1，班機(jī)1，旅客12）站點(diǎn)2：機(jī)場2，班機(jī)2，旅客2 旅客4，旅客6，旅客73）站點(diǎn)3：機(jī)場3，班機(jī)3，旅客3 旅客5根據(jù)頻率表和極化表c.進(jìn)行片段的冗余分配： 根據(jù)應(yīng)用可以將旅客4.5.6分配在兩個(gè)站點(diǎn)上，旅客7分配在三個(gè)站點(diǎn)上。第34頁，共85頁。（6）重構(gòu)局部模式第35頁，共85頁。第36頁，共85頁。第37頁，共85頁。本節(jié)要點(diǎn)1. 理解分布式數(shù)據(jù)庫系統(tǒng)的基本概念及特征，總結(jié)分布式數(shù)據(jù)庫分片設(shè)計(jì)方法。熟練掌握使用SQL

17、語句，定義全局關(guān)系模式的分片方法。2. 總結(jié)“自頂向下”設(shè)計(jì)分布式數(shù)據(jù)庫的方法。掌握從設(shè)計(jì)全局設(shè)計(jì)模式到各站點(diǎn)上局部模式的分布設(shè)計(jì)方法。3. 理解分布式數(shù)據(jù)庫片段分配設(shè)計(jì)方法的思想。第38頁，共85頁。2.分布式數(shù)據(jù)庫查詢處理一、分布式查詢處理的步驟查詢分析若該查詢屬于局部查詢，則執(zhí)行局部查詢處理后，即可結(jié)束。查詢分解把全局查詢或遠(yuǎn)程查詢轉(zhuǎn)換成定義在全局關(guān)系上的關(guān)系代數(shù)表達(dá)式，并優(yōu)化該表達(dá)式。查詢本地化把一個(gè)全局關(guān)系上的查詢，轉(zhuǎn)化為對片段的局部查詢。全局查詢優(yōu)化：找出對各個(gè)片段局部查詢結(jié)果之間的最佳操作次序，使得代價(jià)最小。其重點(diǎn)在連接運(yùn)算和并運(yùn)算的優(yōu)化局部優(yōu)化：由確定的片段所在站點(diǎn)執(zhí)行第39頁

18、，共85頁。二、分布式查詢處理的代價(jià)QC估算： QC=I/O+通信代價(jià)T*通信代價(jià)T估算T = 傳輸次數(shù)（每次傳輸延遲時(shí)間+ 每次傳輸數(shù)據(jù)量/ 數(shù)據(jù)傳輸速率）= 傳輸次數(shù)（C0 + X / D）第40頁，共85頁。三、分布式查詢策略的重要性：例設(shè)：教學(xué)數(shù)據(jù)庫中：S(S#, Sname, Age, Sex) 10,000個(gè)元組， 存放在A站點(diǎn)（男/女各一半）SC(S#, C#, Grade) 1,000,000個(gè)元組， 存放在A站點(diǎn)（每人選課100門）C(C#, Cname, Teacher) 100,000個(gè)元組， 存放在B站點(diǎn)假設(shè)：每個(gè)元組的長度為100 bit; 通信系統(tǒng)傳輸速率為10,0

19、00bit / 秒；每次通信延遲時(shí)間為1秒。查詢：選修課名Maths 的男生的學(xué)號和姓名對于本例， C0 = 1秒，D = 10,000 bit / 秒第41頁，共85頁。解：SQL語句是： SELECT S.S#, Sname FROM S, SC, C WHERE S.S# = SC.S# AND SC.C# = C.C# AND SEX = M AND Cname = Maths策略1：把關(guān)系C傳到A站點(diǎn)；在A站點(diǎn)進(jìn)行處理。T1 = 1 + (100,000 *100) / 10,000 16.7(分)第42頁，共85頁。策略2：先在A站點(diǎn)找出男生選課情況（每人平均選100門課），再根據(jù)

20、C#向B站點(diǎn)核查這些男生的選課是否是Maths。(結(jié)果在A站點(diǎn))T3 = 2 * 500,000 *1秒 11.6 (天)策略3：先在B站點(diǎn)找出Maths元組（假設(shè)最多有10門），再把查找結(jié)果傳到A站點(diǎn)，在A站點(diǎn)繼續(xù)執(zhí)行查詢處理。T6 = 1 + 10* 100/10,000 1秒第43頁，共85頁。四、基于關(guān)系代數(shù)等價(jià)變換的查詢優(yōu)化例1 S(S#, Sname, Age, Sex) SC(S#, C#, Grade)其中，S 和SC都采取水平分片：用戶查詢：SELECT distinct Sname FROM S, SC WHERE S.S# = SC.S# and Sex = M and

21、Grade 90轉(zhuǎn)成關(guān)系代數(shù)表達(dá)式：Sname ( Sex = M Grade 90 ( S.S#=SC.S#( S SC ) ) )第44頁，共85頁。把關(guān)系代數(shù)表達(dá)式轉(zhuǎn)換成查詢樹并優(yōu)化從全局查詢到片段查詢的轉(zhuǎn)換第45頁，共85頁。優(yōu)化片段查詢樹a. 對于水平分片，檢查選擇運(yùn)算（）與水平分片的條件（謂詞）。b. 對于垂直分片，注意消去不提供連接運(yùn)算后所需要屬性的分支。第46頁，共85頁。例2 設(shè)：全局關(guān)系:EMP(E#, Ename, Sal, Dept, Dname)現(xiàn)采取垂直分片：查詢問題：SELECT Ename, SalFROM EMP查詢關(guān)系代數(shù)表達(dá)式Ename, Sal( EMP

22、 )第47頁，共85頁。第48頁，共85頁。五 基于半連接算法的全局查詢優(yōu)化1、半連接運(yùn)算:由投影和連接操作導(dǎo)出的一種關(guān)系代數(shù)操作。設(shè)：關(guān)系R和S在屬性R.A=S.B上的半連接操作記為：RA=BS=R ( RA=BS )(B (S)=RA=BSA=BR=S ( SA=BR )(A (R)=SA=B或者:2、利用半連接運(yùn)算實(shí)現(xiàn)連接運(yùn)算S=RA=B(RA=BS)A=BS(SA=BR)A=BR或者:S=RA=B第49頁，共85頁。3.采用半連接運(yùn)算實(shí)現(xiàn)連接運(yùn)算的代價(jià)及優(yōu)化令：tuple(R) 表示關(guān)系R的元組數(shù) size(B) 表示屬性B的數(shù)據(jù)長度現(xiàn)假設(shè)，用戶希望在站點(diǎn)2上得到R 與 S自然連接的結(jié)

23、果RS網(wǎng)絡(luò)站點(diǎn)1站點(diǎn)2RS網(wǎng)絡(luò)站點(diǎn)1站點(diǎn)2(1)B(S)(2)傳送B(S)(3)R=RB(S)B(4)傳送R(5)RSB第50頁，共85頁?？偞鷥r(jià)：T半= 2C0 + C1 *size(B) * tuple(B(S) +size(R) * tuple(R) 采用半連接操作優(yōu)化的原理：兩個(gè)關(guān)系進(jìn)行連接操作之前，去掉無用的無組，減少數(shù)據(jù)傳輸量。采用直接連接運(yùn)算的總代價(jià)：T = C0 + C1 * size(R) * tuple(R)選擇半連接實(shí)現(xiàn)連接運(yùn)算的原則：經(jīng)半連接操作產(chǎn)生少量元組。4. 查詢優(yōu)化策略1）計(jì)算各種半連接運(yùn)算的代價(jià)。2）計(jì)算直接連接運(yùn)算的代價(jià)。3）比較并選出最優(yōu)者。第51頁，共8

24、5頁。六 基于直接連接算法的查詢優(yōu)化1、利用站點(diǎn)依賴信息的連接算法R1R2=F11F21(F12F22)其成立的條件是什么?第52頁，共85頁。條件： A(F11) A(F12) = A(F21) A(F22) = A(F11) A(F22) = A(F12) A(F21) = 站點(diǎn)依賴：設(shè)：RiA、RjA、SiA 、SjA分別表示關(guān)系R、S在站點(diǎn)i、j的A屬性上的取值。若對于i j ,有： RiA SjA = ,則稱關(guān)系R和S在屬性A上站點(diǎn)依賴。性質(zhì)：若關(guān)系R和S在屬性A上站點(diǎn)依賴，則：iRS=(RiSi)第53頁，共85頁。推論：* 如果R和S在屬性A上站點(diǎn)依賴，B A,則，R和S在屬性B

25、上站點(diǎn)依賴。* 如果R和S在屬性A上站點(diǎn)依賴， S和T在屬性B上站點(diǎn)依賴，則：RS=(RiSiTiTi）使用站點(diǎn)依賴算法實(shí)現(xiàn)直接連接運(yùn)算的優(yōu)點(diǎn):1）無數(shù)據(jù)傳送2）可進(jìn)行并行計(jì)算3）可利用本地索引在查詢優(yōu)化過程中，可以判斷什么時(shí)候使用站點(diǎn)依賴算法（P87）第54頁，共85頁。2、分片和復(fù)制算法當(dāng)查詢不能在無數(shù)據(jù)傳送方式下處理，可采用分片和復(fù)制算法，算法的原理： 選擇一組站點(diǎn)，將查詢中的某一個(gè)關(guān)系的所有片段分布到這些站點(diǎn)上，然后把查詢中的其余關(guān)系復(fù)制到每一個(gè)選定的站點(diǎn)上。優(yōu)點(diǎn)：1）可進(jìn)行并行計(jì)算 2）在一定程度上可利用本地索引選擇方法：從假定某一關(guān)系分片，其余關(guān)系復(fù)制，計(jì)算代價(jià)，然后再選擇另一關(guān)系

26、為分片，最后從中選擇代價(jià)最小的方案。第55頁，共85頁。本節(jié)重點(diǎn)1. 總結(jié)分布式數(shù)據(jù)庫查詢優(yōu)化的主要步驟，并與集中式數(shù)據(jù)庫查詢優(yōu)化相比較。2. 總結(jié)利用半連接算法實(shí)現(xiàn)直接連接運(yùn)算的全局查詢優(yōu)化方法特點(diǎn)。在什么條件下可以利用半連接算法實(shí)現(xiàn)直接連接運(yùn)算？第56頁，共85頁。3.分布式事務(wù)管理及恢復(fù)的討論一、分布式事務(wù)概述1.事務(wù)的特點(diǎn)分布式數(shù)據(jù)庫的事務(wù)稱為全局事務(wù)。一個(gè)全局事務(wù)在執(zhí)行時(shí)分解為由若干與相應(yīng)站點(diǎn)有關(guān)的操作序列組成的“子事務(wù)”。1. 原子性 2. 一致性（或可串行性）3. 隔離性 4. 持久性 5. 系統(tǒng)效率6. 系統(tǒng)可用性：分布式事務(wù)既不能影響本站點(diǎn)上事務(wù)的執(zhí)行，也不能影響其它站點(diǎn)上事

27、務(wù)的執(zhí)行第57頁，共85頁。Begin Transaction 開始事務(wù)T1T2TnCommit / Abort (或Rollback) 結(jié)束事務(wù)子事務(wù)或操作序列全局事務(wù)3 分布式事務(wù)代理執(zhí)行機(jī)制2. 分布式事務(wù)的結(jié)構(gòu)事務(wù)代理的概念：一個(gè)事務(wù)代理就是一個(gè)站點(diǎn)上的一個(gè)進(jìn)程第58頁，共85頁。應(yīng)用請求（源站點(diǎn)總代理根代理）RollbackCommit總代理（根代理）子事務(wù)1失敗子事務(wù)1成功子事務(wù)代理n子事務(wù)代理1Begin Transaction子事務(wù)n失敗子事務(wù)n成功第59頁，共85頁。例銀行轉(zhuǎn)帳事務(wù)：把帳號FROM_ACC上數(shù)量為AMOUNT的資金，轉(zhuǎn)入帳號TO_ACC。全局應(yīng)用事務(wù)：read

28、(AMOUNT, FROM_ACC, TO_ACC);begin transactionselect BALANCE into FROM_AMOUNTfrom ACCOUNT_TABLEwhere ACCOUNT_NO = FROM_ACC;if FROM_AMOUNT - AMOUNT 0then abortelse beginupdate ACCOUNT_TABLEset BALANCE = BALANCE - AMOUNTwhere ACCOUNT_NO = FROM_ACC;update ACCOUNT_TABLEset BALANCE = BALANCE + AMOUNTwhere

29、ACCOUNT_NO = TO_ACC;commitend第60頁，共85頁。設(shè)：轉(zhuǎn)出帳戶在源站點(diǎn)上。ROOT_AGENT:read(AMOUNT, FROM_ACC, TO_ACC);begin transactionselect BALANCE into FROM_AMOUNTfrom ACCOUNT_TABLEwhere ACCOUNT_NO = FROM_ACC;if FROM_AMOUNT - AMOUNT 0then abortelse beginupdate ACCOUNT_TABLEset BALANCE = BALANCE - AMOUNTwhere ACCOUNT_NO =

30、 FROM_ACC;create AGENT;send to AGENT(AMOUNT, TO_ACC);waittingcommit / abortend第61頁，共85頁。AGENT（子代理）:begin transactionreceive from ROOT_AGENT( AMOUNT,TO_ACC );update ACCOUNT_TABLEset BALANCE = BALANCE + AMOUNTwhere ACCOUNT_NO = TO_ACC;send to ROOT_AGENT(SUCCESS / FAIL)waittingcommit / abort第62頁，共85頁。二

31、. 分布式事務(wù)的兩階段提交協(xié)議2-PC:Two-Phase Commitment Protocal協(xié)調(diào)者日志參與者。參與者參與者日志日志日志兩階段提交協(xié)議的活動(dòng)機(jī)制：第63頁，共85頁。初始協(xié)調(diào)者寫end of trans到日志初始參與者寫begin transaction等待準(zhǔn)備提交寫ready到日志有要求撤消的？寫abort到日志提交撤消就緒消息類型?撤消提交準(zhǔn)備撤消提交全局撤消全局提交寫abort到日志no寫commit到日志no寫abort到日志abort寫commit到日志commit第64頁，共85頁。兩階段提交協(xié)議的執(zhí)行過程：1）表決階段：對當(dāng)前事務(wù)形成一個(gè)決定。 協(xié)調(diào)者： 寫“

32、開始事務(wù)”日志； 向各個(gè)參與者發(fā)出“準(zhǔn)備”命令； 進(jìn)入等待狀態(tài)。 對于每一個(gè)參與者 參與者接收“準(zhǔn)備”消息； 參與者檢查子事務(wù)，確定是否提交子事務(wù)： Case1:可以提交子事務(wù)： 參與者寫“就緒”日志； 向協(xié)調(diào)者發(fā)“建議提交”消息； 參與者進(jìn)入“就緒”狀態(tài)。 Case2:不可以提交子事務(wù)： 參與者寫“撤消”日志； 向協(xié)調(diào)者發(fā)“建議撤消”消息； 參與者進(jìn)入“撤消”狀態(tài)。第65頁，共85頁。 協(xié)調(diào)者接收到所有參與者的回答后，作出決定：Case1: 若所有參與者發(fā)出“建議提交”的消息，則，協(xié)調(diào)者作出提交全局事務(wù)的決定。 協(xié)調(diào)者寫提交日志； 協(xié)調(diào)者發(fā)出“全局提交”消息； 協(xié)調(diào)者進(jìn)入“提交”狀態(tài)。Cas

33、e2: 若發(fā)現(xiàn)某參與者發(fā)出“建議撤消”的消息，則，協(xié)調(diào)者作出撤消全局事務(wù)的決定。 協(xié)調(diào)者寫撤消日志； 協(xié)調(diào)者發(fā)出“全局撤消”消息； 協(xié)調(diào)者進(jìn)入“撤消”狀態(tài)。 “一票否決”制！2）執(zhí)行階段 對于每一個(gè)處于“就緒”狀態(tài)的參與者： 參與者根據(jù)協(xié)調(diào)者發(fā)出的全局事務(wù)處理指令，或者撤消子事務(wù)，或者提交子事務(wù)第66頁，共85頁。 參與者發(fā)出“確認(rèn)”(ACK)收到全局事務(wù)處理指令消息。 參與者進(jìn)入“撤消”或“提交”狀態(tài)。 協(xié)調(diào)者寫“結(jié)束事務(wù)”日志。兩階段提交協(xié)議的特點(diǎn)： 參與者有權(quán)單方面撤消事務(wù)。 參與者作出“建議提交” 或“建議撤消”決定之后，不能“翻悔”。 處于“就緒”狀態(tài)的參與者可能進(jìn)入提交狀態(tài)，或撤消

34、狀態(tài)。 協(xié)調(diào)者和參與者可能進(jìn)入互相等待狀態(tài)。第67頁，共85頁。1. 試比較集中式、分布式事務(wù)的特點(diǎn)。2. 總結(jié)分布式數(shù)據(jù)庫2-PC的特點(diǎn)，并指出它所存在的問題。本節(jié)重點(diǎn)第68頁，共85頁。4.分布式數(shù)據(jù)庫并發(fā)控制機(jī)制一、分布式并發(fā)控制概述1 分布式并發(fā)控制的目的：為并發(fā)執(zhí)行的全局事務(wù)，產(chǎn)生一個(gè)可串行化調(diào)度。2 局部調(diào)度：每個(gè)站點(diǎn)上的調(diào)度稱為局部調(diào)度3 全局調(diào)度：數(shù)據(jù)庫系統(tǒng)全局事務(wù)的調(diào)度。4全局調(diào)度的可串行性局部調(diào)度的可串行性！局部調(diào)度的可串行性：全局調(diào)度的可串行性？問題：一個(gè)數(shù)據(jù)對象x，可能存在多個(gè)副本x1, x2, , xn。第69頁，共85頁。T1: Read(y);y := y 15;

35、Write(y);Commit;T2: Read(y);y := y * 2;Write(y);Commit;站點(diǎn)1 調(diào)度S1 = R1, W1, C1, R2, W2, C2 站點(diǎn)2 調(diào)度S2 = R2, W2, C2 , R1, W1, C1 設(shè)：站點(diǎn)1，站點(diǎn)2上都有y的副本，且都執(zhí)行事務(wù)T1, T2。全局調(diào)度不可串行！5. 全局調(diào)度的沖突可串行性應(yīng)滿足的條件:單副本控制協(xié)議1) 每一個(gè)局部調(diào)度是沖突可串行化的。2) 任意兩個(gè)沖突操作在它們同時(shí)出現(xiàn)的各個(gè)局部調(diào)度中，必須有相同的執(zhí)行順序。第70頁，共85頁。二、并發(fā)控制法并發(fā)控制算法悲觀法樂觀法封鎖法時(shí)標(biāo)排序法混合法加鎖法時(shí)標(biāo)排序法集中式加

36、鎖主副本加鎖分布式加鎖基本時(shí)標(biāo)排序法多版本時(shí)標(biāo)排序保守時(shí)標(biāo)排序第71頁，共85頁。1）集中式加鎖法:網(wǎng)絡(luò)中某一個(gè)站點(diǎn)被指定為主站點(diǎn)，用于存放整個(gè)分布式數(shù)據(jù)庫的加鎖表，負(fù)責(zé)整個(gè)系統(tǒng)事務(wù)的加鎖.2）主副本加鎖法：每個(gè)數(shù)據(jù)對象指定一個(gè)主副本，不同數(shù)據(jù)對象的主副本放在不同站點(diǎn)上。算法：對主副本加鎖；執(zhí)行更新操作；開鎖3）分布式加鎖算法：鎖的管理由各個(gè)站點(diǎn)調(diào)度器參與、協(xié)調(diào)，本地調(diào)度器負(fù)責(zé)本站數(shù)據(jù)加鎖。算法：對全部副本加鎖；執(zhí)行更新操作；開鎖第72頁，共85頁。三、分布式數(shù)據(jù)庫并發(fā)控制的加鎖技術(shù)1. 分布式數(shù)據(jù)庫加鎖準(zhǔn)則 讀，鎖一個(gè)；寫，鎖全部(ROWA協(xié)議)。 遵守鎖的相容性規(guī)則 遵守兩段鎖協(xié)議（Two

37、 Phase Locking-2PL) 持有X鎖的事務(wù)，必須到結(jié)束事務(wù)才能開鎖。2、死鎖管理1）全局死鎖：分布式數(shù)據(jù)庫中，涉及多個(gè)站點(diǎn)的死鎖稱為全局死鎖。第73頁，共85頁。站點(diǎn)A站點(diǎn)B事務(wù)T1持有對X的鎖事務(wù)T2持有對Y的鎖事務(wù)T2請求對X的鎖事務(wù)T1請求對Y的鎖T2等待T1完成釋放對X的鎖T1等待T2完成釋放對Y的鎖第74頁，共85頁。2）全局等待圖（GWFG）站點(diǎn)A:擁有x 、y的副本；T1: read(x), write(y)站點(diǎn)B:擁有y 、z的副本；T2: read(y), write(z)站點(diǎn)C:擁有z 的副本； T3: read(z), write(x)T1T2T3Xyz第75

38、頁，共85頁。3）死鎖的檢測A 集中式死鎖檢測法 指定某站點(diǎn)上的鎖管理器作為全局死鎖檢測器 其余站點(diǎn)周期地向全局死鎖檢測器發(fā)送LWFG 全局死鎖檢測器產(chǎn)生GWFG，并檢測有無回路B 分布式死鎖檢測法 每個(gè)站點(diǎn)都有死鎖檢測器，負(fù)責(zé)檢測本地可能的死鎖。 每個(gè)站點(diǎn)按照一定規(guī)則，向相關(guān)站點(diǎn)發(fā)送潛在的死鎖回路圖。4）死鎖的解決原則：撤消并恢復(fù)代價(jià)最小的事務(wù)。 撤消并恢復(fù)年輕的事務(wù)。 撤消并恢復(fù)占用資源較少的事務(wù)。 撤消并恢復(fù)具有最短運(yùn)行時(shí)間的事務(wù)。第76頁，共85頁。四 并發(fā)控制的時(shí)標(biāo)技術(shù)1. 時(shí)標(biāo):唯一識別一個(gè)事務(wù)，并用于對事務(wù)進(jìn)行排序的標(biāo)識符。2. 時(shí)標(biāo)的構(gòu)成：“本地計(jì)數(shù)器值， 站點(diǎn)標(biāo)識符3. 時(shí)標(biāo)

39、的創(chuàng)建：一個(gè)事務(wù)Ti 初始化時(shí)，事務(wù)管理器給該事務(wù)分配一個(gè)時(shí)標(biāo)ts(Ti )4. 時(shí)標(biāo)排序（TO）規(guī)則：已知Qi和Qj是分別屬于事務(wù)Ti和Tj沖突操作。若ts(Ti) ts(Tj) , 則Qi在Qj之前執(zhí)行。5、基本時(shí)標(biāo)法第77頁，共85頁。規(guī)則：1）每個(gè)事務(wù)在本地站點(diǎn)開始時(shí)被賦以一個(gè)全局唯一的時(shí)標(biāo)。3）事務(wù)的每個(gè)讀或?qū)懖僮鞫加性撌聞?wù)的時(shí)標(biāo)。2）如果事務(wù)被重新啟動(dòng)，則被賦予新的時(shí)標(biāo)。4）在事務(wù)結(jié)束之前，不對數(shù)據(jù)庫進(jìn)行物理操作。5）對于數(shù)據(jù)庫每個(gè)數(shù)據(jù)對象x，記錄對它進(jìn)行讀操作和寫操作的最大時(shí)標(biāo)RTM(x)和WTM(x)基本時(shí)標(biāo)法的執(zhí)行過程：1）設(shè)TS是對數(shù)據(jù)對象x進(jìn)行讀操作的當(dāng)前時(shí)標(biāo)。若TS WTM(x)， 則， 拒絕該操作；并使發(fā)出該操作的事務(wù)用新時(shí)標(biāo)重新啟動(dòng)；否則， 執(zhí)行讀操作，且使： RTM(x) = max（