分布式課后習(xí)題答案

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

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

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

4、個(gè)或多個(gè)站點(diǎn)上，稱為該邏輯片段在某個(gè)站點(diǎn)上的物理映像或稱物理片段。對每個(gè)站點(diǎn)來說，在該站點(diǎn)上全部物理映像的集合稱為該站點(diǎn)上的局部概念模式?；蛘哒f，一個(gè)站點(diǎn)上的局部概念模式是該站點(diǎn)上所有全局關(guān)系模式在該站點(diǎn)上物理映像的集合。（8）局部內(nèi)模式：是分布式數(shù)據(jù)庫中關(guān)于物理數(shù)據(jù)庫的描述，描述的內(nèi)容不僅包含局部本站點(diǎn)的數(shù)據(jù)的存儲描述，還包括全局?jǐn)?shù)據(jù)在本站點(diǎn)的存儲描述。1.4什么是分布式數(shù)據(jù)庫系統(tǒng)？它具有哪些主要特點(diǎn)？怎么樣區(qū)別分布式數(shù)據(jù)庫系統(tǒng)與只提供遠(yuǎn)程數(shù)據(jù)訪問功能的網(wǎng)絡(luò)數(shù)據(jù)庫系統(tǒng)？（分布式數(shù)據(jù)庫系統(tǒng)的定義、特點(diǎn)詳見課件第1章4.1.課本P6）分布式數(shù)據(jù)庫系統(tǒng)：物理上分散而邏輯上集中的系統(tǒng)，它使用計(jì)算機(jī)網(wǎng)

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

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

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

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

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

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

11、縮性4. 經(jīng)濟(jì)性和保護(hù)投資5. 適應(yīng)組織的分布式管理和控制6. 數(shù)據(jù)分布具有透明性和站點(diǎn)具有較好的自治性技術(shù)問題：1. 如何控制數(shù)據(jù)的分片、分布與冗余度2. 如何實(shí)現(xiàn)異構(gòu)數(shù)據(jù)庫的互聯(lián)（P.36）3. 如何優(yōu)化分布式數(shù)據(jù)庫的查詢處理（P.36）4. 如何更好地實(shí)現(xiàn)分布式數(shù)據(jù)庫的更新處理（P.36）5. 如何實(shí)現(xiàn)分布式數(shù)據(jù)庫的并發(fā)控制機(jī)制（P.36）6. 如何實(shí)現(xiàn)分布式數(shù)據(jù)庫的恢復(fù)控制機(jī)制（P.36）7. 如何實(shí)現(xiàn)目錄管理（P.36）第二章課后習(xí)題2.1 概述分布式數(shù)據(jù)庫系統(tǒng)的創(chuàng)建方法、方法特點(diǎn)和適用范圍答：創(chuàng)建方法有：組合法、重構(gòu)法組合法的特點(diǎn)：剖析網(wǎng)絡(luò)功能；剖析原有數(shù)據(jù)庫系統(tǒng)；解決數(shù)據(jù)的一致性

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

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

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

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

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

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

18、不可重疊；垂直群集的組在其他屬性上也可以重疊。 2.7為什么說在關(guān)系型分布式數(shù)據(jù)庫中使用導(dǎo)出式水平分片，使關(guān)系之間的連接變得更加容易？試舉例。 答：原因：全局關(guān)系的導(dǎo)出式水平分片不是以其自身的屬性性質(zhì)為基礎(chǔ)，而是從另一個(gè)關(guān)系的屬性性質(zhì)或水平片段推導(dǎo)出來的。 確定一方便的導(dǎo)出式水平分片要求確定應(yīng)用所執(zhí)行的最重要的結(jié)合操作。導(dǎo)出分片可使片段與片段間“連接”變得更容易?？蓪⑦B接條件代之以子查詢，從而使它變?yōu)橐话愕呐袆e條件。具體實(shí)例： 例2.3 設(shè)全局關(guān)系 SC( S#, C#, GRADE) S ( S#, SNAME, AGE, SEX ) 要求： 將SC劃分為男生各門課成績和女生的各門成績。 這

19、不可能從SC本身的屬性性質(zhì)來執(zhí)行選擇，必須從關(guān)系S的屬性性質(zhì)或水平片段來導(dǎo)出。 按S的屬性導(dǎo)出 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已經(jīng)進(jìn)行水平分片，分為SF和SM, 分別為男生全體和女

20、生全體， 則按S的水平分片（SF/SM）導(dǎo)出： 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方法的分布式數(shù)據(jù)庫設(shè)計(jì)與傳統(tǒng)的集中式數(shù)據(jù)庫設(shè)計(jì)在步驟和內(nèi)容上有什么不同？分布要求分析設(shè)計(jì)位于概念設(shè)計(jì)階段之后進(jìn)行，主要工作：1. 收集用戶分布要求信息2. 水平分片的劃分謂詞3. 每一應(yīng)用在各站點(diǎn)激活的頻率分布設(shè)計(jì)全局邏輯設(shè)計(jì)之后

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

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

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

24、。 實(shí)現(xiàn)步驟和方法 將一個(gè)查詢問題轉(zhuǎn)換成關(guān)系代數(shù)表達(dá)式。 從關(guān)系代數(shù)表達(dá)式到查詢樹的變換：對一個(gè)關(guān)系 代數(shù)表達(dá)式進(jìn)行語法分析，可以得到一棵語法樹 (或查詢樹)，即查詢樹根節(jié)點(diǎn)是最終的查詢結(jié)果，葉子節(jié)點(diǎn)是查詢涉及的所有關(guān)系或片段，中間節(jié) 點(diǎn)是按關(guān)系代數(shù)表達(dá)式中的操作順序組成的一組 關(guān)系操作符。 從全局查詢到片段查詢的變換：把基于全局關(guān)系 的查詢樹中的全局關(guān)系名，用其重構(gòu)該全局關(guān)系 的各個(gè)片段名替換，變換成相應(yīng)片段上的查詢樹。 利用關(guān)系代數(shù)等價(jià)變換規(guī)則優(yōu)化算法，對片段的 查詢樹進(jìn)行優(yōu)化處理，最后達(dá)到優(yōu)化查詢目的。3.4 概述基于半連接算法查詢優(yōu)化的基本原理和適用情形?；驹恚簆84p85 適用情

25、形：p85，由此可見那段，第四行的“所以?！遍_頭3.5 概述基于直接連接算法查詢優(yōu)化的基本原理和適用情形。另一種是自然連接。自然連接是一種特殊的等值連接，它要求兩個(gè)關(guān)系中進(jìn)行比較的分量必須是相同的屬性組，并且要在結(jié)果中把重復(fù)的屬性去掉。 3.6 設(shè)有關(guān)系R，S，T 如圖3.13所示。（1）設(shè)計(jì)連接RS T。（2）計(jì)算半連接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 如果習(xí)題3.6中的三個(gè)關(guān)系R,S,T分別位于三個(gè)不同的站點(diǎn)X,Y,Z。若采用基于半連接算法計(jì)算連接R S T，請選擇使得傳輸代價(jià)最小的連接執(zhí)行的站點(diǎn)和確定半連接序列。解：假設(shè)每個(gè)屬性域長度均為1B，考慮所有的半連接a) 選擇得益最高的P2進(jìn)行優(yōu)化，得到新的R,S,T，并對受到影響的的方案重新計(jì)算得益和費(fèi)用。新的R, S, T如下：對受到影響的的方案重新計(jì)算得益和費(fèi)用b) 選擇得益最高的P4進(jìn)行優(yōu)化，得到新的R,S,T，并對受到影響的方案重新計(jì)算得益和

27、費(fèi)用。 新的R, S, T如下：對受到影響的的方案重新計(jì)算得益和費(fèi)用c) 選擇得益最高的P1進(jìn)行優(yōu)化，得到新的R,S,T，并對受到影響的方案重新計(jì)算得益和費(fèi)用。 新的R, S, T如下：對受到影響的的方案重新計(jì)算得益和費(fèi)用d) 選擇得益最高的P3進(jìn)行優(yōu)化，得到X,Y,Z站點(diǎn)上最終的R,S,T。 X,Y,Z站點(diǎn)上最終的R,S,T如下：所以選擇各站點(diǎn)做連接的代價(jià)為： X站點(diǎn)代價(jià)=2*3+2*3=12 Y站點(diǎn)代價(jià)=4*3+2*3=18 Z站點(diǎn)代價(jià)=4*3+2*3=18故選擇X站點(diǎn)作為收集站點(diǎn)代價(jià)最低。由簡化過程得知半連接過程為：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 設(shè)某公司的雇員關(guān)系為employee(name,address,salary,plant-number)，按plant-number水平分片這個(gè)關(guān)系，每個(gè)片段都有兩個(gè)副本：一個(gè)副本存放在New York站點(diǎn)，另一個(gè)副本存放在工廠的站點(diǎn)。請為在Toronto站點(diǎn)提出的下列查詢設(shè)計(jì)一個(gè)好的處理策略。（1）找出Boce廠的所有雇員。（2）找出所有雇員的平均工資。（3）找出在如下每個(gè)站點(diǎn)工資最高的雇員姓名：Toronto，Edmonton，Vancouver，Montreal。（

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

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

31、結(jié)果的站點(diǎn)：（1）plant-number=X的站點(diǎn)，Aromonk站點(diǎn)；（2）plant-number=Xi的站點(diǎn)，Aromonk站點(diǎn)；（3）Aromonk站點(diǎn)4.1 概述分布式數(shù)據(jù)庫系統(tǒng)中事務(wù)的定義、特性、結(jié)構(gòu)和狀態(tài)，以及分布式事務(wù)所特有的性質(zhì)。分布式數(shù)據(jù)庫系統(tǒng)中的事務(wù)是一個(gè)分布式操作的序列，被操作的數(shù)據(jù)分布在不同的站點(diǎn)上，所以稱為分布式事務(wù)。 分布式事務(wù) 分布式數(shù)據(jù)庫系統(tǒng)中的事務(wù)是一個(gè)分布式操作的序列，被操作的數(shù)據(jù)分布在不同的站點(diǎn)上，所以稱為分布式事務(wù)。一個(gè)事務(wù)的執(zhí)行可能涉及多個(gè)站點(diǎn)上的數(shù)據(jù)。事務(wù)也在多個(gè)站點(diǎn)上執(zhí)行。 分布式事務(wù)是集中式事務(wù)的擴(kuò)充，它的ACID特性的保證要比集中式事務(wù)復(fù)雜

32、得多。因?yàn)橛卸鄠€(gè)站點(diǎn)參與執(zhí)行，其中任何一個(gè)站點(diǎn)的故障，或者將這些站點(diǎn)連接起來的任何一條通信鏈路的故障，都可能導(dǎo)致錯(cuò)誤發(fā)生。 因此分布式事務(wù)的恢復(fù)要比集中式事務(wù)的恢復(fù)要復(fù)雜得多。分布式數(shù)據(jù)庫系統(tǒng)中的事務(wù)具有ACID特性：原子性（Atomicity）:指事務(wù)執(zhí)行時(shí)的不可分割性。即事務(wù)的操作要么全部執(zhí)行, 要么全部不執(zhí)行，保證分布式數(shù)據(jù)庫一致性狀態(tài)。一致性（Consistency）:指一個(gè)使分布式數(shù)據(jù)庫從一個(gè)一致狀態(tài)轉(zhuǎn)變?yōu)榱硪粋€(gè)一致狀態(tài)的正確程序。分布式事務(wù)執(zhí)行完畢時(shí)，必須以正確的狀態(tài)退出系統(tǒng)。如果事務(wù)不能達(dá)到一個(gè)正常的結(jié)束狀態(tài)，就必須把分布式數(shù)據(jù)庫退回到該事務(wù)執(zhí)行前的初始狀態(tài)。持久性（Durabi

33、lity）:指一旦某個(gè)事務(wù)被提交后，則無論系統(tǒng)發(fā)生任何故障，都不會丟失該事務(wù)的執(zhí)行結(jié)果。也即，已提交事務(wù)對數(shù)據(jù)庫的改變在數(shù)據(jù)庫中應(yīng)該是持續(xù)存在的，這些改變不會因?yàn)楣收隙l(fā)生丟失。 隔離性（ Isolation）:指一個(gè)正在執(zhí)行的事務(wù)在其提交之前，決不允許把它對共享數(shù)據(jù)所作改變的結(jié)果提供給其他事務(wù)使用。也即事務(wù)的執(zhí)行似乎與其他事務(wù)相隔離，事務(wù)的執(zhí)行不應(yīng)受到其他并發(fā)事務(wù)執(zhí)行的干擾。雖然可以有多個(gè)事務(wù)同時(shí)執(zhí)行，但是單個(gè)事務(wù)的執(zhí)行不應(yīng)該感知其他事務(wù)的存在，因此事務(wù)執(zhí)行的中間結(jié)果應(yīng)該對其他并發(fā)事務(wù)隱藏 。 在分布式數(shù)據(jù)庫系統(tǒng)中，全局事務(wù)的主事務(wù)和子事務(wù)全部成功提交，才能改變數(shù)據(jù)庫狀態(tài)，有一個(gè)失敗，其他子

34、事務(wù)操作都要撤銷。為了保證事務(wù)的原子性，要求組成這個(gè)分布式事務(wù)的各個(gè)子事務(wù)，要么全部提交(成功結(jié)束)，要么全部撤銷(不成功結(jié)束)。如果至少有一個(gè)子事務(wù)執(zhí)行失敗，該分布式事務(wù)所包含的所有子事務(wù)，不管它的執(zhí)行成功與否，一律都被撤銷。各站點(diǎn)上的數(shù)據(jù)庫全都回滾到相應(yīng)子事務(wù)開始前的狀態(tài)，從而使整個(gè)分布式數(shù)據(jù)庫仍處于該分布式事務(wù)開始前的狀態(tài)。只有當(dāng)一個(gè)分布式事務(wù)所包含的所有子事務(wù)，都能成功執(zhí)行，各站點(diǎn)上的數(shù)據(jù)庫全都進(jìn)入一個(gè)新的一致狀態(tài)，才能使整個(gè)分布式數(shù)據(jù)庫轉(zhuǎn)換為新的一致狀態(tài)。為保證分布式事務(wù)的ACID特性，更需要對各子事務(wù)進(jìn)行協(xié)調(diào)和控制。結(jié)構(gòu)：分布式數(shù)據(jù)庫系統(tǒng)中事務(wù)的結(jié)構(gòu)以begin transacti

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

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

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

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

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

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

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

42、記錄并終止事務(wù)。4.8 為什么說兩階段提交協(xié)議在不丟失運(yùn)行日志信息的情況下，可以從從任何故障恢復(fù)？因?yàn)樵趫?zhí)行過程中維護(hù)了事務(wù)日志，記錄了執(zhí)行恢復(fù)所需要的信息。4.9 在分布式數(shù)據(jù)庫系統(tǒng)中對多副本數(shù)據(jù)的更新通常采用什么方法？快照方法的優(yōu)點(diǎn)和缺點(diǎn)是什么？多站點(diǎn)數(shù)據(jù)更新法、主文本更新法、快照方法?？煺辗椒ǖ膬?yōu)缺點(diǎn)： 快照方法不考慮數(shù)據(jù)的輔助副本,只關(guān)心每一數(shù)據(jù)的主文本和在這些主文本上定義的任意多個(gè)快照。 快照與視圖一樣，可以定義為一個(gè)或多個(gè)主文本的部分拷貝或/和全部拷貝。 采用快照方法可以完成復(fù)雜的查詢, 但又不阻止更新，因?yàn)槠渲袛?shù)據(jù)被暫時(shí)“凝固”，不受更新操作的影響，所以不會妨礙其他事務(wù)對有關(guān)數(shù)據(jù)

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

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

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

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

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

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

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

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

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

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