數(shù)據(jù)庫原理與技術(shù)第十四章new.ppt

1、第十四章 分布式數(shù)據(jù)庫,概述,分布式數(shù)據(jù)庫系統(tǒng)是數(shù)據(jù)庫技術(shù)和網(wǎng)絡(luò)技術(shù)兩者相互滲透和有機(jī)結(jié)合的結(jié)果,分布式數(shù)據(jù)庫和分布式數(shù)據(jù)庫系統(tǒng),定義 分布式數(shù)據(jù)庫是由一組數(shù)據(jù)組成的，這組數(shù)據(jù)分布在計(jì)算機(jī)網(wǎng)絡(luò)的不同計(jì)算機(jī)上，網(wǎng)絡(luò)中每個(gè)結(jié)點(diǎn)具有獨(dú)立處理的能力（稱為場地自治），可以執(zhí)行局部應(yīng)用（只對本結(jié)點(diǎn)數(shù)據(jù)進(jìn)行存取的應(yīng)用），同時(shí)每個(gè)結(jié)點(diǎn)也能通過網(wǎng)絡(luò)通訊支持全局應(yīng)用（指存取兩個(gè)或兩個(gè)以上的結(jié)點(diǎn)的數(shù)據(jù)庫應(yīng)用）。 分布式數(shù)據(jù)庫強(qiáng)調(diào)場地自治性（局部應(yīng)用）以及自治場地之間的協(xié)作性（全局應(yīng)用）。,分布式數(shù)據(jù)庫和分布式數(shù)據(jù)庫系統(tǒng),分布式數(shù)據(jù)庫具有以下兩個(gè)特點(diǎn)： 分布性 分布性有兩層含義，一是指數(shù)據(jù)庫中的數(shù)據(jù)不是都存儲(chǔ)在同一結(jié)

2、點(diǎn)（更確切的講，不存儲(chǔ)在同一計(jì)算機(jī)的存儲(chǔ)設(shè)備上），而是分布在多個(gè)結(jié)點(diǎn)上；二是指各結(jié)點(diǎn)具有獨(dú)立的數(shù)據(jù)庫處理能力，能夠有效地支持局部應(yīng)用。 邏輯整體性 分布在各結(jié)點(diǎn)的數(shù)據(jù)不是孤立的，而是相互聯(lián)系的，是一個(gè)邏輯整體，能夠支持存取多個(gè)結(jié)點(diǎn)數(shù)據(jù)的全局應(yīng)用。,分布式數(shù)據(jù)庫和分布式數(shù)據(jù)庫系統(tǒng),分布式數(shù)據(jù)庫系統(tǒng)是在集中式數(shù)據(jù)庫系統(tǒng)技術(shù)的基礎(chǔ)上發(fā)展起來的，但不是簡單地把集中式數(shù)據(jù)庫分散的實(shí)現(xiàn)，它豐富和發(fā)展了集中式數(shù)據(jù)庫的許多概念和技術(shù)，具有自己獨(dú)特的特征和性質(zhì)。具體來說，它具有以下特點(diǎn)： 數(shù)據(jù)獨(dú)立性 數(shù)據(jù)獨(dú)立性在分布式數(shù)據(jù)庫系統(tǒng)中具有了更多的含義，它不僅包括數(shù)據(jù)的邏輯獨(dú)立性和物理獨(dú)立性以外，還包括數(shù)據(jù)的分布獨(dú)立

3、性（也稱分布透明性）。分布透明性指用戶不必關(guān)心數(shù)據(jù)的邏輯分片，不必關(guān)心數(shù)據(jù)物理位置分布的細(xì)節(jié)，不必關(guān)心重復(fù)副本（冗余數(shù)據(jù)）一致性問題，也不必關(guān)心局部結(jié)點(diǎn)上數(shù)據(jù)庫支持哪種數(shù)據(jù)模型。,分布式數(shù)據(jù)庫和分布式數(shù)據(jù)庫系統(tǒng),集中與自治相結(jié)合的控制機(jī)構(gòu) 在分布式數(shù)據(jù)系統(tǒng)中，數(shù)據(jù)的共享有兩個(gè)層次：一是局部共享，即在局部數(shù)據(jù)庫中存儲(chǔ)局部結(jié)點(diǎn)各用戶的共享數(shù)據(jù)；二是全局共享。即在分布式數(shù)據(jù)庫系統(tǒng)的各個(gè)結(jié)點(diǎn)也存儲(chǔ)供其他結(jié)點(diǎn)的用戶共享的數(shù)據(jù)，支持系統(tǒng)的全局應(yīng)用。因此，相應(yīng)的控制機(jī)構(gòu)也具有兩個(gè)層次：集中和自治。分布式數(shù)據(jù)庫系統(tǒng)常常采用集中和自治相結(jié)合的控制機(jī)構(gòu)。各局部的DBMS可以獨(dú)立的管理局部的數(shù)據(jù)庫，具有自治功能。同

4、時(shí)系統(tǒng)又設(shè)有集中控制機(jī)構(gòu)，協(xié)調(diào)各局部DBMS的工作，執(zhí)行全局應(yīng)用。,分布式數(shù)據(jù)庫和分布式數(shù)據(jù)庫系統(tǒng),適當(dāng)增加數(shù)據(jù)冗余 在分布式數(shù)據(jù)庫系統(tǒng)中適當(dāng)?shù)脑黾恿巳哂鄶?shù)據(jù)，在不同的結(jié)點(diǎn)存儲(chǔ)同一數(shù)據(jù)的多個(gè)副本，其原因是：一提高系統(tǒng)的可靠性、可用性，當(dāng)某一結(jié)點(diǎn)出現(xiàn)故障時(shí)，系統(tǒng)可以對另一結(jié)點(diǎn)的相同副本進(jìn)行操作，不會(huì)因?yàn)橐惶幑收隙斐烧麄€(gè)系統(tǒng)的癱瘓；二是提高系統(tǒng)性能，系統(tǒng)可以選擇用戶最近的數(shù)據(jù)副本來進(jìn)行操作，減少通信代價(jià)，改善整個(gè)系統(tǒng)的性能。,分布式數(shù)據(jù)庫和分布式數(shù)據(jù)庫系統(tǒng),全局的一致性、可串行性和可恢復(fù)性 分布式數(shù)據(jù)庫系統(tǒng)中各局部數(shù)據(jù)庫應(yīng)滿足集中式數(shù)據(jù)庫的一致性、并發(fā)事務(wù)的可串行性和可恢復(fù)性。除此之外還應(yīng)保證數(shù)

5、據(jù)庫的全局一致性、全局并發(fā)事務(wù)的可串行性和系統(tǒng)全局的可恢復(fù)性。這是因?yàn)樵诜植际綌?shù)據(jù)庫系統(tǒng)中全局應(yīng)用要涉及兩個(gè)以上結(jié)點(diǎn)的數(shù)據(jù)，全局事務(wù)可能由不同結(jié)點(diǎn)上的多個(gè)操作組成。,分布式數(shù)據(jù)庫和分布式數(shù)據(jù)庫系統(tǒng),分布式數(shù)據(jù)庫系統(tǒng)的目標(biāo) 適應(yīng)部門分布的組織結(jié)構(gòu)，降低費(fèi)用 使用數(shù)據(jù)庫的單位在組織上常常是分布的，在地理上也是分布的。分布式數(shù)據(jù)庫系統(tǒng)的結(jié)構(gòu)符合上述分布的組織結(jié)構(gòu)，允許各個(gè)部門將自己常用的數(shù)據(jù)存儲(chǔ)在本地，降低了通信代價(jià)，提高了響應(yīng)速度。 提高系統(tǒng)的可靠性和可用性 將數(shù)據(jù)分布于多個(gè)結(jié)點(diǎn)，并適當(dāng)增加冗余度，可以提供更好的可靠性。,分布式數(shù)據(jù)庫和分布式數(shù)據(jù)庫系統(tǒng),充分利用數(shù)據(jù)庫資源，提高現(xiàn)有集中式數(shù)據(jù)庫的利

6、用率 當(dāng)在一個(gè)大企業(yè)內(nèi)部和大部門中已經(jīng)建成若干個(gè)數(shù)據(jù)庫后，為了利用相互的資源，開發(fā)全局應(yīng)用可以在現(xiàn)有各局部數(shù)據(jù)庫的基礎(chǔ)上做一定的修改和重構(gòu)，建立一個(gè)分布式數(shù)據(jù)庫系統(tǒng)。 逐步擴(kuò)展處理能力和系統(tǒng)規(guī)模 相對于集中式數(shù)據(jù)庫系統(tǒng)，分布式數(shù)據(jù)庫系統(tǒng)能夠方便地將一個(gè)新結(jié)點(diǎn)納入系統(tǒng)，而不影響現(xiàn)有系統(tǒng)的結(jié)構(gòu)和系統(tǒng)的正常運(yùn)行，提供了逐步擴(kuò)展系統(tǒng)能力的較好途徑。,分布式數(shù)據(jù)庫的體系結(jié)構(gòu),映像1,映像2,映像3,映像4,分布式數(shù)據(jù)庫的體系結(jié)構(gòu),全局外模式 全局應(yīng)用的用戶視圖，是全局概念模式的子集。 全局概念模式 定義分布式數(shù)據(jù)庫中數(shù)據(jù)的整體邏輯結(jié)構(gòu)，使得數(shù)據(jù)如同沒有分布一樣。 分片模式 每一個(gè)全局關(guān)系可以分為若干互不

7、相交的部分，每一部分稱為一個(gè)片段。分片模式定義片段以及全局關(guān)系到片段的映像。 分布模式 定義片段的存放結(jié)點(diǎn)。,分布式數(shù)據(jù)庫的體系結(jié)構(gòu),分布（網(wǎng)絡(luò)）透明性 分片透明性 用戶或應(yīng)用程序只對全局關(guān)系進(jìn)行操作而不必考慮關(guān)系的分片。如果分片模式改變了，通過調(diào)整全局模式與分片模式之間的映象關(guān)系來保持全局模式不變。 位置透明性 用戶或應(yīng)用程序不必了解片段的存儲(chǔ)位置。 局部數(shù)據(jù)模型透明性 用戶或應(yīng)用程序不必了解局部場地上使用的是哪種數(shù)據(jù)模型。,分布式數(shù)據(jù)庫的體系結(jié)構(gòu),示例：設(shè)有全局關(guān)系S，它被劃分為兩個(gè)片段S-A（本科生），S-B（研究生），S-B有兩個(gè)副本。,分布式數(shù)據(jù)庫設(shè)計(jì),數(shù)據(jù)在分布式數(shù)據(jù)庫中的存儲(chǔ)途徑

8、 數(shù)據(jù)的重復(fù)存儲(chǔ) 系統(tǒng)在兩個(gè)或兩個(gè)以上結(jié)點(diǎn)維護(hù)關(guān)系R的幾個(gè)完全相同的副本。如果系統(tǒng)的每個(gè)結(jié)點(diǎn)都存儲(chǔ)R的一個(gè)副本，則稱這種重復(fù)存儲(chǔ)為完全重復(fù)存儲(chǔ)。數(shù)據(jù)重復(fù)存儲(chǔ)具有以下幾個(gè)優(yōu)點(diǎn)： 可用性強(qiáng) 如果某個(gè)存儲(chǔ)R的結(jié)點(diǎn)出了故障，系統(tǒng)仍然可以使用其它結(jié)點(diǎn)上的副本繼續(xù)處理用戶查詢，使系統(tǒng)正常運(yùn)行。 增強(qiáng)并行性 由于R的重復(fù)存儲(chǔ)，可以使更多的用戶并行地查詢R。 數(shù)據(jù)的重復(fù)存儲(chǔ)也會(huì)帶來一些問題，如增加了更新操作的開銷，加大了并行控制的難度,分布式數(shù)據(jù)庫設(shè)計(jì),分片存儲(chǔ) 關(guān)系被劃分為幾個(gè)片段，各個(gè)片段存儲(chǔ)在不同的結(jié)點(diǎn)上。將數(shù)據(jù)分片，使數(shù)據(jù)存放的單位不是關(guān)系而是片段，這既有利于按照用戶的需求較好地組織數(shù)據(jù)的分布，也有利

9、于控制數(shù)據(jù)的冗余度。分片時(shí)必須遵循以下原則： 完全性：被劃分關(guān)系中的每個(gè)元組必須屬于一個(gè)片段。 不相交性：同一個(gè)關(guān)系的片段互不相交。 可重構(gòu)性：如果R被劃分為片段R1、R2、Rn，則R能從R1、R2、Rn恢復(fù)出來。,分布式數(shù)據(jù)庫設(shè)計(jì),分片方式 水平分片 垂直分片 導(dǎo)出分片 混合分片,分布式數(shù)據(jù)庫設(shè)計(jì),水平分片 將關(guān)系r依照一定條件按行分為不相交的若干子集r1，r2，rn，每個(gè)子集ri稱為一個(gè)水平片段。 一個(gè)水平片段可以看成是關(guān)系上的一個(gè)選擇。 ri =P（i）（r） 如C_S=DNO=D06（S） 關(guān)系的重構(gòu)可以通過并運(yùn)算來實(shí)現(xiàn)。 r= r1 r2rn,分布式數(shù)據(jù)庫設(shè)計(jì),垂直分片 將關(guān)系r按列

10、分為若干屬性子集r1，r2，rn，每個(gè)子集ri稱為一個(gè)垂直片段。 一個(gè)垂直片段可以看成是關(guān)系上的一個(gè)投影。 ri =Ri（r） 其中Ri是r的一個(gè)屬性子集。 如P_S = PNO，SAL（P） 關(guān)系的重構(gòu)可以通過連接運(yùn)算來實(shí)現(xiàn)。 r= r1 r2 rn 所有分片都包括關(guān)系的碼,分布式數(shù)據(jù)庫設(shè)計(jì),導(dǎo)出分片 導(dǎo)出水平分片，分片的條件不是關(guān)系本身屬性條件，而是其它關(guān)系的屬性條件。 如SC（SNO，CNO，G）按學(xué)生系別分片。 混合分片 關(guān)系按某種方式分片后，得到的片段再按另一種方式繼續(xù)分片。 如SC（SNO，CNO，G）按學(xué)生系別分片，再對每個(gè)片段按成績（及格，不及格）分片。,分布式數(shù)據(jù)庫設(shè)計(jì),組合

11、存儲(chǔ) 這種方法是重復(fù)存儲(chǔ)和分片存儲(chǔ)相結(jié)合的方法。關(guān)系被劃分為幾個(gè)片段，系統(tǒng)為每個(gè)片段維護(hù)幾個(gè)副本，每個(gè)副本存放于不同的結(jié)點(diǎn)上。,分布式數(shù)據(jù)庫設(shè)計(jì),命名和局部自治性 每個(gè)數(shù)據(jù)項(xiàng)（關(guān)系、副本、片段）必須有唯一的名字，在分布式數(shù)據(jù)庫系統(tǒng)中必須保證在不同的結(jié)點(diǎn)上不會(huì)用同一個(gè)名字來代表不同的數(shù)據(jù)項(xiàng)。 途徑1：名字服務(wù)器 所有名字都在名字服務(wù)器中注冊，每個(gè)名字對應(yīng)一個(gè)數(shù)據(jù)項(xiàng)。 缺陷：名字服務(wù)器成為名字解析的瓶頸；其故障將影響整個(gè)系統(tǒng)的運(yùn)行；局部自治性降低。,分布式數(shù)據(jù)庫設(shè)計(jì),途徑2：將結(jié)點(diǎn)標(biāo)識(shí)作為前綴加到該結(jié)點(diǎn)數(shù)據(jù)項(xiàng)的名字前面。使用這一方法，能夠保證名字的唯一性，不須中央控制，局部自治性提高；但不能保證網(wǎng)

12、絡(luò)透明性。,分布式數(shù)據(jù)庫管理系統(tǒng)概述,D-DBMS由四個(gè)部分組成： LDBMS，局部場地上的DBMS，主要功能是建立和管理局部數(shù)據(jù)庫，提供場地自治能力，執(zhí)行局部應(yīng)用以及全局查詢的子查詢。 GDBMS，全局?jǐn)?shù)據(jù)庫管理系統(tǒng)，主要功能是提供分布透明性，協(xié)調(diào)全局事務(wù)的執(zhí)行，協(xié)調(diào)各局部DBMS以完成全局應(yīng)用，保證數(shù)據(jù)庫的全局一致性，執(zhí)行并發(fā)控制，實(shí)現(xiàn)更新同步，提供全局恢復(fù)等功能。,分布式數(shù)據(jù)庫管理系統(tǒng)概述,全局?jǐn)?shù)據(jù)字典，存放全局概念模式、分片模式、分布模式等的定義，以及各模式之間的映像定義，存放有關(guān)用戶存取權(quán)限的定義、完整性約束的定義等。 通信管理，在分布式數(shù)據(jù)庫各場地之間傳送消息和數(shù)據(jù)，完成通信功能。

13、,分布式數(shù)據(jù)庫管理系統(tǒng)概述,D-DBMS的分類 按全局控制發(fā)生分類 全局控制集中的DDBMS 全局?jǐn)?shù)據(jù)庫器和全局?jǐn)?shù)據(jù)字典集中于某一結(jié)點(diǎn)，其優(yōu)點(diǎn)是控制簡單，容易實(shí)現(xiàn)更新一致性，但該結(jié)點(diǎn)容易成為系統(tǒng)的瓶頸，系統(tǒng)也較脆弱。,分布式數(shù)據(jù)庫管理系統(tǒng)概述,全局控制分散的DDBMS 全局?jǐn)?shù)據(jù)庫器和全局?jǐn)?shù)據(jù)字典分散在網(wǎng)絡(luò)上的每一個(gè)結(jié)點(diǎn)上，每個(gè)結(jié)點(diǎn)都能完成全局事務(wù)的協(xié)調(diào)和局部數(shù)據(jù)庫事務(wù)的控制功能。每個(gè)結(jié)點(diǎn)既是全局事務(wù)的參與者，也是全局事務(wù)的協(xié)調(diào)者。其優(yōu)點(diǎn)是結(jié)點(diǎn)獨(dú)立，自治性強(qiáng)，但全局控制的協(xié)調(diào)機(jī)制和一致性維護(hù)都比較困難。 全局控制部分分散的DDBMS 介于上述兩者之間，根據(jù)應(yīng)用的需要將全局?jǐn)?shù)據(jù)庫管理器和全局?jǐn)?shù)據(jù)字

14、典分散在某些結(jié)點(diǎn)上。,分布式數(shù)據(jù)庫管理系統(tǒng)概述,按局部DBMS的類型分類 同構(gòu)型DDBMS 每個(gè)結(jié)點(diǎn)的局部數(shù)據(jù)庫具有相同的DBMS。 異構(gòu)型DDBMS 各結(jié)點(diǎn)的局部數(shù)據(jù)庫具有不同的DBMS,分布式查詢處理,在分布式數(shù)據(jù)庫系統(tǒng)中，數(shù)據(jù)分布在網(wǎng)絡(luò)上的多個(gè)結(jié)點(diǎn)之中，其查詢需要由多個(gè)結(jié)點(diǎn)利用網(wǎng)絡(luò)協(xié)作完成。在集中式數(shù)據(jù)庫中，查詢優(yōu)化的目標(biāo)是產(chǎn)生最小磁盤I/O數(shù)，在分布式數(shù)據(jù)庫中還要考慮網(wǎng)絡(luò)的傳輸時(shí)間和各結(jié)點(diǎn)的并發(fā)執(zhí)行。因此，分布式查詢處理較集中式數(shù)據(jù)庫復(fù)雜。,分布式查詢處理,在分布式數(shù)據(jù)庫系統(tǒng)中，查詢可分為三類：局部查詢，遠(yuǎn)程查詢，全局查詢。局部查詢和遠(yuǎn)程查詢只涉及單個(gè)結(jié)點(diǎn)的數(shù)據(jù)（本地的或遠(yuǎn)程的），可以

15、采用集中式數(shù)據(jù)庫的處理技術(shù)；二全局查詢涉及到多個(gè)結(jié)點(diǎn)的數(shù)據(jù)，因此相對復(fù)雜的多。,分布式查詢處理,分布式查詢處理的過程包括： 查詢變換 將用戶查詢轉(zhuǎn)換為析取范式或合取范式，并進(jìn)行語義分析，檢查查詢的正確性等工作。,分布式查詢處理,數(shù)據(jù)定位 數(shù)據(jù)定位的目的是把用戶定義在全局概念模式上的查詢轉(zhuǎn)換為定義在局部概念模式上的查詢。由于它定義在片段上，也稱為片段查詢。設(shè)查詢Q中包含關(guān)系R1、R2、Rn，而且對于1in，Ri已經(jīng)被劃分為m個(gè)片段Ri1、Ri2、Rim， Ri=F(Ri1、Ri2、Rim)。Q的數(shù)據(jù)定位包括兩步。第一步，對于1in，用Ri=F(Ri1、Ri2、Rim)代替Q中的Ri ，得到一個(gè)等

16、價(jià)的片段查詢FQ。第二步，進(jìn)一步加工FQ，產(chǎn)生一個(gè)與FQ等價(jià)并且效率更高的片段查詢。,分布式查詢處理,全局查詢優(yōu)化 無論是集中式數(shù)據(jù)庫還是分布式數(shù)據(jù)庫其查詢策略的選擇都是以執(zhí)行查詢的預(yù)期代價(jià)為依據(jù)的。在集中式數(shù)據(jù)庫中，查詢執(zhí)行的開銷主要是：I/O+CPU代價(jià)。而在分布式數(shù)據(jù)庫中查詢執(zhí)行的開銷為：I/O+CPU代價(jià)+通信代價(jià)。因此在全局查詢優(yōu)化時(shí)需要選擇執(zhí)行操作的順序，降低網(wǎng)絡(luò)通信的開銷。,分布式查詢處理,局部查詢優(yōu)化 局部查詢優(yōu)化的目的是為每個(gè)局部查詢選擇優(yōu)化的執(zhí)行計(jì)劃，其方法與集中式數(shù)據(jù)庫的查詢優(yōu)化策略和方法相同。,分布式查詢處理,假定每條元組100bit大小 求供應(yīng)紅色零件的、北京的供應(yīng)商

17、號碼 select S.S# from S, P, SP where S.CITY = 北京 and S.S# = SP.S# and SP.P# = P.P# and P.COLOR = 紅色,分布式查詢處理,傳送時(shí)間T=總傳輸延遲+總數(shù)據(jù)量/傳輸速度 1.把關(guān)系P從B站傳送到A站，在A站進(jìn)行查詢 傳送時(shí)間T=1+105 100 /104=103s,分布式查詢處理,2.把關(guān)系S，SP從A站傳送到B站，在B站進(jìn)行查詢 傳送時(shí)間T=2+(104+106)100/104104s,分布式查詢處理,在A站連接S與SP，選出城市為北京的元組（假定有105個(gè)），然后對其中每個(gè)元組的P#，詢問B站，看其是否

18、為紅色。 傳送時(shí)間T=2 105s,分布式查詢處理,在B站選出紅色零件（假定有10個(gè)），然后對每個(gè)元組詢問A站，看北京的供應(yīng)商是否供應(yīng)此零件。 傳送時(shí)間T=2 10=20s,問,分布式查詢處理,5.在A站選出北京的供應(yīng)商（105個(gè)），傳送到B站，在B站完成查詢。 傳送時(shí)間T=1+ 105100/104=103s,分布式查詢處理,在B站選出紅色零件（10個(gè)），把結(jié)果傳送到A站，在A站完成查詢。 傳送時(shí)間T=1+ 10100/104=1.1s,分布式查詢處理,半連接運(yùn)算 定義 半連接R S=R（R S）,=,分布式查詢處理,半連接作用 找出R中能夠與S中元組相連接的元組來，類似于在連接之前先做選擇

19、和投影。 R S = （R S） S R S = （S R） R 半連接的非對稱性 R S S R,分布式查詢處理,半連接在分布式數(shù)據(jù)庫中的應(yīng)用 R與S位于不同結(jié)點(diǎn)S1，S2上，其屬性組分別為R1，R2，要在S1結(jié)點(diǎn)求R和S的連接結(jié)果。 在S1結(jié)點(diǎn)對R做投影，將R縮減為R， R=R1R2（R） 將R 送往結(jié)點(diǎn)S2。 在S2結(jié)點(diǎn)完成S與R的半連接操作，將S縮減為S， S = S R 將S送回結(jié)點(diǎn)S1 。 在S1結(jié)點(diǎn)完成R與S的連接操作， R S = R S,分布式查詢處理,通訊代價(jià)模型 TC（X）= C0+X*C1 其中X為數(shù)據(jù)傳輸量。 C0為兩結(jié)點(diǎn)初始化一次傳輸所花費(fèi)的開銷。 C1為傳輸率，即

20、單位數(shù)據(jù)傳輸所花費(fèi)的時(shí)間。 采用半連接的通訊代價(jià)： CSJ=2C0+(size(R)*card(R)+size(S)*card(S)*C1 不采用半連接的通訊代價(jià)： CJN=C0+size(S)*card(S) *C1 當(dāng)S中參與連接的元組足夠少時(shí)采用半連接策略是有利的。,分布式數(shù)據(jù)庫系統(tǒng)的事務(wù)處理,分布式事務(wù) 數(shù)據(jù)的分布導(dǎo)致事務(wù)具有了分布性。一個(gè)全局事務(wù)的執(zhí)行被劃分為在許多結(jié)點(diǎn)上子事務(wù)的執(zhí)行。系統(tǒng)不但要保證每個(gè)子事務(wù)的原子性，還要保證全局事務(wù)的原子性。這不是哪一個(gè)局部DBMS能夠完成的，而是需要在結(jié)點(diǎn)間進(jìn)行協(xié)調(diào)。,分布式數(shù)據(jù)庫系統(tǒng)的事務(wù)處理,示例：銀行在兩個(gè)帳戶之間轉(zhuǎn)帳。 對集中式數(shù)據(jù)庫，單

21、個(gè)事務(wù)T： A：=A - 100，B：=B+100 對于分布式數(shù)據(jù)庫，假定A在S1,S2各有一副本，B在S3,S4各有一副本，用戶請求在S5發(fā)出，則分布事務(wù)T由T1,T2,T3,T4,T5構(gòu)成： T1, T2： A：=A - 100 T3, T4 ：B：=B + 100 T5 ： 結(jié)果返回給用戶,分布式數(shù)據(jù)庫系統(tǒng)的事務(wù)處理,分布式事務(wù)處理器 事務(wù)管理器TM：管理那些訪問存儲(chǔ)在一個(gè)局部結(jié)點(diǎn)中的數(shù)據(jù)的事務(wù)。事務(wù)可以是局部事務(wù)，也可以是全局事務(wù)的一部分。 事務(wù)協(xié)調(diào)器TC：協(xié)調(diào)該結(jié)點(diǎn)上發(fā)起的各事務(wù)（局部的或全局的）的執(zhí)行。,分布式數(shù)據(jù)庫系統(tǒng)的事務(wù)處理,事務(wù)管理器功能 維護(hù)一個(gè)用于恢復(fù)的日志。 參與適當(dāng)

22、的并發(fā)控制模式，以協(xié)調(diào)在該結(jié)點(diǎn)上執(zhí)行的事務(wù)的并發(fā)執(zhí)行。 事務(wù)協(xié)調(diào)器功能 啟動(dòng)事務(wù)的執(zhí)行。 將事務(wù)分解為若干子事務(wù)，并將子事務(wù)分派到適當(dāng)?shù)慕Y(jié)點(diǎn)上去執(zhí)行。 協(xié)調(diào)事務(wù)的終止，保證事務(wù)在所有的結(jié)點(diǎn)上都提交或都中止。 一個(gè)全局事務(wù)的各個(gè)子事務(wù)要么全部執(zhí)行，要么全部中止。,分布式數(shù)據(jù)庫系統(tǒng)的事務(wù)處理,事務(wù)兩階段提交協(xié)議 假定事務(wù)T在結(jié)點(diǎn)Si發(fā)起， 階段1： 事務(wù)協(xié)調(diào)器TCi向日志中加入一條記錄，并強(qiáng)制該日志寫入穩(wěn)定存儲(chǔ)器中。 TCi將消息發(fā)送到執(zhí)行T的所有結(jié)點(diǎn)上。 當(dāng)某結(jié)點(diǎn)接受到上述消息時(shí)，該結(jié)點(diǎn)的TM回答確定是否提交T中屬于它的那部分，若否，則TM將記錄加入到日志中，并向TCi發(fā)送消息。若是，則TM將記

23、錄加入到日志中，并將日志強(qiáng)制寫入穩(wěn)定存儲(chǔ)器中，并向TCi發(fā)送消息。,分布式數(shù)據(jù)庫系統(tǒng)的事務(wù)處理,階段2： 當(dāng)TCi收到所有結(jié)點(diǎn)對消息的回答時(shí)，或等待響應(yīng)的時(shí)間已過，TCi決定事務(wù)T是提交還是中止。 如果TCi 收到的都是消息，事務(wù)就可以提交，否則事務(wù)必須被中止。根據(jù)結(jié)果的不同向日志中寫入 或者，并強(qiáng)制將日志寫入穩(wěn)定存儲(chǔ)器中。 向所有參與的結(jié)點(diǎn)發(fā)送消息或。 結(jié)點(diǎn)收到此消息后，就把該消息記入日志中。（向TCi發(fā)送消息； TCi收到該消息后，將記錄加入到日志中）。,分布式并發(fā)控制技術(shù),分布式鎖技術(shù) 若分布式數(shù)據(jù)庫中沒有重復(fù)存儲(chǔ)的數(shù)據(jù)，可以采用如下的分布式鎖技術(shù)：每個(gè)結(jié)點(diǎn)保留一個(gè)局部鎖管理器，處理對存

24、儲(chǔ)在本地的數(shù)據(jù)加鎖和釋放鎖的請求。當(dāng)事務(wù)T希望對結(jié)點(diǎn)Si上的數(shù)據(jù)項(xiàng)Q加鎖時(shí)，T簡單的向結(jié)點(diǎn)上的鎖管理器發(fā)出一個(gè)加鎖請求。分布式鎖技術(shù)具有實(shí)現(xiàn)簡單的特點(diǎn)，它處理一個(gè)加鎖請求需要兩次通信，處理釋放鎖請求需要一次通信。但其死鎖處理較為復(fù)雜。,分布式并發(fā)控制技術(shù),集中式鎖技術(shù) 集中式鎖技術(shù)僅有一個(gè)鎖管理器，這個(gè)鎖管理器位于唯一一個(gè)結(jié)點(diǎn)（如Si）上。所有的加鎖和釋放鎖的請求都在該結(jié)點(diǎn)上處理。集中式鎖技術(shù)具有以下優(yōu)點(diǎn)： 實(shí)現(xiàn)簡單 加鎖請求需要兩次通信，釋放鎖請求需要一次通信。 死鎖處理簡單 可按照集中式數(shù)據(jù)庫的方法進(jìn)行處理 集中式鎖技術(shù)具有以下缺點(diǎn)： 瓶頸問題 Si是一個(gè)鎖管理瓶頸 脆弱性 如果Si出現(xiàn)故

25、障，系統(tǒng)無法正常運(yùn)行。,分布式并發(fā)控制技術(shù),混合鎖技術(shù) 混合鎖技術(shù)是集中式和分布式鎖技術(shù)的折中。這種技術(shù)設(shè)置多個(gè)鎖管理器，每個(gè)鎖管理器管理一組數(shù)據(jù)的加鎖和釋放鎖的請求。每個(gè)鎖管理器位于不同的結(jié)點(diǎn)上。,分布式并發(fā)控制技術(shù),以多為主的鎖協(xié)議 系統(tǒng)在每個(gè)結(jié)點(diǎn)上有一個(gè)鎖管理器。在任何結(jié)點(diǎn)Si上的鎖管理器管理存儲(chǔ)在Si上的所有數(shù)據(jù)項(xiàng)副本的加鎖和釋放鎖的請求。當(dāng)事務(wù)T請求對數(shù)據(jù)項(xiàng)Q加鎖時(shí)，如果n個(gè)結(jié)點(diǎn)存儲(chǔ)Q的副本，則T要向n/2以上的存儲(chǔ)Q副本的結(jié)點(diǎn)發(fā)出加鎖請求。,分布式并發(fā)控制技術(shù),區(qū)分鎖類型的鎖協(xié)議 每個(gè)結(jié)點(diǎn)上有一個(gè)鎖管理器。每個(gè)鎖管理器管理所在結(jié)點(diǎn)上存儲(chǔ)的數(shù)據(jù)的加鎖和釋放鎖的請求。共享鎖和互斥鎖采用不同的方式進(jìn)行處理。當(dāng)事務(wù)T需要在數(shù)據(jù)項(xiàng)加共享鎖時(shí)，T直接向一個(gè)存儲(chǔ)該數(shù)據(jù)項(xiàng)副本的結(jié)點(diǎn)的鎖管理器發(fā)出加