1、第一章 分布式數據庫系統概述1.1請用自己的語言定義下列分布式數據庫系統中的術語：（1）局部數據:只提供本站點的局部應用所需要的數據。全局數據：雖然物理上存儲在個站點上，但是參與全局應用（2）全局/局部用戶：局部用戶： 一個用戶或一個應用如果只訪問他注冊的那個站點上的數據稱為本地或局部用戶或本地應用；全局用戶： 如果訪問涉及兩個或兩個以上的站點中的數據，稱為全局用戶或全局應用。全局/局部DBMS：1）LDBMS(Local DBMS)：局部場地上的數據庫管理系統，其功能是建立和管理局部數據庫，提供場地自治能力，執行局部應用及全局查詢的子查詢。（2）GDBMS(Global DBMS)：全局數據

2、庫管理系統，主要功能是提供分布透明性，協調全局事物的執行，協調各局部DBMS以完成全局應用，保證數據庫的全局一致性，執行并發控制，實現更新同步，提供全局恢復功能等。（3）全局外模式：全局應用的用戶視圖，也稱全局視圖。從一個由各局部數據庫組成的邏輯集合中抽取，即全局外模式是全局概念式的子集。對全局用戶而言，都可以認為在整個分布式數據庫系統的各個站點上的所有數據庫都如同在本站點上一樣，只關心他們自己所使用的那部分數據（4）全局概念模式：描述分布式數據庫中全局數據的邏輯結構和數據特性，是分布式數據庫的全局概念視圖。采用關系模型的全局概念模式由一組全局關系的定義(如關系名、關系中的屬性、每一屬性的數據

3、類型和長度等)和完整性定義(關系的主鍵、外鍵及完整性其他約束條件等)組成。（5）分片模式：描述全局數據的邏輯劃分。每個全局關系可以通過選擇和投影的關系操作被邏輯劃分為若干片段。分片模式描述數據分片或定義片段，以及全局關系與片段之間的映像。這種映像是一對多的。（6）分配模式：根據選定的數據分布策略，定義各片段的物理存放站點，即定義片段映像的類型，確定分布式數據庫是冗余的還是非冗余的，以及冗余的程度。如果一個片段分配在多個站點上，則片段的映像是一對多的，分布式數據庫是冗余的，否則是不冗余的。（7）局部概念模式：是全局概念模式的子集。全局概念模式經邏輯劃分成一個或多個邏輯片段，每個邏輯片段被分配在一

4、個或多個站點上，稱為該邏輯片段在某個站點上的物理映像或稱物理片段。對每個站點來說，在該站點上全部物理映像的集合稱為該站點上的局部概念模式。或者說，一個站點上的局部概念模式是該站點上所有全局關系模式在該站點上物理映像的集合。（8）局部內模式：是分布式數據庫中關于物理數據庫的描述，描述的內容不僅包含局部本站點的數據的存儲描述，還包括全局數據在本站點的存儲描述。1.4什么是分布式數據庫系統？它具有哪些主要特點？怎么樣區別分布式數據庫系統與只提供遠程數據訪問功能的網絡數據庫系統？（分布式數據庫系統的定義、特點詳見課件第1章4.1.課本P6）分布式數據庫系統：物理上分散而邏輯上集中的系統，它使用計算機網

5、絡將地理位置分散而管理和控制又需要不同程度集中的多個邏輯單位（通常是集中式數據庫系統）連接起來，共同組成一個統一的數據庫系統。分布式數據庫系統可以看成是計算機網絡和數據庫系統的有機結合。特點：物理分布性、邏輯整體性、站點自治性、數據分布透明性、集中與自治相結合的控制機制、存在適當的數據冗余度、事務管理的分布性。1.6用自己的語言解析“什么時候需要進行數據分片和數據復制”？（課本第10,11頁）數據分片又稱數據分割、數據分段，局部數據庫是由全局數據庫分割而成；全局數據庫 是由各個局部數據庫邏輯組合而成。一個關系描述了某些數據之間的邏輯相關性，不同站點的用戶需要該關系中的元組可能不同，需要對這個關

6、系進行分割，并將 分割后得到的各部分元組，稱為該關系的邏輯片段，存放在相應的站點上。這樣 處理各得其所，可以減少網絡上的通信，提高系統的相應效率。數據復制指分布式數據庫中的數據根據需要將數據劃分成邏輯片段，按某種策略把數據 分片所得的邏輯片段分散地存儲在各個站點上。全局數據有多個副本，每個站點都有一個完整的數據副本。系統可靠性高，響應速度快，數據庫恢復也較容易。但要保持各個站點上數據的同步修改，將要付出高昂的代價。1.7在分布式數據庫系統中，為什么要對數據進行分片？什么是關系的片段？關系的片段有哪些主要類型？（課本第9-10頁。數據分片又稱數據分割、數據分段，局部數據庫是由全局數據庫分割而成；

7、全局數據庫 是由各個局部數據庫邏輯組合而成。一個關系描述了某些數據之間的邏輯相關性，不同站點的用戶需要該關系中的元組可能不同，需要對這個關系進行分割，并將 分割后得到的各部分元組，稱為該關系的邏輯片段，存放在相應的站點上。這樣 處理各得其所，可以減少網絡上的通信，提高系統的相應效率。數據分片是指數據存放單位不是全部關系，而是關系的一個片段。也就是關系的一部分。包括： （1）水平分片：按一定的條件把全局關系的所有元組劃分成若干不相交的子集，每個子集為關系的一個片段。 （2）垂直分片：把一個全局關系的屬性集分成若干子集，并在這些子集上做投影運算，每個投影為垂直分片。 （3）混合型分片：將水平分片與

8、垂直分片方式綜合使用則為混合型分片。 ）1.8為什么說分布式數據庫系統中，數據獨立性這一目標比集中式數據庫系統更為重要，也更為復雜？（詳見課本第25頁第二段）1.9概述分布式DBMS的參考模型中，用戶處理器、數據處理器、全局數據庫控制和通信子系統的組成和功能。（組成（參考模型）：詳見課件5.6；功能：用戶處理器課本第18頁；數據處理器課本第20頁；全局數據庫控制和通信子系統課本第21頁）用戶處理器：用戶結果格式化器用戶命令翻譯器約束實施器用戶結果用戶命令規范化數據規范化命令外部模式概念模式規范化命令用戶處理器用戶處理器的功能一是它把數據操縱語言中的用戶命令，翻譯成規范化命令。；二是它把來自數據

9、處理器的數據，翻譯成用戶理解的格式。數據處理器：數據處理器負責存取數據庫的數據，數據處理器的組成主要包括：規范化命令翻譯器、規范化結果格式器和運行時支持處理器。全局數據庫控制和通信子系統的組成和功能：全局數據庫控制和通信子系統負責通信和控制分布式的執行。由多個處理器組成：1. 分解器：分解器由一個或幾個數據處理器組成，主要任務是把來自用戶處理器的請求，翻譯成一個由若干命令組成的分布式執行策略。2. 合并器：它的任務是在提交給用戶處理器之前，把分布式執行策略訪問不同站點所得到的結果數據組合起來。3. 分布式執行監視器：負責分布式執行策略的正確執行以及保證分布式環境中事務的原子性。同時還負責提供復

10、制獨立性和分布式并發控制。4. 通信子系統：提供站點之間的信息傳送。每個站點都有一個通信處理器，與此通信子系統相接口。通信處理器使用一組通信協議來正確利用通信設施和為分布系統提供無錯的和可靠的通信。5. 本地執行監視器：負責在本地數據處理器中，執行該分布式執行策略中與本站點有關的部分。當執行策略的某一部分在該數據處理器中完成執行，或出現故障時，就由它來通知全局執行監視器。1.10分布式數據庫系統潛在的優點是什么？存在哪些技術問題？（優點：詳見課本第34-35頁共6點；技術問題詳見課本第35-36頁面共7點）優點：1. 良好的可靠性和可用性2. 提高系統效率，降低通信費用3. 較大的靈活性和可伸

11、縮性4. 經濟性和保護投資5. 適應組織的分布式管理和控制6. 數據分布具有透明性和站點具有較好的自治性技術問題：1. 如何控制數據的分片、分布與冗余度2. 如何實現異構數據庫的互聯（P.36）3. 如何優化分布式數據庫的查詢處理（P.36）4. 如何更好地實現分布式數據庫的更新處理（P.36）5. 如何實現分布式數據庫的并發控制機制（P.36）6. 如何實現分布式數據庫的恢復控制機制（P.36）7. 如何實現目錄管理（P.36）第二章課后習題2.1 概述分布式數據庫系統的創建方法、方法特點和適用范圍答：創建方法有：組合法、重構法組合法的特點：剖析網絡功能；剖析原有數據庫系統；解決數據的一致性

12、、完整性和可靠性；難度較大；組合法適用范圍：通常是異構或者同構異質DDBS重構法的特點：根據實現環境和用戶需求；按照DDBS的設計思想和方法；從總體設計做起，包括LDBS,重新建立一個DDBS；可有效解決數據一致性、完整性和可靠性問題。重構法的適用范圍：通常是同構異質或同構同質DDBS2.2 分布式數據庫設計的主要目標是什么?1. 目標一：分布式數據庫的本地性或近地性2. 目標二：控制數據適當冗余3. 目標三：工作負荷分布4. 目標四：存儲的能力和費用2.3 概述分布式數據庫設計的關鍵問題及解決方法答：關鍵問題：1）數據的實際分布情況。訪問的多個數據對象是存放在同一站點上還是分布在多個站點所需

13、的時間和費用有很大區別。2）數據對否被復制、復制副本的多少問題3）數據分片、片段如何復制、數據或片段如何分布、分布式數據庫管理系統的透明性解決方法：1）分布式數據庫遵循本地性或近地性，盡量減少通信次數和通信量，90/10準則，分片和分布方案（本地和遠程訪問次數）擇優；90%的數據應當在本地站點找到，而只有10%的數據需要在遠程站點上進行訪問。也即最有效的設計是確保數據對最大數目的應用具有本地性。可以采用的設計方法是對每一種可供選擇的分片方法和片段的分配方法都統計出本地訪問和遠程訪問的次數，然后從其中選擇一個最佳的方案。2）控制數據適當冗余，冗余增加了可靠性、可用性，提高了效率，維護數據一致性開

14、銷增加。在分布式數據庫系統中，為了提高系統的本地性、并發度和可靠性，需要增加數據的副本。這不僅使應用具有高度的可用性和本地性，而且當數據的任何一個副本不能使用時，可方便地使用在另一站點中的該數據的副本進行恢復，從而提高系統的可靠性。3）工作負荷分布分布式計算機系統的一個重要特征是把工作負荷分布在網絡中的各個站點上。分布工作負荷的目的是充分利用每個站點計算機的能力和資源，以提高應用執行的平行程度，從而提高系統的性能。4）存儲能力和費用 數據庫的分布會受到各站點的存儲能力的影響。在網絡中可以有專門用于存儲數據的站點，也可以有完全不支持大容量存儲的站點。一般，數據存儲的費用與 CPU，I /O及傳輸

15、的費用相比是不重要的，但是必須考慮各站點可用存儲空間的限制。2.4 考慮為局域網設計的分布式數據庫系統和為廣域網設計的分布式數據庫系統由什么區別?這道不會，參考p42 1.分布式數據庫的本地性或近地性2.5 請用自己的語音闡述分布式數據庫設計的自頂向下和自底向上設計方法及其適用范圍。答: 自頂向下：(1) 從概念設計到形成形式規格說明設計分布式數據庫。從頭開始設計分布式數據庫。該方法假定設計者理解用戶的數據庫應用要求，歷經概念設計、邏輯 設計和物理設計階段，并將與計算機系統無關的規格說明逐漸求精成 低級的、與計算機系統有關的規格說明。概念設計和邏輯設計的結果 是數據庫的全局模式，包含了數據庫的

16、所有數據元素及其使用形式。 專門針對分布式數據庫的一個設計階段稱為分布設計，將全局模式映 射成幾個可能交疊的子集模式，每一個子模式表示與一個站點有關的 信息子集，然后完成每一單個數據庫的設計。(2) 適用范圍：通常是同構異質或同構同質DDBS。自底向上： (1)通過聚集現存數據庫設計分布式數據庫。假定由于需要互聯一些現存數據庫以形成一個多數據庫系統，或由于對各站點已獨立完成了數據庫的概念說明，所以各站點上數據庫的規格說明已是現存的。需要綜合各站點的規格說明，以便得到分布式數據庫的全局概念模式。(2)適用范圍：通常是異構或者同構異質DDBS。2.6數據分片應遵守哪些原則?數據分片要準守的原則：完

17、備性原則：要把所有的數據映射到各個片斷中可重構原則：關系分片后的各個片斷可重構整個關系不相交原則：關系分片后的各個片斷不能重疊數據分片有哪些基本類型和方法?有兩種基本的數據分片方法：水平分片方法和垂直分片方法。通過交替水平分片與垂直分片，可以產生混合分片。 水平分片 水平分片是對全局關系執行“選擇”操作，把具有相同性質的元組進行分組，構成若干個不相交的子集。水平分片的方法可歸為初級分片和導出分片兩類。 垂直分片和垂直群集 一個全局關系的垂直分片是通過“投影”操作把它的屬性分成若干組。根據應用以“同樣方式”(具有相同的使用頻率)訪問的屬性來進行分組。垂直分片的組必須只在某個鍵屬性上重疊，其他屬性

18、不可重疊；垂直群集的組在其他屬性上也可以重疊。 2.7為什么說在關系型分布式數據庫中使用導出式水平分片，使關系之間的連接變得更加容易？試舉例。 答：原因：全局關系的導出式水平分片不是以其自身的屬性性質為基礎，而是從另一個關系的屬性性質或水平片段推導出來的。 確定一方便的導出式水平分片要求確定應用所執行的最重要的結合操作。導出分片可使片段與片段間“連接”變得更容易。可將連接條件代之以子查詢，從而使它變為一般的判別條件。具體實例： 例2.3 設全局關系 SC( S#, C#, GRADE) S ( S#, SNAME, AGE, SEX ) 要求： 將SC劃分為男生各門課成績和女生的各門成績。 這

19、不可能從SC本身的屬性性質來執行選擇，必須從關系S的屬性性質或水平片段來導出。 按S的屬性導出 Define fragment SC1 as （ Define fragment SM as ） Select SC.S#, C#, GRADE From SC, S Where SC.S#=S.S# and SEX=M Define fragment SC2 as （ Define fragment SF as ） Select SC.S#, C#, GRADE From SC, S Where SC.S#=S.S# and SEX=F 如果S已經進行水平分片，分為SF和SM, 分別為男生全體和女

20、生全體， 則按S的水平分片（SF/SM）導出： Define fragment SC1 as Select * From SC Where S# in (Select SF.S from SF) Define fragment SC2 as Select * From SC Where S# in (Select SM.S from SM)2.8 采用DATAID-D方法的分布式數據庫設計與傳統的集中式數據庫設計在步驟和內容上有什么不同？分布要求分析設計位于概念設計階段之后進行，主要工作：1. 收集用戶分布要求信息2. 水平分片的劃分謂詞3. 每一應用在各站點激活的頻率分布設計全局邏輯設計之后

21、進行，主要工作：1. 分布要求和全局邏輯模式作為輸入2. 形式為全局數據庫模式和邏輯訪問表3. 輸出為分片模式和分配模式 第三章3.1 用自己的語言概述分布式查詢優化與集中式查詢優化的異同。 分布式查詢和集中式查詢的相同點即在本地的CPU和I/O代價，不同點為分布式查詢比集中式查詢多了通訊代價3.2 試述分布式查詢優化的層次結構。分布式查詢處理按不同層次結構執行，符合分布式DBMS的體系結構。分布式查詢處理可分為四個層次。 查詢分解 將查詢問題（SQL）轉換成一個定義在全局關系上的關系代數表達式。 本層轉換所需要從全局概念模式中獲得。 數據本地化 把一個在全局關系上的查詢具體化，落實到合適的(

22、使盡可能做到本地化或近地化)片段上的查詢。即將全局關系的關系代數表達式變換為相應片段上的關系代數表達式。 這一變換所需要的信息在分片模式和片段的分配模式中 獲得。 全局優化 輸入的是分片查詢，查詢優化目標是尋找一個近于最優 的執行策略。 全局優化即是找出分片查詢的最佳操作次序，使得代價函數最小。代價函數一般是I/O、CPU和通信代價之和。 全局優化的一個重要方面是關于連接操作的優化。全局 優化處理層輸出是一個優化的、片段上的關系代數查詢。 局部優化 局部查詢優化由擁有與查詢有關的片段的各個站點執行。在每個站點上執行的子查詢被稱為局部查詢。它由該站 點上的DBMS進行優化，采用集中式數據庫系統中

23、查詢 優化的算法。所需信息取自局部模式。3.3 概括基于關系代數等價變換的查詢優化算法的基本原理與實現步驟。 基本原理1. 把查詢問題轉化為關系代數表達式；2. 分析得到查詢樹；3. 進行全局到片段的變換得到基于片段的查詢樹；4. 利用關系代數等價變換規則的優化算法，盡可能先執行 選擇和投影操作，后執行連接和合并操作；5. 對該查詢樹進行優化，從而達到查詢優化的目的。 優化算法1. 連接操作和合并操作盡可能上提（樹根方向）；2. 選擇操作和投影操作盡可能下移（葉子方向）；3. 盡可能先執行選擇和投影操作，后執行連接和合并操作。4. 經過選擇和投影操作不但可以減少其后操作量，還可以 減少操作次數

24、。 實現步驟和方法 將一個查詢問題轉換成關系代數表達式。 從關系代數表達式到查詢樹的變換：對一個關系 代數表達式進行語法分析，可以得到一棵語法樹 (或查詢樹)，即查詢樹根節點是最終的查詢結果，葉子節點是查詢涉及的所有關系或片段，中間節 點是按關系代數表達式中的操作順序組成的一組 關系操作符。 從全局查詢到片段查詢的變換：把基于全局關系 的查詢樹中的全局關系名，用其重構該全局關系 的各個片段名替換，變換成相應片段上的查詢樹。 利用關系代數等價變換規則優化算法，對片段的 查詢樹進行優化處理，最后達到優化查詢目的。3.4 概述基于半連接算法查詢優化的基本原理和適用情形。基本原理：p84p85 適用情

25、形：p85，由此可見那段，第四行的“所以。”開頭3.5 概述基于直接連接算法查詢優化的基本原理和適用情形。另一種是自然連接。自然連接是一種特殊的等值連接，它要求兩個關系中進行比較的分量必須是相同的屬性組，并且要在結果中把重復的屬性去掉。 3.6 設有關系R，S，T 如圖3.13所示。（1）設計連接RS T。（2）計算半連接R S, S R,ST,T R,T S,R T。 A B C B C D B C D2353563565363593591686836833465965965354164162685845846、（1）RSTABCDEI235669168389535669268389（2）R

26、SABC235168535268SRBCD356359683S TBCD356683596416TR 為空RT 為空TSDEI6693893.7 如果習題3.6中的三個關系R,S,T分別位于三個不同的站點X,Y,Z。若采用基于半連接算法計算連接R S T，請選擇使得傳輸代價最小的連接執行的站點和確定半連接序列。解：假設每個屬性域長度均為1B，考慮所有的半連接a) 選擇得益最高的P2進行優化，得到新的R,S,T，并對受到影響的的方案重新計算得益和費用。新的R, S, T如下：對受到影響的的方案重新計算得益和費用b) 選擇得益最高的P4進行優化，得到新的R,S,T，并對受到影響的方案重新計算得益和

27、費用。 新的R, S, T如下：對受到影響的的方案重新計算得益和費用c) 選擇得益最高的P1進行優化，得到新的R,S,T，并對受到影響的方案重新計算得益和費用。 新的R, S, T如下：對受到影響的的方案重新計算得益和費用d) 選擇得益最高的P3進行優化，得到X,Y,Z站點上最終的R,S,T。 X,Y,Z站點上最終的R,S,T如下：所以選擇各站點做連接的代價為： X站點代價=2*3+2*3=12 Y站點代價=4*3+2*3=18 Z站點代價=4*3+2*3=18故選擇X站點作為收集站點代價最低。由簡化過程得知半連接過程為：1. S = SR 2. 將S傳送給T,做半連接TS得到T 3. 將S傳

28、送給R,做半連接RS得到R4. 將T傳送給S,做半連接ST得到S即:(R(SR)(SR) (T(SR)(T(SR) 3.8 設某公司的雇員關系為employee(name,address,salary,plant-number)，按plant-number水平分片這個關系，每個片段都有兩個副本：一個副本存放在New York站點，另一個副本存放在工廠的站點。請為在Toronto站點提出的下列查詢設計一個好的處理策略。（1）找出Boce廠的所有雇員。（2）找出所有雇員的平均工資。（3）找出在如下每個站點工資最高的雇員姓名：Toronto，Edmonton，Vancouver，Montreal。（

29、4）找出該公司中工資最低的雇員姓名1)將New York站點上的副本傳至Toronto站點； 2)在New York站點上求平均工資，傳至Toronto站點； 3)Toronto, Edmonton, Vancouver, Montreal求最高工資，傳至Toronto匯總；3.9 考慮關系employee(eno,name,address,salary,plant-number)主碼為eno，machine(machine-number,type,plant-number)主碼為machine-number。假定關系employee按plant-number水平分片，且每個片段本地存放在它所

30、對應的工廠站點；關系machine沒有被分片，整個關系存放在Armonk站點（整個系統站點的個數等于工廠的個數+1），并且假定存放machine關系的Armonk站點就是提出查詢和需要結果的站點。請為下列的查詢設計一個好的處理策略：（1）找出生成機器號為1130的工廠的所有雇員的雇員號和姓名。（2）找出包含機器類型為milling machine的工廠的所有雇員的雇員號和姓名。（3）找出employee machine。（1）提出查詢的站點：（1）Aromonk站點，plant-number=X的站點；（2）Aromonk站點，plant-number=Xi的站點；（3）各工廠站點 （2）需要

31、結果的站點：（1）plant-number=X的站點，Aromonk站點；（2）plant-number=Xi的站點，Aromonk站點；（3）Aromonk站點4.1 概述分布式數據庫系統中事務的定義、特性、結構和狀態，以及分布式事務所特有的性質。分布式數據庫系統中的事務是一個分布式操作的序列，被操作的數據分布在不同的站點上，所以稱為分布式事務。 分布式事務 分布式數據庫系統中的事務是一個分布式操作的序列，被操作的數據分布在不同的站點上，所以稱為分布式事務。一個事務的執行可能涉及多個站點上的數據。事務也在多個站點上執行。 分布式事務是集中式事務的擴充，它的ACID特性的保證要比集中式事務復雜

32、得多。因為有多個站點參與執行，其中任何一個站點的故障，或者將這些站點連接起來的任何一條通信鏈路的故障，都可能導致錯誤發生。 因此分布式事務的恢復要比集中式事務的恢復要復雜得多。分布式數據庫系統中的事務具有ACID特性：原子性（Atomicity）:指事務執行時的不可分割性。即事務的操作要么全部執行, 要么全部不執行，保證分布式數據庫一致性狀態。一致性（Consistency）:指一個使分布式數據庫從一個一致狀態轉變為另一個一致狀態的正確程序。分布式事務執行完畢時，必須以正確的狀態退出系統。如果事務不能達到一個正常的結束狀態，就必須把分布式數據庫退回到該事務執行前的初始狀態。持久性（Durabi

33、lity）:指一旦某個事務被提交后，則無論系統發生任何故障，都不會丟失該事務的執行結果。也即，已提交事務對數據庫的改變在數據庫中應該是持續存在的，這些改變不會因為故障而發生丟失。 隔離性（ Isolation）:指一個正在執行的事務在其提交之前，決不允許把它對共享數據所作改變的結果提供給其他事務使用。也即事務的執行似乎與其他事務相隔離，事務的執行不應受到其他并發事務執行的干擾。雖然可以有多個事務同時執行，但是單個事務的執行不應該感知其他事務的存在，因此事務執行的中間結果應該對其他并發事務隱藏 。 在分布式數據庫系統中，全局事務的主事務和子事務全部成功提交，才能改變數據庫狀態，有一個失敗，其他子

34、事務操作都要撤銷。為了保證事務的原子性，要求組成這個分布式事務的各個子事務，要么全部提交(成功結束)，要么全部撤銷(不成功結束)。如果至少有一個子事務執行失敗，該分布式事務所包含的所有子事務，不管它的執行成功與否，一律都被撤銷。各站點上的數據庫全都回滾到相應子事務開始前的狀態，從而使整個分布式數據庫仍處于該分布式事務開始前的狀態。只有當一個分布式事務所包含的所有子事務，都能成功執行，各站點上的數據庫全都進入一個新的一致狀態，才能使整個分布式數據庫轉換為新的一致狀態。為保證分布式事務的ACID特性，更需要對各子事務進行協調和控制。結構：分布式數據庫系統中事務的結構以begin transacti

35、on原語作為一個事務的開始，以commit原語作為一個事務成功完成的結束，而以rollback或abort原語作為事務失敗的結束。狀態：活動(active): 從事務開始執行的初始狀態始， 事務執行中保持該狀態。部分提交(partially committed): 事務的最后一個語句執行后進入該狀態.失敗(failed): 一旦發現事務不能正常執行時進入該狀態.回滾/夭折(rollback/aborted): 當事務被回滾后，數據庫恢復到事務開始執行前的狀態。 提交(committed): 當事務成功執行后.分布式事務獨有的特性：大量的數據傳送、通信原語和控制報文等。4.2 請用自己的語言描述

36、分布式事務管理的抽象模型和分布式事務執行的控制模型。務管理器與局部事物管理器之間不必要的數據傳輸。4.3 分布式數據庫系統中的事務管理與集中式數據庫系統中的事務管理有何不同？分布式與集中式相比，會多遇到一些問題：（1）處理數據項的多個副本；（2）單個站點的故障；（3）通信網絡的故障；（4）分布式提交。4.4 什么是事務的提交點？為什么說它們很重要？當事務所有的站點數據庫存取操作都已成功執行，并且所有操作對數據庫的影響都已記錄在日志中時，該事務就到達提交點。事務的提交點：當事務T所有的站點數據庫存取操作都已成功執行，并且 所有操作對數據庫的影響都已記錄在日志中時，該事務就到達提交點。提交點后事務

37、就成為已提交的事務，并假定其結果已永久記錄在數據庫中(事務的永久性)。事務在日志中寫入提交記錄commit，T。在系統發生故障時，需要掃描日志，檢查那些已在日志中寫入start_transaction，T，但沒有寫入commit，T的所有事務T。恢復時必須回滾這些事務以取消它們對數據庫的影響。此外，還必須對日志中記錄的已提交子事務的所有寫操作進行恢復，這樣它們對數據庫的作用才可根據這些記錄重做Redo。4.5 日志、檔案庫和檢查點的作用是什么？典型的日志包含哪些內容？為什么要“先寫日志”？日志的作用是為了能夠從故障狀態中恢復有影響的事務，系統維護一個 日志來保存所有影響數據庫項的值的事務操作的

38、信息，這些信息可以用于故障時的恢復。檔案庫的作用是為了防止因介質故障而破壞數據庫，要定期將整個數據庫的全部內容轉儲到檔案庫中去。存放數據庫的檔案存儲設備稱為數據庫檔案庫(DB archive)檢查點的作用是為了便于恢復，在日志中設定一種周期性(時間/容量)操作點，稱為檢查點，以標識檢查點前已執行完的事務是正確的。典型的日志包含了每個改變數據項值的寫操作記錄。日志Log記錄項 : start_transaction, T：表示事務T開始執行； write_item, T, x, 舊值, 新值：表示事務T已將數據項X的值從舊值改為新值。 read_item, T, x：表示事務T已讀取數據項X的值

39、。 commit, T：表示事務T已成功完成，其結果已被提交(永久記錄) 給數據庫。 abort, T：表示事務T已被撤銷。 Log：記錄長度及用于恢復過程的輔助信息，如指向本事務前一 日志記錄的指針，檢查點記錄等。先寫日志：因為系統崩潰時主存中的內容可能丟失，所以恢復時只能考慮已寫回磁盤的日志內容。因此，在事務到達提交點以前，還未寫到磁盤的日志的任何部分，必須被寫入磁盤，即“先寫日志”。4.6 列出分布式數據庫系統中可能出現故障類型。哪些故障也可能出現在集中式數據庫系統中？事務故障、系統故障、介質故障、站點故障、通信故障。事務故障、系統故障、介質故障也可能出現在集中式數據庫系統中。4.7 請

40、用自己的語言描述兩階段提交過程。 兩階段提交協議基本思想 將本地原子性提交行為的效果擴展到分布式事務, 保證了 分布式事務提交的原子性, 并在不損壞日志的情況下, 實現快速故障恢復, 提高DDB系統的可靠性。 兩階段提交協議把事務的提交過程分為兩個階段： 第一階段：表決階段，即形成一個共同的決定。 第二階段：執行階段，目的是實現這個決定 表決階段 目的是形成一個共同的決定 首先，協調者在日志中寫入一條開始提交記錄，再給所有參與者發送“準備”消息，進入等待狀態。 其次當參與者收到“準備”消息后，檢查是否能夠提交本地事務。 如能提交，參與者在日志中寫入一條開始提交的記錄，并給協調者發送“建議提交”

41、消息，然后進入就緒狀態； 否則，參與者寫入撤銷記錄，并給協調者發送“建議撤銷”消息。 如果某個站點作出“建議撤銷”提議，由于撤銷決定具有否決權(即單方面撤銷)，該站點可以忽略這個事務。 第三，協調者收到所有參與者的消息后，他就做出是否提交事務的決定。 只要有一個參與者投了反對票(建議撤銷)，協調者從整體上撤銷整個事務，發送“全局撤銷”消息給所有參與者，進入撤銷狀態； 否則，它寫入提交記錄，給所有參與者發送“全局提交”消息，然后進入提交狀態。 執行階段 實現表決階段的決定，提交或者撤銷。 根據協調者的指令，參與者或者提交事務，或者撤銷事務，并給協調者發送確認消息。 協調者在日志中寫入一條事務結束

42、記錄并終止事務。4.8 為什么說兩階段提交協議在不丟失運行日志信息的情況下，可以從從任何故障恢復？因為在執行過程中維護了事務日志，記錄了執行恢復所需要的信息。4.9 在分布式數據庫系統中對多副本數據的更新通常采用什么方法？快照方法的優點和缺點是什么？多站點數據更新法、主文本更新法、快照方法。快照方法的優缺點： 快照方法不考慮數據的輔助副本,只關心每一數據的主文本和在這些主文本上定義的任意多個快照。 快照與視圖一樣，可以定義為一個或多個主文本的部分拷貝或/和全部拷貝。 采用快照方法可以完成復雜的查詢, 但又不阻止更新，因為其中數據被暫時“凝固”，不受更新操作的影響，所以不會妨礙其他事務對有關數據

43、的更新操作。 為了與主文本保持同步，當主文本被更新時，需要刷新快照。 快照方法既避免了某些并發控制的開銷，又便于復雜查詢的完成，是提高系統可用性的有效方法。 快照是一個只讀關系，其中數據只能讀而不能寫。即對查詢操作可使用快照，也可使用主文本，對更新操作還是在主文本上進行。4.10 為什么說分布式事務增強了數據庫的一致性？第五章51 為什么說分布式數據并發控制比集中并發控制要復雜得多？ 5.2 描述分布式事務的可串行化理論的一些定義:事務、沖突操作、并發調度、串行調度、一致性調度、兩個調度等價、可串行化調度。 1.事務的定義一個事務是一個偏序集：Ti=i,i，其中：（1）i：操作符集合，包含Ri

44、x,Wix/x為數據項UAi,Ci，Ai,Ci是i中最后一個操作符，且只能出現其中之一個；Ai為撤銷(abort),Ci為提交(commit)；i：排序關系，即(沖突)操作有先后次序執行。（2）如果Rix,Wixi，則它們必滿足Ri(x)iWi(x)或Wi(x)iRi(x)。（3）Rix,Wix，Ai，Ci或公式的每一個都是事務Ti操作符序列中的一個操作。這是對事務的簡單定義，實際上事務中還可能包含其他操作如封鎖、通信原語等。 2. 沖突動作 如果有兩個操作P和Q對同一個數據A進行操作，其中有一個是寫操作W(A)，則 P和Q稱為沖突操作。 一個調度事務的一個操作序列稱為一個調度，一般用S表示。

45、比如，S：R1(x), R2(y), W2(y), R2(x), W1(x), W2(x)3. 并發事務的一個調度(簡稱并發調度)定義令T= T1,T2,Tn 是一組并發執行事務。T上的調度 S 是具有如下順序關系 T 的偏序集，即 S= T , T :(1) T = Ti (2) T i (3) 對任意兩個沖突操作 p,q S, 存在 p q 或 q p關系。 第一種情況簡單地說明了調度的域是每個事務域的并集。第二種情況定義排序關系為每個事務排序關系的超集，這保證了每一個事務內部的操作的順序。最后一種情況定義了沖突操作的執行順序。 4. 串行調度如果一個調度S中的任意兩個事務Ti 和 Tj，

46、i j，若i=1i j=1j 或者 j=1j i=1i 則稱調度S為串行調度。即一個事務的第一個動作是在另一個事務的最后一個動作完成后開始。即一個調度中不同事務的各個操作不會互相交叉, 每個事務是相繼 執行的。 5. 一致性調度如果執行一個調度S，可以使得數據庫從一個一致性狀態轉變為 另一個一致性狀態，則稱調度S為一致性調度。顯然，串行調度是一致性調度。 6.調度等價調度S1與S2是等價的充分條件是：對于兩個有沖突的操作Oi和Oj, 若 Oi, OjS1, 且OiOj在S1中也成立, 則Oi, OjS2, 且也有OiOj 在S2中也成立。 7. 可串行化調度如果一個調度等價于某個串行調度，則該

47、調度稱為可串行化調度。也就是說，該調度可以通過一系列非沖突動作的交換操作使其成 為串行調度。5.5 什么是兩階段封鎖協議？它如何保證可串行性？為什么人們經常更愿意采用嚴格兩階段封鎖和嚴酷兩階段封鎖？答：所謂兩段鎖協議是指所有事務必須分兩個階段對數據項加鎖和解鎖：1. 在對任何數據進行讀、寫操作之前，首先要申請并獲得對該數據的封鎖。2. 在釋放一個封鎖之后，事務不再申請和獲得任何其他封鎖。因此保證可串行性。由于實現基本2PL協議要鎖管理器必須要知道事務的鎖點位置；保守2PL要事先聲明續集和寫集，這都是難以實現的。嚴格2PL和嚴酷2PL容易實現。嚴格2PL的實現方法是：事務在提交或者撤銷之前，絕對

48、不釋放任何一個寫鎖；事務結束時（提交或者撤銷），同時釋放所有的鎖。嚴酷2PL的實現方法是：事務T在提交或撤銷之前，不能釋放任何一個鎖（寫鎖或者讀鎖），因此它比嚴格2PL更容易實現。 如果一個事務所有的封鎖操作(讀封鎖和寫封鎖)都放在第一個解鎖操作 之前，那么就說該事務遵守2PL協議。 事務的執行中Lock的管理分成兩個階段： 第一階段是擴張階段或成長階段：事務只能獲得新的數據項鎖，而 不能釋放任何已持有的鎖。 第二階段是收縮階段或衰退階段：事務只能釋放已經持有的鎖，而 不能獲得任何的新鎖。 一個很有名的理論Eswaran et al.,1976是：遵循了兩段鎖規則的并發控制算法鎖產生的調度都是

49、可串行化的。 可以證明，如果調度中的每個事務都遵守兩階段封鎖協議，就可以 保證該調度是可串行化的，不再需要檢測調度的可串行性。 實施兩階段封鎖規則的封鎖機制，也就實施了調度的可串行性。 兩階段封鎖限制了一個調度中可以發生的并發事務的數量，原因： 如果事務T稍后必須封鎖數據項Y，那么在它使用完數據項X之后， 獲得數據項Y之前，不可以釋放數據項X上的鎖；或者，反過來說，事務T必須在它需要數據項Y上的鎖之前就封鎖Y。以便它可以釋放 X上的鎖。 因此，T 必須一直持有 X上的鎖，直到該事務需要讀或寫的所有 數據項都被它自己封鎖，然后T才可以釋放X上的鎖。同時，即使T 已經使用完X，另一個要訪問X的事務

50、也可能會被強制等待。 相反，如果事務T在需要數據項Y之前就封鎖了它，那么即使T不是 正在使用數據項Y，其他想要訪問Y的事務也被強制等待。這正是 不必檢測調度本身就能保證所有調度可串行性的代價。5.6 描述死鎖預防中的占先權方法和非占先權方法，比較它們的異同。描述檢測分布式死鎖的三種基本方法。答：等待-死亡模式(非占先權)的方法：如果Ti對已被Tj封鎖的一數據項請求封鎖的話，則只有在Ti比Tj年老時（TiTj），則Ti被終止并帶有同一時間戳重新啟動。這個方法的理論基礎是：最好總是重新啟動較年輕的事務，允許較年老的事務去等待已持有資源的較年輕的事務，但不允許較年輕的事務去等待較年老的事務。受傷-等

51、待模式(占先權) 的方法是：如果Ti對已被Tj封鎖的一數據項請求封鎖的話，則只有在Ti比Tj年輕時（TiTj），才允許Ti等待。否則，Ti比Tj年老（TiTj），則Tj被終止并帶有同一時間戳重新啟動,而Ti得鎖執行。這個方法的理論基礎是：只有年輕的等待年老的。集中式死鎖檢測方法：選擇一個站點負責整個系統的死鎖檢測,死鎖檢測器放到這個站點。每個站點的鎖管理器周期性地將本站點的LWFG傳送給死鎖檢測器, 死鎖檢測器構造GWFG, 并在其中尋找回路；或者，其它每個站點上的鎖管理器周期性地把記錄本站點上事務的開始時間，對鎖的持有、請求情況變化的動態表，發送給負責處理封鎖的站點，由它維護一張全局封鎖動態

52、表，形成GWFG, 并在其中尋找回路。如果至少包含一條回路，它會選擇一個或者多個事務，把它們取消并恢復，釋放資源，使得其它事務繼續進行。選擇的標準是盡可能使撤銷并恢復的代價最小，如撤銷年輕的事務，撤銷占有較少資源的事務，撤銷具有最短運行時間的事務，撤銷具有最長運行時間的事務等，使系統情況而定。層次式死鎖檢測方法：樹葉是各站點的局部死鎖檢測器，在本站點建立局部等待圖。本站點的死鎖檢測器找出本站點局部等待圖中的任何回路，并把有關潛在全局回路的信息發送給上一層死鎖檢測器。每個非本地死鎖檢測器只對它所涉及的緊挨下層進行死鎖檢測，合并這些接收到的有關潛在全局回路的信息，并找出任何回路。如果還有上層死鎖檢測器，將經過簡化的有關潛在全局回路的信息發送給它上一層死鎖檢測器，由上一層死鎖檢測器再進行合并，找出任何全局回路。這樣，逐層檢測，直到最高層。分布式死鎖檢測方法：使用局部信息建造LWFG, 該LWFG包含EX節點。對每次接收到的信息, 執行如下對LWFG的修改。對報文中的每個事務, 若LWFG中不存