第一章 分布式數(shù)據(jù)庫系統(tǒng)概述1.1請用自己的語言定義下列分布式數(shù)據(jù)庫系統(tǒng)中的術(shù)語：（1）局部數(shù)據(jù):只提供本站點的局部應(yīng)用所需要的數(shù)據(jù)。全局數(shù)據(jù)：雖然物理上存儲在個站點上，但是參與全局應(yīng)用（2）全局/局部用戶：局部用戶： 一個用戶或一個應(yīng)用如果只訪問他注冊的那個站點上的數(shù)據(jù)稱為本地或局部用戶或本地應(yīng)用；全局用戶： 如果訪問涉及兩個或兩個以上的站點中的數(shù)據(jù)，稱為全局用戶或全局應(yīng)用。全局/局部DBMS：1）LDBMS(Local DBMS)：局部場地上的數(shù)據(jù)庫管理系統(tǒng)，其功能是建立和管理局部數(shù)據(jù)庫，提供場地自治能力，執(zhí)行局部應(yīng)用及全局查詢的子查詢。（2）GDBMS(Global DBMS)：全局數(shù)據(jù)庫管理系統(tǒng)，主要功能是提供分布透明性，協(xié)調(diào)全局事物的執(zhí)行，協(xié)調(diào)各局部DBMS以完成全局應(yīng)用，保證數(shù)據(jù)庫的全局一致性，執(zhí)行并發(fā)控制，實現(xiàn)更新同步，提供全局恢復功能等。（3）全局外模式：全局應(yīng)用的用戶視圖，也稱全局視圖。從一個由各局部數(shù)據(jù)庫組成的邏輯集合中抽取，即全局外模式是全局概念式的子集。對全局用戶而言，都可以認為在整個分布式數(shù)據(jù)庫系統(tǒng)的各個站點上的所有數(shù)據(jù)庫都如同在本站點上一樣，只關(guān)心他們自己所使用的那部分數(shù)據(jù)（4）全局概念模式：描述分布式數(shù)據(jù)庫中全局數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)特性，是分布式數(shù)據(jù)庫的全局概念視圖。采用關(guān)系模型的全局概念模式由一組全局關(guān)系的定義(如關(guān)系名、關(guān)系中的屬性、每一屬性的數(shù)據(jù)類型和長度等)和完整性定義(關(guān)系的主鍵、外鍵及完整性其他約束條件等)組成。（5）分片模式：描述全局數(shù)據(jù)的邏輯劃分。每個全局關(guān)系可以通過選擇和投影的關(guān)系操作被邏輯劃分為若干片段。分片模式描述數(shù)據(jù)分片或定義片段，以及全局關(guān)系與片段之間的映像。這種映像是一對多的。（6）分配模式：根據(jù)選定的數(shù)據(jù)分布策略，定義各片段的物理存放站點，即定義片段映像的類型，確定分布式數(shù)據(jù)庫是冗余的還是非冗余的，以及冗余的程度。如果一個片段分配在多個站點上，則片段的映像是一對多的，分布式數(shù)據(jù)庫是冗余的，否則是不冗余的。（7）局部概念模式：是全局概念模式的子集。全局概念模式經(jīng)邏輯劃分成一個或多個邏輯片段，每個邏輯片段被分配在一個或多個站點上，稱為該邏輯片段在某個站點上的物理映像或稱物理片段。對每個站點來說，在該站點上全部物理映像的集合稱為該站點上的局部概念模式?；蛘哒f，一個站點上的局部概念模式是該站點上所有全局關(guān)系模式在該站點上物理映像的集合。（8）局部內(nèi)模式：是分布式數(shù)據(jù)庫中關(guān)于物理數(shù)據(jù)庫的描述，描述的內(nèi)容不僅包含局部本站點的數(shù)據(jù)的存儲描述，還包括全局數(shù)據(jù)在本站點的存儲描述。1.4什么是分布式數(shù)據(jù)庫系統(tǒng)？它具有哪些主要特點？怎么樣區(qū)別分布式數(shù)據(jù)庫系統(tǒng)與只提供遠程數(shù)據(jù)訪問功能的網(wǎng)絡(luò)數(shù)據(jù)庫系統(tǒng)？（分布式數(shù)據(jù)庫系統(tǒng)的定義、特點詳見課件第1章4.1.課本P6）分布式數(shù)據(jù)庫系統(tǒng)：物理上分散而邏輯上集中的系統(tǒng)，它使用計算機網(wǎng)絡(luò)將地理位置分散而管理和控制又需要不同程度集中的多個邏輯單位（通常是集中式數(shù)據(jù)庫系統(tǒng)）連接起來，共同組成一個統(tǒng)一的數(shù)據(jù)庫系統(tǒng)。分布式數(shù)據(jù)庫系統(tǒng)可以看成是計算機網(wǎng)絡(luò)和數(shù)據(jù)庫系統(tǒng)的有機結(jié)合。特點：物理分布性、邏輯整體性、站點自治性、數(shù)據(jù)分布透明性、集中與自治相結(jié)合的控制機制、存在適當?shù)臄?shù)據(jù)冗余度、事務(wù)管理的分布性。1.6用自己的語言解析“什么時候需要進行數(shù)據(jù)分片和數(shù)據(jù)復制”？（課本第10,11頁）數(shù)據(jù)分片又稱數(shù)據(jù)分割、數(shù)據(jù)分段，局部數(shù)據(jù)庫是由全局數(shù)據(jù)庫分割而成；全局數(shù)據(jù)庫 是由各個局部數(shù)據(jù)庫邏輯組合而成。一個關(guān)系描述了某些數(shù)據(jù)之間的邏輯相關(guān)性，不同站點的用戶需要該關(guān)系中的元組可能不同，需要對這個關(guān)系進行分割，并將 分割后得到的各部分元組，稱為該關(guān)系的邏輯片段，存放在相應(yīng)的站點上。這樣 處理各得其所，可以減少網(wǎng)絡(luò)上的通信，提高系統(tǒng)的相應(yīng)效率。數(shù)據(jù)復制指分布式數(shù)據(jù)庫中的數(shù)據(jù)根據(jù)需要將數(shù)據(jù)劃分成邏輯片段，按某種策略把數(shù)據(jù) 分片所得的邏輯片段分散地存儲在各個站點上。全局數(shù)據(jù)有多個副本，每個站點都有一個完整的數(shù)據(jù)副本。系統(tǒng)可靠性高，響應(yīng)速度快，數(shù)據(jù)庫恢復也較容易。但要保持各個站點上數(shù)據(jù)的同步修改，將要付出高昂的代價。1.7在分布式數(shù)據(jù)庫系統(tǒng)中，為什么要對數(shù)據(jù)進行分片？什么是關(guān)系的片段？關(guān)系的片段有哪些主要類型？（課本第9-10頁。數(shù)據(jù)分片又稱數(shù)據(jù)分割、數(shù)據(jù)分段，局部數(shù)據(jù)庫是由全局數(shù)據(jù)庫分割而成；全局數(shù)據(jù)庫 是由各個局部數(shù)據(jù)庫邏輯組合而成。一個關(guān)系描述了某些數(shù)據(jù)之間的邏輯相關(guān)性，不同站點的用戶需要該關(guān)系中的元組可能不同，需要對這個關(guān)系進行分割，并將 分割后得到的各部分元組，稱為該關(guān)系的邏輯片段，存放在相應(yīng)的站點上。這樣 處理各得其所，可以減少網(wǎng)絡(luò)上的通信，提高系統(tǒng)的相應(yīng)效率。數(shù)據(jù)分片是指數(shù)據(jù)存放單位不是全部關(guān)系，而是關(guān)系的一個片段。也就是關(guān)系的一部分。包括： （1）水平分片：按一定的條件把全局關(guān)系的所有元組劃分成若干不相交的子集，每個子集為關(guān)系的一個片段。 （2）垂直分片：把一個全局關(guān)系的屬性集分成若干子集，并在這些子集上做投影運算，每個投影為垂直分片。 （3）混合型分片：將水平分片與垂直分片方式綜合使用則為混合型分片。 ）1.8為什么說分布式數(shù)據(jù)庫系統(tǒng)中，數(shù)據(jù)獨立性這一目標比集中式數(shù)據(jù)庫系統(tǒng)更為重要，也更為復雜？（詳見課本第25頁第二段）1.9概述分布式DBMS的參考模型中，用戶處理器、數(shù)據(jù)處理器、全局數(shù)據(jù)庫控制和通信子系統(tǒng)的組成和功能。（組成（參考模型）：詳見課件5.6；功能：用戶處理器課本第18頁；數(shù)據(jù)處理器課本第20頁；全局數(shù)據(jù)庫控制和通信子系統(tǒng)課本第21頁）用戶處理器：用戶結(jié)果格式化器用戶命令翻譯器約束實施器用戶結(jié)果用戶命令規(guī)范化數(shù)據(jù)規(guī)范化命令外部模式概念模式規(guī)范化命令用戶處理器用戶處理器的功能一是它把數(shù)據(jù)操縱語言中的用戶命令，翻譯成規(guī)范化命令。；二是它把來自數(shù)據(jù)處理器的數(shù)據(jù)，翻譯成用戶理解的格式。數(shù)據(jù)處理器：數(shù)據(jù)處理器負責存取數(shù)據(jù)庫的數(shù)據(jù)，數(shù)據(jù)處理器的組成主要包括：規(guī)范化命令翻譯器、規(guī)范化結(jié)果格式器和運行時支持處理器。全局數(shù)據(jù)庫控制和通信子系統(tǒng)的組成和功能：全局數(shù)據(jù)庫控制和通信子系統(tǒng)負責通信和控制分布式的執(zhí)行。由多個處理器組成：1. 分解器：分解器由一個或幾個數(shù)據(jù)處理器組成，主要任務(wù)是把來自用戶處理器的請求，翻譯成一個由若干命令組成的分布式執(zhí)行策略。2. 合并器：它的任務(wù)是在提交給用戶處理器之前，把分布式執(zhí)行策略訪問不同站點所得到的結(jié)果數(shù)據(jù)組合起來。3. 分布式執(zhí)行監(jiān)視器：負責分布式執(zhí)行策略的正確執(zhí)行以及保證分布式環(huán)境中事務(wù)的原子性。同時還負責提供復制獨立性和分布式并發(fā)控制。4. 通信子系統(tǒng)：提供站點之間的信息傳送。每個站點都有一個通信處理器，與此通信子系統(tǒng)相接口。通信處理器使用一組通信協(xié)議來正確利用通信設(shè)施和為分布系統(tǒng)提供無錯的和可靠的通信。5. 本地執(zhí)行監(jiān)視器：負責在本地數(shù)據(jù)處理器中，執(zhí)行該分布式執(zhí)行策略中與本站點有關(guān)的部分。當執(zhí)行策略的某一部分在該數(shù)據(jù)處理器中完成執(zhí)行，或出現(xiàn)故障時，就由它來通知全局執(zhí)行監(jiān)視器。1.10分布式數(shù)據(jù)庫系統(tǒng)潛在的優(yōu)點是什么？存在哪些技術(shù)問題？（優(yōu)點：詳見課本第34-35頁共6點；技術(shù)問題詳見課本第35-36頁面共7點）優(yōu)點：1. 良好的可靠性和可用性2. 提高系統(tǒng)效率，降低通信費用3. 較大的靈活性和可伸縮性4. 經(jīng)濟性和保護投資5. 適應(yīng)組織的分布式管理和控制6. 數(shù)據(jù)分布具有透明性和站點具有較好的自治性技術(shù)問題：1. 如何控制數(shù)據(jù)的分片、分布與冗余度2. 如何實現(xiàn)異構(gòu)數(shù)據(jù)庫的互聯(lián)（P.36）3. 如何優(yōu)化分布式數(shù)據(jù)庫的查詢處理（P.36）4. 如何更好地實現(xiàn)分布式數(shù)據(jù)庫的更新處理（P.36）5. 如何實現(xiàn)分布式數(shù)據(jù)庫的并發(fā)控制機制（P.36）6. 如何實現(xiàn)分布式數(shù)據(jù)庫的恢復控制機制（P.36）7. 如何實現(xiàn)目錄管理（P.36）第二章課后習題2.1 概述分布式數(shù)據(jù)庫系統(tǒng)的創(chuàng)建方法、方法特點和適用范圍答：創(chuàng)建方法有：組合法、重構(gòu)法組合法的特點：剖析網(wǎng)絡(luò)功能；剖析原有數(shù)據(jù)庫系統(tǒng)；解決數(shù)據(jù)的一致性、完整性和可靠性；難度較大；組合法適用范圍：通常是異構(gòu)或者同構(gòu)異質(zhì)DDBS重構(gòu)法的特點：根據(jù)實現(xiàn)環(huán)境和用戶需求；按照DDBS的設(shè)計思想和方法；從總體設(shè)計做起，包括LDBS,重新建立一個DDBS；可有效解決數(shù)據(jù)一致性、完整性和可靠性問題。重構(gòu)法的適用范圍：通常是同構(gòu)異質(zhì)或同構(gòu)同質(zhì)DDBS2.2 分布式數(shù)據(jù)庫設(shè)計的主要目標是什么?1. 目標一：分布式數(shù)據(jù)庫的本地性或近地性2. 目標二：控制數(shù)據(jù)適當冗余3. 目標三：工作負荷分布4. 目標四：存儲的能力和費用2.3 概述分布式數(shù)據(jù)庫設(shè)計的關(guān)鍵問題及解決方法答：關(guān)鍵問題：1）數(shù)據(jù)的實際分布情況。訪問的多個數(shù)據(jù)對象是存放在同一站點上還是分布在多個站點所需的時間和費用有很大區(qū)別。2）數(shù)據(jù)對否被復制、復制副本的多少問題3）數(shù)據(jù)分片、片段如何復制、數(shù)據(jù)或片段如何分布、分布式數(shù)據(jù)庫管理系統(tǒng)的透明性解決方法：1）分布式數(shù)據(jù)庫遵循本地性或近地性，盡量減少通信次數(shù)和通信量，90/10準則，分片和分布方案（本地和遠程訪問次數(shù)）擇優(yōu)；90%的數(shù)據(jù)應(yīng)當在本地站點找到，而只有10%的數(shù)據(jù)需要在遠程站點上進行訪問。也即最有效的設(shè)計是確保數(shù)據(jù)對最大數(shù)目的應(yīng)用具有本地性。可以采用的設(shè)計方法是對每一種可供選擇的分片方法和片段的分配方法都統(tǒng)計出本地訪問和遠程訪問的次數(shù)，然后從其中選擇一個最佳的方案。2）控制數(shù)據(jù)適當冗余，冗余增加了可靠性、可用性，提高了效率，維護數(shù)據(jù)一致性開銷增加。在分布式數(shù)據(jù)庫系統(tǒng)中，為了提高系統(tǒng)的本地性、并發(fā)度和可靠性，需要增加數(shù)據(jù)的副本。這不僅使應(yīng)用具有高度的可用性和本地性，而且當數(shù)據(jù)的任何一個副本不能使用時，可方便地使用在另一站點中的該數(shù)據(jù)的副本進行恢復，從而提高系統(tǒng)的可靠性。3）工作負荷分布分布式計算機系統(tǒng)的一個重要特征是把工作負荷分布在網(wǎng)絡(luò)中的各個站點上。分布工作負荷的目的是充分利用每個站點計算機的能力和資源，以提高應(yīng)用執(zhí)行的平行程度，從而提高系統(tǒng)的性能。4）存儲能力和費用 數(shù)據(jù)庫的分布會受到各站點的存儲能力的影響。在網(wǎng)絡(luò)中可以有專門用于存儲數(shù)據(jù)的站點，也可以有完全不支持大容量存儲的站點。一般，數(shù)據(jù)存儲的費用與 CPU，I /O及傳輸?shù)馁M用相比是不重要的，但是必須考慮各站點可用存儲空間的限制。2.4 考慮為局域網(wǎng)設(shè)計的分布式數(shù)據(jù)庫系統(tǒng)和為廣域網(wǎng)設(shè)計的分布式數(shù)據(jù)庫系統(tǒng)由什么區(qū)別?這道不會，參考p42 1.分布式數(shù)據(jù)庫的本地性或近地性2.5 請用自己的語音闡述分布式數(shù)據(jù)庫設(shè)計的自頂向下和自底向上設(shè)計方法及其適用范圍。答: 自頂向下：(1) 從概念設(shè)計到形成形式規(guī)格說明設(shè)計分布式數(shù)據(jù)庫。從頭開始設(shè)計分布式數(shù)據(jù)庫。該方法假定設(shè)計者理解用戶的數(shù)據(jù)庫應(yīng)用要求，歷經(jīng)概念設(shè)計、邏輯 設(shè)計和物理設(shè)計階段，并將與計算機系統(tǒng)無關(guān)的規(guī)格說明逐漸求精成 低級的、與計算機系統(tǒng)有關(guān)的規(guī)格說明。概念設(shè)計和邏輯設(shè)計的結(jié)果 是數(shù)據(jù)庫的全局模式，包含了數(shù)據(jù)庫的所有數(shù)據(jù)元素及其使用形式。 專門針對分布式數(shù)據(jù)庫的一個設(shè)計階段稱為分布設(shè)計，將全局模式映 射成幾個可能交疊的子集模式，每一個子模式表示與一個站點有關(guān)的 信息子集，然后完成每一單個數(shù)據(jù)庫的設(shè)計。(2) 適用范圍：通常是同構(gòu)異質(zhì)或同構(gòu)同質(zhì)DDBS。自底向上： (1)通過聚集現(xiàn)存數(shù)據(jù)庫設(shè)計分布式數(shù)據(jù)庫。假定由于需要互聯(lián)一些現(xiàn)存數(shù)據(jù)庫以形成一個多數(shù)據(jù)庫系統(tǒng)，或由于對各站點已獨立完成了數(shù)據(jù)庫的概念說明，所以各站點上數(shù)據(jù)庫的規(guī)格說明已是現(xiàn)存的。需要綜合各站點的規(guī)格說明，以便得到分布式數(shù)據(jù)庫的全局概念模式。(2)適用范圍：通常是異構(gòu)或者同構(gòu)異質(zhì)DDBS。2.6數(shù)據(jù)分片應(yīng)遵守哪些原則?數(shù)據(jù)分片要準守的原則：完備性原則：要把所有的數(shù)據(jù)映射到各個片斷中可重構(gòu)原則：關(guān)系分片后的各個片斷可重構(gòu)整個關(guān)系不相交原則：關(guān)系分片后的各個片斷不能重疊數(shù)據(jù)分片有哪些基本類型和方法?有兩種基本的數(shù)據(jù)分片方法：水平分片方法和垂直分片方法。通過交替水平分片與垂直分片，可以產(chǎn)生混合分片。 水平分片 水平分片是對全局關(guān)系執(zhí)行“選擇”操作，把具有相同性質(zhì)的元組進行分組，構(gòu)成若干個不相交的子集。水平分片的方法可歸為初級分片和導出分片兩類。 垂直分片和垂直群集 一個全局關(guān)系的垂直分片是通過“投影”操作把它的屬性分成若干組。根據(jù)應(yīng)用以“同樣方式”(具有相同的使用頻率)訪問的屬性來進行分組。垂直分片的組必須只在某個鍵屬性上重疊，其他屬性不可重疊；垂直群集的組在其他屬性上也可以重疊。 2.7為什么說在關(guān)系型分布式數(shù)據(jù)庫中使用導出式水平分片，使關(guān)系之間的連接變得更加容易？試舉例。 答：原因：全局關(guān)系的導出式水平分片不是以其自身的屬性性質(zhì)為基礎(chǔ)，而是從另一個關(guān)系的屬性性質(zhì)或水平片段推導出來的。 確定一方便的導出式水平分片要求確定應(yīng)用所執(zhí)行的最重要的結(jié)合操作。導出分片可使片段與片段間“連接”變得更容易?？蓪⑦B接條件代之以子查詢，從而使它變?yōu)橐话愕呐袆e條件。具體實例： 例2.3 設(shè)全局關(guān)系 SC( S#, C#, GRADE) S ( S#, SNAME, AGE, SEX ) 要求： 將SC劃分為男生各門課成績和女生的各門成績。 這不可能從SC本身的屬性性質(zhì)來執(zhí)行選擇，必須從關(guān)系S的屬性性質(zhì)或水平片段來導出。 按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已經(jīng)進行水平分片，分為SF和SM, 分別為男生全體和女生全體， 則按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方法的分布式數(shù)據(jù)庫設(shè)計與傳統(tǒng)的集中式數(shù)據(jù)庫設(shè)計在步驟和內(nèi)容上有什么不同？分布要求分析設(shè)計位于概念設(shè)計階段之后進行，主要工作：1. 收集用戶分布要求信息2. 水平分片的劃分謂詞3. 每一應(yīng)用在各站點激活的頻率分布設(shè)計全局邏輯設(shè)計之后進行，主要工作：1. 分布要求和全局邏輯模式作為輸入2. 形式為全局數(shù)據(jù)庫模式和邏輯訪問表3. 輸出為分片模式和分配模式 第三章3.1 用自己的語言概述分布式查詢優(yōu)化與集中式查詢優(yōu)化的異同。 分布式查詢和集中式查詢的相同點即在本地的CPU和I/O代價，不同點為分布式查詢比集中式查詢多了通訊代價3.2 試述分布式查詢優(yōu)化的層次結(jié)構(gòu)。分布式查詢處理按不同層次結(jié)構(gòu)執(zhí)行，符合分布式DBMS的體系結(jié)構(gòu)。分布式查詢處理可分為四個層次。 查詢分解 將查詢問題（SQL）轉(zhuǎn)換成一個定義在全局關(guān)系上的關(guān)系代數(shù)表達式。 本層轉(zhuǎn)換所需要從全局概念模式中獲得。 數(shù)據(jù)本地化 把一個在全局關(guān)系上的查詢具體化，落實到合適的(使盡可能做到本地化或近地化)片段上的查詢。即將全局關(guān)系的關(guān)系代數(shù)表達式變換為相應(yīng)片段上的關(guān)系代數(shù)表達式。 這一變換所需要的信息在分片模式和片段的分配模式中 獲得。 全局優(yōu)化 輸入的是分片查詢，查詢優(yōu)化目標是尋找一個近于最優(yōu) 的執(zhí)行策略。 全局優(yōu)化即是找出分片查詢的最佳操作次序，使得代價函數(shù)最小。代價函數(shù)一般是I/O、CPU和通信代價之和。 全局優(yōu)化的一個重要方面是關(guān)于連接操作的優(yōu)化。全局 優(yōu)化處理層輸出是一個優(yōu)化的、片段上的關(guān)系代數(shù)查詢。 局部優(yōu)化 局部查詢優(yōu)化由擁有與查詢有關(guān)的片段的各個站點執(zhí)行。在每個站點上執(zhí)行的子查詢被稱為局部查詢。它由該站 點上的DBMS進行優(yōu)化，采用集中式數(shù)據(jù)庫系統(tǒng)中查詢 優(yōu)化的算法。所需信息取自局部模式。3.3 概括基于關(guān)系代數(shù)等價變換的查詢優(yōu)化算法的基本原理與實現(xiàn)步驟。 基本原理1. 把查詢問題轉(zhuǎn)化為關(guān)系代數(shù)表達式；2. 分析得到查詢樹；3. 進行全局到片段的變換得到基于片段的查詢樹；4. 利用關(guān)系代數(shù)等價變換規(guī)則的優(yōu)化算法，盡可能先執(zhí)行 選擇和投影操作，后執(zhí)行連接和合并操作；5. 對該查詢樹進行優(yōu)化，從而達到查詢優(yōu)化的目的。 優(yōu)化算法1. 連接操作和合并操作盡可能上提（樹根方向）；2. 選擇操作和投影操作盡可能下移（葉子方向）；3. 盡可能先執(zhí)行選擇和投影操作，后執(zhí)行連接和合并操作。4. 經(jīng)過選擇和投影操作不但可以減少其后操作量，還可以 減少操作次數(shù)。 實現(xiàn)步驟和方法 將一個查詢問題轉(zhuǎn)換成關(guān)系代數(shù)表達式。 從關(guān)系代數(shù)表達式到查詢樹的變換：對一個關(guān)系 代數(shù)表達式進行語法分析，可以得到一棵語法樹 (或查詢樹)，即查詢樹根節(jié)點是最終的查詢結(jié)果，葉子節(jié)點是查詢涉及的所有關(guān)系或片段，中間節(jié) 點是按關(guān)系代數(shù)表達式中的操作順序組成的一組 關(guān)系操作符。 從全局查詢到片段查詢的變換：把基于全局關(guān)系 的查詢樹中的全局關(guān)系名，用其重構(gòu)該全局關(guān)系 的各個片段名替換，變換成相應(yīng)片段上的查詢樹。 利用關(guān)系代數(shù)等價變換規(guī)則優(yōu)化算法，對片段的 查詢樹進行優(yōu)化處理，最后達到優(yōu)化查詢目的。3.4 概述基于半連接算法查詢優(yōu)化的基本原理和適用情形?；驹恚簆84p85 適用情形：p85，由此可見那段，第四行的“所以?！遍_頭3.5 概述基于直接連接算法查詢優(yōu)化的基本原理和適用情形。另一種是自然連接。自然連接是一種特殊的等值連接，它要求兩個關(guān)系中進行比較的分量必須是相同的屬性組，并且要在結(jié)果中把重復的屬性去掉。 3.6 設(shè)有關(guān)系R，S，T 如圖3.13所示。（1）設(shè)計連接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）RSABC235168535268SRBCD356359683S TBCD356683596416TR 為空RT 為空TSDEI6693893.7 如果習題3.6中的三個關(guān)系R,S,T分別位于三個不同的站點X,Y,Z。若采用基于半連接算法計算連接R S T，請選擇使得傳輸代價最小的連接執(zhí)行的站點和確定半連接序列。解：假設(shè)每個屬性域長度均為1B，考慮所有的半連接a) 選擇得益最高的P2進行優(yōu)化，得到新的R,S,T，并對受到影響的的方案重新計算得益和費用。新的R, S, T如下：對受到影響的的方案重新計算得益和費用b) 選擇得益最高的P4進行優(yōu)化，得到新的R,S,T，并對受到影響的方案重新計算得益和費用。 新的R, S, T如下：對受到影響的的方案重新計算得益和費用c) 選擇得益最高的P1進行優(yōu)化，得到新的R,S,T，并對受到影響的方案重新計算得益和費用。 新的R, S, T如下：對受到影響的的方案重新計算得益和費用d) 選擇得益最高的P3進行優(yōu)化，得到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傳送給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水平分片這個關(guān)系，每個片段都有兩個副本：一個副本存放在New York站點，另一個副本存放在工廠的站點。請為在Toronto站點提出的下列查詢設(shè)計一個好的處理策略。（1）找出Boce廠的所有雇員。（2）找出所有雇員的平均工資。（3）找出在如下每個站點工資最高的雇員姓名：Toronto，Edmonton，Vancouver，Montreal。（4）找出該公司中工資最低的雇員姓名1)將New York站點上的副本傳至Toronto站點； 2)在New York站點上求平均工資，傳至Toronto站點； 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水平分片，且每個片段本地存放在它所對應(yīng)的工廠站點；關(guān)系machine沒有被分片，整個關(guān)系存放在Armonk站點（整個系統(tǒng)站點的個數(shù)等于工廠的個數(shù)+1），并且假定存放machine關(guān)系的Armonk站點就是提出查詢和需要結(jié)果的站點。請為下列的查詢設(shè)計一個好的處理策略：（1）找出生成機器號為1130的工廠的所有雇員的雇員號和姓名。（2）找出包含機器類型為milling machine的工廠的所有雇員的雇員號和姓名。（3）找出employee machine。（1）提出查詢的站點：（1）Aromonk站點，plant-number=X的站點；（2）Aromonk站點，plant-number=Xi的站點；（3）各工廠站點 （2）需要結(jié)果的站點：（1）plant-number=X的站點，Aromonk站點；（2）plant-number=Xi的站點，Aromonk站點；（3）Aromonk站點4.1 概述分布式數(shù)據(jù)庫系統(tǒng)中事務(wù)的定義、特性、結(jié)構(gòu)和狀態(tài)，以及分布式事務(wù)所特有的性質(zhì)。分布式數(shù)據(jù)庫系統(tǒng)中的事務(wù)是一個分布式操作的序列，被操作的數(shù)據(jù)分布在不同的站點上，所以稱為分布式事務(wù)。 分布式事務(wù) 分布式數(shù)據(jù)庫系統(tǒng)中的事務(wù)是一個分布式操作的序列，被操作的數(shù)據(jù)分布在不同的站點上，所以稱為分布式事務(wù)。一個事務(wù)的執(zhí)行可能涉及多個站點上的數(shù)據(jù)。事務(wù)也在多個站點上執(zhí)行。 分布式事務(wù)是集中式事務(wù)的擴充，它的ACID特性的保證要比集中式事務(wù)復雜得多。因為有多個站點參與執(zhí)行，其中任何一個站點的故障，或者將這些站點連接起來的任何一條通信鏈路的故障，都可能導致錯誤發(fā)生。 因此分布式事務(wù)的恢復要比集中式事務(wù)的恢復要復雜得多。分布式數(shù)據(jù)庫系統(tǒng)中的事務(wù)具有ACID特性：原子性（Atomicity）:指事務(wù)執(zhí)行時的不可分割性。即事務(wù)的操作要么全部執(zhí)行, 要么全部不執(zhí)行，保證分布式數(shù)據(jù)庫一致性狀態(tài)。一致性（Consistency）:指一個使分布式數(shù)據(jù)庫從一個一致狀態(tài)轉(zhuǎn)變?yōu)榱硪粋€一致狀態(tài)的正確程序。分布式事務(wù)執(zhí)行完畢時，必須以正確的狀態(tài)退出系統(tǒng)。如果事務(wù)不能達到一個正常的結(jié)束狀態(tài)，就必須把分布式數(shù)據(jù)庫退回到該事務(wù)執(zhí)行前的初始狀態(tài)。持久性（Durability）:指一旦某個事務(wù)被提交后，則無論系統(tǒng)發(fā)生任何故障，都不會丟失該事務(wù)的執(zhí)行結(jié)果。也即，已提交事務(wù)對數(shù)據(jù)庫的改變在數(shù)據(jù)庫中應(yīng)該是持續(xù)存在的，這些改變不會因為故障而發(fā)生丟失。 隔離性（ Isolation）:指一個正在執(zhí)行的事務(wù)在其提交之前，決不允許把它對共享數(shù)據(jù)所作改變的結(jié)果提供給其他事務(wù)使用。也即事務(wù)的執(zhí)行似乎與其他事務(wù)相隔離，事務(wù)的執(zhí)行不應(yīng)受到其他并發(fā)事務(wù)執(zhí)行的干擾。雖然可以有多個事務(wù)同時執(zhí)行，但是單個事務(wù)的執(zhí)行不應(yīng)該感知其他事務(wù)的存在，因此事務(wù)執(zhí)行的中間結(jié)果應(yīng)該對其他并發(fā)事務(wù)隱藏 。 在分布式數(shù)據(jù)庫系統(tǒng)中，全局事務(wù)的主事務(wù)和子事務(wù)全部成功提交，才能改變數(shù)據(jù)庫狀態(tài)，有一個失敗，其他子事務(wù)操作都要撤銷。為了保證事務(wù)的原子性，要求組成這個分布式事務(wù)的各個子事務(wù)，要么全部提交(成功結(jié)束)，要么全部撤銷(不成功結(jié)束)。如果至少有一個子事務(wù)執(zhí)行失敗，該分布式事務(wù)所包含的所有子事務(wù)，不管它的執(zhí)行成功與否，一律都被撤銷。各站點上的數(shù)據(jù)庫全都回滾到相應(yīng)子事務(wù)開始前的狀態(tài)，從而使整個分布式數(shù)據(jù)庫仍處于該分布式事務(wù)開始前的狀態(tài)。只有當一個分布式事務(wù)所包含的所有子事務(wù)，都能成功執(zhí)行，各站點上的數(shù)據(jù)庫全都進入一個新的一致狀態(tài)，才能使整個分布式數(shù)據(jù)庫轉(zhuǎn)換為新的一致狀態(tài)。為保證分布式事務(wù)的ACID特性，更需要對各子事務(wù)進行協(xié)調(diào)和控制。結(jié)構(gòu)：分布式數(shù)據(jù)庫系統(tǒng)中事務(wù)的結(jié)構(gòu)以begin transaction原語作為一個事務(wù)的開始，以commit原語作為一個事務(wù)成功完成的結(jié)束，而以rollback或abort原語作為事務(wù)失敗的結(jié)束。狀態(tài)：活動(active): 從事務(wù)開始執(zhí)行的初始狀態(tài)始， 事務(wù)執(zhí)行中保持該狀態(tài)。部分提交(partially committed): 事務(wù)的最后一個語句執(zhí)行后進入該狀態(tài).失敗(failed): 一旦發(fā)現(xiàn)事務(wù)不能正常執(zhí)行時進入該狀態(tài).回滾/夭折(rollback/aborted): 當事務(wù)被回滾后，數(shù)據(jù)庫恢復到事務(wù)開始執(zhí)行前的狀態(tài)。 提交(committed): 當事務(wù)成功執(zhí)行后.分布式事務(wù)獨有的特性：大量的數(shù)據(jù)傳送、通信原語和控制報文等。4.2 請用自己的語言描述分布式事務(wù)管理的抽象模型和分布式事務(wù)執(zhí)行的控制模型。務(wù)管理器與局部事物管理器之間不必要的數(shù)據(jù)傳輸。4.3 分布式數(shù)據(jù)庫系統(tǒng)中的事務(wù)管理與集中式數(shù)據(jù)庫系統(tǒng)中的事務(wù)管理有何不同？分布式與集中式相比，會多遇到一些問題：（1）處理數(shù)據(jù)項的多個副本；（2）單個站點的故障；（3）通信網(wǎng)絡(luò)的故障；（4）分布式提交。4.4 什么是事務(wù)的提交點？為什么說它們很重要？當事務(wù)所有的站點數(shù)據(jù)庫存取操作都已成功執(zhí)行，并且所有操作對數(shù)據(jù)庫的影響都已記錄在日志中時，該事務(wù)就到達提交點。事務(wù)的提交點：當事務(wù)T所有的站點數(shù)據(jù)庫存取操作都已成功執(zhí)行，并且 所有操作對數(shù)據(jù)庫的影響都已記錄在日志中時，該事務(wù)就到達提交點。提交點后事務(wù)就成為已提交的事務(wù)，并假定其結(jié)果已永久記錄在數(shù)據(jù)庫中(事務(wù)的永久性)。事務(wù)在日志中寫入提交記錄commit，T。在系統(tǒng)發(fā)生故障時，需要掃描日志，檢查那些已在日志中寫入start_transaction，T，但沒有寫入commit，T的所有事務(wù)T。恢復時必須回滾這些事務(wù)以取消它們對數(shù)據(jù)庫的影響。此外，還必須對日志中記錄的已提交子事務(wù)的所有寫操作進行恢復，這樣它們對數(shù)據(jù)庫的作用才可根據(jù)這些記錄重做Redo。4.5 日志、檔案庫和檢查點的作用是什么？典型的日志包含哪些內(nèi)容？為什么要“先寫日志”？日志的作用是為了能夠從故障狀態(tài)中恢復有影響的事務(wù)，系統(tǒng)維護一個 日志來保存所有影響數(shù)據(jù)庫項的值的事務(wù)操作的信息，這些信息可以用于故障時的恢復。檔案庫的作用是為了防止因介質(zhì)故障而破壞數(shù)據(jù)庫，要定期將整個數(shù)據(jù)庫的全部內(nèi)容轉(zhuǎn)儲到檔案庫中去。存放數(shù)據(jù)庫的檔案存儲設(shè)備稱為數(shù)據(jù)庫檔案庫(DB archive)檢查點的作用是為了便于恢復，在日志中設(shè)定一種周期性(時間/容量)操作點，稱為檢查點，以標識檢查點前已執(zhí)行完的事務(wù)是正確的。典型的日志包含了每個改變數(shù)據(jù)項值的寫操作記錄。日志Log記錄項 : start_transaction, T：表示事務(wù)T開始執(zhí)行； write_item, T, x, 舊值, 新值：表示事務(wù)T已將數(shù)據(jù)項X的值從舊值改為新值。 read_item, T, x：表示事務(wù)T已讀取數(shù)據(jù)項X的值。 commit, T：表示事務(wù)T已成功完成，其結(jié)果已被提交(永久記錄) 給數(shù)據(jù)庫。 abort, T：表示事務(wù)T已被撤銷。 Log：記錄長度及用于恢復過程的輔助信息，如指向本事務(wù)前一 日志記錄的指針，檢查點記錄等。先寫日志：因為系統(tǒng)崩潰時主存中的內(nèi)容可能丟失，所以恢復時只能考慮已寫回磁盤的日志內(nèi)容。因此，在事務(wù)到達提交點以前，還未寫到磁盤的日志的任何部分，必須被寫入磁盤，即“先寫日志”。4.6 列出分布式數(shù)據(jù)庫系統(tǒng)中可能出現(xiàn)故障類型。哪些故障也可能出現(xiàn)在集中式數(shù)據(jù)庫系統(tǒng)中？事務(wù)故障、系統(tǒng)故障、介質(zhì)故障、站點故障、通信故障。事務(wù)故障、系統(tǒng)故障、介質(zhì)故障也可能出現(xiàn)在集中式數(shù)據(jù)庫系統(tǒng)中。4.7 請用自己的語言描述兩階段提交過程。 兩階段提交協(xié)議基本思想 將本地原子性提交行為的效果擴展到分布式事務(wù), 保證了 分布式事務(wù)提交的原子性, 并在不損壞日志的情況下, 實現(xiàn)快速故障恢復, 提高DDB系統(tǒng)的可靠性。 兩階段提交協(xié)議把事務(wù)的提交過程分為兩個階段： 第一階段：表決階段，即形成一個共同的決定。 第二階段：執(zhí)行階段，目的是實現(xiàn)這個決定 表決階段 目的是形成一個共同的決定 首先，協(xié)調(diào)者在日志中寫入一條開始提交記錄，再給所有參與者發(fā)送“準備”消息，進入等待狀態(tài)。 其次當參與者收到“準備”消息后，檢查是否能夠提交本地事務(wù)。 如能提交，參與者在日志中寫入一條開始提交的記錄，并給協(xié)調(diào)者發(fā)送“建議提交”消息，然后進入就緒狀態(tài)； 否則，參與者寫入撤銷記錄，并給協(xié)調(diào)者發(fā)送“建議撤銷”消息。 如果某個站點作出“建議撤銷”提議，由于撤銷決定具有否決權(quán)(即單方面撤銷)，該站點可以忽略這個事務(wù)。 第三，協(xié)調(diào)者收到所有參與者的消息后，他就做出是否提交事務(wù)的決定。 只要有一個參與者投了反對票(建議撤銷)，協(xié)調(diào)者從整體上撤銷整個事務(wù)，發(fā)送“全局撤銷”消息給所有參與者，進入撤銷狀態(tài)； 否則，它寫入提交記錄，給所有參與者發(fā)送“全局提交”消息，然后進入提交狀態(tài)。 執(zhí)行階段 實現(xiàn)表決階段的決定，提交或者撤銷。 根據(jù)協(xié)調(diào)者的指令，參與者或者提交事務(wù)，或者撤銷事務(wù)，并給協(xié)調(diào)者發(fā)送確認消息。 協(xié)調(diào)者在日志中寫入一條事務(wù)結(jié)束記錄并終止事務(wù)。4.8 為什么說兩階段提交協(xié)議在不丟失運行日志信息的情況下，可以從從任何故障恢復？因為在執(zhí)行過程中維護了事務(wù)日志，記錄了執(zhí)行恢復所需要的信息。4.9 在分布式數(shù)據(jù)庫系統(tǒng)中對多副本數(shù)據(jù)的更新通常采用什么方法？快照方法的優(yōu)點和缺點是什么？多站點數(shù)據(jù)更新法、主文本更新法、快照方法。快照方法的優(yōu)缺點： 快照方法不考慮數(shù)據(jù)的輔助副本,只關(guān)心每一數(shù)據(jù)的主文本和在這些主文本上定義的任意多個快照。 快照與視圖一樣，可以定義為一個或多個主文本的部分拷貝或/和全部拷貝。 采用快照方法可以完成復雜的查詢, 但又不阻止更新，因為其中數(shù)據(jù)被暫時“凝固”，不受更新操作的影響，所以不會妨礙其他事務(wù)對有關(guān)數(shù)據(jù)的更新操作。 為了與主文本保持同步，當主文本被更新時，需要刷新快照。 快照方法既避免了某些并發(fā)控制的開銷，又便于復雜查詢的完成，是提高系統(tǒng)可用性的有效方法。 快照是一個只讀關(guān)系，其中數(shù)據(jù)只能讀而不能寫。即對查詢操作可使用快照，也可使用主文本，對更新操作還是在主文本上進行。4.10 為什么說分布式事務(wù)增強了數(shù)據(jù)庫的一致性？第五章51 為什么說分布式數(shù)據(jù)并發(fā)控制比集中并發(fā)控制要復雜得多？ 5.2 描述分布式事務(wù)的可串行化理論的一些定義:事務(wù)、沖突操作、并發(fā)調(diào)度、串行調(diào)度、一致性調(diào)度、兩個調(diào)度等價、可串行化調(diào)度。 1.事務(wù)的定義一個事務(wù)是一個偏序集：Ti=i,i，其中：（1）i：操作符集合，包含Rix,Wix/x為數(shù)據(jù)項UAi,Ci，Ai,Ci是i中最后一個操作符，且只能出現(xiàn)其中之一個；Ai為撤銷(abort),Ci為提交(commit)；i：排序關(guān)系，即(沖突)操作有先后次序執(zhí)行。（2）如果Rix,Wixi，則它們必滿足Ri(x)iWi(x)或Wi(x)iRi(x)。（3）Rix,Wix，Ai，Ci或公式的每一個都是事務(wù)Ti操作符序列中的一個操作。這是對事務(wù)的簡單定義，實際上事務(wù)中還可能包含其他操作如封鎖、通信原語等。 2. 沖突動作 如果有兩個操作P和Q對同一個數(shù)據(jù)A進行操作，其中有一個是寫操作W(A)，則 P和Q稱為沖突操作。 一個調(diào)度事務(wù)的一個操作序列稱為一個調(diào)度，一般用S表示。比如，S：R1(x), R2(y), W2(y), R2(x), W1(x), W2(x)3. 并發(fā)事務(wù)的一個調(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) 對任意兩個沖突操作 p,q S, 存在 p q 或 q p關(guān)系。 第一種情況簡單地說明了調(diào)度的域是每個事務(wù)域的并集。第二種情況定義排序關(guān)系為每個事務(wù)排序關(guān)系的超集，這保證了每一個事務(wù)內(nèi)部的操作的順序。最后一種情況定義了沖突操作的執(zhí)行順序。 4. 串行調(diào)度如果一個調(diào)度S中的任意兩個事務(wù)Ti 和 Tj，i j，若i=1i j=1j 或者 j=1j i=1i 則稱調(diào)度S為串行調(diào)度。即一個事務(wù)的第一個動作是在另一個事務(wù)的最后一個動作完成后開始。即一個調(diào)度中不同事務(wù)的各個操作不會互相交叉, 每個事務(wù)是相繼 執(zhí)行的。 5. 一致性調(diào)度如果執(zhí)行一個調(diào)度S，可以使得數(shù)據(jù)庫從一個一致性狀態(tài)轉(zhuǎn)變?yōu)?另一個一致性狀態(tài)，則稱調(diào)度S為一致性調(diào)度。顯然，串行調(diào)度是一致性調(diào)度。 6.調(diào)度等價調(diào)度S1與S2是等價的充分條件是：對于兩個有沖突的操作Oi和Oj, 若 Oi, OjS1, 且OiOj在S1中也成立, 則Oi, OjS2, 且也有OiOj 在S2中也成立。 7. 可串行化調(diào)度如果一個調(diào)度等價于某個串行調(diào)度，則該調(diào)度稱為可串行化調(diào)度。也就是說，該調(diào)度可以通過一系列非沖突動作的交換操作使其成 為串行調(diào)度。5.5 什么是兩階段封鎖協(xié)議？它如何保證可串行性？為什么人們經(jīng)常更愿意采用嚴格兩階段封鎖和嚴酷兩階段封鎖？答：所謂兩段鎖協(xié)議是指所有事務(wù)必須分兩個階段對數(shù)據(jù)項加鎖和解鎖：1. 在對任何數(shù)據(jù)進行讀、寫操作之前，首先要申請并獲得對該數(shù)據(jù)的封鎖。2. 在釋放一個封鎖之后，事務(wù)不再申請和獲得任何其他封鎖。因此保證可串行性。由于實現(xiàn)基本2PL協(xié)議要鎖管理器必須要知道事務(wù)的鎖點位置；保守2PL要事先聲明續(xù)集和寫集，這都是難以實現(xiàn)的。嚴格2PL和嚴酷2PL容易實現(xiàn)。嚴格2PL的實現(xiàn)方法是：事務(wù)在提交或者撤銷之前，絕對不釋放任何一個寫鎖；事務(wù)結(jié)束時（提交或者撤銷），同時釋放所有的鎖。嚴酷2PL的實現(xiàn)方法是：事務(wù)T在提交或撤銷之前，不能釋放任何一個鎖（寫鎖或者讀鎖），因此它比嚴格2PL更容易實現(xiàn)。 如果一個事務(wù)所有的封鎖操作(讀封鎖和寫封鎖)都放在第一個解鎖操作 之前，那么就說該事務(wù)遵守2PL協(xié)議。 事務(wù)的執(zhí)行中Lock的管理分成兩個階段： 第一階段是擴張階段或成長階段：事務(wù)只能獲得新的數(shù)據(jù)項鎖，而 不能釋放任何已持有的鎖。 第二階段是收縮階段或衰退階段：事務(wù)只能釋放已經(jīng)持有的鎖，而 不能獲得任何的新鎖。 一個很有名的理論Eswaran et al.,1976是：遵循了兩段鎖規(guī)則的并發(fā)控制算法鎖產(chǎn)生的調(diào)度都是可串行化的。 可以證明，如果調(diào)度中的每個事務(wù)都遵守兩階段封鎖協(xié)議，就可以 保證該調(diào)度是可串行化的，不再需要檢測調(diào)度的可串行性。 實施兩階段封鎖規(guī)則的封鎖機制，也就實施了調(diào)度的可串行性。 兩階段封鎖限制了一個調(diào)度中可以發(fā)生的并發(fā)事務(wù)的數(shù)量，原因： 如果事務(wù)T稍后必須封鎖數(shù)據(jù)項Y，那么在它使用完數(shù)據(jù)項X之后， 獲得數(shù)據(jù)項Y之前，不可以釋放數(shù)據(jù)項X上的鎖；或者，反過來說，事務(wù)T必須在它需要數(shù)據(jù)項Y上的鎖之前就封鎖Y。以便它可以釋放 X上的鎖。 因此，T 必須一直持有 X上的鎖，直到該事務(wù)需要讀或?qū)懙乃?數(shù)據(jù)項都被它自己封鎖，然后T才可以釋放X上的鎖。同時，即使T 已經(jīng)使用完X，另一個要訪問X的事務(wù)也可能會被強制等待。 相反，如果事務(wù)T在需要數(shù)據(jù)項Y之前就封鎖了它，那么即使T不是 正在使用數(shù)據(jù)項Y，其他想要訪問Y的事務(wù)也被強制等待。這正是 不必檢測調(diào)度本身就能保證所有調(diào)度可串行性的代價。5.6 描述死鎖預防中的占先權(quán)方法和非占先權(quán)方法，比較它們的異同。描述檢測分布式死鎖的三種基本方法。答：等待-死亡模式(非占先權(quán))的方法：如果Ti對已被Tj封鎖的一數(shù)據(jù)項請求封鎖的話，則只有在Ti比Tj年老時（TiTj），則Ti被終止并帶有同一時間戳重新啟動。這個方法的理論基礎(chǔ)是：最好總是重新啟動較年輕的事務(wù)，允許較年老的事務(wù)去等待已持有資源的較年輕的事務(wù)，但不允許較年輕的事務(wù)去等待較年老的事務(wù)。受傷-等待模式(占先權(quán)) 的方法是：如果Ti對已被Tj封鎖的一數(shù)據(jù)項請求封鎖的話，則只有在Ti比Tj年輕時（TiTj），才允許Ti等待。否則，Ti比Tj年老（TiTj），則Tj被終止并帶有同一時間戳重新啟動,而Ti得鎖執(zhí)行。這個方法的理論基礎(chǔ)是：只有年輕的等待年老的。集中式死鎖檢測方法：選擇一個站點負責整個系統(tǒng)的死鎖檢測,死鎖檢測器放到這個站點。每個站點的鎖管理器周期性地將本站點的LWFG傳送給死鎖檢測器, 死鎖檢測器構(gòu)造GWFG, 并在其中尋找回路；或者，其它每個站點上的鎖管理器周期性地把記錄本站點上事務(wù)的開始時間，對鎖的持有、請求情況變化的動態(tài)表，發(fā)送給負責處理封鎖的站點，由它維護一張全局封鎖動態(tài)表，形成GWFG, 并在其中尋找回路。如果至少包含一條回路，它會選擇一個或者多個事務(wù)，把它們?nèi)∠⒒謴停尫刨Y源，使得其它事務(wù)繼續(xù)進行。選擇的標準是盡可能使撤銷并恢復的代價最小，如撤銷年輕的事務(wù)，撤銷占有較少資源的事務(wù)，撤銷具有最短運行時間的事務(wù)，撤銷具有最長運行時間的事務(wù)等，使系統(tǒng)情況而定。層次式死鎖檢測方法：樹葉是各站點的局部死鎖檢測器，在本站點建立局部等待圖。本站點的死鎖檢測器找出本站點局部等待圖中的任何回路，并把有關(guān)潛在全局回路的信息發(fā)送給上一層死鎖檢測器。每個非本地死鎖檢測器只對它所涉及的緊挨下層進行死鎖檢測，合并這些接收到的有關(guān)潛在全局回路的信息，并找出任何回路。如果還有上層死鎖檢測器，將經(jīng)過簡化的有關(guān)潛在全局回路的信息發(fā)送給它上一層死鎖檢測器，由上一層死鎖檢測器再進行合并，找出任何全局回路。這樣，逐層檢測，直到最高層。分布式死鎖檢測方法：使用局部信息建造LWFG, 該LWFG包含EX節(jié)點。對每次接收到的信息, 執(zhí)行如下對LWFG的修改。對報文中的每個事務(wù), 若LWFG中不存