數(shù)據(jù)庫(kù)系統(tǒng)概論-第四版chp14

1、1數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論An Introduction to Database System第十四章第十四章 分布式數(shù)據(jù)庫(kù)分布式數(shù)據(jù)庫(kù)2第十四章 分布式數(shù)據(jù)庫(kù)14.1 概述概述14.2 分布式數(shù)據(jù)庫(kù)系統(tǒng)的體系結(jié)構(gòu)分布式數(shù)據(jù)庫(kù)系統(tǒng)的體系結(jié)構(gòu)14.3 查詢處理和優(yōu)化查詢處理和優(yōu)化14.4 分布事務(wù)管理分布事務(wù)管理14.5 小結(jié)小結(jié)314.1 概述14.1.1 分布式數(shù)據(jù)庫(kù)系統(tǒng)分布式數(shù)據(jù)庫(kù)系統(tǒng)14.1.2 分布式數(shù)據(jù)庫(kù)系統(tǒng)的特點(diǎn)分布式數(shù)據(jù)庫(kù)系統(tǒng)的特點(diǎn)414.1.1 分布式數(shù)據(jù)庫(kù)系統(tǒng)什么是分布式數(shù)據(jù)庫(kù)？分布式數(shù)據(jù)庫(kù)由一組數(shù)據(jù)組成，這些數(shù)據(jù)物理上分布在計(jì)算機(jī)網(wǎng)絡(luò)的不同結(jié)點(diǎn)(亦稱場(chǎng)地)上，邏輯上是屬

2、于同一個(gè)系統(tǒng)。 分布性邏輯整體性5分布式數(shù)據(jù)庫(kù)系統(tǒng)(續(xù))圖14.1 一個(gè)分布式數(shù)據(jù)庫(kù)系統(tǒng) v例1如圖14.1所示6分布式數(shù)據(jù)庫(kù)系統(tǒng)(續(xù))區(qū)分一個(gè)系統(tǒng)是若干集中式數(shù)據(jù)庫(kù)的簡(jiǎn)單連網(wǎng)還是分布式數(shù)據(jù)庫(kù)系統(tǒng)的技術(shù)要點(diǎn)在于： 系統(tǒng)是否支持全局應(yīng)用系統(tǒng)是否支持全局應(yīng)用 一個(gè)典型的例子是銀行轉(zhuǎn)賬從一個(gè)分行的賬戶(設(shè)在DB1數(shù)據(jù)庫(kù))中轉(zhuǎn)移若干金額到另一個(gè)分行的賬戶(設(shè)在DB3數(shù)據(jù)庫(kù))中去要同時(shí)更新兩個(gè)結(jié)點(diǎn)上的數(shù)據(jù)庫(kù)7分布式數(shù)據(jù)庫(kù)系統(tǒng)(續(xù))圖14.2 一個(gè)多處理機(jī)系統(tǒng)(SN并行結(jié)構(gòu))v例2如圖14.2所示8分布式數(shù)據(jù)庫(kù)系統(tǒng)(續(xù))多處理機(jī)系統(tǒng)(SN并行結(jié)構(gòu))沒(méi)有局部應(yīng)用分布式數(shù)據(jù)庫(kù)不僅要求數(shù)據(jù)的物理分布，而且要求這

3、種分布是面向處理、面向應(yīng)用的9分布式數(shù)據(jù)庫(kù)系統(tǒng)(續(xù))分布式數(shù)據(jù)庫(kù)：分布式數(shù)據(jù)庫(kù)是由一組數(shù)據(jù)組成的，這組數(shù)據(jù)分布在計(jì)算機(jī)網(wǎng)絡(luò)的不同計(jì)算機(jī)上，網(wǎng)絡(luò)中的每個(gè)結(jié)點(diǎn)具有獨(dú)立處理的能力(稱為場(chǎng)地自治)，可以執(zhí)行局部應(yīng)用。同時(shí)，每個(gè)結(jié)點(diǎn)也能通過(guò)網(wǎng)絡(luò)通信子系統(tǒng)執(zhí)行全局應(yīng)用。場(chǎng)地自治性自治場(chǎng)地之間的協(xié)作性1014.1 概述14.1.1 分布式數(shù)據(jù)庫(kù)系統(tǒng)分布式數(shù)據(jù)庫(kù)系統(tǒng)14.1.2 分布式數(shù)據(jù)庫(kù)系統(tǒng)的特點(diǎn)分布式數(shù)據(jù)庫(kù)系統(tǒng)的特點(diǎn)11分布式數(shù)據(jù)庫(kù)系統(tǒng)的特點(diǎn)(續(xù))一、數(shù)據(jù)獨(dú)立性邏輯獨(dú)立性物理獨(dú)立性數(shù)據(jù)分布獨(dú)立性(分布透明性)用戶的應(yīng)用程序書(shū)寫(xiě)起來(lái)就如同數(shù)據(jù)沒(méi)有分布一樣12分布式數(shù)據(jù)庫(kù)系統(tǒng)的特點(diǎn)(續(xù))二、集中與自治相結(jié)合

4、的控制結(jié)構(gòu)數(shù)據(jù)共享：(1) 局部共享(2)全局共享控制機(jī)制：集中自治13分布式數(shù)據(jù)庫(kù)系統(tǒng)的特點(diǎn)(續(xù))三、適當(dāng)增加數(shù)據(jù)冗余度提高系統(tǒng)的可靠性、可用性提高系統(tǒng)性能四、全局的一致性、可串行性和可恢復(fù)性局部數(shù)據(jù)庫(kù)要保證ACID全局?jǐn)?shù)據(jù)庫(kù)也要保證ACID14第十四章 分布式數(shù)據(jù)庫(kù)14.1 概述概述14.2 分布式數(shù)據(jù)庫(kù)系統(tǒng)的體系結(jié)構(gòu)分布式數(shù)據(jù)庫(kù)系統(tǒng)的體系結(jié)構(gòu)14.3 查詢處理和優(yōu)化查詢處理和優(yōu)化14.4 分布事務(wù)管理分布事務(wù)管理14.5 小結(jié)小結(jié)1514.2 分布式數(shù)據(jù)庫(kù)系統(tǒng)的體系結(jié)構(gòu)14.2.1 分布式數(shù)據(jù)庫(kù)系統(tǒng)的模式結(jié)構(gòu)分布式數(shù)據(jù)庫(kù)系統(tǒng)的模式結(jié)構(gòu)14.2.2 數(shù)據(jù)分片數(shù)據(jù)分片14.2.3 分布透明性

5、分布透明性14.2.4 分布式數(shù)據(jù)庫(kù)管理系統(tǒng)分布式數(shù)據(jù)庫(kù)管理系統(tǒng)1614.2.1 分布式數(shù)據(jù)庫(kù)系統(tǒng)的模式結(jié)構(gòu)圖14.3 分布式數(shù)據(jù)庫(kù)系統(tǒng)的模式結(jié)構(gòu)17分布式數(shù)據(jù)庫(kù)系統(tǒng)的模式結(jié)構(gòu)(續(xù))分布式數(shù)據(jù)庫(kù)系統(tǒng)增加的模式級(jí)別(1) 全局外模式(Global External Schema)(2) 全局概念模式(Global Conceptual Schema)(3) 分片模式(Fragmentation Schema)片段(Fragment)定義片段以及全局關(guān)系到片段的映象(4) 分布模式(Allocation Schema)定義片段的存放地點(diǎn)1814.2 分布式數(shù)據(jù)庫(kù)系統(tǒng)的體系結(jié)構(gòu)14.2.1 分布式數(shù)

6、據(jù)庫(kù)系統(tǒng)的模式結(jié)構(gòu)分布式數(shù)據(jù)庫(kù)系統(tǒng)的模式結(jié)構(gòu)14.2.2 數(shù)據(jù)分片數(shù)據(jù)分片14.2.3 分布透明性分布透明性14.2.4 分布式數(shù)據(jù)庫(kù)管理系統(tǒng)分布式數(shù)據(jù)庫(kù)管理系統(tǒng)1914.2.2 數(shù)據(jù)分片數(shù)據(jù)分片有利于按照用戶的需求較好地組織數(shù)據(jù)的分布有利于控制數(shù)據(jù)的冗余度數(shù)據(jù)分片的方式水平分片垂直分片混合分片導(dǎo)出分片20數(shù)據(jù)分片(續(xù))水平分片按一定的條件將關(guān)系按行(水平方向)分為若干不相交的子集，每個(gè)子集為關(guān)系的一個(gè)片段。垂直分片指將關(guān)系按列(垂直方向)分為若干子集。每個(gè)片段通常都包含關(guān)系的碼 21數(shù)據(jù)分片(續(xù))導(dǎo)出分片是指導(dǎo)出水平分片，即水平分片的條件不是本身屬性的條件而是其他關(guān)系的屬性的條件。 22數(shù)據(jù)

7、分片(續(xù))例學(xué)生選課關(guān)系SC(Sno，Cno，Grade)，按照學(xué)生年齡18歲和18歲分片(學(xué)生年齡是學(xué)生關(guān)系Student的屬性) 年齡18歲的學(xué)生選課片段由下面的查詢結(jié)果組成： SELECT Sno，Cno，Grade FROM S，SC WHERE S.SnoSC.Sno AND S.Sage18；年齡18歲的片段SC_B由下面的查詢結(jié)果組成： SELECT Sno，Cno，Grade FROM S，SC WHERE S.SnoSC.Sno AND S.Sage18；數(shù)據(jù)分片(續(xù))混合分片是指按上述三種分片方式得到的片段繼續(xù)按另一種方式分片。v 例如，先按垂直分片再按水平分片方式繼續(xù)分片

8、。 v 例如，先按水平分片得到的某一片段再進(jìn)行垂直分片。24數(shù)據(jù)分片(續(xù))分片應(yīng)滿足的條件完全性不相交性可重構(gòu)性垂直分片：連接水平分片：并操作2514.2 分布式數(shù)據(jù)庫(kù)系統(tǒng)的體系結(jié)構(gòu)14.2.1 分布式數(shù)據(jù)庫(kù)系統(tǒng)的模式結(jié)構(gòu)分布式數(shù)據(jù)庫(kù)系統(tǒng)的模式結(jié)構(gòu)14.2.2 數(shù)據(jù)分片數(shù)據(jù)分片14.2.3 分布透明性分布透明性14.2.4 分布式數(shù)據(jù)庫(kù)管理系統(tǒng)分布式數(shù)據(jù)庫(kù)管理系統(tǒng)2614.2.3 分布透明性分片透明性 最高層次用戶或應(yīng)用程序只對(duì)全局關(guān)系進(jìn)行操作而不必考慮關(guān)系的分片位置透明 下一層次用戶或應(yīng)用程序不必了解片段的存儲(chǔ)場(chǎng)地，當(dāng)存儲(chǔ)場(chǎng)地改變了，由于分片模式到分布模式的映像(映像3)，應(yīng)用程序不必改變局

9、部數(shù)據(jù)模型透明性 較低層次是指用戶或用戶程序不必了解局部場(chǎng)地上使用的是哪種數(shù)據(jù)模型，模型的轉(zhuǎn)換以及數(shù)據(jù)庫(kù)語(yǔ)言的轉(zhuǎn)換均由映像4完成27分布透明性(續(xù))例1設(shè)在分布式數(shù)據(jù)庫(kù)系統(tǒng)中有全局關(guān)系 Student(Sno，Sname，Sdept，Sage) Student關(guān)系被劃分為兩個(gè)片段S_A和S_B。 S_A代表理學(xué)院的學(xué)生，S_B代表文學(xué)院的學(xué)生。 S_A存儲(chǔ)在場(chǎng)地1(Site1)，S_B冗余地存儲(chǔ)在場(chǎng)地2和場(chǎng)地3上。28分布透明性(續(xù))要求從終端讀入一個(gè)學(xué)號(hào)，查找該學(xué)號(hào)的學(xué)生姓名、年齡，并把它們顯示在屏幕上。設(shè)應(yīng)用程序是用嵌入SQL語(yǔ)句的C語(yǔ)言寫(xiě)的?，F(xiàn)給出查詢部分的算法思想。29分布透明性(續(xù))

10、情況1系統(tǒng)具有分片透明性 Scanf(“% s”,Snumber)； EXEC SQL SELECT Sname,Sage INTO:NAME,:AGE FROM Student WHERE Sno ：Snumber； Printf(% s，% d，NAME，AGE)；程序變量程序變量30分布透明性(續(xù))情況2系統(tǒng)具有位置透明性，但不具有分片透明性 Scanf(% s“,Snumber); EXEC SQL SELECT Sname,Sage INTO:NAME,:AGE FROM S_A WHERE Sno :Snumber; If(! FOUND) EXEC SQL SELECT Snam

11、e,Sage INTO :NAME,:AGE FROM S_B WHERE Sno :Snumber; Printf(% s,% d“,NAME,AGE)；31分布透明性(續(xù))情況3系統(tǒng)只具有局部數(shù)據(jù)模型透明性，不具有位置透明性 Scanf(% s“,Snumber); EXEC SQL SELECT Sname, Sage INTO : NAME,:AGE FROM S_A AT Site1 WHERE Sno :Snumber; If(! FOUND) EXEC SQL SELECT Sname, Sage INTO : NAME,:AGE FROM S_B AT Site2 WHERE

12、Sno:Snumber; Printf(“% s,% d”, NAME,AGE);3214.2 分布式數(shù)據(jù)庫(kù)系統(tǒng)的體系結(jié)構(gòu)14.2.1 分布式數(shù)據(jù)庫(kù)系統(tǒng)的模式結(jié)構(gòu)分布式數(shù)據(jù)庫(kù)系統(tǒng)的模式結(jié)構(gòu)14.2.2 數(shù)據(jù)分片數(shù)據(jù)分片14.2.3 分布透明性分布透明性14.2.4 分布式數(shù)據(jù)庫(kù)管理系統(tǒng)分布式數(shù)據(jù)庫(kù)管理系統(tǒng)3314.2.4 分布式數(shù)據(jù)庫(kù)管理系統(tǒng)分布式數(shù)據(jù)庫(kù)管理系統(tǒng)(Distributed Data Management System，D-DBMS)建立、管理和維護(hù)分布式數(shù)據(jù)庫(kù)的一組軟件 分布式數(shù)據(jù)庫(kù)管理系統(tǒng)(續(xù))D-DBMS的結(jié)構(gòu) 分布式數(shù)據(jù)庫(kù)管理系統(tǒng)的結(jié)構(gòu) 35分布式數(shù)據(jù)庫(kù)管理系統(tǒng)(續(xù))D-D

13、BMS由四部分組成：(1)局部數(shù)據(jù)庫(kù)管理系統(tǒng)LDBMS(Local DBMS)(2)全局?jǐn)?shù)據(jù)庫(kù)管理系統(tǒng)GDBMS(Global DBMS)(3) 全局?jǐn)?shù)據(jù)字典(Global Data Directory，GDD)(4) 通信管理(Communication Management，CM)36分布式數(shù)據(jù)庫(kù)管理系統(tǒng)(續(xù))一、按全局控制方式分類1.全局控制集中的D-DBMS 全局控制成分GDBMS集中在某一結(jié)點(diǎn)上，全局?jǐn)?shù)據(jù)字典只有一個(gè)，也存放在該結(jié)點(diǎn)上。2.全局控制分散的D-DBMS 全局控制成分GDBMS分散在網(wǎng)絡(luò)的每一個(gè)結(jié)點(diǎn)上，全局?jǐn)?shù)據(jù)字典也在每個(gè)結(jié)點(diǎn)上存放一份。3.全局控制部分分散的D-DBMS

14、根據(jù)應(yīng)用的需要將GDBMS和全局?jǐn)?shù)據(jù)字典分散在某些結(jié)點(diǎn)上。37分布式數(shù)據(jù)庫(kù)管理系統(tǒng)(續(xù))二、按局部DBMS的類型分類 同構(gòu)型D-DBMS每個(gè)結(jié)點(diǎn)的局部數(shù)據(jù)庫(kù)具有相同的DBMS即使操作系統(tǒng)和計(jì)算機(jī)硬件并不相同異構(gòu)型D-DBMS各結(jié)點(diǎn)的局部數(shù)據(jù)庫(kù)具有不同的DBMS38第十四章 分布式數(shù)據(jù)庫(kù)14.1 概述概述14.2 分布式數(shù)據(jù)庫(kù)系統(tǒng)的體系結(jié)構(gòu)分布式數(shù)據(jù)庫(kù)系統(tǒng)的體系結(jié)構(gòu)14.3 查詢處理和優(yōu)化查詢處理和優(yōu)化14.4 分布事務(wù)管理分布事務(wù)管理14.5 小結(jié)小結(jié)3914.3 查詢處理和優(yōu)化14.3.1 一個(gè)實(shí)例一個(gè)實(shí)例14.3.2 查詢處理和優(yōu)化要解決的問(wèn)題查詢處理和優(yōu)化要解決的問(wèn)題14.3.3 查詢優(yōu)

15、化的目標(biāo)查詢優(yōu)化的目標(biāo)14.3.4 連接查詢的優(yōu)化連接查詢的優(yōu)化4014.3.1 一個(gè)實(shí)例數(shù)據(jù)庫(kù)：簡(jiǎn)化了的供應(yīng)商和零件數(shù)據(jù)庫(kù) S(Sno，City)104個(gè)元組，存放在場(chǎng)地A； P(Pno，Color)105個(gè)元組，存放在場(chǎng)地B； SP(Sno，Pno)166個(gè)元組，存放在場(chǎng)地A； 設(shè)每個(gè)關(guān)系的元組均為100字節(jié)長(zhǎng)。查詢：求供應(yīng)紅色零件的、北京的供應(yīng)商號(hào) SELECT S.Sno FROM S，P，SP WHERE S.City=北京 AND SP.Pno=P.Pno AND P.Color=紅色41一個(gè)實(shí)例(續(xù))估算值(某些中間結(jié)果的元組數(shù)) 紅色零件數(shù)=10 北京供應(yīng)商的裝運(yùn)單數(shù)=105對(duì)

16、通信系統(tǒng)的假定 數(shù)據(jù)傳輸速度=104字節(jié)/秒 傳輸延遲=1秒一個(gè)實(shí)例(續(xù))6種可能的查詢存取策略，對(duì)每種i 分別計(jì)算通信時(shí)間Ti：Ti總傳輸延遲+總數(shù)據(jù)量/數(shù)據(jù)傳輸速度(單位：b/s)策略1 把關(guān)系P傳送到場(chǎng)地A，在A地進(jìn)行查詢處理。 T1=1+105100/104=103秒(16.7分)一個(gè)實(shí)例(續(xù))策略2 把關(guān)系S、SP傳到場(chǎng)地B，在B地執(zhí)行查詢處理 T2=2+(104+106)100/10410100秒(2.8小時(shí)) 一個(gè)實(shí)例(續(xù))策略3 在場(chǎng)地A連接關(guān)系S和SP，選出城市為北京的元組(105個(gè))，然后對(duì)這些元組中的每個(gè)元組的Pno，詢問(wèn)場(chǎng)地B，看此零件是否紅色。共問(wèn)答105次，由于不是

17、傳送數(shù)據(jù)，只是消息的問(wèn)答，所以 T3=2105 s(2.3天)一個(gè)實(shí)例(續(xù))策略4 在場(chǎng)地B選出紅色零件的元組(10個(gè))，然后對(duì)每一個(gè)元組逐一檢查場(chǎng)地A，看北京供應(yīng)商的裝運(yùn)單中是否有這個(gè)零件裝運(yùn)單(若有則選出S#)。 每做這樣一次檢查包括2次消息，共問(wèn)一答10次，所以 T4=210=20秒一個(gè)實(shí)例(續(xù))策略5 在場(chǎng)地A選出北京的供應(yīng)商的裝運(yùn)單把結(jié)果送到場(chǎng)地B，在場(chǎng)地B完成最后處理，所以 T5=1+(105100)/1041000秒(16.7分)一個(gè)實(shí)例(續(xù))策略6 在場(chǎng)地B的關(guān)系 P 中選出紅色的元組(10個(gè))，把結(jié)果送到場(chǎng)地A完成最終處理。所以 T6=1+(10100)/1041秒48一個(gè)實(shí)

18、例(續(xù))表14.1 分布環(huán)境下查詢策略實(shí)例比較策 略通信時(shí)間方 法116.7分把P傳到場(chǎng)地A22.8小時(shí)把S，SP傳到場(chǎng)地B32.3天對(duì)每一北京的裝運(yùn)單，檢查相應(yīng)零件是否紅色420秒對(duì)每一紅色零件，檢查北京供應(yīng)商中是否有人供應(yīng)516.7分把北京供應(yīng)商的裝運(yùn)單傳送到場(chǎng)地B61秒把紅色零件傳送到場(chǎng)地A49一個(gè)實(shí)例(續(xù))(1) 不同的存取策略通信時(shí)間相差很大，達(dá)多個(gè)數(shù)量級(jí)！ - 優(yōu)化。(2)不同策略，不同的考慮方式 有些策略中數(shù)據(jù)傳輸速度和傳輸延遲都要考慮有些策略中(如策略3、策略4)主要考慮傳輸延遲有些策略中(如策略1、策略2、策略5)數(shù)據(jù)傳輸量大，主要考慮傳輸時(shí)間5014.3 查詢處理和優(yōu)化14

19、.3.1 一個(gè)實(shí)例一個(gè)實(shí)例14.3.2 查詢處理和優(yōu)化要解決的問(wèn)題查詢處理和優(yōu)化要解決的問(wèn)題14.3.3 查詢優(yōu)化的目標(biāo)查詢優(yōu)化的目標(biāo)14.3.4 連接查詢的優(yōu)化連接查詢的優(yōu)化5114.3.2 查詢處理和優(yōu)化要解決的問(wèn)題分布式數(shù)據(jù)庫(kù)系統(tǒng)中的三類查詢：局部查詢遠(yuǎn)程查詢?nèi)植樵兙植坎樵兒瓦h(yuǎn)程查詢優(yōu)化采用的技術(shù)是集中式數(shù)據(jù)庫(kù)的查詢優(yōu)化技術(shù)(代數(shù)優(yōu)化和非代數(shù)優(yōu)化)52查詢處理和優(yōu)化要解決的問(wèn)題(續(xù))全局查詢處理和優(yōu)化涉及的問(wèn)題 1.查詢分解2.選擇操作執(zhí)行的次序3.選擇執(zhí)行操作的方法5314.3 查詢處理和優(yōu)化14.3.1 一個(gè)實(shí)例一個(gè)實(shí)例14.3.2 查詢處理和優(yōu)化要解決的問(wèn)題查詢處理和優(yōu)化要解決的

20、問(wèn)題14.3.3 查詢優(yōu)化的目標(biāo)查詢優(yōu)化的目標(biāo)14.3.4 連接查詢的優(yōu)化連接查詢的優(yōu)化5414.3.3 查詢優(yōu)化的目標(biāo)集中式數(shù)據(jù)庫(kù)的查詢開(kāi)銷I/O代價(jià)+CPU代價(jià)分布式數(shù)據(jù)庫(kù)的查詢開(kāi)銷I/O代價(jià)+CPU代價(jià)+通信代價(jià)查詢優(yōu)化首要目標(biāo)：通信代價(jià)最省55查詢優(yōu)化的目標(biāo)(續(xù))通信代價(jià)可以用下面的公式粗略計(jì)算： TC(X)C0 + X * C1 X：數(shù)據(jù)傳輸量，這里以b(位)為單位計(jì)算；C0 ：兩結(jié)點(diǎn)之間初始化一次傳輸所花費(fèi)的開(kāi)銷，它由通信系統(tǒng)決定，近似為一個(gè)常數(shù)，單位為s(秒)；C1 ：?jiǎn)挝粩?shù)據(jù)(b)傳輸?shù)拇鷥r(jià)，單位為(s/b)。 5614.3 查詢處理和優(yōu)化14.3.1 一個(gè)實(shí)例一個(gè)實(shí)例14.3

21、.2 查詢處理和優(yōu)化要解決的問(wèn)題查詢處理和優(yōu)化要解決的問(wèn)題14.3.3 查詢優(yōu)化的目標(biāo)查詢優(yōu)化的目標(biāo)14.3.4 連接查詢的優(yōu)化連接查詢的優(yōu)化5714.3.4 連接查詢的優(yōu)化兩種優(yōu)化方法半連接：縮減關(guān)系（或片段）進(jìn)而節(jié)省傳輸開(kāi)銷直接連接5814.3.4 連接查詢的優(yōu)化（續(xù)） 半連接 R S R ( B(S)用半連接實(shí)現(xiàn)的連接運(yùn)算R S = (R S) SA = BA = BA = BA = BA = B5914.3.4 連接查詢的優(yōu)化（續(xù)）設(shè)關(guān)系R和S分別存放在結(jié)點(diǎn)r和s上結(jié)點(diǎn)結(jié)點(diǎn)rR結(jié)點(diǎn)結(jié)點(diǎn)sS B(S) R S RR n1. 在結(jié)點(diǎn)s作關(guān)系S的投影n2. 把投影 送到結(jié)點(diǎn)r，代價(jià)為 C0

22、C1 size(B) val(BS)n3. 在結(jié)點(diǎn)r計(jì)算半連接，結(jié)果為R， R = R Sn4. 把R從結(jié)點(diǎn)r送到結(jié)點(diǎn)s，代價(jià)為C0 C1 size(R) card(R)n5. 在結(jié)點(diǎn)s執(zhí)行連接操作B(S)B(S)A = B6014.3.4 連接查詢的優(yōu)化（續(xù)）半連接方案的總代價(jià)Csj 2C0 C1(size(B) val(B(S) + size(R) card(R)直接連接代價(jià)Cjn = C0 C1 size(R) card(R)Csj Cjn 時(shí)采用半連接。6114.3.4 連接查詢的優(yōu)化（續(xù)）直接連接R*系統(tǒng)(IBM SanJose研究室研制)嵌套循環(huán)排序-合并兩種傳輸方式整體傳輸按需傳

23、輸62第十四章 分布式數(shù)據(jù)庫(kù)14.1 概述概述14.2 分布式數(shù)據(jù)庫(kù)系統(tǒng)的體系結(jié)構(gòu)分布式數(shù)據(jù)庫(kù)系統(tǒng)的體系結(jié)構(gòu)14.3 查詢處理和優(yōu)化查詢處理和優(yōu)化14.4 分布事務(wù)管理分布事務(wù)管理14.5 小結(jié)小結(jié)6314.4 分布事務(wù)管理14.4.1 分布事務(wù)的恢復(fù)分布事務(wù)的恢復(fù)14.4.2 并發(fā)控制并發(fā)控制6414.4 分布事務(wù)管理事務(wù)分布執(zhí)行分布事務(wù)的原子性組成該事務(wù)的所有子事務(wù)要么一致地全部提交，要么一致地全部回滾分布事務(wù)的可串行性6514.4.1 分布事務(wù)的恢復(fù)故障和錯(cuò)誤各場(chǎng)地和集中式數(shù)據(jù)庫(kù)相同通信網(wǎng)絡(luò)中信息丟失、長(zhǎng)時(shí)間延遲、網(wǎng)絡(luò)線路中斷等恢復(fù)策略局部事務(wù)管理器：保證子事務(wù)完整性局部管理器之間相互協(xié)調(diào)6614.4.1 分布事務(wù)的恢復(fù)（續(xù)）兩段提交協(xié)議(2-Phase-Commitment Protocol)協(xié)調(diào)者：一個(gè)