大工---分布式資料庫 重點總結

大工分布式資料庫總結+部分考題

分布式資料庫文章我又重新整理了一遍 加了圖檔！ 詳細請點選上面連結！！

第一章：

1.2 分布式資料庫系統有幾種分類方法？這些方法分别是如何分類的？

1.按局部資料庫管理系統的資料模型的類型分類。

（1）同構型：

同構同質型：各個站點上的資料庫的資料模型都是同一類型的，而且是同一種DBMS。

同構異質型：各個站點上的資料庫的資料模型都是同一類型的，但不是同一種DBMS。

（2）異構型：各個站點上的資料庫的資料模型各不相同。

2.按分布式資料庫系統全局控制系統類型分類。

（1）全局控制集中型DDBS

（2）全局控制分散型DDBS

（3）全局控制可變型DDBS

1.3(*) 什麼是分布式資料庫系統？它具有哪些特點？怎樣差別分布式資料庫系統與隻提供遠端資料通路功能的網絡資料庫系統？

分布式資料庫系統是實體上分散而邏輯上集中的資料庫系統，其可以看成是計算機網絡和資料庫系統的有機結合。

基本特點：實體分布性、邏輯整體性、站點自治性。

導出特點：資料分布透明性、集中與自治相結合的機制、存在适當的資料備援度、事務管理的分布性。

區分：分布式資料庫的分布性是透明的，使用者感覺不到遠端與本地結合的接縫的存在。

1.4 簡述基于四層模式的分布式資料庫系統的體系結構。

全局外模式：全局概念模式的子集，從局部資料庫組成的邏輯集合中抽取；

全局概念模式：描述全局資料的邏輯結構和資料特性，由全局關系的定義和完整性定義組成；

分片模式：全局關系與片段之間的映像，全局關系通過選擇、投影操作被劃分為若幹片段；

配置設定模式：根據資料分布政策，定義各片段的實體存放站點；

局部概念模式：全局概念模式的子集，是該站點上全部實體映像的集合；

局部内模式：全局資料在本站點的存儲描述，與本站點上局部資料的存儲描述；

1.11(*) 簡述分布式資料庫目錄的内容、用途、組織方式、邏輯結構和分布方式、為什麼說在分布式資料庫系統中目錄系統的地位非常重要？

①　目錄的内容：全局模式描述；分片模式描述；分布模式描述；存取方式描述；局部名稱映射；資料庫統計資訊；狀态資訊；一緻性限制；資料表示；資料指令；系統描述；

②　目錄系統的用途：設計應用；翻譯應用；優化處理；運作監督；系統維護；

③　 目錄系統的組織方式:獨立式；分離式；嵌入式；

④　目錄系統的邏輯結構：

⑤　目錄系統的分布方式：集中式目錄；全複制式目錄；局部式目錄；混合式目錄；

⑥　為什麼目錄系統的地位非常重要？

因為目錄系統是存放對象和控制資訊的場所。

1.12 分布式資料庫系統的實作技術主要包括哪些内容？

分布式資料庫 設計；

分布式資料庫 查詢、優化；

分布式資料庫 并發控制；

分布式資料庫 事務管理與恢複；

分布式資料庫 安全性；

分布式資料庫 可靠性。

1.13 你認為現實生活中哪些系統是分布式資料庫？

銀行管理 分布式資料庫系統；

連鎖超市 分布式資料庫系統；

飛機訂票 分布式資料庫系統。

1.14(老師沒說，但書上畫了) 分布式資料庫系統的主要優點是什麼？存在哪些技術問題？

1)分布式資料庫系統的優點？

靈活性、可伸縮性；

可用性、可靠性；

效率高、（通信）費用低；

經濟性、保護投資；

資料分布透明性、站點自治性；

适合組織的分布式管理和控制。

2)分布式資料庫系統存在的技術的問題？

通信速度 （最重要的問題）；目錄管理；資料的分片、分布、備援度；（優化） 查詢處理；

（優化） 更新處理；并發控制 （機制）；恢複控制 （機制）；異構資料庫互聯；

第三章（全加）*

3.3 資料分片應遵守哪些基本原則？資料分片有哪些基本類型和方法？

1)資料分片應遵守的原則：

完備性原則；

可重構原則；

不相交原則；

2）資料分片的基本類型及方法：

水準分片；

垂直分片；

混合分片。

3.5 資料分布政策有哪幾種形式？如何把設計好的資料片段配置設定到相應的站點上？

1)資料分布政策的形式：

分割式；

複制式；

混合式；

2)如何把設計好的資料片段配置設定到相應的站點上？

根據應用需求确定是非備援配置設定還是備援配置設定；

非備援配置設定中，每個片段映射到一個站點上；

備援配置設定中，每個片段映射到一個或多個站點上；

設計者決定片段複制情況，使遠端通路次數少，效益高；

3.6 采用DATAID-D方法的分布式資料庫設計與傳統的集中式資料庫設計在步驟和内容上有什麼不同？

DATAID-D 是作為集中式資料庫設計DATAID-1 方法論的擴充面構造的；

DATAID-1 方法分成四個階段：需求分析、概念設計、邏輯設計和實體設計。

DATAID-D 要求對其增加兩個階段：分布要求分析階段和分布設計階段。

分布要求分析階段位于概念設計階段之後，主要工作：

1.收集使用者分布要求資訊；

2.水準分片的劃分謂詞；

3.每一應用在各站點激活的頻率。

分布設計階段在全局邏輯設計之後，主要工作：

1.分布要求和全局邏輯模式作為輸入；

2.形成為全局資料庫模式和邏輯通路表；

3.輸出為分片模式和配置設定模式。

3.7 為什麼說在分布式資料庫系統中，資料獨立性這一目标比集中式資料庫系統更為重要，也更為複雜？（老師沒說，但書上畫了）

集中式資料庫中，資料獨立性包括邏輯獨立性與資料的實體獨立性，分别表示使用者程式與資料的全局邏輯結構和資料的實體結構無關。在分布式資料庫中，除了資料的邏輯獨立性與資料的實體獨立性之外，還有資料的分布獨立性。所謂資料分布獨立性是指使用者或者使用者程式使用分布式資料庫如同使用集中式資料庫那樣，不必關心全局資料的分布情況，包括全局資料的邏輯分片情況，邏輯片段的站點位置分片情況，以及各站點上資料庫的資料模型等，也就是說全局資料的邏輯分片、片段的實體位置配置設定、各站點資料庫的資料模型等情況對使用者和使用者程式是透明的。分布獨立性也稱為分布透明性，分布透明性包括三個層次：分片透明性、位置透明性和局部資料模型透明性。

第四章

4.3 概述基于關系代數等價變換的查詢優化算法的基本原理和實作步驟。

基于關系代數等價變換的查詢優化的基本原則：把查詢問題轉變為關系代數表達式，分析得到查詢樹（文法樹）。進行從全局到片段的變換得到基于片段上的查詢樹，然後利用關系代數等價變換規則優化算法，，盡可能地先執行選擇和投影操作。

基于關系代數等價變換查詢優化的主要實作步驟如下：

1.将一個查詢問題轉換成關系代數表達式。

2.将關系代數表達式轉換為查詢樹，對一個關系代數表達式進行文法分析，可以得到一棵文法樹；

3.從全局查詢到片段查詢的變換：這個變換的典型方法是把基于全局關系的查詢樹中的全局關系名，用其重構該全局關系的各片段名替換，變換成相應片段上的查詢樹；

4.利用關系代數等價變換規則的優化算法對片段上的查詢樹進行優化處理，最後達到優化查詢的目的。

實作步驟的簡單寫法：

1.把查詢問題轉化為關系代數表達式；

2.分析所得查詢樹；

3.進行全局到片段的變換，得到基于片段的查詢樹；

4.先執行選擇、投影操作，後執行連接配接、合并操作；

5.優化查詢樹。

4.4 概述基于半連接配接算法的查詢優化的基本原理和适用情形。

基于半連接配接算法的查詢優化的基本原理：

從一個站點傳送關系到另一個站點做連接配接操作之前，除去與連接配接無關的資料，減少傳輸代價；

基于半連接配接算法的查詢優化的适用情形：

隻需要一個關系中的一小部分元組參與和另一個關系連接配接；

當傳輸費用是主要的因素時，适用半連接配接方案。

4.6 設有關系 R、S、T，如下圖所示：

（1）計算連接配接R∞S∞T

（2）計算半連接配接R∝S, S∝R, S ∝T, T∝R,R∝T, T∝S

（3）三個關系R,S,T分别位于三個不同的站點X,Y,Z。若采用基于半連接配接算法計算連接配接R∞S∞T ，請選擇使得傳輸代價最少的連接配接執行的站點和确定半連接配接序列。（對應4.7題）

解：

（老師讓看的題）設有關系S,T,如圖所示，

（1）計算連接配接S∞T

（2）計算半連接配接S ∝T, T∝S

（3）假設每個屬性域長度均為1B，C0=0, C1=1, 則

計算R=S∝T 選擇度ρ； 公式為ρ =Card®/Card(S)

計算S∝T收益； 公式Benefit1(S∝T )=(1-ρ)*Size(S)*Card(S)C1

計算S∝T代價； 公式Cost(S∝T )= C0+C1size (D)*val(D[T])

解：

、

第五章

5.1 概述分布式資料庫系統中的事務的定義、特性、結構和狀态，以及分布式事務所特有的性質。

定義：一個分布式操作的序列，被操作的資料分布在不同的站點上，是以稱為分布式事務;

特性：原子性、一緻性、隔離性和耐久性；（ACID, atomicity，consistency、isolation、durability）

結構：

以 begin transaction 作為事務的開始；

以 commit 作為事務成功完成的結束；

以 rollback 或 abort 作為事務失敗的結束；

狀态：活動、失敗、復原/夭折、部分送出、送出；

分布式事務特有的性質：大量的資料傳遞、通信原語和控制封包；

5.4 什麼是事務的送出點？為什麼說他們很重要？

什麼是事務的送出點？

當所有站點上的存取操作均已完成，并記錄在日志中時，即為事務送出點；

為什麼說事務的送出點很重要？

送出點後，事務在日志中寫入送出記錄；系統發生故障時，掃描日志，檢查已在日志中寫入，但沒有寫入送出記錄的所有事務 ；恢複時復原這些事務，取消它們對資料庫的影響。

5.5 日志、檔案庫和檢查點的作用是什麼？典型的日志包含哪些内容？為什麼要先寫日志？ 日志、檔案庫和檢查點的作用是什麼？典型的日志包含哪些内容？

日志的作用是：從故障中恢複事務；

檔案庫的作用：防止因媒體故障而破壞日志和資料庫；

檢查點的作用：便于恢複事務；

典型的日志包含：每個改變資料項值的寫操作記錄；

為什麼要“先寫日志”？

系統崩潰時主存内容丢失，恢複時隻考慮已寫入磁盤的日志内容；是以，要“先寫日志”。

5.7 請用自己的語言描述兩階段送出協定的執行過程

第一階段：表決階段；

首先，協調者在日志中寫入 開始送出記錄，再發送“準備”消息給所有參與者，進入等待狀态。

其次，參與者收到“準備”消息後，檢查是否能夠送出本地事務；

如能送出，參與者在日志中寫入開始送出記錄，并發送 “建議送出”消息給協調者，然後進入就緒狀态；

否則，參與者寫入撤銷記錄，并發送“建議撤銷”消息給協調者；

第三，協調者收到所有參與者的消息後，做出是否送出事務的決定；

隻要有一個參與者建議撤銷，協調者發送“全局撤銷”消息給所有參與者，進入撤銷狀态；

否則，協調者發送“全局送出”消息給所有參與者，進入送出狀态；

第二階段：執行階段；

根據協調者的指令，參與者送出或撤銷事務，并發送确認資訊給協調者；

協調者在日志中寫入事務結束記錄并終止事務；

5.8 為什麼說兩階段送出協定在不丢失運作日志資訊的情況下，可從任何故障恢複？

執行過程中，事務日志記錄了所需資訊；

第六章

6.2 描述分布式事務的可串行化理論的一些定義：事務，沖突操作，并發排程，串行排程，一緻性排程，等價排程，可串行化排程。

一、事務的定義

二、沖突操作

如果有兩個操作P和Q對同一個資料A進行操作，其中有一個是寫操作W(A)，則 P和Q稱為沖突操作。

三、并發排程【并發事務的一個排程】

五、串行排程

五、一緻性排程

如果執行一個排程S，可以使得資料庫從一個一緻性狀态轉變為另一個一緻性狀态，則稱排程S為一緻性排程。顯然，串行排程是一緻性排程。

六、排程等價

排程S1與S2是等價的充分條件是：對于兩個有沖突的操作Oi和Oj, 若 Oi, Oj∈S1, 且 Oi<Oj 在S1中成立, 則Oi, Oj∈S2, 且也有Oi<Oj 在S2中也成立。

七、可串行化排程

如果一個排程等價于某個串行排程，則該排程稱為可串行化排程。也即該排程可以通過一系列非沖突動作的交換操作使其成為串行排程。

簡單寫法：

6.3 在圖6.25中，圖（a）表示的是三個事務，每個事務含有多個Read_item和Write-item操作。圖b和圖c分别表示的是這三個事務的兩個排程E和F，使用優先圖判别E和F是否為串行化排程。

6.5 什麼是兩階段封鎖協定？它如何保證可串行性？為什麼人們更願意采用嚴格兩階段封鎖和嚴酷兩階段封鎖？

兩階段封鎖協定：

對資料進行讀、寫操作前，申請封鎖該資料；

釋放一個封鎖後，事務不再申請、獲得其他封鎖；

以此保證可串行性；

如果一個事務所有的封鎖操作都放在第一個解鎖操作之前，那麼就說該事務遵守兩階段封鎖協定（2PL），這樣的一個事務可以分為兩階段：第一階段稱為擴張階段，事務隻能獲得新的資料項鎖，而不能釋放任何已持有的鎖；第二階段稱為收縮階段，該階段事務隻能釋放已持有的鎖，而不能獲得任何新鎖。它限制了一個排程中可以發生的并發事務的數量，因而能夠保證可串行性。 由于實作基本2PL協定，鎖管理器必須要知道事務的鎖點位置。保守2PL要事先聲明讀集和寫集，這都是難以實作的。嚴格2PL和嚴酷2PL容易實作。

6.6描述死鎖預防中的占先權方法和非占先權方法，比較他們的異同，描述檢測分布式死鎖的三種基本方法。

非占先權方法(排隊在先者可能失去優先)也稱等待-死亡模式。

•如果Ti對已被Tj封鎖的一資料項請求封鎖的話，則隻有在Ti比Tj年老時（Ti<Tj），才允許Ti等待(失去優先)。如果Ti比Tj年輕（Ti>Tj），則Ti被終止并帶有同一時間戳重新啟動。

•這個方法的理論基礎是：最好總是重新啟動較年輕的事務。允許較年老的事務去等待已持有資源的較年輕的事務，但不允許較年輕的事務去等待較年老的事務。

如果Ti<Tj （Ti比Tj年老），則允許Ti等待(失去優先)。

如果Ti>Tj （Ti比Tj年輕），則Ti被終止并帶有同一時間戳重新啟動。

占先權方法(排隊在先者絕對優先)----也稱受傷-等待模式。

•如果Ti對已被Tj封鎖的資料項請求封鎖的話，則Ti比Tj年老（Ti<Tj），則Tj被終止并帶有同一時間戳重新啟動, 而允許Ti獲得鎖執行；否則，隻有在Ti比Tj年輕時（Ti>Tj），才允許Ti等待。

•這個方法的理論基礎是：要求終止較年輕的事務，并且允許年老的事務絕對優于年輕的事務，因而隻有年輕的等待年老的。

如果Ti<Tj （Ti比Tj年老），則Tj被終止并帶有同一時間戳重新啟動。

如果Ti>Tj （Ti比Tj年輕），則允許Ti等待。

6.7 什麼是多粒度封鎖和意向鎖？它們在什麼情況下使用？

多粒度封鎖是：封鎖的粒度不是單一的一種粒度，而是有多種粒度。可以定義多粒度樹，根節點是整個資料庫，葉節點表示最小的封鎖粒度。

意向鎖是：如果對一個節點加意向鎖，則說明該節點的下層節點正在被封鎖。對任一節點封鎖時，必須先對它的上層節點加意向鎖。

具有意向鎖的多粒度加鎖方法中，任意事務T要對一個資料對象加鎖，必須先對它的上層節點加意向鎖。申請封鎖時應該按自上而下的次序進行，釋放鎖時則應該按自下而上的次序進行。具有意向鎖的多粒度加鎖方法提高了系統的并發度, 減少了加鎖和釋放鎖的開銷。它已經在實際的DBMS系統中廣泛應用，例如Oracle中。

簡單寫法：

多粒度封鎖：封鎖多種粒度；可定義多粒度樹，根節點是整個資料庫，葉節點表示最小封鎖粒度；

意向鎖：

若對一個節點加意向鎖，則表明該節點的下層節點正被封鎖；

對任一節點封鎖時，必先對上層節點加意向鎖；

6.8 在分布式資料庫系統中如何産生和調整全局時标？讨論給予時标的并發控制方法中的基本時标法和保守時标法。

全局唯一時标由本地計數器值和站點辨別符構成。有兩個站點，在每個站點設定一個計數器, 每當發生一個事務, 計數器加一，這解決了同一站點内事務的次序問題。對于不同站點，在發送封包時把本站點的計數器值包含在封包中，用以近似地同步各站點的計數器值。若站點1收到一個封包的計數器值為Y，它比本地現行計數器X的值大，即Y>X，則把本地計數器值X改為Y+1；否則，若Y<X，則本地計數器值為原值基礎上加1(如站點2)。用這種方法來協調不同站點的計數器值保持同步。

基本時标法：

基本時标法使用下述規則：

–每個事務在本站點開始時賦予一個全局唯一時标；

–在事務結束前，不對資料庫進行實體更新；

–事務的每個讀操作或寫操作都具有該事務的時标；

–對于資料庫中的每個資料項x, 記錄對其進行讀操作和寫操作的 最大時标，分别記為RTM(x)和WTM(x)；

–如果事務被重新啟動，則被賦予新的時标。

基本時标法執行過程：

–令read_TS是事務對資料項x進行讀操作時的時标，

•若read_TS<WTM(x)，則拒絕該操作，并使發出該操作的事務用新時标重新啟動；否則執行該操作, 且令RTM(x)=max{RTM(x), read_TS}。

–令write_TS是對資料進行寫操作時的時标，

•若write_TS < RTM(x) 或 write_TS < WTM(x) ,則拒絕該 寫操作，并使發出該操作的事務用新時标重新啟動。否則執行該寫操作, 令WTM(x)=max{WTM(x), write_TS}。

•基本時标法執行過程確定了有沖突的操作在所有站點都是按時标順序執行的，是以是正确的。

•基本時标法的特點是不會産生死鎖，任何一個事務都不會阻塞，如果某一操作不能執行就重新啟動，而不是等待。這種方法避免死鎖是以重新開機動為代價的，缺點是重新開機動多。

保守時标法：

•保守時标法基本思想

•一種消除重新開機動的方法，通過緩沖年輕的操作，直至年長的操作執行完成，是以操作不會被拒絕，事務也絕不被重新開機動。為了執行一個被緩沖的操作，需知道什麼時候已沒有任何較年長 事務且與之沖突的操作。

•保守時标法的規則

規則1. 每個事務隻在一個站點執行, 它不能激活遠端的程式, 但是 可以向遠端站點發讀/寫請求消息；

規則2. 站點i 接收到來自不同站點j 的讀/寫請求必須按時标順序， 即每個站點必須按時标順序發送讀/寫資料請求，在傳輸中也不會改變這個順序，以保證各站點能夠按時标順序接收來自不同站點的全部讀/寫請求。要實作這一規則，較好的方法是使每個事務做到對同一資料先讀後寫；

規則3. 每個站點都為其它站點發來的讀/寫操作開辟一個緩沖區, 把接收到的讀/寫操作分别儲存在相應的緩沖區隊列中。

• 保守時标法的執行步驟：

假定某個站點k上，其各個緩沖區隊列都已不為空，即每個站點都已向它至少發送了一個讀和一個寫操作，就停止接收，處理在緩沖區中的操作。假定站點i 至少有一個緩沖的讀和緩沖的寫來自網絡中其它站點, 根據規則2, 站點i 知道沒有年老的請求來自其它站點 ( 因為按序接收, 是以不可能有比此更年老的請求到來, 年老的比年輕的先到)

(1)設RT=min(Rij), WT= min(Wij)

(2)按下列方法處理緩沖區隊列中的Rij和Wij

a. 掃描R隊列，若各隊列中存在(Rij) < WT的Rij , 則順序執行這些Rij，執行完從隊列中把它們删掉；

b. 掃描W隊列，若各隊列中存在(Wij) < RT的Wij, 則順序執行這些Wij，執行完從隊列中把它們删掉；

(3)更新 RT=min(Rij),WT=min(Wij), 此時Rij和Wij是隊列中剩餘的Rij和Wij ；

(4)重複上述(2)和(3), 直到沒有滿足條件的操作, 或者:a.若某個或某些R隊列為空時, RT=0;b.若某個或某些W隊列為空時, WT=0繼續接收各站點發送來的讀/寫請求操作。回到上述情形，若其各個緩沖區隊列又都不空，仍按上面步驟繼續。

簡單寫法:

1.在分布式資料庫系統中如何産生和調整全局時标？

每個站點設定一個計數器, 每發生一個事務, 計數器加 1。發送封包時包含本地計數器值, 近似同步各站點計數器；

2.讨論基于時标的并發控制方法中的基本時标法和保守時标法。

基本時标法：

事務開始時賦予全局時标；

事務的讀、寫操作具有該事務的時标；

對每個資料項 ，記錄讀、寫操作的最大時标；

若事務重新開機，則賦予新時标；

保守時标法：

每個事務隻在一個站點執行, 不能激活遠端程式, 但可以向遠端站點發讀、寫請求；

讀、寫請求按時标順序發送；

站點開辟緩沖區，儲存讀、寫請求。