分布式數(shù)據(jù)庫總結(jié)(申德榮)

1、第一章 分布式數(shù)據(jù)庫系統(tǒng)概述一、分布式數(shù)據(jù)庫的發(fā)展1、分布式數(shù)據(jù)庫的發(fā)展：集中式數(shù)據(jù)庫管理系統(tǒng)的局限性：a.通訊瓶頸；b.響應(yīng)速度。推動分布式數(shù)據(jù)庫發(fā)展的動力：a.應(yīng)用需求；b.硬件環(huán)境的發(fā)展。二、分布式數(shù)據(jù)庫系統(tǒng)的定義：分布式數(shù)據(jù)庫系統(tǒng)，通俗地說，是物理上分散而邏輯上集中的數(shù)據(jù)庫系統(tǒng)。分布式數(shù)據(jù)庫系統(tǒng)使用計算機(jī)網(wǎng)絡(luò)將地理位置分散而管理和控制又需要不同程度集中的多個邏輯單位（通常是集中是數(shù)據(jù)庫系統(tǒng)）連接起來，共同組成一個統(tǒng)一的數(shù)據(jù)庫系統(tǒng)。三、分布式數(shù)據(jù)庫系統(tǒng)的特點(diǎn)：a.物理分布性：數(shù)據(jù)不是存放在一個站點(diǎn)上b.邏輯整體性：是與分散式數(shù)據(jù)庫系統(tǒng)的區(qū)別c.站點(diǎn)自治性：是與多處理機(jī)系統(tǒng)的區(qū)別d.數(shù)據(jù)分

2、布透明性e.集中與自治相結(jié)合的控制機(jī)制f.存在適當(dāng)?shù)臄?shù)據(jù)冗余度g.事務(wù)管理的分布性四、分布式數(shù)據(jù)庫系統(tǒng)的分類按局部數(shù)據(jù)庫管理系統(tǒng)的數(shù)據(jù)模型分類：同構(gòu)性（homogeneous）（分為同構(gòu)同質(zhì)型和同構(gòu)異質(zhì)型）DDBS和異構(gòu)性(heterogeneous)DDBS按分布式數(shù)據(jù)庫系統(tǒng)的全局控制系統(tǒng)類型分類：全局控制集中型DDBS，全局控制分散型DDBS，全局控制可變型DDBS。五、分布式數(shù)據(jù)庫中數(shù)據(jù)的獨(dú)立性和分布透明性所謂數(shù)據(jù)獨(dú)立性是指用戶或用戶程序使用分布式數(shù)據(jù)庫如同使用集中式數(shù)據(jù)庫那樣，不必關(guān)心全局?jǐn)?shù)據(jù)的分布情況，包括全局?jǐn)?shù)據(jù)的邏輯分片情況、邏輯片段站點(diǎn)位置的分配情況，以及各站點(diǎn)上數(shù)據(jù)庫的數(shù)據(jù)模

3、型等。也就是說，全局?jǐn)?shù)據(jù)的邏輯分片、片段的物理位置分配，各站點(diǎn)數(shù)據(jù)庫的數(shù)據(jù)模型等情況對用戶和用戶程序透明。所以，在分布式數(shù)據(jù)庫中分布獨(dú)立性也稱為分布透明性。六、分布式數(shù)據(jù)庫系統(tǒng)的體系結(jié)構(gòu)、組成成分集中式數(shù)據(jù)庫管理系統(tǒng)結(jié)構(gòu)：a. DB（數(shù)據(jù)庫）b. DBMS(集中式數(shù)據(jù)庫管理系統(tǒng)) c. DBA(數(shù)據(jù)庫管理員)分布式數(shù)據(jù)庫管理系統(tǒng)（DDBMS）結(jié)構(gòu)：a. LDB（局部數(shù)據(jù)庫） b. GDB（全局?jǐn)?shù)據(jù)庫） c. LDBMS (局部數(shù)據(jù)庫管理系統(tǒng))d. GDBMS (全局?jǐn)?shù)據(jù)庫管理系統(tǒng)) e. LDBA（局部數(shù)據(jù)庫管理員） f. GDBA (全局?jǐn)?shù)據(jù)庫管理員)七、分布式數(shù)據(jù)庫系統(tǒng)的特性：1. 數(shù)據(jù)透

4、明性：a.分布透明性 b. 分片透明性 c. 復(fù)制透明性2. 場地自治性：a. 設(shè)計自治性 b. 通信自治性 c. 執(zhí)行自治性八、分布式數(shù)據(jù)庫系統(tǒng)的優(yōu)點(diǎn):分布式數(shù)據(jù)庫系統(tǒng)是在集中式數(shù)據(jù)庫系統(tǒng)的基礎(chǔ)上發(fā)展來的，比較分布式數(shù)據(jù)庫系統(tǒng)與集中式數(shù)據(jù)庫系統(tǒng)，可以發(fā)現(xiàn)分布是數(shù)據(jù)庫系統(tǒng)具有下列優(yōu)點(diǎn)：1.更適合分布式的管理與控制。分布式數(shù)據(jù)庫系統(tǒng)的結(jié)構(gòu)更適合具有地理分布特性的組織或機(jī)構(gòu)使用，允許分布在不同區(qū)域、不同級別的各個部門對其自身的數(shù)據(jù)實(shí)行局部控制。例如：實(shí)現(xiàn)全局?jǐn)?shù)據(jù)在本地錄入、查詢、維護(hù)，這時由于計算機(jī)資源靠近用戶，可以降低通信代價，提高響應(yīng)速度，而涉及其他場地數(shù)據(jù)庫中的數(shù)據(jù)只是少量的，從而可以大大減

5、少網(wǎng)絡(luò)上的信息傳輸量；同時，局部數(shù)據(jù)的安全性也可以做得更好。2.具有靈活的體系結(jié)構(gòu)。集中式數(shù)據(jù)庫系統(tǒng)強(qiáng)調(diào)的是集中式控制，物理數(shù)據(jù)庫是存放在一個場地上的，由一個DBMS集中管理。多個用戶只可以通過近程或遠(yuǎn)程終端在多用戶操作系統(tǒng)支持下運(yùn)行該DBMS來共享集中是數(shù)據(jù)庫中的數(shù)據(jù)。而分布式數(shù)據(jù)庫系統(tǒng)的場地局部DBMS的自治性，使得大部分的局部事務(wù)管理和控制都能就地解決，只有在涉及其他場地的數(shù)據(jù)時才需要通過網(wǎng)絡(luò)作為全局事務(wù)來管理。分布式DBMS可以設(shè)計成具有不同程度的自治性，從具有充分的場地自治到幾乎是完全集中式的控制。3.系統(tǒng)經(jīng)濟(jì)，可靠性高，可用性好。與一個大型計算機(jī)支持一個大型的集中式數(shù)據(jù)庫在加一些進(jìn)

6、程和遠(yuǎn)程終端相比，由超級微型計算機(jī)或超級小型計算機(jī)支持的分布式數(shù)據(jù)庫系統(tǒng)往往具有更高的性價比和實(shí)施靈活性。分布式系統(tǒng)比集中式系統(tǒng)具有更高的可靠性和更好的可用性。如由于數(shù)據(jù)分布在多個場地并有許多復(fù)制數(shù)據(jù)，在個別場地或個別通信鏈路發(fā)生故障時，不致于導(dǎo)致整個系統(tǒng)的崩潰，而且系統(tǒng)的局部故障不會引起全局失控。4.在一定條件下響應(yīng)速度加快。如果存取的數(shù)據(jù)在本地數(shù)據(jù)庫中，那末就可以由用戶所在的計算機(jī)來執(zhí)行，速度就快。5.可擴(kuò)展性好，易于集成現(xiàn)有系統(tǒng)，也易于擴(kuò)充。對于一個企業(yè)或組織，可以采用分布式數(shù)據(jù)庫技術(shù)在以建立的若干數(shù)據(jù)庫的基礎(chǔ)上開發(fā)全局應(yīng)用，對原有的局部數(shù)據(jù)庫系統(tǒng)作某些改動，形成一個分布式系統(tǒng)。這比重建

7、一個大型數(shù)據(jù)庫系統(tǒng)要簡單，既省時間，又省財力、物力。也可以通過增加場地數(shù)的辦法，迅速擴(kuò)充已有的分布式數(shù)據(jù)庫系統(tǒng)。九、分布式數(shù)據(jù)庫系統(tǒng)的缺點(diǎn):1.通信開銷較大，故障率高。例如，在網(wǎng)絡(luò)通信傳輸速度不高時，系統(tǒng)的響應(yīng)速度慢，與通信縣官的因素往往導(dǎo)致系統(tǒng)故障，同時系統(tǒng)本身的復(fù)雜性也容易導(dǎo)致較高的故障率。當(dāng)故障發(fā)生后系統(tǒng)恢復(fù)也比較復(fù)雜，可靠性有待提高。2.數(shù)據(jù)的存取結(jié)構(gòu)復(fù)雜。一般來說，在分布時數(shù)據(jù)庫中存取數(shù)據(jù)，比在集中時數(shù)據(jù)庫中存取數(shù)據(jù)更復(fù)雜，開銷更大。3.數(shù)據(jù)的安全性和保密性較難控制。在具有高度場地自治的分布時數(shù)據(jù)庫中，不同場地的局部數(shù)據(jù)庫管理員可以采用不同的安全措施，但是無法保證全局?jǐn)?shù)據(jù)都是安全的。

8、安全性問題式分布式系統(tǒng)固有的問題。因?yàn)榉植际较到y(tǒng)式通過通信網(wǎng)絡(luò)來實(shí)現(xiàn)分布控制的，而通信網(wǎng)絡(luò)本身卻在保護(hù)數(shù)據(jù)的安全性和保密性方面存在弱點(diǎn)，數(shù)據(jù)很容易被竊取。4.分布式數(shù)據(jù)庫的設(shè)計、場地劃分及數(shù)據(jù)在不同場地的分配比較復(fù)雜。數(shù)據(jù)的劃分及分配對系統(tǒng)的性能、響應(yīng)速度及可用性等具有極大的影響。不同場地的通信速度與局部數(shù)據(jù)庫系統(tǒng)的存取部件的存取速度相比，是非常慢的。通信系統(tǒng)有較高的延遲，在CPU上處理通信信息的代價很高。分布式數(shù)據(jù)庫系統(tǒng)中要注意解決分布式數(shù)據(jù)庫的設(shè)計、查詢處理和優(yōu)化、事務(wù)管理及并發(fā)控制和目錄管理等問題。第二章 分布式數(shù)據(jù)庫系統(tǒng)的結(jié)構(gòu)通常從三種不同的角度來描述一個系統(tǒng)的體系結(jié)構(gòu)，分別為基于層次

9、結(jié)構(gòu)、基于組件結(jié)構(gòu)和基于數(shù)據(jù)模型結(jié)構(gòu)的描述方法。基于層次結(jié)構(gòu)的描述方法是依據(jù)系統(tǒng)不同層次的功能描述系統(tǒng)的構(gòu)成?；诮M件結(jié)構(gòu)的描述方法是定義系統(tǒng)的構(gòu)成組件及組件間的關(guān)系?；跀?shù)據(jù)模式結(jié)構(gòu)的描述方法是定義不同的數(shù)據(jù)類別結(jié)構(gòu)及其相互關(guān)系，定義不同的視圖提供給相應(yīng)的組件應(yīng)用。一、分布式數(shù)據(jù)庫系統(tǒng)的物理結(jié)構(gòu)和邏輯結(jié)構(gòu)場地4網(wǎng)絡(luò)場地1場地2場地3場地m分布式數(shù)據(jù)庫的物理結(jié)構(gòu)DDBMS全局用戶LDBMS1LDBMSnDB1DBn分布式式數(shù)據(jù)庫的邏輯結(jié)構(gòu)二、DDBS 的體系結(jié)構(gòu)系統(tǒng)的體系結(jié)構(gòu)（ Architecture）指按組件、組件功能以及它們的交互作用定義系統(tǒng)的結(jié)構(gòu)(Structure）DDBS的組件結(jié)構(gòu)

10、1.應(yīng)用處理器（AP）功能：a.用戶接口：檢查用戶身份，接受用戶命令，如：SQL命令。b.語義數(shù)據(jù)控制器： 視圖管理、安全控制、語義完整性控制（全局概念模式）。這些約束定義在字典中。c.全局查詢處理器:將用戶命令翻譯成數(shù)據(jù)庫命令；生成全局查詢的分布執(zhí)行計劃；收集局部執(zhí)行結(jié)果并返回給用戶。d.全局執(zhí)行監(jiān)控器（全局事務(wù)管理器):調(diào)度協(xié)調(diào)和監(jiān)視AP和DP之間的分布執(zhí)行；保證復(fù)制數(shù)據(jù)的一致性；保證全局事務(wù)的原子性。2.DP功能a.局部查詢處理：實(shí)現(xiàn)全局命令到局部命令的轉(zhuǎn)換；訪問路徑選擇器，選擇最好的路徑執(zhí)行。b.局部恢復(fù)管理器： 維護(hù)本地數(shù)據(jù)庫一致性的故障恢復(fù)。c.運(yùn)行支持處理器（存儲管理器）：按調(diào)度

11、命令訪問數(shù)據(jù)庫；控制數(shù)據(jù)庫緩存管理器；返回局部執(zhí)行結(jié)果；保證子事務(wù)執(zhí)行的正確性。d.局部事務(wù)管理器：以局部子事務(wù)為單位調(diào)度執(zhí)行，保證子事務(wù)執(zhí)行的正確性。e.局部調(diào)度管理器：負(fù)責(zé)局部場地上的并發(fā)控制，按可串行化調(diào)度和執(zhí)行數(shù)據(jù)操作。三、模式結(jié)構(gòu)我國分布式數(shù)據(jù)庫系統(tǒng)標(biāo)準(zhǔn)草案中給定的抽象為四層的模式結(jié)構(gòu)：全局外層、全局概念層、局部概念層和局部內(nèi)層。模式與模式之間是映射關(guān)系。1.全局模式或外模式（ES）:全局外模式即全局用戶視圖，是分布式數(shù)據(jù)庫的全局用戶對分布式數(shù)據(jù)庫的最高層抽象。全局用戶使用視圖時，不必關(guān)心數(shù)據(jù)的分片和具體的物理分配細(xì)節(jié)。2.全局概念模式（GCS）: 全局概念模式即全局概念視圖，是分布

12、式 數(shù)據(jù)庫的整體抽象，包含了全部數(shù)據(jù)特性和邏輯結(jié)構(gòu)。像集中式數(shù)據(jù)庫中的概念模式一樣，是對數(shù)據(jù)庫全體的描述。全局概念模式再經(jīng)過分片模式和分配模式映射到局部模式。3.分片模式是描述全局?jǐn)?shù)據(jù)的邏輯劃分視圖。即全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)根據(jù)某種條件的劃分，將全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)劃分為局部數(shù)據(jù)邏輯結(jié)構(gòu)。每一個邏輯劃分成一個分片。在關(guān)系數(shù)據(jù)庫中，一個關(guān)系中的一個子關(guān)系稱該關(guān)系的一個片段。4.分配模式是描述局部數(shù)據(jù)邏輯的局部物理結(jié)構(gòu)，即劃分后的分片的物理分配視圖。5.局部概念視圖（LCS）：局部概念模式為局部概念視圖，是全局概念模式的子集。局部概念模式用于描述局部場地上的局部數(shù)據(jù)邏輯結(jié)構(gòu)。當(dāng)全局?jǐn)?shù)據(jù)模型與局部數(shù)據(jù)模型不同

13、時，還涉及數(shù)據(jù)模型轉(zhuǎn)換等內(nèi)容。 6.局部內(nèi)模式定義局部物理視圖，是對物理數(shù)據(jù)庫的描述，類似集中數(shù)據(jù)庫的內(nèi)層。7.分布式數(shù)據(jù)庫的四層結(jié)構(gòu)及模式定義描述了分布式數(shù)據(jù)庫是一組用網(wǎng)絡(luò)聯(lián)結(jié)的局部數(shù)據(jù)庫的邏輯集合。它將數(shù)據(jù)庫分為全局?jǐn)?shù)據(jù)庫和局部數(shù)據(jù)庫。全局?jǐn)?shù)據(jù)庫到局部數(shù)據(jù)庫由映射（1：N）模式描述。全局?jǐn)?shù)據(jù)庫是虛擬的，由全局概念層描述。局部數(shù)據(jù)庫是全局?jǐn)?shù)據(jù)庫的內(nèi)層，由局部概念層和局部內(nèi)層描述。全局用戶只關(guān)心全局外層定義的數(shù)據(jù)庫用戶視圖，其內(nèi)部數(shù)據(jù)模型的轉(zhuǎn)換、場地分配節(jié)等由系統(tǒng)自動實(shí)現(xiàn)。四、 DDB 和 數(shù)據(jù)庫集成系統(tǒng)通常，分布式數(shù)據(jù)庫系統(tǒng)是自上而下（top-down）地設(shè)計數(shù)據(jù)庫，可靈活地進(jìn)行分片和分配設(shè)

14、計。用戶可得益于其“集中控制”和數(shù)據(jù)庫系統(tǒng)具有的數(shù)據(jù)處理能力。但分布式數(shù)據(jù)庫系統(tǒng)具有數(shù)據(jù)庫組件數(shù)量的限制，通常不多于數(shù)十個數(shù)據(jù)庫組件。數(shù)據(jù)集成系統(tǒng)通過約束數(shù)據(jù)管理能力（只支持只讀），可將數(shù)據(jù)庫組件數(shù)量擴(kuò)展到數(shù)百個。在數(shù)據(jù)集成系統(tǒng)中，通常數(shù)據(jù)和數(shù)據(jù)庫已存在，是遵循自下而上（bottom-up）地集成各局部場地上的數(shù)據(jù)。 多數(shù)據(jù)庫系統(tǒng)（MDB）MDBS 是在己經(jīng)存在的數(shù)據(jù)庫系統(tǒng) (稱為局部數(shù)據(jù)庫系統(tǒng):LDBs) 之上為用戶提供一個統(tǒng)一的存取數(shù)據(jù)的環(huán)境。 P2P數(shù)據(jù)庫系統(tǒng)(P2PDBS)對等型 模型(又稱P2P 模型)是一種新型的體系結(jié)構(gòu)模型，面向大范圍的多數(shù)據(jù)資源點(diǎn)的松散耦合。特點(diǎn)：a.每個點(diǎn)均可

15、貢獻(xiàn)數(shù)據(jù)，系統(tǒng)資源具有豐富性、多樣性；b.可直接訪問數(shù)據(jù)源中的數(shù)據(jù)資源，即時得到最新鮮的數(shù)據(jù)，不同于如數(shù)據(jù)倉庫等集中的數(shù)據(jù)資源倉；c.采用自組織原則，具有健壯性；d.每個點(diǎn)可隨時加入和退出，系統(tǒng)具有分散性、可擴(kuò)展性；e.以Web上的資源為Peer點(diǎn)，系統(tǒng)部署簡單，不需要復(fù)雜的框架部署實(shí)現(xiàn)。五、分布式數(shù)據(jù)庫系統(tǒng)分類 分布式數(shù)據(jù)庫系統(tǒng)的分類很多。為全面、系統(tǒng)地對分布式數(shù)據(jù)庫系統(tǒng)進(jìn)行分類，采用分布式數(shù)據(jù)庫的三個特性（分布性、異構(gòu)性、自治性）組成的三維空間圖來描述分布式數(shù)據(jù)庫的類型。 三個基本特性：1.分布性是指系統(tǒng)的各組成單元是否位于同一場地上。 分布式數(shù)據(jù)庫系統(tǒng)是物理上分散、邏輯上統(tǒng)一的系統(tǒng)，即具

16、有分布性。而集中式數(shù)據(jù)庫系統(tǒng)集中在一個場地上，所以不具有分布性。2.異構(gòu)性是指系統(tǒng)的各組成單元是否相同，不同為異構(gòu)，相同為同構(gòu)。異構(gòu)主要:a.數(shù)據(jù)異構(gòu)性：指數(shù)據(jù)在格式上、語法和語義上存在不同。b.數(shù)據(jù)系統(tǒng)異構(gòu)性：指各個場地上的局部數(shù)據(jù)庫系統(tǒng)是否相同。如：均采用ORACLE數(shù)據(jù)庫系統(tǒng)的同構(gòu)數(shù)據(jù)系統(tǒng)?；蚰承﹫龅夭捎肧YBASE數(shù)據(jù)庫系統(tǒng)，某些場地采用INFORMIX系統(tǒng)的異構(gòu)數(shù)據(jù)庫系統(tǒng)。c.平臺異構(gòu)性：指計算機(jī)系統(tǒng)是否相同。如：均為微機(jī)系統(tǒng)組成的平臺同構(gòu)系統(tǒng)或由VAX或ALPHA系統(tǒng)等異構(gòu)平臺組成的系統(tǒng)。3.自治性是指每個場地的獨(dú)立自主能力。自治性通常由設(shè)計自治性、通訊自治性和執(zhí)行自治性三方面來描

17、述。根據(jù)系統(tǒng)的自治性，可分為集中式系統(tǒng)、聯(lián)邦式系統(tǒng)（Federated DB）和多數(shù)據(jù)庫系統(tǒng)（Multi DB）。a.集中式系統(tǒng)即為傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)。b.聯(lián)邦式系統(tǒng)：實(shí)現(xiàn)需要交互的所有數(shù)據(jù)庫對之間的一對一連接。 c.多數(shù)據(jù)庫系統(tǒng)：是指若干相關(guān)數(shù)據(jù)庫的集合。各個數(shù)據(jù)庫可以存在同一場地，也可分布多個場地。對多數(shù)據(jù)庫系統(tǒng)進(jìn)行管理的軟件稱多數(shù)據(jù)庫管理系統(tǒng)，多數(shù)據(jù)庫管理系統(tǒng)是對一組自治的數(shù)據(jù)庫進(jìn)行管理，并提供透明訪問。第三章 分布式數(shù)據(jù)庫設(shè)計在系統(tǒng)設(shè)計中，最基本問題就是分布式數(shù)據(jù)庫的分布問題，即如何對分布式數(shù)據(jù)庫進(jìn)行邏輯劃分和實(shí)際物理分配。數(shù)據(jù)的邏輯劃分稱數(shù)據(jù)分片。一、 兩種設(shè)計策略分布式數(shù)據(jù)庫系統(tǒng)設(shè)計

18、的基本策略：從頂向下（Top_Down）的設(shè)計處理或者從下向上（Bottom-UP）的設(shè)計處理。Top_Down: 適于新設(shè)計一個數(shù)據(jù)庫系統(tǒng)。 （designed from scratch）Bottom-UP: 已存在許多數(shù)據(jù)庫系統(tǒng)，并將它們集成為一個數(shù)據(jù)庫。典型的數(shù)據(jù)集成的研究。二、分布式數(shù)據(jù)庫的設(shè)計目標(biāo)1.分布式數(shù)據(jù)庫的本地性或近地性2.控制數(shù)據(jù)的適當(dāng)冗余3.工作負(fù)荷分布4.存儲的能力和費(fèi)用 三、數(shù)據(jù)劃分原則及分片方法分片操作原則:數(shù)據(jù)劃分的基本思路：首先按DDB 外部特征劃分?jǐn)?shù)據(jù)，然后根據(jù)DDB 的內(nèi)部特征，提出應(yīng)遵守的基本原則以檢驗(yàn)數(shù)據(jù)劃分的正確性。外部特征是指構(gòu)成DDB 的屬性群集特

19、性，包括屬性值集和數(shù)據(jù)項(xiàng)集等。內(nèi)部特征是指DDB 的組成性質(zhì)?；驹瓌t：當(dāng)對DDB 劃分后，仍應(yīng)保持DDB 原有的特質(zhì)，所以劃分后的各邏輯關(guān)系之間應(yīng)遵守下列原則：完整性原則、重構(gòu)性原則、不相交原則分片操作水平分片：水平分片是將關(guān)系按行橫向以某些條件劃分成元組的子集，（即：滿足條件的記錄的集合）每個子集含有一定的邏輯意義，稱邏輯片段。水平分片實(shí)際上是關(guān)系的選擇操作。即屬性=“值”的具體條件的子關(guān)系Ri，因此片段可用q(R)表示。垂直分片:垂直分片是將關(guān)系按列縱向以屬性組劃分成若干片段。在垂直分片時，為了保證片段的重構(gòu)性，應(yīng)將“鍵屬性”屬于各個片段中（放松的不相交性）。關(guān)系的垂直分片實(shí)際上是對指定

20、屬性集上的投影操作。所以，R 關(guān)系的垂直分片片段是 R 的部分屬性組合子關(guān)系 Ri，可用Ai(R)表示，其中 KAi?；旌戏制?混合分片是水平分片和垂直分片的內(nèi)部混合。混合分片是水平分片和垂直分片的混合操作，即對關(guān)系的選擇和投影。當(dāng)要重構(gòu)混合分片的各片段，可按相應(yīng)次序做合并（UNION）操作和聯(lián)接（JOIN）操作。 分片的基本原則:完備性原則：要把所有的數(shù)據(jù)映射到各個片斷中可重構(gòu)原則：關(guān)系分片后的各個片斷可重構(gòu)整個關(guān)系不相交原則：關(guān)系分片后的各個片斷不能重疊第四章 分布式查詢處理和優(yōu)化一、分布式環(huán)境下查詢分為三種類型 ：局部查詢：查詢本站點(diǎn)上存放的數(shù)據(jù)遠(yuǎn)程查詢：查詢在網(wǎng)絡(luò)上的另一個站點(diǎn)上存放的

21、數(shù)據(jù)全局查詢：查詢涉及多個站點(diǎn)上存放的數(shù)據(jù)二、 查詢優(yōu)化的目標(biāo) 集中式查詢優(yōu)化目的：為每個用戶查詢尋求總代價（QC）最小的執(zhí)行策略總代價QC = I/O代價+CPU代價總代價最小意味著使查詢的響應(yīng)時間最短三、優(yōu)化內(nèi)容優(yōu)化內(nèi)容體現(xiàn)如下幾點(diǎn)：1.執(zhí)行運(yùn)算的次序。2.執(zhí)行每種運(yùn)算的方法。如上例，不同方法代價不同。3.所訪問的副本場地。如：選擇就近的場地，節(jié)約傳輸代價。4.執(zhí)行運(yùn)算的場地的選擇。使總的傳輸代價或總代價最低。綜合考慮，確定出一種執(zhí)行代價最小的查詢執(zhí)行策略。四、影響查詢處理效率的因素有：網(wǎng)絡(luò)傳輸代價（數(shù)據(jù)量和延遲等）、局部I/O代價及CPU使用情況代價等，但主要由網(wǎng)絡(luò)通信代價和局部I/O代

22、價來衡量。不同的分布式數(shù)據(jù)庫系統(tǒng)可能對評估查詢處理的傳輸代價和I/O代價的側(cè)重不同。為提高查詢的效率，在查詢處理過程中還要進(jìn)行優(yōu)化處理。查詢優(yōu)化就是確定出一種執(zhí)行代價最小的查詢執(zhí)行策略或?qū)ふ蚁鄬^優(yōu)的操作執(zhí)行步驟。一般可采用多級優(yōu)化。本章介紹全局查詢的處理與優(yōu)化。五、查詢處理層次 全局查詢優(yōu)化（Global Query Optimization）1.找接近于最優(yōu)的執(zhí)行策略；2.找片段查詢中最佳的操作順序，包括通信操作。3.需要實(shí)時定義代價函數(shù)。4.局部查詢優(yōu)化（Local Query Optimization） 集中的系統(tǒng)算法.1.INGRES 動態(tài)優(yōu)化（ dynamic optimizati

23、on）2.System R 基于窮舉法的靜態(tài)優(yōu)化（static optimization based on exhaustive search）第五章 分布式查詢的存取優(yōu)化一、分布執(zhí)行過程實(shí)際上就是從查詢場地發(fā)出查詢命令、從數(shù)據(jù)源獲取數(shù)據(jù)、確定最佳的執(zhí)行場地和返回執(zhí)行結(jié)果的過程。 查詢場地：指發(fā)出查詢命令和存儲最終查詢結(jié)果的場地。查詢場地也稱最終結(jié)果文件。源數(shù)據(jù)場地：指查詢命令需要訪問的數(shù)據(jù)副本所在的場地，可能涉及到一個或一個以上的場地。源數(shù)據(jù)場地也稱源數(shù)據(jù)文件。執(zhí)行場地：指查詢操作執(zhí)行所在的場地。執(zhí)行場地可以和查詢場地或源數(shù)據(jù)場地處于同一場地，也可不處于同一場地。執(zhí)行場地也稱中間結(jié)果文件。

24、二、分布查詢的存取優(yōu)化的目標(biāo)對于遠(yuǎn)程網(wǎng)，主要考慮通信開銷，使通信代價最小。對于局域網(wǎng)，需同時考慮通信代價和本地處理代價，使綜合代價最小。 三、優(yōu)化的內(nèi)容優(yōu)化是在片段查詢的基礎(chǔ)上進(jìn)行的實(shí)際物理副本查詢操作的優(yōu)化。具體如下：輸入：片段查詢表達(dá)式輸出：分布執(zhí)行計劃內(nèi)容：1.確定片段查詢需訪問的物理副本。通常：a.本場地上的物理副本優(yōu)先；b.若二元運(yùn)算存在盡量選擇本場地上的二元運(yùn)算；c.數(shù)據(jù)最小的物理關(guān)系應(yīng)被優(yōu)先選中；d.網(wǎng)絡(luò)通信代價小的應(yīng)優(yōu)先選中2.確定片段查詢表達(dá)式操作執(zhí)行的最優(yōu)順序。包括從葉到根的執(zhí)行和同一層葉子上表達(dá)式執(zhí)行的先后，特別是對查詢樹上的并操作和聯(lián)接操作的執(zhí)行次序的確定，其代價差別很

25、大。3.選擇執(zhí)行每個操作的方法。如：盡量將同一場地上的、同一物理副本的全部操作組合在一起統(tǒng)一考慮完成。 四、查詢代價模型主要指傳輸代價（Ccom）、I/O代價（CIO）和CPU代價（Ccpu）Total cost = Ccom+CIO+Ccpu傳輸代價費(fèi)用和延遲。其中費(fèi)用起決定作用。傳輸費(fèi)用是指使通信中的整個傳輸開銷，即傳輸?shù)臄?shù)據(jù)量。模型為：CCOM（X）=C0+C1*X其中：C0：場地間傳輸數(shù)據(jù)的啟動所需的固定費(fèi)用（啟動一次），簡稱啟動代價； C1：網(wǎng)絡(luò)單位傳輸數(shù)據(jù)費(fèi)用，簡稱單位傳輸代價； X：需傳輸?shù)臄?shù)據(jù)量。五、 半聯(lián)接優(yōu)化方法對聯(lián)接操作的優(yōu)化有兩種趨勢，一種為采用半聯(lián)接技術(shù)，減少聯(lián)接操作

26、的操作數(shù)，以降低傳輸費(fèi)用；另一種為采用全聯(lián)接技術(shù)，主要考慮局部代價。一個系統(tǒng)需根據(jù)其目標(biāo)綜合確定其優(yōu)化算法。半聯(lián)接的作用采用半聯(lián)接技術(shù)的優(yōu)化目標(biāo)是減少聯(lián)接操作的操作數(shù)，以降低傳輸費(fèi)用。六、枚舉法是基于直接聯(lián)接的實(shí)現(xiàn)方法。常見的直接連接算法主要有：1.嵌套循環(huán)連接算法(nest-loop)2.歸并排序連接算法（merge-scan）3.哈希連接算法（Hash）4.基于索引的連接算法七、集中式系統(tǒng)中的查詢優(yōu)化算法 分布式查詢優(yōu)化技術(shù)是在集中式查詢優(yōu)化技術(shù)基礎(chǔ)上的擴(kuò)展，其中增加了對通信代價的評估，主要介紹四種優(yōu)化方法，核心是： INGRES和System R 1.INGRES dynamic opt

27、imization2.System R static optimization based on exhaustive search3.考慮代價的動態(tài)規(guī)劃方法（ System R ） 4.PostgreSQL的遺傳算法 第六章 分布式事物管理一、事務(wù)的定義任何數(shù)據(jù)庫應(yīng)用最終都將轉(zhuǎn)換為一系列對數(shù)據(jù)庫進(jìn)行存取的操作系列；為了保證數(shù)據(jù)庫的正確性及操作的有效性，將數(shù)據(jù)庫應(yīng)用中全部或部分操作序列的執(zhí)行定義為事務(wù)；一個事務(wù)所包含的所有操作，要么全做，要么全不做，是一個不可分割的整體；二、事務(wù)的基本模型一個事務(wù)由三部分組成：a.開始標(biāo)識begin_transactionb.數(shù)據(jù)庫操作c.結(jié)束標(biāo)識commit

28、或abortcommit：表示提交，即成功完成事務(wù)中的所有數(shù)據(jù)庫操作，將操作結(jié)果永久化，使數(shù)據(jù)庫狀態(tài)從事務(wù)執(zhí)行前的狀態(tài)改變到事務(wù)執(zhí)行后的狀態(tài)；abort：表示廢棄，即在事務(wù)執(zhí)行過程中發(fā)生了某種故障，使得事務(wù)中的操作不能繼續(xù)執(zhí)行，系統(tǒng)需要將該事務(wù)中已完成的操作全部撤銷，使數(shù)據(jù)庫保持事務(wù)執(zhí)行前的狀態(tài)；三、事務(wù)的基本性質(zhì)原子性(atomicity)事務(wù)所包含的操作要么全做，要么全不做。由于輸入錯誤、系統(tǒng)過載、死鎖等導(dǎo)致的事務(wù)廢棄而需要進(jìn)行的事務(wù)的原子性維護(hù)，稱為事務(wù)恢復(fù)。由于系統(tǒng)崩潰（死機(jī)、掉電）而導(dǎo)致的事務(wù)廢棄或者提交結(jié)果的丟失而需要進(jìn)行的原子性維護(hù)處理，稱為故障恢復(fù)。一致性(consistenc

29、y)假如數(shù)據(jù)庫的狀態(tài)滿足所有的完整性約束，則稱該數(shù)據(jù)庫是一致的。事務(wù)的一致性，是事務(wù)執(zhí)行的結(jié)果必須是使數(shù)據(jù)庫從一個一致性狀態(tài)變化到另一個一致性狀態(tài)，而不會停留在某種不一致的中間狀態(tài)上隔離性(isolation)當(dāng)多個事務(wù)的操作交叉執(zhí)行時，若不加控制，一個事務(wù)的操作及所使用的數(shù)據(jù)可能會對其它事務(wù)造成影響。事務(wù)的隔離性是指：一個事務(wù)的執(zhí)行既不能被其它事務(wù)所干擾，同時也不能干擾其它事務(wù)。耐久性(durability)事務(wù)的耐久性體現(xiàn)在：當(dāng)一個事務(wù)提交后，系統(tǒng)保證該事務(wù)的結(jié)果不會因以后的故障而丟失。也就是說，事務(wù)一旦被提交，它對數(shù)據(jù)庫的更改將是永久性的。即使發(fā)生了故障，系統(tǒng)應(yīng)具備有效的恢復(fù)能力，將已提

30、交事務(wù)的操作結(jié)果恢復(fù)過來，即重做（REDO）處理，使這些事務(wù)的執(zhí)行結(jié)果不受任何影響。 四、事務(wù)的種類按照組成結(jié)構(gòu)的不同，可以將事務(wù)劃分為兩類：平面事務(wù)（flat）和嵌套事務(wù)(nest)。平面事務(wù)是指每個事務(wù)都與系 統(tǒng)中其它事務(wù)相分離，并獨(dú)立于其它事務(wù)。平面事務(wù)是用begin和end括起來的自治執(zhí)行方式。嵌套事務(wù)是指一個事務(wù)的執(zhí)行包括另一個事務(wù)。其中，內(nèi)部事務(wù)稱為外部事務(wù)的子事務(wù)，外部事務(wù)稱為子事務(wù)的父事務(wù)。五、分布式事務(wù)從宏觀上來看，分布式事務(wù)是由一系列分布在多個場地上執(zhí)行的數(shù)據(jù)庫操作所組成的。分布式事務(wù)：是指分布式數(shù)據(jù)庫應(yīng)用中的事務(wù)，也稱為全局事務(wù)。子事務(wù)：一個分布式事務(wù)在執(zhí)行時將被分解為若

31、干個場地上獨(dú)立執(zhí)行的操作序列，即一個分布式事務(wù)在某個場地上操作的集合。六、 進(jìn)程模型全局事務(wù)為每一個子事務(wù)在相應(yīng)的場地上創(chuàng)建一個代理者進(jìn)程（也稱局部進(jìn)程或子進(jìn)程），由代理者進(jìn)程執(zhí)行該場地上的有關(guān)操作。同時，為協(xié)調(diào)各子事務(wù)的操作，全局事務(wù)還要啟動一個協(xié)調(diào)者進(jìn)程，來進(jìn)行代理者進(jìn)程間的通訊，控制和協(xié)調(diào)各代理者進(jìn)程的操作。發(fā)出分布式事務(wù)的場地（根代理所在的場地）稱為該事務(wù)的源場地。七、服務(wù)器模型服務(wù)器模型要求在事務(wù)的每個執(zhí)行場地上創(chuàng)建一個服務(wù)器進(jìn)程，用于執(zhí)行發(fā)生在該場地上的所有子事務(wù)。每個服務(wù)器進(jìn)程可以交替地為多個事務(wù)的子事務(wù)服務(wù)。也就是說，不同全局事務(wù)中的子事務(wù)在同一個場地上共用一個服務(wù)器進(jìn)程。八、

32、分布式2PC“分布式”是指事務(wù)的所有參與者同時也都是協(xié)調(diào)者，都可以決定事務(wù)的提交和廢棄，提交過程是完全分布地完成。由事務(wù)的始發(fā)場地完成提交的初始化工作。 分布式2PC最大的特點(diǎn)是事務(wù)的提交過程只需要一個階段，即決定階段。所有場地都可以互相通信，使得各個場地均可以獲悉其它場地的當(dāng)前狀態(tài)（“準(zhǔn)備提交”或“準(zhǔn)備廢棄”），獨(dú)立地做出事務(wù)是否提交的決定。九、非阻塞分布式事務(wù)提交協(xié)議如果在兩段提交協(xié)議執(zhí)行的過程中出現(xiàn)協(xié)調(diào)者故障或網(wǎng)絡(luò)故障，那么參與者就不能及時收到協(xié)調(diào)者發(fā)出的“提交”命令，參與者處的子事務(wù)將處于等待狀態(tài)。在故障恢復(fù)前，參與者子事務(wù)所占有的系統(tǒng)資源也不能被釋放，參與者的子事務(wù)進(jìn)入了阻塞狀態(tài)。若

33、參與者一直收不到協(xié)調(diào)者的命令，則子事務(wù)將始終處于阻塞狀態(tài)而掛在相應(yīng)的執(zhí)行場地上，所占用的系統(tǒng)資源也不能被其它事務(wù)利用。全局事務(wù)的提交分為三個階段：階段一：投票表決階段階段二：準(zhǔn)備提交階段階段三：執(zhí)行階段第七章 分布式恢復(fù)管理數(shù)據(jù)庫系統(tǒng)的可恢復(fù)性和高可靠性是保證各種應(yīng)用正確而可靠地運(yùn)行所不可缺少的重要組成部分。可恢復(fù)性，提供恢復(fù)措施，把數(shù)據(jù)庫系統(tǒng)從故障狀態(tài)恢復(fù)到一個已知的正確狀態(tài)；高可靠性，盡量將崩潰后數(shù)據(jù)庫的不可用的時間減少到最低，并保證事務(wù)的原子性和耐久性。 一、故障模型故障（Fault）：系統(tǒng)單元內(nèi)部發(fā)生的錯誤或系統(tǒng)內(nèi)部設(shè)計錯誤；錯誤（Error）：系統(tǒng)單元內(nèi)出現(xiàn)了不正確的狀態(tài)，是故障的內(nèi)

34、在表現(xiàn)形式；失效（Failure）：指系統(tǒng)的外部狀態(tài)中所表現(xiàn)出來的錯誤；當(dāng)系統(tǒng)單元被組建得不合理或系統(tǒng)內(nèi)部設(shè)計存在不足時，將會引發(fā)系統(tǒng)故障，此時系統(tǒng)的內(nèi)部狀態(tài)處于錯誤的狀態(tài)，進(jìn)而使系統(tǒng)的外部環(huán)境受到影響，最終產(chǎn)生失效。二、 故障模型1.事務(wù)內(nèi)部的故障事務(wù)內(nèi)部的故障可細(xì)分為可預(yù)期的和不可預(yù)期的。2.系統(tǒng)故障系統(tǒng)故障的表現(xiàn)形式是使系統(tǒng)停止運(yùn)轉(zhuǎn)，必須經(jīng)過重啟后系統(tǒng)才能恢復(fù)正常。例如，CPU故障、系統(tǒng)死循環(huán)、緩沖區(qū)溢出、系統(tǒng)斷電等。這類故障的特點(diǎn)是：僅使正在運(yùn)行的事務(wù)受到影響，但數(shù)據(jù)庫本身沒有被破壞；內(nèi)存中的數(shù)據(jù)全部丟失。一方面，一些尚未完成的事務(wù)的結(jié)果可能已被寫入數(shù)據(jù)庫中；另一方面，一些已提交的事務(wù)

35、的結(jié)果可能還未更新到磁盤上。因此，系統(tǒng)故障發(fā)生后數(shù)據(jù)庫可能處于不一致的狀態(tài)。 3.存儲介質(zhì)故障存儲介質(zhì)故障是指存儲數(shù)據(jù)的磁盤等硬件設(shè)備發(fā)生的故障。例如，磁盤壞損、磁頭碰撞、瞬時強(qiáng)磁場干擾等均為存儲介質(zhì)故障。這類故障的特點(diǎn)是：不僅使正在運(yùn)行的所有事務(wù)受到影響，而且數(shù)據(jù)庫本身也被破壞。因此，同前兩種故障相比，存儲介質(zhì)故障是一種較嚴(yán)重的故障類型。4.通信故障前三個故障都是單場地故障、也是集中式數(shù)據(jù)庫中的故障。對于分布式數(shù)據(jù)庫而言，還要進(jìn)行各個場地的通信，因此還會產(chǎn)生通信故障。三、 恢復(fù)模型在故障恢復(fù)過程中，數(shù)據(jù)庫恢復(fù)管理器依據(jù)數(shù)據(jù)庫日志文件（log）對數(shù)據(jù)庫事務(wù)進(jìn)行恢復(fù)操作。1.日志文件的格式和內(nèi)容

36、內(nèi)容：記錄事務(wù)的執(zhí)行信息。作用：a.用來進(jìn)行數(shù)據(jù)庫的恢復(fù)； b.數(shù)據(jù)庫使用情況統(tǒng)計和分析的數(shù)據(jù)源。2.反做(undo)和重做(redo)恢復(fù)策略反做（undo）也稱撤消、回滾（rollback） ，是將一個數(shù)據(jù)項(xiàng)的值恢復(fù)到其修改之前的值，即取消一個事務(wù)所完成的操作結(jié)果。當(dāng)一個事務(wù)尚沒提交時，如果緩沖區(qū)管理器允許該事務(wù)修改過的數(shù)據(jù)寫到外存數(shù)據(jù)庫，一旦此事務(wù)出現(xiàn)故障需廢棄時，就需對被這個事務(wù)修改過的數(shù)據(jù)項(xiàng)進(jìn)行反做，即根據(jù)日志文件將其恢復(fù)到前像。反做的目的是保持?jǐn)?shù)據(jù)庫的原子性。重做（redo）也稱為前滾操作（rollforward），是將一個數(shù)據(jù)項(xiàng)的值恢復(fù)到其修改后的值，即恢復(fù)一個事務(wù)的操作結(jié)果。當(dāng)

37、一個事務(wù)提交時，如果緩沖區(qū)管理器允許該事務(wù)修改過的數(shù)據(jù)不立刻寫到外存數(shù)據(jù)庫，一旦此事務(wù)出現(xiàn)故障，需對被這個事務(wù)修改過的數(shù)據(jù)項(xiàng)進(jìn)行重做（redo），即根據(jù)日志文件將其恢復(fù)到后像。重做（redo）的目的是保持?jǐn)?shù)據(jù)庫的持久性。3.故障恢復(fù)模型 當(dāng)軟故障發(fā)生時，造成數(shù)據(jù)庫不一致狀態(tài)的原因包括：一些未完成事務(wù)對數(shù)據(jù)庫的更新已寫入外存數(shù)據(jù)庫；一些已提交事務(wù)對數(shù)據(jù)庫的更新還沒來得及寫入外存數(shù)據(jù)庫。因此，需要的恢復(fù)操作有undo和重做redo。四、硬故障的恢復(fù)模型硬故障的恢復(fù)模型硬故障的主要恢復(fù)措施是進(jìn)行數(shù)據(jù)轉(zhuǎn)儲和建立日志文件。首先，DBA要定期地將數(shù)據(jù)庫轉(zhuǎn)儲到其它磁盤上，形成一系列備份數(shù)據(jù)庫（也稱“后備副本”）。接下來，利用日志文件重新運(yùn)行轉(zhuǎn)儲以后的所有更新事務(wù)，使數(shù)據(jù)庫再進(jìn)一步地恢復(fù)到故障發(fā)生時的狀態(tài)。 五、可靠性與可用性可靠性（Reliability）：在給定環(huán)境條件下和規(guī)定的時間內(nèi)，數(shù)據(jù)庫系統(tǒng)符合其行為規(guī)范的概率。強(qiáng)調(diào)正確性?？捎眯裕ˋvailab