大連理工大學(xué)算法分析與設(shè)計(jì)2014 3章-分布式數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)2014-12-3

1徐喜榮分布式數(shù)據(jù)庫(kù)系統(tǒng)2012年11月——2013年1月徐喜榮（xirongxu@)21分布式數(shù)據(jù)庫(kù)系統(tǒng)設(shè)計(jì)的目標(biāo)

在理想情況下，分布式數(shù)據(jù)庫(kù)系統(tǒng)的用戶可不關(guān)心數(shù)據(jù)的物理分布，由系統(tǒng)負(fù)責(zé)處理在不同站點(diǎn)上的分布數(shù)據(jù)。但是數(shù)據(jù)實(shí)際分布情況會(huì)影響系統(tǒng)的總體性能：訪問(wèn)多個(gè)數(shù)據(jù)對(duì)象所需的時(shí)間和費(fèi)用，會(huì)因?yàn)檫@些數(shù)據(jù)對(duì)象是存放在同一站點(diǎn)，還是分布在多個(gè)站點(diǎn)有很大差別。分布式數(shù)據(jù)庫(kù)系統(tǒng)中最重要的目標(biāo)是盡量減少對(duì)網(wǎng)絡(luò)的利用，即盡可能減少站點(diǎn)之間的通信次數(shù)和通信量。

因此，分布式數(shù)據(jù)庫(kù)系統(tǒng)的數(shù)據(jù)庫(kù)設(shè)計(jì)者必須仔細(xì)考慮數(shù)據(jù)是否分片，片段如何復(fù)制，以及數(shù)據(jù)或片段如何分布，甚至在分布式數(shù)據(jù)庫(kù)管理系統(tǒng)支持高的分布透明性時(shí)也要如此。3

DDBS設(shè)計(jì)目標(biāo)目標(biāo)一：本地性或近地性；目標(biāo)四：存儲(chǔ)能力和費(fèi)用。目標(biāo)二：控制數(shù)據(jù)適當(dāng)冗余；目標(biāo)三：工作負(fù)荷分布；1分布式數(shù)據(jù)庫(kù)系統(tǒng)設(shè)計(jì)的目標(biāo)41分布式數(shù)據(jù)庫(kù)系統(tǒng)設(shè)計(jì)的目標(biāo)目標(biāo)一：分布式數(shù)據(jù)庫(kù)的本地性或近地性分布式數(shù)據(jù)庫(kù)設(shè)計(jì)中的一個(gè)主要原則是使數(shù)據(jù)和應(yīng)用實(shí)現(xiàn)最大程度的本地性。開發(fā)一個(gè)分布式數(shù)據(jù)庫(kù)的主要目的：通過(guò)盡可能地使數(shù)據(jù)靠近使用該數(shù)據(jù)的應(yīng)用進(jìn)行分配，從而提高處理的本地性或近地性，減少通信。在一個(gè)精心設(shè)計(jì)的分布式數(shù)據(jù)庫(kù)中，90%的數(shù)據(jù)應(yīng)當(dāng)在本地站點(diǎn)找到而只有10%的數(shù)據(jù)需要在遠(yuǎn)程站點(diǎn)上進(jìn)行訪問(wèn)。也即最有效的設(shè)計(jì)是確保數(shù)據(jù)對(duì)最大數(shù)目的應(yīng)用具有本地性。設(shè)計(jì)方法是對(duì)每種可供選擇的分片方法和片段的分配方法都統(tǒng)計(jì)出本地訪問(wèn)和遠(yuǎn)程訪問(wèn)的次數(shù)，然后從其中選擇一個(gè)最佳的方案。5目標(biāo)二：控制數(shù)據(jù)適當(dāng)冗余

1分布式數(shù)據(jù)庫(kù)系統(tǒng)設(shè)計(jì)的目標(biāo)控制數(shù)據(jù)的適當(dāng)冗余是分布式數(shù)據(jù)庫(kù)系統(tǒng)設(shè)計(jì)的又一個(gè)目標(biāo)。

在分布式數(shù)據(jù)庫(kù)系統(tǒng)中，為了提高系統(tǒng)的本地性、并發(fā)度和可靠性，需要增加數(shù)據(jù)的副本。這不僅使應(yīng)用具有高度的可用性和本地性，而且當(dāng)數(shù)據(jù)的任何一個(gè)副本不能使用時(shí)，可方便地使用在另一站點(diǎn)中的該數(shù)據(jù)的副本進(jìn)行恢復(fù)，從而提高系統(tǒng)的可靠性。6目標(biāo)三：工作負(fù)荷分布1分布式數(shù)據(jù)庫(kù)系統(tǒng)設(shè)計(jì)的目標(biāo)分布式計(jì)算機(jī)系統(tǒng)的一個(gè)重要特征是把工作負(fù)荷分布在網(wǎng)絡(luò)中的各個(gè)站點(diǎn)上。分布工作負(fù)荷的目的是充分利用每個(gè)站點(diǎn)的計(jì)算機(jī)的能力和資源以提高應(yīng)用執(zhí)行的并行程度，從而提高系統(tǒng)的性能。7

數(shù)據(jù)庫(kù)的分布會(huì)受到各站點(diǎn)的存儲(chǔ)能力的影響。在網(wǎng)絡(luò)中可以有專門用于存儲(chǔ)數(shù)據(jù)的站點(diǎn)，也可以有完全不支持大量容存儲(chǔ)的站點(diǎn)。一般數(shù)據(jù)存儲(chǔ)的費(fèi)用與CPU，I/O及傳輸?shù)馁M(fèi)用相比是不重要的，但是必須考慮各站點(diǎn)可用存儲(chǔ)空間的限制。1分布式數(shù)據(jù)庫(kù)系統(tǒng)設(shè)計(jì)的目標(biāo)目標(biāo)四：存儲(chǔ)的能力和費(fèi)用82分布式數(shù)據(jù)庫(kù)系統(tǒng)設(shè)計(jì)的內(nèi)容

分布式數(shù)據(jù)庫(kù)系統(tǒng)設(shè)計(jì)的內(nèi)容包括：分布式數(shù)據(jù)庫(kù)的設(shè)計(jì)和應(yīng)用設(shè)計(jì)。分布式數(shù)據(jù)庫(kù)的設(shè)計(jì)包括全局模式設(shè)計(jì)和每個(gè)站點(diǎn)的局部數(shù)據(jù)庫(kù)設(shè)計(jì)。其中的關(guān)鍵是數(shù)據(jù)庫(kù)的全局模式應(yīng)如何劃分，并映射到合適的站點(diǎn)上。由此產(chǎn)生了分布式數(shù)據(jù)庫(kù)設(shè)計(jì)所特有的兩個(gè)新問(wèn)題：數(shù)據(jù)的分片設(shè)計(jì)和片段的位置分配設(shè)計(jì)。分片設(shè)計(jì)研究的是全局模式分片的“邏輯準(zhǔn)則”，而片段的位置分配設(shè)計(jì)研究的是處理數(shù)據(jù)在各站點(diǎn)上的“物理布局”。在分布式數(shù)據(jù)庫(kù)設(shè)計(jì)中，為使分片設(shè)計(jì)和片段的位置分配設(shè)計(jì)得到的模式能夠高效地支持應(yīng)用，還需要知道應(yīng)用的確切要求。92分布式數(shù)據(jù)庫(kù)系統(tǒng)設(shè)計(jì)的內(nèi)容DDBS設(shè)計(jì)DDB設(shè)計(jì)應(yīng)用設(shè)計(jì)全局模式設(shè)計(jì)局部數(shù)據(jù)庫(kù)設(shè)計(jì)各個(gè)應(yīng)用的原發(fā)站點(diǎn)各個(gè)應(yīng)用在每個(gè)站點(diǎn)激活頻率各個(gè)應(yīng)用對(duì)要求訪問(wèn)數(shù)據(jù)對(duì)象的訪問(wèn)次數(shù)、類型和統(tǒng)計(jì)分布數(shù)據(jù)的分片設(shè)計(jì)和位置分配設(shè)計(jì)1.2分布式數(shù)據(jù)庫(kù)的發(fā)展重構(gòu)法：一種自頂向下的創(chuàng)建方法。根據(jù)系統(tǒng)的實(shí)現(xiàn)環(huán)境和用戶需求，按照分布式數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)思想和方法，采用統(tǒng)一觀點(diǎn)，從總體設(shè)計(jì)做起，包括各站點(diǎn)上的數(shù)據(jù)庫(kù)系統(tǒng)，重新建立一個(gè)分布式數(shù)據(jù)庫(kù)系統(tǒng)。按照統(tǒng)一的思想來(lái)考慮分布式數(shù)據(jù)庫(kù)系統(tǒng)中的各種問(wèn)題，有效地解決分布式數(shù)據(jù)庫(kù)系統(tǒng)數(shù)據(jù)一致性、完整性和可靠性?；ㄙM(fèi)的人力、物力會(huì)比較多，研制周期也比較長(zhǎng)，系統(tǒng)建設(shè)的代價(jià)會(huì)比較大。采用重構(gòu)法創(chuàng)建的分布式數(shù)據(jù)庫(kù)系統(tǒng)，通常是同構(gòu)異質(zhì)或同構(gòu)同質(zhì)DDBS。大多選擇同構(gòu)型分布式數(shù)據(jù)庫(kù)系統(tǒng)。用戶1用戶2用戶n分布式數(shù)據(jù)庫(kù)管理系統(tǒng)網(wǎng)絡(luò)3分布式數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)方法113.1分布式數(shù)據(jù)庫(kù)的發(fā)展3分布式數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)方法組合法：一種自底向上的創(chuàng)建方法，也稱集成法。利用現(xiàn)有的計(jì)算機(jī)網(wǎng)絡(luò)和獨(dú)立存在于各個(gè)站點(diǎn)上的現(xiàn)存數(shù)據(jù)庫(kù)系統(tǒng)，通過(guò)建立一個(gè)分布式協(xié)調(diào)管理系統(tǒng)，集成為一個(gè)統(tǒng)一的分布式數(shù)據(jù)庫(kù)系統(tǒng)。先剖析網(wǎng)絡(luò)功能；剖析各個(gè)站點(diǎn)上原有的數(shù)據(jù)庫(kù)系統(tǒng)；解決數(shù)據(jù)的一致性、完整性和可靠性；若各站點(diǎn)上DBMS不相同，理論和實(shí)踐難度較大。

采用組合法的分布式數(shù)據(jù)庫(kù)系統(tǒng)通常是異構(gòu)或者同構(gòu)異質(zhì)DDBS。用戶1用戶2用戶n分布式協(xié)調(diào)管理系統(tǒng)DBMS1DBMS2DBMSm網(wǎng)絡(luò)12

DDBS設(shè)計(jì)方法自頂向下方法（重構(gòu)法）：從頭開始設(shè)計(jì)分布式數(shù)據(jù)庫(kù)。設(shè)計(jì)者理解用戶的數(shù)據(jù)庫(kù)應(yīng)用要求，歷經(jīng)概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)階段，并將與計(jì)算機(jī)系統(tǒng)無(wú)關(guān)的規(guī)格說(shuō)明逐漸求精成低級(jí)的、與計(jì)算機(jī)系統(tǒng)有關(guān)的規(guī)格說(shuō)明。概念設(shè)計(jì)和邏輯設(shè)計(jì)的結(jié)果是數(shù)據(jù)庫(kù)的全局模式，包含了數(shù)據(jù)庫(kù)的所有數(shù)據(jù)元素及其使用形式。專門針對(duì)分布式數(shù)據(jù)庫(kù)的一個(gè)設(shè)計(jì)階段稱為分布設(shè)計(jì)，將全局模式映射成幾個(gè)可能交疊的子集模式，每一個(gè)子模式表示與一個(gè)站點(diǎn)有關(guān)的信息子集，然后完成每一單個(gè)數(shù)據(jù)庫(kù)的設(shè)計(jì)?；旌戏椒ǎ涸S多實(shí)際情況中，設(shè)計(jì)者一部分使用自頂向下方法，另一部分使用自底向上方法。自底向上方法（組合法）：通過(guò)聚集現(xiàn)存數(shù)據(jù)庫(kù)設(shè)計(jì)分布式數(shù)據(jù)庫(kù)。由于需要互聯(lián)一些現(xiàn)存數(shù)據(jù)庫(kù)以形成一個(gè)多數(shù)據(jù)庫(kù)系統(tǒng)，或者是由于對(duì)各站點(diǎn)已獨(dú)立完成了數(shù)據(jù)庫(kù)的概念說(shuō)明，所以各站點(diǎn)上數(shù)據(jù)庫(kù)規(guī)格說(shuō)明已是現(xiàn)存的。需綜合各站點(diǎn)的規(guī)格說(shuō)明，以便得到分布式數(shù)據(jù)庫(kù)的全局概念模式。3分布式數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)方法133.1自頂向下設(shè)計(jì)方法需求分析概念設(shè)計(jì)視圖設(shè)計(jì)分布設(shè)計(jì)物理設(shè)計(jì)觀察與監(jiān)視系統(tǒng)需求全局概念模式訪問(wèn)模式外部模式定義局部概念模式物理模式用戶輸入視圖集成用戶輸入反饋反饋?zhàn)皂斚蛳略O(shè)計(jì)過(guò)程3分布式數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)方法一、集中式數(shù)據(jù)庫(kù)設(shè)計(jì)

包括四個(gè)階段：需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)、物理設(shè)計(jì)。需求分析涉及收集用戶數(shù)據(jù)庫(kù)應(yīng)用的非結(jié)構(gòu)規(guī)格說(shuō)明，并收集在

設(shè)計(jì)數(shù)據(jù)字典中。

概念設(shè)計(jì)產(chǎn)生全局、綜合數(shù)據(jù)庫(kù)模式的一種概念規(guī)格說(shuō)明和在此

模式上執(zhí)行應(yīng)用的概念規(guī)格說(shuō)明。

邏輯設(shè)計(jì)將綜合概念模式轉(zhuǎn)換成一給定的DBMS類型(關(guān)系、網(wǎng)狀、

層次或面向?qū)ο竽Ｐ?的數(shù)據(jù)庫(kù)模式。

物理設(shè)計(jì)要遵照所選擇的特定DBMS的能力和特征進(jìn)行，并產(chǎn)生

實(shí)現(xiàn)數(shù)據(jù)庫(kù)的物理訪問(wèn)結(jié)構(gòu)的定義。3.1自頂向下設(shè)計(jì)方法3分布式數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)方法15二、分布式數(shù)據(jù)庫(kù)設(shè)計(jì)增加一個(gè)新的階段：分布設(shè)計(jì)分布設(shè)計(jì)位于邏輯設(shè)計(jì)與物理設(shè)計(jì)之間，以一個(gè)全局的、與站點(diǎn)無(wú)關(guān)的模式作為輸入，以產(chǎn)生分布式數(shù)據(jù)庫(kù)各站點(diǎn)的子模式(局部概念模式)作為結(jié)果輸出。分布設(shè)計(jì)包括：數(shù)據(jù)的分片設(shè)計(jì)和片段的位置分配設(shè)計(jì)。分片是指把一個(gè)全局對(duì)象(實(shí)體或關(guān)系)細(xì)分成若干邏輯片段的過(guò)程；分配是指把各片段映射到一個(gè)或多個(gè)站點(diǎn)的過(guò)程，片段是最合適的數(shù)據(jù)分配單位。3.1自頂向下設(shè)計(jì)方法3分布式數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)方法把現(xiàn)有數(shù)據(jù)庫(kù)集成起來(lái)構(gòu)成分布式數(shù)據(jù)庫(kù)時(shí)，可采用自底向上的方法。此方法重點(diǎn)是把將現(xiàn)有的各種不同的數(shù)據(jù)庫(kù)模式集成為全局模式。集成就是把公用數(shù)據(jù)定義合并起來(lái)，并解決對(duì)同一個(gè)數(shù)據(jù)的不同表示方法之間的沖突。把現(xiàn)有數(shù)據(jù)庫(kù)集成為一分布式數(shù)據(jù)庫(kù)時(shí)，現(xiàn)有數(shù)據(jù)庫(kù)很可能使用的是不同的DBMS，這將構(gòu)成異構(gòu)系統(tǒng)，從而增加了數(shù)據(jù)集成的復(fù)雜性。此時(shí)可以在每對(duì)不同的DBMS之間進(jìn)行一對(duì)一的翻譯，也可選擇一個(gè)公用數(shù)據(jù)模型，然后再把涉及這個(gè)DBMS的所有的不同模式都翻譯成這種唯一的表示方法。

3.2自底向上設(shè)計(jì)方法3分布式數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)方法自底向上設(shè)計(jì)方法主要問(wèn)題是構(gòu)造一個(gè)全局模式（超視圖）.把分布式數(shù)據(jù)庫(kù)中各站點(diǎn)上的數(shù)據(jù)庫(kù)模式看成是全局模式的一個(gè)視圖，則尋求全局模式的問(wèn)題可以看作是視圖綜合問(wèn)題。概括分層結(jié)構(gòu)支持視圖綜合。概括分層允許定義兩個(gè)實(shí)體之間的類型和子類型關(guān)聯(lián)，用于兩個(gè)視圖對(duì)同一實(shí)體的部分屬性相交時(shí)。視圖綜合問(wèn)題的經(jīng)典方法就是生成三個(gè)實(shí)體：

一個(gè)實(shí)體具有共同屬性（超類型），兩個(gè)實(shí)體具有不相交屬性（子類型）。在全局視圖中，共同屬性與子類型相關(guān)聯(lián)，并且對(duì)包含非相交屬性的各個(gè)視圖生成一子類型。視圖綜合次序問(wèn)題：一次把一個(gè)視圖和全局模式進(jìn)行綜合，逐步構(gòu)造起全局視圖。通常最好首先綜合最大的或最重要的視圖，然后綜合小的或者不重要的視圖。3.2自底向上設(shè)計(jì)方法3分布式數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)方法一、構(gòu)造全局模式問(wèn)題分析班機(jī)機(jī)號(hào)日期可用座位出入口座位圖延期班機(jī)機(jī)號(hào)日期可用座位機(jī)型座位圖班機(jī)班機(jī)1班機(jī)2機(jī)號(hào)日期可用座位座位圖出入口延期機(jī)型使用概括分層的兩個(gè)視圖的合并3.2自底向上設(shè)計(jì)方法3分布式數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)方法識(shí)別相似性：綜合兩個(gè)模式的第一步是識(shí)別它們的相似性，識(shí)別相似性是綜合模式的出發(fā)點(diǎn)。從先前存在的數(shù)據(jù)庫(kù)中數(shù)據(jù)的相似性可以推得匹配，相似的值集表明相交。通過(guò)比較屬性，可以識(shí)別匹配屬性域。如果在不同站點(diǎn)上有相似應(yīng)用，使用各自數(shù)據(jù)庫(kù)中的數(shù)據(jù)副本,則這兩站點(diǎn)的數(shù)據(jù)庫(kù)之間有某些相似點(diǎn)。3.2自底向上設(shè)計(jì)方法3分布式數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)方法二、識(shí)別相似性和識(shí)別沖突識(shí)別沖突：識(shí)別不同模式中相似數(shù)據(jù)的不同表示或域定義。通過(guò)在全局模式中引入差異或在源模型中做一些折中，可以解決沖突。

模式差異包括命名沖突、域差異、定標(biāo)差異和結(jié)構(gòu)差異。命名沖突：同物異名（EMP,EMPLOYEE）和異物同名。通過(guò)在全局模式中存儲(chǔ)名字對(duì)應(yīng)表就能方便地解決。域差異：檢測(cè)此問(wèn)題通過(guò)比較源數(shù)據(jù)庫(kù)或文件并注意不一致性來(lái)進(jìn)行。概括分層可以用來(lái)表示這一問(wèn)題的解。定標(biāo)差異：在具有同一數(shù)值的不同視圖中可以見到定標(biāo)差異，如計(jì)量單位不同(天、小時(shí)、分鐘、秒）。設(shè)計(jì)中如有可能，應(yīng)使用更精確的定標(biāo)來(lái)檢索數(shù)據(jù)，并使用換算公式進(jìn)行連接或輸出。結(jié)構(gòu)差異：同一對(duì)象有的用實(shí)體描述,有的用屬性描述。視圖設(shè)計(jì)中，一般通過(guò)改變一個(gè)或兩個(gè)視圖來(lái)解決結(jié)構(gòu)差異。3.2自底向上設(shè)計(jì)方法3分布式數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)方法處理操作期間的不一致數(shù)據(jù)策略（5種）對(duì)于設(shè)計(jì)時(shí)不能解決的沖突，需設(shè)計(jì)可供選擇的策略，當(dāng)執(zhí)行時(shí)檢測(cè)到不一致性時(shí)，以回答有不一致數(shù)據(jù)的查詢。這些策略包括：顯示任一不一致值，但不通知用戶。這是最直截了當(dāng)，同時(shí)也是最危險(xiǎn)的解決辦法。顯示所有不一致值，并告訴用戶不一致值信息源。在這種情況下，用戶應(yīng)能評(píng)價(jià)不一致性的原因。求不一致值的某些組合函數(shù)值，并向用戶顯示此結(jié)果?？赡苁褂玫慕M合函數(shù)包括求平均、求最小值、求最大值。使用這種技術(shù)是在不同時(shí)間內(nèi)出現(xiàn)時(shí)預(yù)期觀察值也不同的場(chǎng)合。顯示最新值。這一策略需要更新操作的時(shí)間戳。它所依據(jù)的假設(shè)是不一致性歸因于更新不及時(shí)，因此，最新的值也是最可能的值。顯示最可靠系統(tǒng)的值。這一策略所依據(jù)的假設(shè)是，設(shè)計(jì)者可以評(píng)價(jià)分布式數(shù)據(jù)庫(kù)中站點(diǎn)的可靠性。3.2自底向上設(shè)計(jì)方法3分布式數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)方法分片設(shè)計(jì)的基本目的：產(chǎn)生一個(gè)對(duì)全局?jǐn)?shù)據(jù)合適的劃分方案。使用這種方案得到的片段作為分布式數(shù)據(jù)庫(kù)中數(shù)據(jù)的分配和存儲(chǔ)單位時(shí)，不但能夠減少應(yīng)用中的操作量，而且能夠?qū)τ趹?yīng)用具有最大可能的本地性，使絕大多數(shù)應(yīng)用所使用的數(shù)據(jù)位于該應(yīng)用的原發(fā)站點(diǎn)。在數(shù)據(jù)分片設(shè)計(jì)時(shí)，是從分配的觀點(diǎn)來(lái)看，根據(jù)具有“相同性質(zhì)”的元組或?qū)傩赃M(jìn)行分組，每組就構(gòu)成一個(gè)片段。如果同一個(gè)片段的任意兩個(gè)元素具有“相同性質(zhì)”(例如訪問(wèn)頻率相同)的話，則數(shù)據(jù)分配時(shí)所用的任意一種方法都將把這兩個(gè)元素放在一起，以這種方式得到的片段將是分布式數(shù)據(jù)庫(kù)中數(shù)據(jù)合適的分配和存儲(chǔ)單位。4.1分片設(shè)計(jì)的基本目的4數(shù)據(jù)分片設(shè)計(jì)有兩種基本的數(shù)據(jù)分片方法：水平分片方法和垂直分片方法。

水平分片是對(duì)全局關(guān)系執(zhí)行“選擇”操作，把具有相同性質(zhì)的元組進(jìn)行分組，構(gòu)成若干個(gè)不相交的子集。水平分片的方法可歸為基本水平分片和導(dǎo)出水平分片兩類。

垂直分片是通過(guò)“投影”操作把它的屬性分成若干組。根據(jù)應(yīng)用以“同樣方式”(具有相同的使用頻率)訪問(wèn)的屬性來(lái)進(jìn)行分組。垂直分片的方法可歸為基本垂直分片和垂直群集兩類?；敬怪狈制辉谀硞€(gè)鍵屬性上重疊，其他屬性不可重疊；垂直群集的組在其他屬性上也可以重疊。通過(guò)交替水平分片與垂直分片，可以產(chǎn)生混合分片。4.2數(shù)據(jù)分片的基本類型和方法4數(shù)據(jù)分片設(shè)計(jì)不論哪種分片方法，必須遵守如下規(guī)則：假若有全局關(guān)系R被分片為子關(guān)系(片段)集合

R={R1,R2,…,Rn},則R滿足完整性條件：對(duì)任意x

R,RiR必有xRi

，i=1,2,…,n可重構(gòu)條件：R=∪Ri(水平分片）,

R=∞

Ri

（垂直分片）不相交條件：Ri

∩Rj=空集,i≠j,i,j=1,2,…,n

(水平分片)Ri

∩Rj=主鍵屬性,i,j=1,2,…,n(垂直分片)4.2數(shù)據(jù)分片的基本類型和方法4數(shù)據(jù)分片設(shè)計(jì)例2.1S(S#,SNAME,AGE,SEX)definefragmentS1asselect*fromswheresex=‘M’definefragmentS2asselect*fromswheresex=‘F’一、基本水平分片

以關(guān)系自身的屬性性質(zhì)為基礎(chǔ)，執(zhí)行“選擇”操作，將關(guān)系分割成若干個(gè)不相交的片段。4.3水平分片4數(shù)據(jù)分片設(shè)計(jì)限定語(yǔ)：把初級(jí)分片對(duì)片段的定義中，執(zhí)行選擇操作的條件(或稱謂詞)叫做限定語(yǔ)(qualification)。例如：sex=‘M’和sex=‘F’----是限定語(yǔ)水平分片正確性原則的三個(gè)條件可以這樣實(shí)現(xiàn)：若R={R1,R2,…,Rn},則完整性條件：各片段定義中的限定語(yǔ)集合必須是完整的，即至少是它們?cè)试S值的集合。可重構(gòu)條件：如果限定語(yǔ)集合是完整的，則通過(guò)并操作總能重構(gòu)全局關(guān)系。不相交條件：如果限定語(yǔ)之間是互斥的，它們的片段必不相交。4.3水平分片4數(shù)據(jù)分片設(shè)計(jì)對(duì)全局關(guān)系進(jìn)行水平初級(jí)分片需要確定一組不相交的、完整的限定語(yǔ)(選擇條件/謂詞)。即表征合適分片的兩個(gè)性質(zhì)是：令P={p1,p2,…,pn}是一簡(jiǎn)單謂詞集合，為保證分片的正確性，則P必須是：完整的：同一分片中的任意兩個(gè)元組被任一應(yīng)用以同樣概率訪問(wèn)。最小的：集合P中的所有謂詞與應(yīng)用密切相關(guān)。限定語(yǔ)具有完整性和最小性不是必要條件,但是對(duì)于簡(jiǎn)化分配問(wèn)題有好處。4.3水平分片4數(shù)據(jù)分片設(shè)計(jì)例2.2設(shè)全局關(guān)系EMP(E#,NAME,DEPT,JOB,SAL,TEL,…)DEPT={1,2}JOB={‘P’,‘-P’}假定應(yīng)用經(jīng)常查詢的內(nèi)容是屬于部門1且是程序員的職員。則可能有的水平分段限定：(1)P={DEPT=1}（不是完整的）(2)P={DEPT=1,JOB=‘P’}是正確且合適（完整的、最小的）這樣分片得到的四個(gè)片段：

{DEPT=1,JOB=‘P’},{DEPT=1,JOB=‘-P’}{DEPT=2,JOB=‘P’},{DEPT=2,JOB=‘-P’}

每一片段中元組被訪問(wèn)的概率是相等的，因此是完整的；每一限定語(yǔ)都與應(yīng)用密切相關(guān)，因此是最小的；限定語(yǔ)之間互斥，因此片段之間必不相交。(3)P={DEPT=1,JOB=‘P’,SAL>500}（完整的，不是最小的）因?yàn)镾AL>500與應(yīng)用無(wú)關(guān)。4.3水平分片4數(shù)據(jù)分片設(shè)計(jì)例2.3設(shè)全局關(guān)系

SC(S#,C#,GRADE)，S(S#,SNAME,AGE,SEX)

要求：將SC劃分為男生各門課成績(jī)和女生的各門成績(jī)。這不可能從SC本身的屬性性質(zhì)來(lái)執(zhí)行選擇，必須從關(guān)系S的屬性性質(zhì)或水平片段來(lái)導(dǎo)出。二、導(dǎo)出水平分片全局關(guān)系的導(dǎo)出式水平分片不是以其自身屬性性質(zhì)為基礎(chǔ)，而是從另一個(gè)關(guān)系的屬性性質(zhì)或水平片段推導(dǎo)出來(lái)的。確定一方便的導(dǎo)出式水平分片要求確定應(yīng)用所執(zhí)行的最重要的結(jié)合操作。導(dǎo)出分片可以使片段與片段間“連接”變得更容易。4.3水平分片4數(shù)據(jù)分片設(shè)計(jì)按S的屬性導(dǎo)出

DefinefragmentSC1

as（DefinefragmentSM

as）

SelectSC.S#,C#,GRADEFromSC,SWhereSC.S#=S.S#andSEX=‘M’DefinefragmentSC2

as（DefinefragmentSF

as）

SelectSC.S#,C#,GRADEFromSC,SWhereSC.S#=S.S#andSEX=‘F’如果S已經(jīng)進(jìn)行水平分片，分為SM和SF,分別為男生全體和女生全體，則按S的水平分片（SM/SF）導(dǎo)出：

DefinefragmentSC1asSelect*FromSCWhereS#in(SelectSF.S#fromSM)DefinefragmentSC2asSelect*FromSCWhereS#in(SelectSM.S#fromSF)4.3水平分片4數(shù)據(jù)分片設(shè)計(jì)全局關(guān)系R=∪Ri,i=1,2,…,n

如果屬性A∈R,必有A∈Ri,i=1,2,…,n,而且Ri∩Rj=Ap,

i≠j，Ap為R的碼，則稱{Ri|i=1,2,…,n}是關(guān)系R的一個(gè)垂直分片。如果屬性A∈R,必有A∈Ri,i=1,2,…,n,而且Ri∩Rj=(Ap,A-p),i≠j，A-p為R的一個(gè)或多個(gè)非碼屬性時(shí)，稱{Ri|i=1,2,…,n},是關(guān)系R的一個(gè)垂直群集。

垂直分片和垂直群集的目的在于使得許多重要應(yīng)用可以只訪問(wèn)一個(gè)

片段來(lái)執(zhí)行，從而使操作具有本地性。4.4垂直分片與垂直群集4數(shù)據(jù)分片設(shè)計(jì)全局關(guān)系EMP(Eno#,NAME,SAL,TEL,MAGNUM,DEPT)，其碼為Eno#。主要應(yīng)用有:

在Sa站點(diǎn)查詢

NAME,SAL,TEL;

在Sb站點(diǎn)查詢NAME,MAGNUM,DEPT.采用垂直分片:EMP1(Eno#,NAME,SAL,TEL)EMP2(Eno#,MAGNUM,DEPT)

則NAME屬性只屬于一個(gè)片段，對(duì)于上述應(yīng)用，必須進(jìn)行連接操作和非本地訪問(wèn)。采用垂直群集:EMP1(Eno#,NAME,SAL,TEL)EMP2(Eno#,NAME,MAGNUM,DEPT)

則對(duì)于上述應(yīng)用不需要執(zhí)行連接操作且可實(shí)現(xiàn)較好的本地性。4.4垂直分片與垂直群集4數(shù)據(jù)分片設(shè)計(jì)33數(shù)據(jù)分布是指分布式數(shù)據(jù)庫(kù)中的數(shù)據(jù)不是存儲(chǔ)在一個(gè)站點(diǎn)的計(jì)算機(jī)上，而是根據(jù)需要將數(shù)據(jù)劃分成若干邏輯片段，按某種策略把數(shù)據(jù)分片所得的邏輯片段分散地存儲(chǔ)在各個(gè)站點(diǎn)上。數(shù)據(jù)分布的策略有：集中式、分割式、復(fù)制式、混合式。集中式：

所有數(shù)據(jù)片段都安排在同一站點(diǎn)上。對(duì)數(shù)據(jù)的控制和管理比較容易，數(shù)據(jù)的一致性和完整性能得到保證。缺點(diǎn)是該站點(diǎn)負(fù)擔(dān)過(guò)重，系統(tǒng)對(duì)該站點(diǎn)的依賴性過(guò)多，容易出現(xiàn)瓶頸，系統(tǒng)可靠性較差。5.1數(shù)據(jù)分布策略5數(shù)據(jù)分布設(shè)計(jì)34分割式：所有數(shù)據(jù)只有一份，被分割成若干個(gè)邏輯片段，每個(gè)邏輯片段被指派在某個(gè)特定的站點(diǎn)上?？沙浞掷酶鱾€(gè)站點(diǎn)上的存儲(chǔ)設(shè)備，數(shù)據(jù)的存儲(chǔ)量大。各站點(diǎn)可自治的檢索和修改數(shù)據(jù)，發(fā)揮系統(tǒng)的并發(fā)操作能力。當(dāng)部分站點(diǎn)出現(xiàn)故障時(shí)，系統(tǒng)仍能運(yùn)行，提高了系統(tǒng)的可靠性。復(fù)制式：全局?jǐn)?shù)據(jù)有多個(gè)副本，每個(gè)站點(diǎn)都有一個(gè)完整的數(shù)據(jù)副本。系統(tǒng)可靠性高，響應(yīng)速度快，數(shù)據(jù)庫(kù)恢復(fù)也較容易。但是要保持各個(gè)站點(diǎn)上數(shù)據(jù)的同步修改，將要付出高昂的代價(jià)。5數(shù)據(jù)分布設(shè)計(jì)5.1數(shù)據(jù)分布策略35混合式：全部數(shù)據(jù)被分為若干子集，每個(gè)子集安置在不同的站點(diǎn)上，但任一站點(diǎn)都沒(méi)有保存全部的數(shù)據(jù)，并且根據(jù)數(shù)據(jù)的重要性決定各個(gè)子集的副本的多少。

這種分布策略兼顧了分割式和復(fù)制式的做法，獲得兩者優(yōu)點(diǎn)，但也包含兩者的復(fù)雜性。5數(shù)據(jù)分布設(shè)計(jì)5.1數(shù)據(jù)分布策略在滿足用戶需求的前提下,把設(shè)計(jì)好的數(shù)據(jù)片段分配到相應(yīng)的站點(diǎn)上存儲(chǔ)，盡可能提高系統(tǒng)的效益。片段分配的主要目的在于使應(yīng)用執(zhí)行的遠(yuǎn)程訪問(wèn)次數(shù)最少。例子:Emp(Eno#,Name,Location,Salary)

R1=

loc=SaEmp;R2=

loc=SbEmp

Querya:select…whereLocation=Sa... Queryb:select…whereLocation=Sb…SiteaSitebR1,R2存放在哪??5.2數(shù)據(jù)片段位置分配的方法5數(shù)據(jù)分布設(shè)計(jì)根據(jù)應(yīng)用需求確定是非冗余分配還是冗余分配。在非冗余分配中，每個(gè)片段恰好映射到一個(gè)站點(diǎn)上；在冗余分配中，每個(gè)片段映射到一個(gè)或多個(gè)站點(diǎn)上；設(shè)計(jì)者決定每一片段復(fù)制程度，復(fù)制利益隨檢索與更新間的比值而增加。分配方法非冗余分配設(shè)計(jì)方法最佳適應(yīng)法：對(duì)每一種分配都進(jìn)行估算，然后選擇最佳的站點(diǎn)。其他方法冗余分配的設(shè)計(jì)方法所有得益站點(diǎn)法附加復(fù)制法：?jiǎn)l(fā)式方法應(yīng)用需求確定非復(fù)制問(wèn)題的解；確定一組站點(diǎn)分配片段的一個(gè)副本。確定非復(fù)制問(wèn)題的解；從最有益處起逐步附加復(fù)制的副本，直到附加復(fù)制無(wú)好處為止。5.2數(shù)據(jù)片段位置分配的方法5數(shù)據(jù)分布設(shè)計(jì)

設(shè)F為單個(gè)片段，共有m個(gè)站點(diǎn)S1,…Sm,變量X1,…,Xm取值如下：

0如果片段F不在站點(diǎn)Sj上存儲(chǔ)

1如果片段F在站點(diǎn)Sj上存儲(chǔ)則總代價(jià)為：

Totalcost=ReadCost+WriteCost+StorageCost

讀代價(jià)寫代價(jià)存儲(chǔ)代價(jià)

確定Xj

的值,1jm,使總代價(jià)最小。Xj=5.2數(shù)據(jù)片段位置分配的方法—分配的簡(jiǎn)化模型5數(shù)據(jù)分布設(shè)計(jì)讀代價(jià)：

Readcost=

[

tiMINCij

]

i:

讀申請(qǐng)?jiān)凑军c(diǎn)；

ti:站點(diǎn)Si上的讀申請(qǐng)激活次數(shù)；

Cij:

從Si讀Sj站點(diǎn)上的片段F的代價(jià)。

i=1m...3ici,3ci,1ci,2ti

FFF.12j5.2數(shù)據(jù)片段位置分配的方法—分配的簡(jiǎn)化模型5數(shù)據(jù)分布設(shè)計(jì)寫代價(jià)：

Writecost=

XjuiC’iji:寫申請(qǐng)?jiān)凑军c(diǎn)

j:被更新站點(diǎn)

Xj:

0如果片段F不在站點(diǎn)Sj上存儲(chǔ) 1如果片段F在站點(diǎn)Sj上存儲(chǔ)ui:站點(diǎn)Si

上更新激活次數(shù)

C’ij:從站點(diǎn)Si更新

Sj

分段F的代價(jià)i=1j=1mm....iFFFUpdatesui5數(shù)據(jù)分布設(shè)計(jì)5.2數(shù)據(jù)片段位置分配的方法—分配的簡(jiǎn)化模型存儲(chǔ)代價(jià)：

StoreCost=

Xidi

Xi: 0如果片段F不在站點(diǎn)Si上存儲(chǔ)

1如果片段F在站點(diǎn)Si上存儲(chǔ)di: 站點(diǎn)Si

存儲(chǔ)片段F的代價(jià)i=1m5數(shù)據(jù)分布設(shè)計(jì)5.2數(shù)據(jù)片段位置分配的方法—分配的簡(jiǎn)化模型目標(biāo)函數(shù)：確定Xj

的值,1jm,使總代價(jià)最小。min

[ti

MINCij

+

Xj

ui

C’ij

]

+

Xidi

ji=1j=1i=1mmm即使最簡(jiǎn)單的公式也是NP-完全問(wèn)題。通常使用方法是盡可能將片段分配在被局部訪問(wèn)位置。5數(shù)據(jù)分布設(shè)計(jì)5.2數(shù)據(jù)片段位置分配的方法—分配的簡(jiǎn)化模型為了進(jìn)行數(shù)據(jù)片段分配的費(fèi)用和得益的估算，假定和得算，假定：

i：表示片段下標(biāo)；

j：表示站點(diǎn)下標(biāo)；

k：表示應(yīng)用下標(biāo)；

Fkj：表示應(yīng)用k在站點(diǎn)j上激活的頻率；

Rki：表示應(yīng)用k被激活一次，對(duì)片段i檢索訪問(wèn)的次數(shù)；

Uki：表示應(yīng)用k被激活一次，對(duì)片段i更新訪問(wèn)的次數(shù)；

Nki=Rki+Uki：表示應(yīng)用k被激活一次訪問(wèn)片段i的總次數(shù)；

Fkj*Nki:表示應(yīng)用k在站點(diǎn)j上對(duì)片段i的訪問(wèn)頻度；

Fkj*Rki

:表示應(yīng)用k在站點(diǎn)j上對(duì)片段i的檢索頻度；

Fkj*Uki:表示應(yīng)用k在站點(diǎn)j上對(duì)片段i的更新頻度。5數(shù)據(jù)分布設(shè)計(jì)5.3數(shù)據(jù)片段分配的費(fèi)用和得益估算最佳適應(yīng)法（非冗余分配）：

將片段Ri分配到訪問(wèn)片段Ri次數(shù)最多的那個(gè)站點(diǎn)上。在站點(diǎn)j上片段Ri

的本地訪問(wèn)次數(shù)(對(duì)全部應(yīng)用加和)是：

Bij=

kFkj*

Nki

=

kFkj*(Rki+Uki)

(1)估算：max(Bij)=Bij’則片段Ri就分配在站點(diǎn)j’上。5數(shù)據(jù)分布設(shè)計(jì)5.3數(shù)據(jù)片段分配的費(fèi)用和得益估算—水平分片情況j例：設(shè)有一個(gè)片段Ri,有兩個(gè)應(yīng)用A1,A2

,可能在三個(gè)場(chǎng)地分別設(shè)定為

Site<1>,Site<2>,Site<3>，并從應(yīng)用需求分析得到的頻度參數(shù)為：

應(yīng)用k=A1：在j=Site<1>上訪問(wèn)頻度FA1,<1>*NA1,Ri=60,

在j=Site<2>上訪問(wèn)頻度FA1,<2>*NA1,Ri=30,

在j=Site<3>上訪問(wèn)頻度FA1,<3>*NA1,Ri=20,

應(yīng)用k=A2：在j=Site<1>上訪問(wèn)頻度FA2,<1>*NA2,Ri=40,

在j=Site<2>上訪問(wèn)頻度FA2,<2>*NA2,Ri=50,

在j=Site<3>上訪問(wèn)頻度FA2,<3>*NA2,Ri=50.

則計(jì)算站點(diǎn)j上片段Ri

的本地訪問(wèn)次數(shù)Bij

如下：

當(dāng)j=Site<1>,

Bij=

k=A1,A2

Fkj*Nki=(60+40)=100,

當(dāng)j=Site<2>,

Bij=

k=A1,A2

Fkj*Nki=(30+50)=80,

當(dāng)j=Site<3>,

Bij=

k=A1,A2Fkj*Nki=(20+50)=70,

從計(jì)算結(jié)果可以得到Bij’=100，j’被選定為Site<1>,也就是說(shuō)片段Ri

應(yīng)分配在Site<1>上。5數(shù)據(jù)分布設(shè)計(jì)5.3數(shù)據(jù)片段分配的費(fèi)用和得益估算—水平分片情況所有得益站點(diǎn)法（冗余分配方法一）：將片段Ri的副本分配到所有得益站點(diǎn)j上。

所有得益站點(diǎn)：指在這些站點(diǎn)上，所有應(yīng)用的檢索訪問(wèn)費(fèi)用總比從任何一個(gè)其他站點(diǎn)發(fā)出的所有應(yīng)用對(duì)片段Ri進(jìn)行更新訪問(wèn)費(fèi)用要低。初始時(shí)使用非冗余分配，確定非冗余問(wèn)題的解。在每次迭代時(shí)，計(jì)算因增加一副本使其變成本地檢索訪問(wèn)的得益與為了維護(hù)該副本一致性所需要的附加遠(yuǎn)程修改訪問(wèn)的損失之差值。這個(gè)數(shù)字是個(gè)較大的正數(shù)時(shí)，把該片段的副本存儲(chǔ)到這個(gè)站點(diǎn)。由此可以確定一組得益站點(diǎn)。

5數(shù)據(jù)分布設(shè)計(jì)5.3數(shù)據(jù)片段分配的費(fèi)用和得益估算—水平分片情況所有得益站點(diǎn)法（冗余分配方法一）：

估算增加一個(gè)副本使其變成本地檢索訪問(wèn)的得益與為了維護(hù)該副本一致性所需要的附加遠(yuǎn)程修改訪問(wèn)的損失之差額值：

Bij=

kFkj*Rki

-c*k

j’≠j

Fkj’*Uki(2)其中：

c=更新/檢索為度量更新訪問(wèn)費(fèi)用與檢索訪問(wèn)費(fèi)用之比的一個(gè)常數(shù)，因更新有大量控制信息和局部操作，所以代價(jià)較高，一般c≥1.

通過(guò)計(jì)算，如果Bij*＞0，則站點(diǎn)j*是得益站點(diǎn)，應(yīng)把片段Ri分配在所有場(chǎng)地j*上；如果所有Bij<0，把Ri的單一副本放在Bij*為最大的場(chǎng)地上。5數(shù)據(jù)分布設(shè)計(jì)5.3數(shù)據(jù)片段分配的費(fèi)用和得益估算—水平分片情況附加復(fù)制法（冗余分配方法二）：首先確定非冗余問(wèn)題的解，然后從最有益處起逐步附加復(fù)制的副本，此過(guò)程直到“附加復(fù)制”已無(wú)明顯好處時(shí)結(jié)束。這種方法就是典型的啟發(fā)式方法。由于副本數(shù)與可用、可靠不是線性關(guān)系，意大利學(xué)者S.Ceri曾發(fā)表文章提出，可以用一函數(shù)β(Di)來(lái)估計(jì)存放一個(gè)Ri新副本在增加系統(tǒng)的可靠性和可用性方面的得益。令Di表示片段Ri的冗余度(副本個(gè)數(shù)),Fi表示Ri在每個(gè)站點(diǎn)全部都復(fù)制的得益。Di與Fi之間存在如下關(guān)系：

當(dāng)Di=1,β(1)=0；Di=2,

β(2)=Fi/2；

Di=3,β(3)=3*Fi/4等。

5數(shù)據(jù)分布設(shè)計(jì)5.3數(shù)據(jù)片段分配的費(fèi)用和得益估算—水平分片情況附加復(fù)制法（冗余分配方法二）：從給出的上述函數(shù)出發(fā)可以得到求站點(diǎn)j上引入片段Ri新副本的得益公式：用上面公式來(lái)評(píng)估在站點(diǎn)j上Ri的新副本得益。采用這種方法隨著冗余度的增加得益逐漸減少。一般，當(dāng)一個(gè)片段只有兩三個(gè)副本時(shí)，系統(tǒng)的得益在增加；但是當(dāng)副本數(shù)再增加時(shí)，系統(tǒng)的得益就不再明顯增加。5數(shù)據(jù)分布設(shè)計(jì)5.3數(shù)據(jù)片段分配的費(fèi)用和得益估算—水平分片情況rs其他站點(diǎn)tRtRRs網(wǎng)絡(luò)A1A2AsAtA35數(shù)據(jù)分布設(shè)計(jì)5.3數(shù)據(jù)片段分配的費(fèi)用和得益估算—垂直分片情況假設(shè)把站點(diǎn)r上的關(guān)系R垂直分片成兩個(gè)片段Rs和Rt,并將Rs分配到s站點(diǎn)Rt分配到t站點(diǎn)，然后將應(yīng)用分組為As,

At,

A1,

A2,

A3,并估算它們的得益情況。估算各個(gè)應(yīng)用分組得益情況如下：

應(yīng)用組As：自站點(diǎn)s發(fā)出只使用Rs,因而是本地應(yīng)用，節(jié)省了一次遠(yuǎn)程訪問(wèn)，得益：

BAs=

FksNki(kAs)應(yīng)用組At：自站點(diǎn)t發(fā)出,只使用Rt,因而是本地應(yīng)用，節(jié)省了一次遠(yuǎn)程訪問(wèn)，得益：

BAt=

FktNki(kAt)5數(shù)據(jù)分布設(shè)計(jì)5.3數(shù)據(jù)片段分配的費(fèi)用和得益估算—垂直分片情況rs其他站點(diǎn)tRtRRs網(wǎng)絡(luò)A1A2AsAtA3應(yīng)用組A1:

由站點(diǎn)r發(fā)出,原先使用Rt或Rs,現(xiàn)在這些應(yīng)用需要進(jìn)行一次額外的遠(yuǎn)程訪問(wèn)，損失：

BA1=

FkrNki(kA1)應(yīng)用組A2:由站點(diǎn)r發(fā)出,原先使用R(本地訪問(wèn)),現(xiàn)在這些應(yīng)用需要進(jìn)行兩次額外的遠(yuǎn)程訪問(wèn)，損失：

BA2=

2FkrNki(kA2)應(yīng)用組A3:由不同于站點(diǎn)r,s,t的站點(diǎn)發(fā)出,它們要訪問(wèn)Rt或Rs這兩者的屬性,現(xiàn)在這些應(yīng)用需一次額外的遠(yuǎn)程訪問(wèn)，損失：

BA3=

FkjNki(kA3,

j≠r,s,t)5數(shù)據(jù)分布設(shè)計(jì)5.3數(shù)據(jù)片段分配的費(fèi)用和得益估算—垂直分片情況rs其他站點(diǎn)tRtRRs網(wǎng)絡(luò)A1A2AsAtA3這種分片和分配的得益為：

Bist=BAs+BAt-BA1-BA2-BA3

其中：BAs=FksNki(kAs)BAt=FktNki(kAt)BA1=FkrNki(kA1)BA2=2FkrNki(kA2)

BA3=FkjNki(kA3,j≠r,s,t)這個(gè)公式可以用在窮舉式“分裂”算法(exhaustive‘splitting’algorithm)中，以確定用試探站點(diǎn)s和t的全部可能組合的方法來(lái)把站點(diǎn)i的R分裂

成站點(diǎn)s的Rs和站點(diǎn)t的Rt是否方便。5數(shù)據(jù)分布設(shè)計(jì)5.3數(shù)據(jù)片段分配的費(fèi)用和得益估算—垂直分片情況把R分成兩個(gè)片段Rs和Rt,分別分配到站點(diǎn)s和站點(diǎn)t,它們具有重疊的屬性I。因此要求重新考慮應(yīng)用的分組問(wèn)題：

(1)應(yīng)用As含局限于站點(diǎn)s的本地應(yīng)用，它們或者讀取Rs的任何屬性，或者更新不在重疊部分I的Rs的屬性。

(2)應(yīng)用At類同應(yīng)用As。

(3)應(yīng)用A1含有原先局限于站點(diǎn)r本地的更新應(yīng)用，它們對(duì)I的屬性進(jìn)行更新，而現(xiàn)在它們需要同時(shí)訪問(wèn)Rs和Rt。

(4)應(yīng)用A2含有原先局限于站點(diǎn)r本地的查詢應(yīng)用，現(xiàn)在它們需要同時(shí)訪問(wèn)Rs和Rt。

(5)應(yīng)用A3含有不在站點(diǎn)r、s或t的應(yīng)用，它們對(duì)I的屬性進(jìn)行更新，而現(xiàn)在也需要同時(shí)訪問(wèn)Rs和Rt?？梢允褂蒙厦娴年P(guān)于Bist的表示公式來(lái)評(píng)價(jià)這種垂直群集方法的得益。5數(shù)據(jù)分布設(shè)計(jì)5.3數(shù)據(jù)片段分配的費(fèi)用和得益估算—垂直群集情況分布式數(shù)據(jù)庫(kù)設(shè)計(jì)階段需求分析概念設(shè)計(jì)分布要求分析設(shè)計(jì)全局邏輯設(shè)計(jì)分布設(shè)計(jì)局部邏輯設(shè)計(jì)局部物理設(shè)計(jì)位于概念設(shè)計(jì)階段之后進(jìn)行，主要工作：1.收集用戶分布要求信息2.水平分片的劃分謂詞3.每一應(yīng)用在各站點(diǎn)激活的頻率Fkj全局邏輯設(shè)計(jì)之后進(jìn)行，主要工作：1.分布要求和全局邏輯模式作為輸入2.形式為全局?jǐn)?shù)據(jù)庫(kù)模式和邏輯訪問(wèn)表3.輸出為分片模式和分配模式DATAID-D方法是自頂向下設(shè)計(jì)分布式數(shù)據(jù)庫(kù)的一個(gè)典型方法，由意大利米蘭工業(yè)大學(xué)提出，由集中式數(shù)據(jù)庫(kù)設(shè)計(jì)DATAID-1方法論的擴(kuò)充而得到。

DATAID-1方法有四個(gè)階段：需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)。擴(kuò)充的DATAID-D對(duì)其增加兩個(gè)階段：分布要求分析階段和分布設(shè)計(jì)階段。6DATAID-D方法6.1DATAID-D方法概述說(shuō)明：1.設(shè)計(jì)數(shù)據(jù)字典；2.全局?jǐn)?shù)據(jù)模式；3.全局操作模式；4.簡(jiǎn)化全局模式；5.邏輯訪問(wèn)表；6.各站點(diǎn)邏輯模式；7.各站點(diǎn)訪問(wèn)表；8.局部邏輯模式（關(guān)系或網(wǎng)狀）；9.局部物理模式（關(guān)系或網(wǎng)狀）全局邏輯設(shè)計(jì)分布設(shè)計(jì)局部邏輯設(shè)計(jì)邏輯設(shè)計(jì)需求分析概念設(shè)計(jì)分布要求分析局部物理設(shè)計(jì)187654329要求頻率表劃分表極化表6DATAID-D方法6.1DATAID-D方法概述分布要求分析用戶分布要求全局?jǐn)?shù)據(jù)概念模型全局?jǐn)?shù)據(jù)操作模式應(yīng)用頻率表實(shí)體訪問(wèn)表應(yīng)用極化表

分布要求分析的目的是收集以后用于推動(dòng)分布設(shè)計(jì)所需要的信息。這一階段的輸入：是用戶對(duì)分布的要求、全局?jǐn)?shù)據(jù)概念模型與全局?jǐn)?shù)據(jù)操作模式。建立三種類型的表作為這一階段的輸出：應(yīng)用的頻率表、實(shí)體的訪問(wèn)表和數(shù)據(jù)與應(yīng)用的極化表(polarization)。6DATAID-D方法6.2分布要求分析階段分布要求分析階段應(yīng)用頻率表：給出各站點(diǎn)j上每一個(gè)應(yīng)用k激活的次數(shù)Fkj（假設(shè)所有應(yīng)用在所有站點(diǎn)上都能執(zhí)行；當(dāng)一個(gè)應(yīng)用在一個(gè)站點(diǎn)上從不執(zhí)行時(shí)，相應(yīng)位置的頻率項(xiàng)為零）。實(shí)體訪問(wèn)表：可用于模式中各實(shí)體的潛在水平分片規(guī)則。每條分片規(guī)則指明引入水平分片的可能理由，并與在一給定站點(diǎn)訪問(wèn)一給定數(shù)據(jù)子集的一個(gè)或多個(gè)應(yīng)用有關(guān)。應(yīng)用極化表：基于定量分析方法來(lái)說(shuō)明分片如何影響著應(yīng)用處理的本地性。一個(gè)極化表指明由一個(gè)站點(diǎn)j發(fā)出一個(gè)給定應(yīng)用k訪問(wèn)一個(gè)給定片段i

的頻率Pkji。6DATAID-D方法6.2分布要求分析階段分布設(shè)計(jì)全局?jǐn)?shù)據(jù)模式實(shí)體邏輯訪問(wèn)表分布要求站點(diǎn)邏輯模式站點(diǎn)邏輯訪問(wèn)表分布設(shè)計(jì)的目的是把全局?jǐn)?shù)據(jù)模式、實(shí)體邏輯訪問(wèn)表和分布要求做為輸入，將數(shù)據(jù)分配在站點(diǎn)上。分布設(shè)計(jì)階段輸出：各站點(diǎn)的邏輯模式和站點(diǎn)邏輯訪問(wèn)表。在以后的局部邏輯設(shè)計(jì)階段和在各站點(diǎn)上獨(dú)立進(jìn)行的物理設(shè)計(jì)階段，要使用這些邏輯模式和邏輯訪問(wèn)表。6DATAID-D方法6.3分布設(shè)計(jì)階段DATAID-D的分布設(shè)計(jì)分成四個(gè)階段：分片設(shè)計(jì)階段；非冗余分配階段；冗余分配階段；局部模式的重新構(gòu)造階段。6DATAID-D方法6.3分布設(shè)計(jì)階段一、分片設(shè)計(jì)階段：分片設(shè)計(jì)對(duì)實(shí)體進(jìn)行水平分片和垂直分片，以便為以后設(shè)計(jì)階段確定可能的分配單位。要使每一個(gè)片段i是一個(gè)合適的分配單位，就必須保證由各站點(diǎn)j上執(zhí)行的各應(yīng)用k，大約以同一方式(即相同頻率)訪問(wèn)片段中的實(shí)例(元組)。存在一個(gè)閾值條件，超過(guò)這一閾值，進(jìn)一步分片行不通。分片設(shè)計(jì)主要包括邏輯判定。進(jìn)行邏輯判定時(shí)，從極化表中選擇某些謂詞，并用它們定義邏輯片段。6DATAID-D方法6.3分布設(shè)計(jì)階段二、非冗余分配階段：非冗余分配的執(zhí)行是把各片段i映射到使用最多的站點(diǎn)j上。根據(jù)頻率表與極化表，采用“最佳適應(yīng)法”，可得到從一給定站點(diǎn)j訪問(wèn)一個(gè)給定片段i次數(shù)的定量測(cè)度，從中選出該片段的定位站點(diǎn)。在該站點(diǎn)發(fā)出的所有應(yīng)用事務(wù)k上，求極化值Pkji與該片段所使用的頻率Fkj之積的和，可以得到各片段在每一站點(diǎn)上可能的使用頻率。有可能識(shí)別最頻繁訪問(wèn)該片段的站點(diǎn)，將該片段分配到這一站點(diǎn)上。令：Fkj表示應(yīng)用k使用站點(diǎn)j的頻率；

Pkji表示應(yīng)用k使用站點(diǎn)j訪問(wèn)片段i的極化值(即頻率)。于是，全部應(yīng)用k從站點(diǎn)j訪問(wèn)片段i的次數(shù)給出如下：

Nij=

kFkj*Pkji

因此，片段i被分配到站點(diǎn)j’,使得Nij’=max所有jNij

6DATAID-D方法6.3分布設(shè)計(jì)階段三、冗余分配階段：冗余分配的執(zhí)行是使用“貪婪”啟發(fā)式，可采用“所有得益站點(diǎn)法”或采用“附加復(fù)制法”。初始使用非冗余分配，在每次迭代時(shí)，計(jì)算因增加一個(gè)副本使其變成本地檢索訪問(wèn)的得益與為維護(hù)該副本的一致性所需要的附加遠(yuǎn)程修改訪問(wèn)的損失之差值。這個(gè)數(shù)字是個(gè)較大的正數(shù)時(shí)，把該片段的副本存儲(chǔ)到這些得益站點(diǎn)上，有理由說(shuō)明增加冗余度的必要性，否則就不增加。6DATAID-D方法6.3分布設(shè)計(jì)階段四、局部模式重新構(gòu)造階段：局部模式的重新構(gòu)造是重新構(gòu)造片段分配站點(diǎn)上的局部模式。這一階段也負(fù)責(zé)E-R全局模型中的聯(lián)系分配。大多數(shù)聯(lián)系是作為對(duì)應(yīng)實(shí)體標(biāo)識(shí)符間的結(jié)合實(shí)現(xiàn)的。DATAID-D方法建議把聯(lián)系放置在具有最大基數(shù)性的實(shí)體或片段的站點(diǎn)上，使得必須傳送的實(shí)體標(biāo)識(shí)符盡可能少。6DATAID-D方法6.3分布設(shè)計(jì)階段本飛機(jī)訂票系統(tǒng)維護(hù)一個(gè)分布在三個(gè)站點(diǎn)上的數(shù)據(jù)庫(kù)。在美國(guó)開業(yè)的一家公司，有三個(gè)站點(diǎn)即機(jī)場(chǎng)1、2、3.其中：站點(diǎn)1：丹佛機(jī)場(chǎng)（代碼CO）；站點(diǎn)2：紐約機(jī)場(chǎng)（代碼NY）；站點(diǎn)3：亞特蘭大機(jī)場(chǎng)（代碼GA）；數(shù)據(jù)庫(kù)存儲(chǔ)數(shù)據(jù)內(nèi)容如下：機(jī)場(chǎng)有關(guān)規(guī)程；班機(jī)調(diào)度及班機(jī)可用情況；旅客訂票情況；訂票系統(tǒng)共有三個(gè)應(yīng)用：訂票應(yīng)用；登記應(yīng)用；起飛應(yīng)用。7實(shí)例研究：飛機(jī)訂票系統(tǒng)7.1實(shí)例研究簡(jiǎn)述班機(jī)訂票從到機(jī)場(chǎng)登記旅客到達(dá)時(shí)間機(jī)號(hào)日期可用座位起飛時(shí)間符號(hào)城市進(jìn)入口座位圖延期區(qū)域安全規(guī)則種類座位號(hào)檢查行李名字電話權(quán)力7實(shí)例研究：飛機(jī)訂票系統(tǒng)7.1實(shí)例研究簡(jiǎn)述-飛機(jī)訂票系統(tǒng)數(shù)據(jù)庫(kù)的全局?jǐn)?shù)據(jù)模式種類[w]電話[w]240機(jī)場(chǎng)320000班機(jī)日期[k]起飛時(shí)間[k]符號(hào)[k]從可用座位[o、w]到到達(dá)時(shí)間[k]名字[w]1100000旅客訂票

每當(dāng)一新的旅客想預(yù)定一個(gè)班機(jī)的機(jī)票時(shí)，訂票應(yīng)用就被激活。1.實(shí)體左下角和右下角的數(shù)字表示：示例總數(shù)和應(yīng)用選擇的平均示例數(shù)。2.訪問(wèn)數(shù)據(jù)庫(kù)中①起飛與到達(dá)機(jī)場(chǎng);②起飛與到達(dá)時(shí)間;③班機(jī)日期.

k表示關(guān)鍵詞。3.確定班機(jī)后建立旅客的一個(gè)新的示例及聯(lián)系“訂票”的一個(gè)示例，把用戶的名字、電話和種類（對(duì)應(yīng)于票價(jià)）的數(shù)據(jù)寫入數(shù)據(jù)庫(kù)。O表示輸出，w表示寫入。7實(shí)例研究：飛機(jī)訂票系統(tǒng)7.1實(shí)例研究簡(jiǎn)述-飛機(jī)訂票數(shù)據(jù)庫(kù)的訂票應(yīng)用全局操作模式1100000旅客120000班機(jī)機(jī)號(hào)[k]日期[k]座位圖[o、w]座位號(hào)[w]檢查行李[w]訂票登記種類[o]名字[k]凡旅客實(shí)際登機(jī)時(shí)，先執(zhí)行登記任務(wù)，激活登記應(yīng)用。根據(jù)數(shù)據(jù)庫(kù)中的①旅客名字，②班機(jī)號(hào)，③班機(jī)日期，查明有關(guān)旅客和班機(jī)的示例（“k”屬性），然后顯示檢索“種類”信息（“o”）。根據(jù)“種類”信息和班機(jī)座位圖，將一個(gè)座位號(hào)分配給旅客，并寫入座位圖和座位號(hào)屬性，以及旅客的檢查行李號(hào)（即托運(yùn)行李的票據(jù)號(hào)）。7實(shí)例研究：飛機(jī)訂票系統(tǒng)7.1實(shí)例研究簡(jiǎn)述-飛機(jī)訂票數(shù)據(jù)庫(kù)的登記應(yīng)用全局操作模式140機(jī)場(chǎng)3020000班機(jī)30

40機(jī)場(chǎng)日期[k]符號(hào)[k]起飛時(shí)間[k,o]班機(jī)號(hào)[o]從到出入口[o]延期[o]城市[o]符號(hào)[o]到達(dá)時(shí)間[k,o]從機(jī)場(chǎng)起飛時(shí)的應(yīng)用，產(chǎn)生描述即將離開機(jī)場(chǎng)的30架班機(jī)的起飛信息的報(bào)告并顯示在TV監(jiān)視器上。激活起飛應(yīng)用。1.根據(jù)數(shù)據(jù)庫(kù)中①機(jī)場(chǎng)符號(hào);②當(dāng)前日期;③起飛時(shí)間;④到達(dá)時(shí)間,

查明①班機(jī)號(hào)、②起飛時(shí)間、③出入口、④延期、⑤目的地機(jī)場(chǎng)符號(hào)、⑥目的地城市，然后顯示在TV監(jiān)視器。7實(shí)例研究：飛機(jī)訂票系統(tǒng)7.1實(shí)例研究簡(jiǎn)述-飛機(jī)訂票數(shù)據(jù)庫(kù)的起飛應(yīng)用全局操作模式屬性操作a（訂票）b（登記）c（起飛）班機(jī)號(hào)ko日期kkk座位圖o/w進(jìn)入口o延期o可用座位o/w表2.1(1)實(shí)體訪問(wèn)表：班機(jī)對(duì)每個(gè)實(shí)體，需估算應(yīng)用的定量數(shù)據(jù)，建立起邏輯訪問(wèn)表。表中的列對(duì)應(yīng)于操作，行對(duì)應(yīng)于實(shí)體屬性，矩陣元素表示在對(duì)象上所執(zhí)行的動(dòng)作類型(“o：表示輸出”，“w：表示寫入”，“k：表示關(guān)鍵詞”)。7實(shí)例研究：飛機(jī)訂票系統(tǒng)7.1實(shí)例研究簡(jiǎn)述-邏輯訪問(wèn)表:班機(jī)屬性操作a（訂票）b（登記）c（起飛）符號(hào)kk/o城市o權(quán)力區(qū)域安全規(guī)則表2.1(2)實(shí)體訪問(wèn)表：機(jī)場(chǎng)7實(shí)例研究：飛機(jī)訂票系統(tǒng)7.1實(shí)例研究簡(jiǎn)述-邏輯訪問(wèn)表:機(jī)場(chǎng)屬性操作a（訂票）b（登記）c（起飛）名字wk電話w表2.1(3)實(shí)體訪問(wèn)表：旅客7實(shí)例研究：飛機(jī)訂票系統(tǒng)7.1實(shí)例研究簡(jiǎn)述-邏輯訪問(wèn)表:旅客屬性操作a（訂票）b（登記）c（起飛）起飛時(shí)間kk/o表2.1(4)聯(lián)系訪問(wèn)表：從7實(shí)例研究：飛機(jī)訂票系統(tǒng)7.1實(shí)例研究簡(jiǎn)述-邏輯訪問(wèn)表:從屬性操作a（訂票）b（登記）c（起飛）到達(dá)時(shí)間kk/o表2.1(5)聯(lián)系訪問(wèn)表：到7實(shí)例研究：飛機(jī)訂票系統(tǒng)7.1實(shí)例研究簡(jiǎn)述-邏輯訪問(wèn)表:到屬性操作a（訂票）b（登記）c（起飛）種類wo表2.1(6)聯(lián)系訪問(wèn)表：訂票7實(shí)例研究：飛機(jī)訂票系統(tǒng)7.1實(shí)例研究簡(jiǎn)述-邏輯訪問(wèn)表:訂票屬性操作a（訂票）b（登記）c（起飛）座位號(hào)w檢查行李w表2.1(7)聯(lián)系訪問(wèn)表：登記7實(shí)例研究：飛機(jī)訂票系統(tǒng)7.1實(shí)例研究簡(jiǎn)述-邏輯訪問(wèn)表:登記

應(yīng)用頻率表給出各站點(diǎn)j上每一個(gè)應(yīng)用k激活的次數(shù)Fkj。下面頻率表中說(shuō)明了在站點(diǎn)1：丹佛(CO),站點(diǎn)2：紐約(NY)和站點(diǎn)3：亞特蘭大(GA)上全局操作模式描述的三個(gè)應(yīng)用a,b,c(即應(yīng)用a：訂票、應(yīng)用b：登記、應(yīng)用c：起飛)的頻率。7實(shí)例研究：飛機(jī)訂票系統(tǒng)7.2飛機(jī)訂票系統(tǒng)中的分布要求分析

基本劃分表中給出實(shí)體機(jī)場(chǎng)和實(shí)體旅客的基本劃分表。

1.將機(jī)場(chǎng)的區(qū)域?qū)傩赃x作為機(jī)場(chǎng)實(shí)體的劃分準(zhǔn)則；

2.將旅客電話號(hào)碼前三位(區(qū)域碼)作為旅客實(shí)體的劃分屬性；

3.謂詞選擇性表示按照該準(zhǔn)則劃分各類元組所占的百分?jǐn)?shù)。7實(shí)例研究：飛機(jī)訂票系統(tǒng)7.2飛機(jī)訂票系統(tǒng)中的分布要求分析1.兩種方法導(dǎo)出劃分班機(jī)實(shí)體：應(yīng)用不同的聯(lián)系“從”(起飛機(jī)場(chǎng))或“到”(到達(dá)機(jī)場(chǎng))和基于已把機(jī)場(chǎng)劃分成區(qū)域來(lái)劃分班機(jī)實(shí)體。使用兩個(gè)不同聯(lián)系于同一基本劃分，產(chǎn)生兩種不同導(dǎo)出劃分，如下表前兩行。2.下表最后兩行給出了導(dǎo)出劃分旅客實(shí)體的兩個(gè)方法：依據(jù)聯(lián)系訂票和班機(jī)，按班機(jī)起飛區(qū)域或第一訂票地點(diǎn)劃分。在這種情況下，導(dǎo)出機(jī)制分兩步，因?yàn)樗鼜臋C(jī)場(chǎng)作用到班機(jī)，然后從班機(jī)作用到旅客。前一種情形，依據(jù)他們第一次訂票的班機(jī)的地點(diǎn)來(lái)劃分旅客；后一情形中，依據(jù)他們各次的訂票的班機(jī)起飛區(qū)域來(lái)劃分旅客。7實(shí)例研究：飛機(jī)訂票系統(tǒng)7.2飛機(jī)訂票系統(tǒng)中的分布要求分析

導(dǎo)出劃分表的注釋表說(shuō)明了七種可能情形：旅客可能預(yù)定只離開一個(gè)區(qū)域(A,B,C)的班機(jī)，或離開兩個(gè)區(qū)域(AB,BC,AC)的班機(jī)，或離開所有區(qū)域(ABC)的班機(jī)。由于訂票是一種多對(duì)多關(guān)系，所以需要以上七種情況(考慮往返機(jī)票)。7實(shí)例研究：飛機(jī)訂票系統(tǒng)7.2飛機(jī)訂票系統(tǒng)中的分布要求分析極化表a訂票b登記c起飛1丹佛2紐約3亞特123123按區(qū)域劃分機(jī)場(chǎng)P180×100P21075×100P31080×100按出發(fā)機(jī)場(chǎng)劃分航班P17010080P27510080P37010080...……………………

一個(gè)極化值表指明由一個(gè)站點(diǎn)j發(fā)出的一個(gè)給定應(yīng)用k訪問(wèn)一個(gè)給定片段i的頻率Pkji。下表中的列關(guān)系到每一站點(diǎn)上應(yīng)用的激活信息，表中行關(guān)系到劃分謂詞。極化表中的第一個(gè)子矩陣，與訂票應(yīng)用有關(guān)聯(lián)且使用按區(qū)域劃分機(jī)場(chǎng)實(shí)體(P1代表區(qū)域1,P2代表區(qū)域2,P3代表區(qū)域3)。此子矩陣表明，如果選定按區(qū)域劃分機(jī)場(chǎng)，那么在區(qū)域1發(fā)出的關(guān)于訂票查詢應(yīng)用有80%的概率是關(guān)系到區(qū)域1的機(jī)場(chǎng)。對(duì)第1列中的其他兩個(gè)位置，假定其余20%訪問(wèn)是均勻分配的各占10%.7實(shí)例研究：飛機(jī)訂票系統(tǒng)飛機(jī)訂票系統(tǒng)中的分布設(shè)計(jì)分四步：對(duì)每一個(gè)實(shí)體選擇分片原則；確定非冗余分配；在非冗余分配上引入冗余；在每一站點(diǎn)上重新構(gòu)造局部模式。7實(shí)例研究：飛機(jī)訂票系統(tǒng)7.3飛機(jī)訂票系統(tǒng)中的分布設(shè)計(jì)所有實(shí)體都有水平分片：機(jī)場(chǎng)實(shí)體：基于區(qū)域的水平分段：片段：機(jī)場(chǎng)1，機(jī)場(chǎng)2，機(jī)場(chǎng)3班機(jī)實(shí)體：基于起飛機(jī)場(chǎng)的導(dǎo)出水平分段：