分布式數(shù)據(jù)庫系統(tǒng)及其應用通過本課程的學習，使得同學們對分布式數(shù)據(jù)庫學科的重要技術不僅知其然，更要知其所以然。掌握分布式數(shù)據(jù)庫系統(tǒng)的理論、結(jié)構(gòu)、技術和方法。了解實現(xiàn)分布式數(shù)據(jù)庫的關鍵和難點。認清數(shù)據(jù)庫學科的發(fā)展趨勢和前景。為今后從事分布式數(shù)據(jù)庫研究和應用打下良好的專業(yè)基礎。課程目標課程內(nèi)容（1）第1章分布式數(shù)據(jù)庫系統(tǒng)概述第2章分布式數(shù)據(jù)庫系統(tǒng)的設計第3章分布式數(shù)據(jù)庫中的查詢處理和優(yōu)化第4章分布式數(shù)據(jù)庫中的事務管理和恢復第5章分布式數(shù)據(jù)庫中的并發(fā)控制第6章分布式數(shù)據(jù)庫中的可靠性第7章分布式數(shù)據(jù)庫的安全性與目錄管理第8章分布式數(shù)據(jù)庫與客戶機/服務器模式第9章分布式數(shù)據(jù)庫與WWW數(shù)據(jù)庫和移動數(shù)據(jù)庫第10章分布式數(shù)據(jù)庫系統(tǒng)的發(fā)展趨勢●

課程講授（32學時）教材：邵佩英：《分布式數(shù)據(jù)庫系統(tǒng)及其應用》（第2版），科學出版社，北京，2005

考核方式1.大作業(yè)之實驗報告（40%）2.最后閉卷考試（60%）選修了分布式數(shù)據(jù)庫的小伙伴們請注意啦：1.選擇文獻分析類型的，以個人為單位。電子版提交：作業(yè)報告；紙質(zhì)版提交：作業(yè)報告2.選擇項目類型的，組隊不能多于5個人，要做與分布式數(shù)據(jù)庫相關的項目。電子版提交：作業(yè)報告和代碼；紙質(zhì)版提交：作業(yè)報告3.請于14周之前提交大作業(yè),電子版發(fā)送至2215489878@（標明是分布式數(shù)據(jù)庫大作業(yè)），紙質(zhì)版交到我的工位1-062（沒有人在的情況下請放在桌子顯眼處）4.1

分布式數(shù)據(jù)庫的定義和特點4分布式數(shù)據(jù)庫系統(tǒng)的定義和分類分布式數(shù)據(jù)庫定義（P.4）：物理上分散而邏輯上集中的系統(tǒng)，它使用計算機網(wǎng)絡將地理位置分散而管理和控制又需要不同程度集中的多個邏輯單位（通常是集中式數(shù)據(jù)庫系統(tǒng)）連接起來，共同組成一個統(tǒng)一的數(shù)據(jù)庫系統(tǒng)。分布式數(shù)據(jù)庫系統(tǒng)可以看成是計算機網(wǎng)絡和數(shù)據(jù)庫系統(tǒng)的有機結(jié)合。分布式數(shù)據(jù)庫系統(tǒng)的特點（P.4~5）物理分布性：數(shù)據(jù)不是存放在一個站點上邏輯整體性：是與分散式數(shù)據(jù)庫系統(tǒng)的區(qū)別站點自治性：是與多處理機系統(tǒng)的區(qū)別數(shù)據(jù)分布透明性集中與自治相結(jié)合存在適當?shù)臄?shù)據(jù)冗余度事務管理的分布性4.1

分布式數(shù)據(jù)庫的定義和特點4分布式數(shù)據(jù)庫系統(tǒng)的定義和分類DB1DB2DB3全局用戶1局部用戶1全局用戶2局部用戶2全局用戶3局部用戶3網(wǎng)絡DDBMSDBMS1DDBMSDBMS2DDBMSDBMS3分布式數(shù)據(jù)庫系統(tǒng)示意圖（P.6）4.2

分布式數(shù)據(jù)庫的分類4分布式數(shù)據(jù)庫系統(tǒng)的定義和分類按局部DBMS的數(shù)據(jù)模型分類（P.7）同構(gòu)型DDBS同構(gòu)同質(zhì)型同構(gòu)異質(zhì)型異構(gòu)型DDBS按DDBS的全局控制類型分類（P.8）全局控制集中型DDBS：全局控制機制和全局數(shù)據(jù)詞典位于中心站點全局控制分散型DDBS：全局控制機制和全局數(shù)據(jù)詞典分散在網(wǎng)絡的各個站點上。全局控制可變型DDBS：也稱主從型DDBS。分成兩組站點，一組包含全局控制機制和全局控制詞典，另外一組不包含。5.1

分布式數(shù)據(jù)庫系統(tǒng)的體系結(jié)構(gòu)5分布式數(shù)據(jù)庫系統(tǒng)的體系結(jié)構(gòu)和組成成分分布式數(shù)據(jù)庫系統(tǒng)的體系結(jié)構(gòu)（P.9）GDBMSLDBMSLDD全局用戶局部用戶網(wǎng)絡CMLDBGDDGDB全局用戶GDDGDB局部用戶GDBMSLDBMSLDDCMLDBGDBMSLDBMSCM全局用戶GDDGDB局部用戶LDDLDB數(shù)據(jù)（P.9）分布式數(shù)據(jù)庫的主體局部數(shù)據(jù)：只提供本站點的局部應用所需要的數(shù)據(jù)。全局數(shù)據(jù)：雖然物理上存儲在個站點上，但是參與全局應用。數(shù)據(jù)目錄（P.9）數(shù)據(jù)結(jié)構(gòu)的定義、全局數(shù)據(jù)的分片、分布、授權(quán)、事務恢復等描述局部數(shù)據(jù)目錄：局部站點上的數(shù)據(jù)詞典全局數(shù)據(jù)目錄：提供全局數(shù)據(jù)的描述和管理相關信息5.2

分布式數(shù)據(jù)庫系統(tǒng)的組成成分5分布式數(shù)據(jù)庫系統(tǒng)的體系結(jié)構(gòu)和組成成分數(shù)據(jù)分片（P.10）又稱數(shù)據(jù)分割、數(shù)據(jù)分段，局部數(shù)據(jù)庫是由全局數(shù)據(jù)庫分割而成水平分片（對全局關系施加選擇運算）垂直分片（對全局關系施加投影運算）混合分片（兩種方法的混合）數(shù)據(jù)分片要準守的原則：完備性原則：要把所有的數(shù)據(jù)映射到各個片斷中可重構(gòu)原則：關系分片后的各個片斷可重構(gòu)整個關系不相交原則：關系分片后的各個片斷不能重疊5.3DDBS中數(shù)據(jù)的分片與分布5分布式數(shù)據(jù)庫系統(tǒng)的體系結(jié)構(gòu)和組成成分分布式數(shù)據(jù)庫的模式結(jié)構(gòu)（P.12）5.4

分布式數(shù)據(jù)庫的模式結(jié)構(gòu)5分布式數(shù)據(jù)庫系統(tǒng)的體系結(jié)構(gòu)和組成成分全局外模式全局概念模式分片模式分配模式局部概念模式局部內(nèi)模式DB局部概念模式局部內(nèi)模式DB全局外模式全局外模式全局DBMS局部DBMS

分布式數(shù)據(jù)庫特有的集中式數(shù)據(jù)庫也有的映象1映象3映象2映象4良好的可靠性和可用性（P.34）提高系統(tǒng)效率，降低通信費用（P.34）較大的靈活性和可伸縮性（P.35）經(jīng)濟性和保護投資（P.35）適應組織的分布式管理和控制（P.35）數(shù)據(jù)分布具有透明性和站點具有較好的自治性（P.35）7.1DDBS的優(yōu)點7DDBS的優(yōu)點和存在的技術問題最重要的問題是通信網(wǎng)絡速度問題如何控制數(shù)據(jù)的分片、分布與冗余度（P.35）如何實現(xiàn)異構(gòu)數(shù)據(jù)庫的互聯(lián)（P.36）如何優(yōu)化分布式數(shù)據(jù)庫的查詢處理（P.36）如何更好地實現(xiàn)分布式數(shù)據(jù)庫的更新處理（P.36）如何實現(xiàn)分布式數(shù)據(jù)庫的并發(fā)控制機制（P.36）如何實現(xiàn)分布式數(shù)據(jù)庫的恢復控制機制（P.36）如何實現(xiàn)目錄管理（P.36）7.2DDBS中存在的技術問題7DDBS的優(yōu)點和存在的技術問題分布式數(shù)據(jù)庫設計概述1創(chuàng)建方法1.1

組合法剖析網(wǎng)絡功能剖析原有數(shù)據(jù)庫系統(tǒng)解決數(shù)據(jù)的一致性、完整性和可靠性難度較大

通常是異構(gòu)或者同構(gòu)異質(zhì)DDBS用戶1用戶2用戶n分布式協(xié)調(diào)管理系統(tǒng)DBMS1DBMS2DBMSm

網(wǎng)絡分布式數(shù)據(jù)庫設計概述1DDBS創(chuàng)建方法1.1

重構(gòu)法根據(jù)實現(xiàn)環(huán)境和用戶需求按照DDBS的設計思想和方法從總體設計做起，包括LDBS,重新建立一個DDBS可有效解決數(shù)據(jù)一致性、完整性和可靠性問題。

通常是同構(gòu)異質(zhì)或同構(gòu)同質(zhì)DDBS用戶1用戶2用戶n分布式數(shù)據(jù)庫管理系統(tǒng)

網(wǎng)絡2.1

步驟和內(nèi)容2自頂向下設計DDB需求分析概念設計視圖設計分布設計物理設計觀察與監(jiān)視系統(tǒng)需求全局概念模式訪問模式外部模式定義局部概念模式物理模式用戶輸入視圖集成用戶輸入反饋反饋自頂向下設計過程假若有全局關系R被分片為子關系(片段)集合R={R1,R2,…,Rn},則R滿足完整性xR,RiR必有xRi，i=1,2,…,n可重構(gòu)性存在函數(shù)g使得R=g(R1,R2,…,Rn)即，R=∪Ri(水平分片）,R=∞Ri（垂直分片）不相交性Ri∩Rj=空集,i≠j,i,j=1,2,…,n(水平分片)Ri∩Rj=主鍵屬性,i,j=1,2,…,n(垂直分片)2.2

數(shù)據(jù)的分片設計2自頂向下設計DDB

分片原則基本水平分片以關系自身的屬性性質(zhì)為基礎，執(zhí)行“選擇”操作，將關系分割成若干個不相交的片段。

R={R1,R2}R1=

loc=Sa(E)R2=

loc=Sb(E)2.2

數(shù)據(jù)的分片設計2自頂向下設計DDB

基本水平分片若R={R1,R2,…,Rn},則完整性對于每一個元組

t

R,RiR使得

tRi

不相交性對

tRi,Rj

使得

tRj,ij可重構(gòu)性操作是∪

(可以忽略,因為完整性就蘊含著)R=

∪{R1,R2,…,Rn}P={p1,p2,…,pn}是一簡單謂詞集合，為保證分片的正確性，P必須是：完整的：同一分片中的任意兩個元組被應用同樣概率訪問。最小的：集合P中的所有謂詞與應用密切相關。(不同分片中的元組被訪問的概率是不同的)具有完整性和最小性不是必要條件,但是對于簡化分配問題有好處2.2

數(shù)據(jù)的分片設計2自頂向下設計DDB

基本水平分片例子EMP(E#,NAME,DEPT,JOB,SAL,TEL,…)DEPT={1,2}JOB={‘P’,‘-P’}假定，應用經(jīng)常查詢的內(nèi)容是屬于部門1且是程序員的職員。則可能有的水平分段限定

P={DEPT=1}（不是完整的）

P={DEPT=1,JOB=‘P’}（是完整的、最小的）

P={DEPT=1,JOB=‘P’,SAL>500}（完整的，不是最小的）2.2

數(shù)據(jù)的分片設計2自頂向下設計DDB

基本水平分片如何保證分片原則“手工”檢查! e.g.,R1=

loc=‘Sa’E;R2=

loc=‘Sb’E生成具有滿足分段原則的限定謂詞2.2

數(shù)據(jù)的分片設計2自頂向下設計DDB

基本水平分片設有關系E(e#,name,Loc,sal,A,…),查詢使用的簡單謂詞（Ai

Value）是:A<10,A>5,Loc=Sa,Loc=Sb下一步: -生成“小項”謂詞

-消除無用謂詞給定簡單謂詞集Pr={p1,p2,..pn},則“小項”謂詞（mintermpredicate）形式:

p1*

p2*…pn*

這里pk*是pk

或是?pk2.2

數(shù)據(jù)的分片設計2自頂向下設計DDB

謂詞生成舉例(1)A<10

A>5

Loc=SA

Loc=SB(2)A<10

A>5

Loc=SA

?(Loc=SB)(3)A<10

A>5

?(Loc=SA)

Loc=SB(4)A<10

A>5

?(Loc=SA)

?(Loc=SB)(5)A<10

?(A>5)

Loc=SA

Loc=SB(6)A<10

?(A>5)

Loc=SA

?(Loc=SB)(7)A<10

?(A>5)

?(Loc=SA)

Loc=SB(8)A<10

?(A>5)

?(Loc=SA)

?(Loc=SB)2.2

數(shù)據(jù)的分片設計2自頂向下設計DDB小項謂詞選擇(9)?(A<10)

A>5

Loc=SA

Loc=SB(10)?(A<10)

A>5

Loc=SA

?(Loc=SB)(11)?(A<10)

A>5

?(Loc=SA)

Loc=SB(12)?(A<10)

A>5

?(Loc=SA)

?(Loc=SB)(13)?(A<10)

?(A>5)

Loc=SA

Loc=SB(14)?(A<10)

?(A>5)

Loc=SA

?(Loc=SB)(15)?(A<10)

?(A>5)

?(Loc=SA)

Loc=SB(16)?(A<10)

?(A>5)

?(Loc=SA)

?(Loc=SB)2.2

數(shù)據(jù)的分片設計2自頂向下設計DDB小項謂詞選擇R2: 5<A<10

Loc=SA

R3: 5<A<10

Loc=SB

R6: A

5

Loc=SA

R7: A

5

Loc=SB

R10: A

10

Loc=SA

R11: A

10

Loc=SB

分片結(jié)果2.2

數(shù)據(jù)的分片設計2自頂向下設計DDB注:無用段的消除依賴于應用的語義e.g.:

如果LOC可以是

SA,SB,則最終分段集合應該加上R4: 5<A<10

LocSA

LocSB

R8: A

5

LocSA

LocSB

R12: A

10

LocSA

LocSB2.2

數(shù)據(jù)的分片設計2自頂向下設計DDB導出分片從另一個關系的屬性性質(zhì)或水平分片推導出來例子

SC(S#,C#,GRADE)S(S#,SNAME,AGE,SEX)要求：將SC劃分為男生各門課成績和女生的各門成績2.2

數(shù)據(jù)的分片設計2自頂向下設計DDB

導出水平分片按S的屬性導出

DefinefragmentSC1asSelectSC.S#,C#,GRADEFromSC,SWhereSC.S#=S.S#andSEX=‘M’DefinefragmentSC2asSelectSC.S#,C#,GRADEFromSC,SWhereSC.S#=S.S#andSEX=‘F’按S的水平分片（SF/SM）導出DefinefragmentSC1asSelect*FromSCWhereS#in(SelectSF.SfromSF)DefinefragmentSC2asSelect*FromSCWhereS#in(SelectSM.SfromSM)

2.2

數(shù)據(jù)的分片設計2自頂向下設計DDB

導出水平分片例子通過“投影”操作把一個全局關系的屬性分成若干組，基本目標是將使用頻繁的屬性聚集在一起全局關系R={Ri},i=1,2,…,n如果屬性A∈R,必有A∈Ri,i=1,2,…,n,而且Ri∩Rj=Ap,i≠j，Ap為R的碼或元組標識符，則稱{Ri},i=1,2,…,n}是關系R的一個垂直分片。如果屬性A∈R,必有A∈Ri,i=1,2,…,n,而且Ri∩Rj=（Ap,A-p),i≠j，A-p為R的一個或多個非碼屬性時，稱{Ri},i=1,2,…,n}是關系R的一個垂直群集。2.2

數(shù)據(jù)的分片設計2自頂向下設計DDB

垂直分片和垂直群集EMP(E#,NAME,SAL,TEL,MAGNUM,DEPT)假定Key:E#主要應用:Sa站點查詢NAME,SAL,TEL;Sb站點查詢NAME,MAGNUM,DEPT垂直分片:EMP1(E#,NAME,SAL,TEL)EMP2(E#,MAGNUM,DEPT)垂直群集:EMP1(E#,NAME,SAL,TEL)EMP2(E#,NAME,MAGNUM,DEPT)2.2

數(shù)據(jù)的分片設計2自頂向下設計DDB

垂直分片/垂直群集例子2.2

數(shù)據(jù)的分片設計2自頂向下設計DDBE1EE2

垂直分片例子

例子: E1(#,NM,LOC) E2(#,SAL)E(#,NM,LOC,SAL) E1(#,NM) E2(#,LOC) E3(#,SAL)2.2

數(shù)據(jù)的分片設計2自頂向下設計DDB

垂直分片設計非鍵屬性A1,A2,…,An應用Q1,Q2,….,Qmfreq(Qi)=Qi

的訪問頻率2.2

數(shù)據(jù)的分片設計2自頂向下設計DDB

屬性的親和關系7578021A47975400A540974845A3024810050A201455096A1

A5A4A3A2A1R1[K,A1,A2,A3]R2[K,A4,A5]2.2

數(shù)據(jù)的分片設計2自頂向下設計DDB

屬性和矩陣窮舉屬性親和矩陣的列排列行與列要同時調(diào)整發(fā)現(xiàn)好的“分割點”極大化每個分割內(nèi)的親合力（affinity）,極小化跨分割的訪問2.2

數(shù)據(jù)的分片設計2自頂向下設計DDB垂直分片算法

單個片段F站點S1,…Sm

變量X1,…,Xm0如果F不在Sj上存儲

1如果F在Sj上存儲

Totalcost=ReadCost+WriteCost+ StorageCost

確定Xj的值,1jm,使總代價極小Xj=2.3

數(shù)據(jù)的分配設計2自頂向下設計DDB分配的簡化模型班機機號日期可用座位出入口座位圖延期班機機號日期可用座位機型座位圖班機班機1班機2機號日期可用座位座位圖出入口延期機型5.2構(gòu)造全局模式設計問題5自底向上設計分布式數(shù)據(jù)庫5.3識別相似性和識別沖突5自底向上設計分布式數(shù)據(jù)庫識別相似性模式命名相似性模式結(jié)構(gòu)相似性不同Site上有相似應用,使用各自DB的數(shù)據(jù)副本,則這兩Site之間有某些相似點.識別沖突命名沖突：同物異名（EMP,EMPLOYEE），異物同名域差異定標差異：計量單位不同(天、小時、分鐘、秒）結(jié)構(gòu)差異：同一對象有的用實體描述,有的用屬性描述.處理操作期間不一致的數(shù)據(jù)策略（5種，p64-65）從到機場登記起飛時間到達時間符號城市權(quán)力區(qū)域安全規(guī)則座位號檢查行李班機訂票旅客機號日期可用座位進入口座位圖延期種類名字電話系統(tǒng)A概念模式5.4自底向上綜合的一個例子5自底向上設計分布式數(shù)據(jù)庫站點1站點2站點3站點3站點2站點1A1R1A3R2A2R3A1R1,R2A3A2R2,R3方案A方案B讀取更新10101055實現(xiàn)步驟和方法轉(zhuǎn)換一：查詢問題——〉關系代數(shù)表達式轉(zhuǎn)換二：關系代數(shù)表達式——〉查詢樹轉(zhuǎn)換三：全局查詢樹分拆成片段查詢樹優(yōu)化：利用關系代數(shù)等價變換規(guī)則的優(yōu)化算法，優(yōu)化查詢樹，進而優(yōu)化查詢4.1

基本原理和實現(xiàn)方法4基于關系代數(shù)等價變換的查詢優(yōu)化處理4.2

查詢優(yōu)化處理舉例4基于關系代數(shù)等價變換的查詢優(yōu)化處理全局關系S(S#,SNAME,AGE,SEX)和SC(S#,C#,GRADE)被水平分片hhSSCS1:SEX=‘M’男學生全體S2:SEX=‘F’女學生全體SC1：C#<=20課程號<=20SC2：C#>20課程號>20查詢問題：查找至少有一門功課成績在90分以上的男生姓名

SNAME(SEX=‘M’andGRADE>90(S.S#=SC.S#(S×SC)))4.2

查詢優(yōu)化處理舉例4基于關系代數(shù)等價變換的查詢優(yōu)化處理

SNAMES.S#=SC.S#S.S#=SC.S#

S#,SNAME

S#,SNAME

GRADE>90

GRADE>90

SNAME

SEX=‘M’

SSC

SEX=‘M’US1[SEX=‘M’]S2[SEX=‘F’]USC1[C#

‘C20’]SC1[C#>’C20’](a)全局關系上的查詢樹(b)對應片段上的查詢樹

變換∞∞4.2

查詢優(yōu)化處理舉例4基于關系代數(shù)等價變換的查詢優(yōu)化處理

SNAMES.S#=SC.S#S.S#=SC.S#

S#,SNAME

S#,SNAME

GRADE>90

SNAME

SEX=‘M’USC1[C#

‘C20’（c）把投影和選擇下移后的查詢樹(d)一個簡化的查詢樹產(chǎn)生矛盾去掉一支

S#,SNAME

GRADE>90S2[SEX=‘F’]

SEX=‘M’SC1[C#

‘C20’]SC2[C#

‘C20’]S1[SEX=‘M’]SC2[C#

‘C20’S1[SEX=‘M’]UUGRADE>90]GRADE>90]∞∞4.2

查詢優(yōu)化處理舉例4基于關系代數(shù)等價變換的查詢優(yōu)化處理水平分片的查詢優(yōu)化的基本思想：盡量把選擇條件下移到分片的限定關系處再把分片的限定關系與選擇條件進行比較去掉它們之間存在矛盾的相應片斷如果最后剩下一個水平片斷，則重構(gòu)全局關系的操作中，就可去掉“并”操作（至少可以減少“并”操作的次數(shù)）4.2

查詢優(yōu)化處理舉例4基于關系代數(shù)等價變換的查詢優(yōu)化處理全局關系EMP(EMP#,ENAME,SALARY,DEPT#,DNAME)垂直分片：E1(EMP#,DEPT#,DNAME)EMP2(EMP#,ENAME,SALARY)vSE1E2:查詢問題：雇員的姓名和工資情況

ENAME,SALARY(EMP)4.2

查詢優(yōu)化處理舉例4基于關系代數(shù)等價變換的查詢優(yōu)化處理ENAME,SALARY

ENAME

EMP#,DEPT#,

EMP#,ENAME,

DEPTNAMESALARYENAME,SALARY

EMP#,ENAME,

SALARYENAME,SALARY

EMPE2:EMP#,ENAME,SALARY去掉無關的片段

移植到片段上去掉連接E1：E2：E1.EMP#=E2.EMP#∞∞4.2

查詢優(yōu)化處理舉例4基于關系代數(shù)等價變換的查詢優(yōu)化處理垂直分片的查詢優(yōu)化的基本思想：把垂直分片所用到的屬性集，與查詢條件中的投影操作所涉及的屬性相比較，去掉無關的垂直片斷如果最后只剩下一個垂直片斷與查詢有關時，去掉重構(gòu)全局關系的“連接”操作（至少可以減少“連接”操作的次數(shù)）假定有兩個關系R,S,在屬性R.A=S.B上做半連接操作，可表示為：R∝A=BS=

R(R∞A=BS)=R∞A=B(B(S))S∝A=BR=

S(S∞A=BR)=S∞A=B(A(R))用半連接表示連接操作R∞A=BS=(R∝A=BS)∞A=BS=（R∞A=B(B(S))∞A=BSS∞A=BR=(S∝A=BR)∞A=BR=(S∞A=B(A(R))∞A=BR5.1

半連接操作5基于半連接算法的查詢優(yōu)化處理例子1:R∝S

A B

2 a10 b25 c30 d25 w3 x10 y15 z32 x

A

(R)=[2,10,25,30]R∝SS∝R=AC10y25wA=AA=AA CSR10 b25 c

A B

5.2

半連接表示連接的代價估算5基于半連接算法的查詢優(yōu)化處理RS網(wǎng)絡

站點1站點2(1)

B(S)(3)R’=R∝A=B

B(S)(2)

B(S)(4)R’=R∝A=B

B(S)(5)R’∞A=BS設c=Val(B[S]),m=Val(B[R]),r=Card(S),n=Card(R)c=(n,m,r)=r,當r<m/2c=(n,m,r)=(r+m)/3,當m/2≤r<2mc=(n,m,r)=m,當r≥2m代數(shù)操作對關系概貌的影響連接操作

T=R∞S

Card(T)=(Card(R)*Card(S))/Val(A[R])Size(T)=Size(R)+Size(S)Val(A[T])Min(Val(A[R]),Val(B[S]))A是連接屬性

Val(A[T])Val(A[R])+Val(B[S])A不是連接屬性半連接

T=R∝Sρ=Val(A[S])/Val(Dom(A))Card(T)=ρ*Card(R)Size(T)=第一個操作數(shù)Size（R）

Val(A[T])=ρ*Val(A[R])5.2

半連接表示連接的代價估算5基于半連接算法的查詢優(yōu)化處理代價公式：T=C0+C1*X在站點2上做投影

B(S)把B(S)傳到站點1上，代價為：C0+C1*size(B)*val(B[S])在站點1上計算半連接，R’=R∝A=BS把R’從站點1傳到站點2的代價為：C0+C1*size(R’)*card(R’)在站點2上執(zhí)行連接操作：R’∞A=BS采用半連接的總代價T半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.2

半連接表示連接的代價估算5基于半連接算法的查詢優(yōu)化處理基本原理通常有兩次傳輸?shù)莻鬏數(shù)臄?shù)據(jù)量和傳輸整個關系相比，要遠遠少一般有：T半<<T全半連接的得益：當card（R）>>card（R’），可減少站點間的數(shù)據(jù)傳輸量半連接的損失：傳輸

B(S)=C0+C1*size(B)*val(B[S])基本原理是在傳到另一個站點做連接前，消除與連接無關的數(shù)據(jù)，減少做連接操作的數(shù)據(jù)量，從而減小傳輸代價采用半連接優(yōu)化算法的步驟計算每種半連接方案的代價，并從中選擇一種最佳方案選擇傳輸代價最小的站點，計算采用全連接的方案的代價比較兩種方案，確定最優(yōu)方案5.3

半連接算法優(yōu)化原理和步驟5基于半連接算法的查詢優(yōu)化處理事務概念事務是訪問或更新各種數(shù)據(jù)項的最小邏輯工作單位。它是一個操作序列它可以使數(shù)據(jù)庫從一個一致狀態(tài)到另外一個一致狀態(tài)事務必須保證數(shù)據(jù)庫的一致性事務執(zhí)行期間數(shù)據(jù)庫可能不一致1.1

分布式事務定義和特性1分布式事務概述

當事務提交（commit）時數(shù)據(jù)庫必須是一致的事務T開始事務T結(jié)束事務T的執(zhí)行數(shù)據(jù)庫一致數(shù)據(jù)庫一致數(shù)據(jù)庫可能臨時不一致1.1

分布式事務定義和特性1分布式事務概述事務概念分布式事務集中式事務和操作數(shù)據(jù)在一個站點上不存在傳輸費用分布式操作數(shù)據(jù)分布在不同的站點上事務也在多個站點上執(zhí)行分布式事務是集中式事務的擴充站點和通信鏈路故障都可能導致錯誤發(fā)生分布式事務的恢復要比集中式事務復雜的多1.1

分布式事務定義和特性1分布式事務概述

事務分類:全局事務通常由一個主事務和在不同站點上執(zhí)行的子事務組成主事務：負責事務的開始、提交和異常終止子事務：完成對相應站點上的數(shù)據(jù)庫的訪問操作局部事務僅訪問或更新一個站點上的數(shù)據(jù)的事務1.1

分布式事務定義和特性1分布式事務概述分布式數(shù)據(jù)庫中的事務ACID特性原子性（Atomicity）事務的操作要么全部執(zhí)行，要么全部不執(zhí)行，保證數(shù)據(jù)庫一致性狀態(tài)。一致性（Consistency）事務的正確性，串行性，并發(fā)執(zhí)行的多個事務，其操作的結(jié)果應與以某種順序串行執(zhí)行這幾個事務所得的結(jié)果相同。持久性（Durability）當事務提交后，其操作的結(jié)果將永久化，而與提交后發(fā)生的故障無關。1.1

分布式事務定義和特性1分布式事務概述分布式事務特性隔離性（Isolation）

雖然可以有多個事務同時執(zhí)行，但是單個事務的執(zhí)行不應該感知其他事務的存在，因此事務執(zhí)行的中間結(jié)果應該對其他并發(fā)事務隱藏。此外，分布式數(shù)據(jù)庫系統(tǒng)中還要考慮數(shù)據(jù)傳送、通信原語和控制報文等。全局事務的主事務和子事務全部成功提交，才能改變數(shù)據(jù)庫狀態(tài)，有一個失敗，其他子事務操作都要撤銷。1.1

分布式事務定義和特性1分布式事務概述分布式事務特性分布式事務管理目標目的：事務能有效、可靠、并發(fā)的執(zhí)行除了策略之外，效率的幾個重要方面CPU和主存的使用控制報文響應時間可用性目標維護事務的ACID性質(zhì)獲得最小的主存和CPU開銷，降低報文數(shù)目，加快響應時間獲得最大限度的可靠性和可用性1.3

分布式事務管理的問題和目標1分布式事務概述事務管理LTM功能保證本地事務的ACID特性維護一個用于恢復的日志，代替DTM把分布事務的執(zhí)行與恢復信息記入日志參與適當?shù)牟l(fā)控制模式，以協(xié)調(diào)在該站點上執(zhí)行的事務的并發(fā)執(zhí)行。接收并遵從本Site上DTM發(fā)來的Log原語，記入Log并執(zhí)行之Log原語：

LocalBegin-Trans,Local-Commit,Local-Abort2.1

分布式事務管理的抽象模型2分布式事務的執(zhí)行與恢復基本思想將本地原子性提交行為的效果擴展到分布式事務,保證了分布式事務提交的原子性,并在不損壞Log的情況下,實現(xiàn)快速故障恢復,提高DDB系統(tǒng)的可靠性.第一階段：表決階段第二階段：執(zhí)行階段兩類代理協(xié)調(diào)者(Coordinator)：提交和撤銷事務的決定權(quán)，一般是總代理參與者(Participants)：負責在本地數(shù)據(jù)庫中執(zhí)行寫操作，并且向協(xié)調(diào)者提出提交和撤銷子事務的意向3.1

基本思想和內(nèi)容3兩階段提交協(xié)議初始寫begin_commit到日志等待有要求撤消的？寫commit到日志提交寫end_of_transt到日志初始準備提交？寫ready到日志就緒消息類型？寫abort到日志寫commit到日志提交撤消撤消寫abort到日志寫abort到日志協(xié)調(diào)者參與者nonoabortcommit準備撤消提交全局撤消全局提交ACKACK兩階段提交協(xié)議的活動2PC協(xié)議的重要特點允許參與者單方面撤銷事務一旦參與者確定了提交或撤銷協(xié)議，它就不能再更改它的提議當參與者處于就緒狀態(tài)時，根據(jù)協(xié)調(diào)者發(fā)出的消息種類，它可以轉(zhuǎn)換為提交狀態(tài)或者撤銷狀態(tài)協(xié)調(diào)者根據(jù)全局提交規(guī)則做出全局終止決定協(xié)調(diào)者和參與者可能進入互相等待對方消息的狀態(tài)，使用定時器，保證退出消息等待狀態(tài)3.1

基本思想和內(nèi)容3兩階段提交協(xié)議集中式通訊只發(fā)生在協(xié)調(diào)者和參與者之間，參與者之間不交換信息分層式協(xié)調(diào)者是在樹根的DTM代理者，協(xié)調(diào)者與參與者之間的通訊不用直接廣播的方法進行，而是使報文在樹中上下傳播。每個DTM代理是通信樹的一個內(nèi)部節(jié)點，它從下層節(jié)點處收集報文或向它們廣播報文。線性參與者之間可以互相通信。系統(tǒng)中的站點間要排序，消息串行傳遞。支持沒有廣播功能的網(wǎng)絡分布式允許所有參與者在第一階段相互通信，從而可以獨立做出事務終止決定。3.2

通信結(jié)構(gòu)3兩階段提交協(xié)議23451234511協(xié)調(diào)者參與者協(xié)調(diào)者協(xié)調(diào)者參與者第一階段第二階段準備建議撤消/提交全局撤消/提交提交/撤消集中式34251511協(xié)調(diào)者參與者協(xié)調(diào)者協(xié)調(diào)者參與者第一階段第二階段準備建議撤消/提交全局撤消/提交提交/撤消23422分層式1234n第一階段第二階段準備建議提交/撤消建議提交/撤消建議提交/撤消全局提交/撤消全局提交/撤消全局提交/撤消全局提交/撤消線性式1n4324321n……協(xié)調(diào)者協(xié)調(diào)者協(xié)調(diào)者+參與者第一階段準備建議撤消/提交全局撤消/提交可獨立做決定分布式站點故障a>

參與者在將“Ready”記錄入Log之前故障此時協(xié)調(diào)者(C)達到超時，Abort發(fā)生。站點（P）恢復時，重啟動程序?qū)?zhí)行Abort，不必從其他站點獲取信息。b>

當將“Ready”寫入Log后，站點故障此時所有運行的站點都將正常結(jié)束事務（Commit/Abort)。P恢復時，因為P已Ready，所以不可判定C的最終決定。因此恢復時，重啟動程序要詢問C或其他站點。c>當C將“Prepare”寫入Log，但“G-commit”/”G-abort”還沒有寫入前故障所有回答“Ready”的P等待C恢復。C重啟動時，將重開提交協(xié)議，重發(fā)“Prepare”，于是P要識別重發(fā)。d>C在將“G-commit”/”G-abort”寫入Log后，“Complete”沒有寫入前故障收到命令的P正常執(zhí)行，C重啟動程序必須再次向所有P重發(fā)命令。以前沒有收到命令的P也必須等待C恢復，P要識別兩次命令。e>“Complete”寫入Log后故障無任何動作發(fā)生3.2

兩階段提交協(xié)議和故障恢復3兩階段提交協(xié)議2.報文丟失a>從P發(fā)出的“Ready”/“Abort”報文丟失C達到超時，整個事務執(zhí)行“G-abort”。該故障僅能被C識別，此時C認為P故障，但P并無故障，不需執(zhí)行重啟動程序。b>“Prepare”報文丟失P等待，C得不到回答，結(jié)果同2.a>c>“G-commit”/”G-abort”報文丟失P處于不確定狀態(tài)?；卮稹癆bort”的可以確定其工作，回答“Ready”的不行。此時可以修改加入計時器，超時則申請重發(fā)命令。d>“Ack”報文丟失C超時，可重發(fā)“G-commit”/”G-abort”命令，P無論是否有活動，都重發(fā)“Ack”報文3.2

兩階段提交協(xié)議和故障恢復3兩階段提交協(xié)議網(wǎng)絡分割站點假設分成兩組：協(xié)調(diào)者組和參與者組。一組是協(xié)調(diào)者，一組是參與者。于是從協(xié)調(diào)者看是參與者組故障，結(jié)果同1.a>,1.b>。從參與者組看是協(xié)調(diào)者站點故障，動作如1.c>,1.d>。3.2

兩階段提交協(xié)議和故障恢復3兩階段提交協(xié)議初始寫begin_commit到日志等待有要求撤消的？寫commit到日志提交寫Complete到日志初始準備提交？寫ready到日志就緒消息類型？寫abort到日志寫commit到日志提交撤消撤消寫abort到日志寫abort到日志協(xié)調(diào)者參與者nonoabortcommit2.b>

準備2.a>撤消2.a>

提交2.c>全局撤消全局提交ACKACK1.c>1.d>1.e>1.a>1.b>2.d>主文本更新思想：指定主副本,修改只對主副本進行,修改輔助副本時,也按在主副本上執(zhí)行的更新順序執(zhí)行問題修改傳播必須在短時間內(nèi)完成,否則將獲得“過時”數(shù)據(jù)主副本不可用,引得其他副本也不可用4.2

主文本更新4分布式數(shù)據(jù)庫中的數(shù)據(jù)更新4.2

主文本更新4分布式數(shù)據(jù)庫中的數(shù)據(jù)更新網(wǎng)絡站點AX主文本站點B2X輔文本站點B1X輔文本站點B3X輔文本站點B5X輔文本站點B4X輔文本T1T2未連通T1在T2之前移動主文本法若初次更新在輔文本上進行，然后再把更新引向該數(shù)據(jù)的主站點如果主站點此時尚未連通，則另選一個輔站點中的輔文本為該數(shù)據(jù)新的主文本進行更新待原主文本站點連通后，系統(tǒng)將自動把它改為輔文本，并按記錄要求執(zhí)行更新如果初次更新在主文本上進行，但主文本站點與網(wǎng)絡未接通，則此次更新操作失敗，事務被撤銷，因為無法傳播更新移動文本法的問題網(wǎng)絡分割成很多部分時，更新處理會不一致網(wǎng)絡分割成W1,W2，W1中X更新為R,W2中X更新為S,網(wǎng)絡連通時，使用R還是S來恢復X呢？4.2

主文本更新4分布式數(shù)據(jù)庫中的數(shù)據(jù)更新例子

DefineSnapshotHP-BookasSELECT*FROMBookWHEREPrice>$100REFRESHEveryday特點快照不考慮數(shù)據(jù)的輔助副本,只關心主文本和這個主本上定義的多個快照快照與視圖一樣可以定義為一個或多個主副本的部分或全部快照可以完成復雜的查詢,但又不阻止更新查詢操作可使用快照，也可使用主文本，對更新操作還是在主文本上進行4.3

快照方法4分布式數(shù)據(jù)庫中的數(shù)據(jù)更新5.2

冗余數(shù)據(jù)的一致性5分布式事務增強數(shù)據(jù)庫一致性分布式數(shù)據(jù)庫冗余設計的理由提高系統(tǒng)的可用性和可靠性如果用戶由于某種原因無法訪問某個成員數(shù)據(jù)庫，它可以訪問另外一個成員數(shù)據(jù)庫上的相同片斷提高“讀”事務的本地性降低通信成本例如，一個片斷存放在該事務的原發(fā)站點中，則就免除了傳輸請求和返回結(jié)果的花費但是，如果事務包含對片斷的更新，則其所有副本也必須做同樣的更新，這時反而增加而不是降低通信成本事務TiTi={

i,<i}其中：

i:操作符集合：{Ri(x),Wi(x)}U{Ai,Ci}Ai,Ci

是最后的操作符，只能是其一<i:(沖突)操作有序執(zhí)行，Ri(x)<iWi(x)或Wi(x)<iRi(x)1.2

事務可串行化理論1并發(fā)控制的概念和理論操作符集讀Ri(x)和寫Wi(x)動作序列沖突動作

R1(A)

W2(A)W1(A) W2(A)

R1(A)W2(A)一個調(diào)度事務的一個操作序列稱為一個調(diào)度，一般用S表示比如，S:R1(x),R2(y),W2(y),R2(x),W1(x),W2(x)1.2

事務可串行化理論1并發(fā)控制的概念和理論T1

T21 (T1)a

X 5 (T2)c

X2 (T1)X

a+100 6 (T2)X

2c3 (T1)b

Y 7 (T2)d

Y4 (T1)Y

b+100 8 (T2)Y

2d先序關系例子已知：站點1有數(shù)據(jù)X，站點2有數(shù)據(jù)Y約束：X=Y1.2

事務可串行化理論1并發(fā)控制的概念和理論 (X站點) (Y站點)1 (T1) a

X 2 (T1)X

a+100 5 (T2)c

X 3(T1)b

Y 6 (T2)X

2c 4(T1)Y

b+100 7(T2)d

Y 8(T2)Y

2d

初值:X=Y=0,結(jié)果:X=Y=200調(diào)度S1事務內(nèi)

事務間令T={T1,T2,…,Tn}是一組事務.T上的調(diào)度S是具有如下順序關系<T的偏序，即S={

T,<T}

:(1)

T=

Ti(2)<T

<i(3)對于任意一組沖突操作p,qS,存在p<q或q<p關系并發(fā)調(diào)度定義i=1NNi=11.2

事務可串行化理論1并發(fā)控制的概念和理論調(diào)度一組事務的調(diào)度必須包含這些事務的所有操作調(diào)度中某個事務的操作順序必須保持與該事務原有的順序相同串行調(diào)度

一個事務的第一個動作是在另一個事務的最后一個動作完成后開始.即調(diào)度中事務的各個操作不會交叉,每個事務相繼執(zhí)行.一致性調(diào)度調(diào)度可以使得數(shù)據(jù)庫從一個一致性狀態(tài)轉(zhuǎn)變?yōu)榱硪粋€一致性狀態(tài)，則稱調(diào)度為一致性調(diào)度1.2

事務可串行化理論1并發(fā)控制的概念和理論調(diào)度等價S1與S2等價,也就是說,對于沖突操作,<Oi,Oj>,Oi<Oj在S1中成立,同時Oi<Oj

在S2中也成立可串行化調(diào)度如果一個調(diào)度等價于某個串行調(diào)度，則該調(diào)度稱為可串行化調(diào)度。也就是說，該調(diào)度可以通過一系列非沖突動作的交換操作使其成為串行調(diào)度1.2

事務可串行化理論1并發(fā)控制的概念和理論例子兩個事務，定義如下：T1:Read(x）x=x+10Write(x)Read(y)y=y-15Write(y)commit1.2

事務可串行化理論1并發(fā)控制的概念和理論T2:Read(x）x=x-20Write(x)Read(y)y=y*2Write(y)commit五種調(diào)度：S1={R1(x),x=x+10,W1(x),R1(y),y=y-15,W1(y),C1,R2(x),x=x-20,W2(x),R2(y),y=y*2,W2(y),C2}S2={R1(x),x=x+10,W1(x),R2(x),x=x-20,W2(x),R1(y),y=y-15,W1(y),C1,R2(y),y=y*2,W2(y),C2}S3={R1(x),x=x+10,W1(x),R2(x),x=x-20,W2(x),R2(y),y=y*2,W2(y),C2,R1(y),y=y-15,W1(y),C1}S4={R2(x),x=x-20,W2(x),R2(y),y=y*2,W2(y),C2,R1(x),x=x+10,W1(x),R1(y),y=y-15,W1(y),C1}S5={R2(x),x=x-20,W2(x),R1(x),x=x+10,W1(x),R2(y),y=y*2,W2(y),C2,R1(y),y=y-15,W1(y),C1}1.2

事務可串行化理論1并發(fā)控制的概念和理論如果將事務提交延遲到兩個事務操作完成之后執(zhí)行，有：調(diào)度S1和S4是串行調(diào)度調(diào)度S2和S1的沖突操作具有相同的順序，因此是等價調(diào)度；S2是可串行化調(diào)度，也是一致性調(diào)度調(diào)度S3雖是一致調(diào)度，但是它不與S1或S4等價，所以S3不是可串行化調(diào)度調(diào)度S5和S4等價，所以S5是一致調(diào)度，也是可串行化調(diào)度1.2

事務可串行化理論1并發(fā)控制的概念和理論有以下推論：一個可串行化調(diào)度必定與某個串行調(diào)度等價，且是一致性調(diào)度一致性調(diào)度不一定是可串行化調(diào)度同一事務集幾個可串行化調(diào)度，他們的結(jié)果未必相同1.2

事務可串行化理論1并發(fā)控制的概念和理論優(yōu)先圖P(S)調(diào)度S的優(yōu)先圖是一個有向圖G(N,E)，其中N:一組節(jié)點N={T1T2,…,Tn},S中的事務E:一組有向邊E={e1,e2,…,en},Ti

Tj

是圖中的一條邊，當且僅當pTi,qTj

使得p,q沖突，并且p<Sq1.3

分布式事務的可串行化調(diào)度測試1并發(fā)控制的概念和理論測試調(diào)度S的可串行化對于調(diào)度S中的事務Ti，在圖中創(chuàng)建一個節(jié)點Ti對于每一種這樣的情形：如果S中的在Ti執(zhí)行了W(X)操作后執(zhí)行Tj的R(X)操作，則在優(yōu)先圖中創(chuàng)建一條邊（Ti→Tj）對于每一種這樣的情形：如果S中的在Ti執(zhí)行了R(X)操作后執(zhí)行Tj的W(X)操作，則在優(yōu)先圖中創(chuàng)建一條邊（Ti→Tj）對于每一種這樣的情形：如果S中的在Ti執(zhí)行了W(X)操作后執(zhí)行Tj的W(X)操作，則在優(yōu)先圖中創(chuàng)建一條邊（Ti→Tj）當且僅當優(yōu)先圖中沒有閉環(huán)時，調(diào)度S是可串行化的1.3

分布式事務的可串行化調(diào)度測試1并發(fā)控制的概念和理論測試調(diào)度S的可串行化優(yōu)先圖中存在環(huán)路，說明調(diào)度是不可串行化的，否則是可串行化的。環(huán)路是指有向圖中每條邊的起始節(jié)點（第一條邊除外），都與前一條邊的終止節(jié)點連接，而第一條邊的起始節(jié)點于最后一條邊的終止節(jié)點連接，即事務序列是以同一個節(jié)點作為開始和結(jié)束的調(diào)度S中事務Ti在事務Tj之前，與S等價的調(diào)度中Ti也必須在Tj之前某項數(shù)據(jù)導致了調(diào)度中的一條邊的生成，就把數(shù)據(jù)項標注到優(yōu)先圖中這條邊的旁邊如果調(diào)度S中不存在環(huán)路，則就可能存在若干個與S等價的串行調(diào)度1.3

分布式事務的可串行化調(diào)度測試1并發(fā)控制的概念和理論1.3

分布式事務的可串行化調(diào)度測試1并發(fā)控制的概念和理論S1的優(yōu)先圖S2的優(yōu)先圖S3的優(yōu)先圖S4的優(yōu)先圖S5的優(yōu)先圖XYXYXYXYXY存在環(huán)路舉例考慮如下3個事務：

T1:Read(x);Write(x);Commit;T2:Write(x);Write(y);Read(z);Commit;T3:Read(x);Read(y);Read(z);Commit;

這3個事務的一個調(diào)度：S={W2(x),W2(y),R2(z),C2,R1(x),W1(x),C1,R3(x),R3(y),R3(z),C3}

優(yōu)先圖：

T2T1T3無環(huán)，S是串行調(diào)度。1.3

分布式事務的可串行化調(diào)度測試1并發(fā)控制的概念和理論另外一個調(diào)度S’:S={W2(x),R1(x),W1(x),C1,R3(x),W2(y),R3(y),R2(z),C2,R3(z),C3}

先序圖：

T2T1T3無環(huán)，是可串調(diào)度。1.3

分布式事務的可串行化調(diào)度測試1并發(fā)控制的概念和理論可串性理論擴展可串性理論可以直接擴展到無重復副本的分布式數(shù)據(jù)庫中。事務在每個站點上的執(zhí)行調(diào)度稱作局部調(diào)度如果數(shù)據(jù)庫無重復副本的分布式數(shù)據(jù)庫，并且每個局部調(diào)度都是可串調(diào)度，只要這些局部調(diào)度的順序一致，則它們的并（全局調(diào)度）也是可串調(diào)度但是有副本的情況下，就比較復雜?？赡芫植空{(diào)度是可串行化的，而全局調(diào)度不是可串行化的。1.3

分布式事務的可串行化調(diào)度測試1并發(fā)控制的概念和理論并發(fā)控制算法悲觀法樂觀法加鎖法集中式加鎖分布式加鎖時標排序法混合法加鎖法時序排序法主副本加鎖基本時標排序保守時標排序多版本時標排序并發(fā)控制算法的分類封鎖法事務的同步化是通過對數(shù)據(jù)庫的片斷或者數(shù)據(jù)項進行物理或邏輯封鎖來實現(xiàn)的封鎖對象的大小通常稱為封鎖粒度封鎖方法的類型可以根據(jù)在哪里進行封鎖來進一步細分封鎖法分類集中式封鎖方法一個站點被指定為主站點，存放對整個數(shù)據(jù)庫的封鎖表，并且負責對全系統(tǒng)事務進行封鎖主副本封鎖法：主副本所在站點封鎖分布式封鎖法：網(wǎng)絡中的站點共享鎖的管理1.4

并發(fā)控制機制的常用方法及其分類1并發(fā)控制的概念和理論基本思想和概念基本思想事務訪問數(shù)據(jù)項之前要對該數(shù)據(jù)項封鎖，如果已經(jīng)被其他事務鎖定，就要等待，直到那個事務釋放該鎖為止鎖的粒度鎖定數(shù)據(jù)項的范圍數(shù)據(jù)項層次數(shù)據(jù)庫記錄中的一個字段值一條數(shù)據(jù)庫記錄一個磁盤塊（頁面）一個完整的文件整個數(shù)據(jù)庫2.1

基于封鎖的并發(fā)控制方法概述2分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術基本思想和概念粒度對并發(fā)控制的影響大多數(shù)DBMS缺省設置為記錄鎖或頁面鎖粒度小，并發(fā)度高，鎖開銷大數(shù)據(jù)項比較多，鎖也多，解鎖和封鎖操作多，鎖表存儲空間大（如存儲讀寫時間戳）粒度大，并發(fā)度低，鎖開銷小如果是磁盤塊，封鎖磁盤塊中的一條記錄B的事務T必須封鎖整個磁盤塊而另外一個事務S如果要封鎖記錄C,而C也在磁盤塊中，由于磁盤塊正在封鎖中，S只能等待如果是封鎖粒度是一條記錄的話，就不用等待了2.1

基于封鎖的并發(fā)控制方法概述2分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術基本思想和概念如何來確定粒度取決于參與事務的類型如果參與事務都訪問少量的記錄，則選擇一個記錄作為粒度較好如果參與事務都訪問同一文件中大量的記錄，則最好采用塊或者文件作為粒度2.1

基于封鎖的并發(fā)控制方法概述2分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術開始加鎖點結(jié)束事務執(zhí)行過程獲得鎖釋放鎖兩階段封鎖協(xié)議2.2

基本2PL協(xié)議2分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術基本2PL協(xié)議實現(xiàn)的難點鎖管理器必須要知道事務的鎖點位置級聯(lián)撤銷(cascadingaborts)如果事務在開始釋放Lock后又Abort時,將引起級聯(lián)撤銷(cascadingaborts)（其他訪問這個數(shù)據(jù)項的事務也被撤銷）保守2PL要求事務在開始執(zhí)行之前就持有所有它要訪問的數(shù)據(jù)項上的鎖事務要預先聲明它的讀集和寫集大多數(shù)2PL調(diào)度器實現(xiàn)的是嚴格2PL(S2PL)事務在提交或者撤銷之前，絕對不釋放任何一個寫鎖事務結(jié)束時（提交或者撤銷），同時釋放所有的鎖2.22PL協(xié)議2分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術嚴酷2PL事務T在提交或撤銷之前，不能釋放任何一個鎖（寫鎖或者讀鎖），因此它比嚴格2PL更容易實現(xiàn)保守2PL與嚴酷2PL之間的區(qū)別前者，事務必須在開始之前封鎖它所需要的所有數(shù)據(jù)項，因此，一旦事務開始就處在收縮階段后者,直到事務結(jié)束（提交或者撤銷）后才開始解鎖，因此，事務一直處于擴張階段，直到結(jié)束2.22PL協(xié)議2分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術開始結(jié)束事務執(zhí)行階段獲得鎖釋放鎖

嚴格2PL(StrictTwo-phaseLocking)協(xié)議數(shù)據(jù)項使用2.22PL協(xié)議2分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術并發(fā)控制子系統(tǒng)可以負責產(chǎn)生讀鎖和寫鎖操作（以嚴格2PL協(xié)議為例）當事務T發(fā)出read_item(x)操作請求時，系統(tǒng)會代表T調(diào)用read_lock(x)操作如果Lock(x)的狀態(tài)是被另外一個事務T’持有寫鎖，則系統(tǒng)會把T放到數(shù)據(jù)項X的等待隊列中；否則，系統(tǒng)同意read_lock(x)的請求，從而允許事務T執(zhí)行read_item(x)操作另外一個方面，如果事務T發(fā)出write_item（x）操作請求時，系統(tǒng)會代表T調(diào)用write_lock(x)操作如果Lock(x)的狀態(tài)是被另外一個事務T’持有讀鎖或?qū)戞i，則系統(tǒng)會把T放到數(shù)據(jù)項X的等待隊列中；如果Lock(x)的狀態(tài)是讀鎖，并且事務T本身就是持有x上的讀鎖的唯一事務，則系統(tǒng)將該鎖升級為寫鎖，并且允許T執(zhí)行write_item(x)操作如果Lock(x)的狀態(tài)是沒有鎖，則系統(tǒng)同意write_lock(x)的請求，進而允許事務T執(zhí)行write_item(x)操作2.22PL協(xié)議2分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術多粒度封鎖封鎖的粒度不是單一的一種粒度，而是有多種粒度可以定義多粒度樹，根節(jié)點是整個數(shù)據(jù)庫，葉節(jié)點表示最小的封鎖粒度直接封鎖事務對要進行讀/寫的數(shù)據(jù)對象直接申請加鎖分層封鎖DB中各數(shù)據(jù)對象從大到小存在一種層次關系,例如劃分為DB,段,關系,元組,字段等當封鎖了外層數(shù)據(jù)對象時,蘊含著也同時封鎖了它的所有內(nèi)層數(shù)據(jù)對象數(shù)據(jù)項的顯式封鎖和隱式封鎖2.4

多粒度封鎖與意向鎖2分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術T2T1YYYYYY-YNNYNNSIXYNYYNNIXYYYYNYISYNNNNNXYNNYNYS-SIXIXISXSXSIXSIXISY=yes，表示相容的請求N=no，表示不相容的請求(a)數(shù)據(jù)鎖的相容矩陣(b)鎖的強度的偏序關系

鎖的相容矩陣2.4

多粒度封鎖與意向鎖2分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術鎖的強度：對其它鎖的排斥程度多粒度封鎖協(xié)議的規(guī)則必須遵守鎖的相容性規(guī)則必須首先封鎖樹的根節(jié)點，可以用任何一種方式的鎖只有當節(jié)點N的父節(jié)點已經(jīng)被事務T以IS或IX方式封鎖后，節(jié)點N才可以被T以S或者IS方式封鎖只有當節(jié)點N的父節(jié)點已經(jīng)被事務T以IX或SIX方式封鎖后，節(jié)點N才可以被T以X,IX或者SIX方式封鎖只有當事務T還沒有釋放任何節(jié)點時，T才可以封鎖一個節(jié)點只有當事務T當前沒有封鎖節(jié)點N的任何子節(jié)點時，T才可以為節(jié)點N解鎖。2.4

多粒度封鎖與意向鎖2分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術總結(jié)具有意向鎖的多粒度加鎖方法中，任意事務T要對一個數(shù)據(jù)對象加鎖，必須先對它的上層節(jié)點加意向鎖申請封鎖時應該按自上而下的次序進行釋放鎖時則應該按自下而上的次序進行具有意向鎖的多粒度加鎖方法提高了系統(tǒng)的并發(fā)度,減少了加鎖和釋放鎖的開銷它已經(jīng)在實際的DBMS系統(tǒng)中廣泛應用，例如Oracle中2.4

多粒度封鎖與意向鎖2分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術集中式死鎖檢測選擇一個站點負責整個系統(tǒng)的死鎖檢測,死鎖檢測器放到這個站點每個站點的鎖管理器周期性地將本站點的LWFG傳送給死鎖檢測器,死鎖檢測器構(gòu)造GWFG,并在其中尋找回路或者，其它每個站點上的鎖管理器周期性地把記錄本站點上事務的開始時間，對鎖的持有、請求情況變化的動態(tài)表，發(fā)送給負責處理封鎖的站點，由它維護一張全局封鎖動態(tài)表，形成GWFG,并在其中尋找回路如果至少包含一條回路，它會選擇一個或者多個事務，把它們?nèi)∠⒒謴?，釋放資源，使得其它事務繼續(xù)進行選擇的標準是盡可能使撤銷并恢復的代價最小，如撤銷年輕的事務，撤銷占有較少資源的事務，撤銷具有最短運行時間的事務，撤銷具有最長運行時間的事務等，視系統(tǒng)情況而定3.3

死鎖的檢測和解決方法3分布式數(shù)據(jù)庫系統(tǒng)中的死鎖處理層次式死鎖檢測的步驟樹葉是各站點的局部死鎖檢測器，在本站點建立局部等待圖本站點的死鎖檢測器找出本站點局部等待圖中的任何回路，并把有關潛在全局回路的信息發(fā)送給上一層死鎖檢測器每個非本地死鎖檢測器只對它所涉及的緊挨下層進行死鎖檢測，合并這些接收到的有關潛在全局回路的信息，并找出任何回路如果還有上層死鎖檢測器，將經(jīng)過簡化的有關潛在全局回路的信息發(fā)送給它上一層死鎖檢測器，由上一層死鎖檢測器再進行合并，找出任何全局回路這樣，逐層檢測，直到最高層。3.3

死鎖的檢測和解決方法3分布式數(shù)據(jù)庫系統(tǒng)中的死鎖處理分布式檢測每個站點的檢測死鎖責任相同,站點之間交換信息(LWFG)，是為了確定全局死鎖EX是指的本地事務正在等待的其他事務所在的還不確定的站點例子站點1站點2T1T2T4T3EXEX3.3

死鎖的檢測和解決方法3分布式數(shù)據(jù)庫系統(tǒng)中的死鎖處理信息傳遞方向此處規(guī)定一種,以避免多次重復傳遞EX等待的事務號>等待EX的事務號分布式死鎖檢測算法使用局部信息建造LWFG,該LWFG包含EX節(jié)點對每次接收到的信息,執(zhí)行如下對LWFG的修改對報文中的每個事務,若LWFG中不存在,則將其加入從EX節(jié)點開始,按照報文所給的信息,建立一個到下一個事務的邊在新的LWFG中尋找不含EX的Loop,若存在,則檢測到死鎖在新的LWFG中找到含有EX的Loop,于是有潛在的死鎖,再按規(guī)定向外傳送信息3.3

死鎖的檢測和解決方法3分布式數(shù)據(jù)庫系統(tǒng)中的死鎖處理基本概念 不通過互斥來支持串行性，而是通過在事務啟動時賦給時標（時間戳）來實現(xiàn)時標是用來唯一識別每個事務并允許排序的標識如果ts(T1)<ts(T2)…<ts(Tn),則調(diào)度器產(chǎn)生的序是:T1,T2,...Tn規(guī)則如果T1的操作O1(x)和T2的操作O2(x)是沖突操作,則,O1在O2之前執(zhí)行,當且僅當ts(T1)<ts(T2)4.1

基于時標的并發(fā)控制方法4分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術時標分配方法 全局時標使用全局的單調(diào)遞增的計數(shù)器全局的計數(shù)器維護是個難題局部時標每個站點基于其本地計數(shù)器自治地指定一個時標標識符由兩部分組成：〈本地計數(shù)器值，站點標識符〉站點標識符是次要的，主要是本地計數(shù)器值可以使用站點系統(tǒng)時鐘來代替計數(shù)器值4.1

基于時標的并發(fā)控制方法4分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術時標法思想 每個事務賦一個唯一的時標，事務的執(zhí)行等效于按時標次序串行執(zhí)行如果發(fā)生沖突，是通過撤銷并重新啟動一個事務來解決的事務重新啟動時，則賦予新的時標優(yōu)點是沒有死鎖，不必設置鎖封鎖和死鎖檢測引起的通信開銷也避免了但要求時標在全系統(tǒng)中是唯一的4.1

基于時標的并發(fā)控制方法4分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術時標性質(zhì)唯一性單調(diào)性全局唯一時間的形成與調(diào)整每個站點設置一個計數(shù)器,每發(fā)生一個事務,計數(shù)器加一發(fā)送報文時包含本地計數(shù)器值,近似同步各站點計數(shù)器4.1

基于時標的并發(fā)控制方法4分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術4.1

基于時標的并發(fā)控制方法4分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術

計數(shù)器X初值X=0計數(shù)器Y初值Y=10

站點1站點2

時標AD時標

TS(A)=<1,1>TS(D)=<11,2>

因為X<YETS(E)=<12,2>

改X=Y+1=11BTS(B)=<11,1>F因為Y>XTS(C)=<12,1>CTS(F)=<13,2>

本地計數(shù)器本地計數(shù)器

(或時鐘)(或時鐘)報文1報文2計數(shù)器站點基本時標法規(guī)則每個事務在本站點開始時賦予一個全局唯一時標在事務結(jié)束前，不對數(shù)據(jù)庫進行物理更新事務的每個讀操作或?qū)懖僮鞫季哂性撌聞盏?/p>