大連理工大學算法分析與設計2014 3章-分布式數據庫系統(tǒng)的設計2014-12-3

1徐喜榮分布式數據庫系統(tǒng)2012年11月——2013年1月徐喜榮（xirongxu@)21分布式數據庫系統(tǒng)設計的目標

在理想情況下，分布式數據庫系統(tǒng)的用戶可不關心數據的物理分布，由系統(tǒng)負責處理在不同站點上的分布數據。但是數據實際分布情況會影響系統(tǒng)的總體性能：訪問多個數據對象所需的時間和費用，會因為這些數據對象是存放在同一站點，還是分布在多個站點有很大差別。分布式數據庫系統(tǒng)中最重要的目標是盡量減少對網絡的利用，即盡可能減少站點之間的通信次數和通信量。

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

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

1分布式數據庫系統(tǒng)設計的目標控制數據的適當冗余是分布式數據庫系統(tǒng)設計的又一個目標。

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

數據庫的分布會受到各站點的存儲能力的影響。在網絡中可以有專門用于存儲數據的站點，也可以有完全不支持大量容存儲的站點。一般數據存儲的費用與CPU，I/O及傳輸的費用相比是不重要的，但是必須考慮各站點可用存儲空間的限制。1分布式數據庫系統(tǒng)設計的目標目標四：存儲的能力和費用82分布式數據庫系統(tǒng)設計的內容

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

采用組合法的分布式數據庫系統(tǒng)通常是異構或者同構異質DDBS。用戶1用戶2用戶n分布式協(xié)調管理系統(tǒng)DBMS1DBMS2DBMSm網絡12

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

包括四個階段：需求分析、概念設計、邏輯設計、物理設計。需求分析涉及收集用戶數據庫應用的非結構規(guī)格說明，并收集在

設計數據字典中。

概念設計產生全局、綜合數據庫模式的一種概念規(guī)格說明和在此

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

邏輯設計將綜合概念模式轉換成一給定的DBMS類型(關系、網狀、

層次或面向對象模型)的數據庫模式。

物理設計要遵照所選擇的特定DBMS的能力和特征進行，并產生

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

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

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

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

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

垂直分片是通過“投影”操作把它的屬性分成若干組。根據應用以“同樣方式”(具有相同的使用頻率)訪問的屬性來進行分組。垂直分片的方法可歸為基本垂直分片和垂直群集兩類。基本垂直分片只在某個鍵屬性上重疊，其他屬性不可重疊；垂直群集的組在其他屬性上也可以重疊。通過交替水平分片與垂直分片，可以產生混合分片。4.2數據分片的基本類型和方法4數據分片設計不論哪種分片方法，必須遵守如下規(guī)則：假若有全局關系R被分片為子關系(片段)集合

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

R,RiR必有xRi

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

R=∞

Ri

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

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

(水平分片)Ri

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

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

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

每一片段中元組被訪問的概率是相等的，因此是完整的；每一限定語都與應用密切相關，因此是最小的；限定語之間互斥，因此片段之間必不相交。(3)P={DEPT=1,JOB=‘P’,SAL>500}（完整的，不是最小的）因為SAL>500與應用無關。4.3水平分片4數據分片設計例2.3設全局關系

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

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

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已經進行水平分片，分為SM和SF,分別為男生全體和女生全體，則按S的水平分片（SM/SF）導出：

DefinefragmentSC1asSelect*FromSCWhereS#in(SelectSF.S#fromSM)DefinefragmentSC2asSelect*FromSCWhereS#in(SelectSM.S#fromSF)4.3水平分片4數據分片設計全局關系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}是關系R的一個垂直分片。如果屬性A∈R,必有A∈Ri,i=1,2,…,n,而且Ri∩Rj=(Ap,A-p),i≠j，A-p為R的一個或多個非碼屬性時，稱{Ri|i=1,2,…,n},是關系R的一個垂直群集。

垂直分片和垂直群集的目的在于使得許多重要應用可以只訪問一個

片段來執(zhí)行，從而使操作具有本地性。4.4垂直分片與垂直群集4數據分片設計全局關系EMP(Eno#,NAME,SAL,TEL,MAGNUM,DEPT)，其碼為Eno#。主要應用有:

在Sa站點查詢

NAME,SAL,TEL;

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

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

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

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

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

R1=

loc=SaEmp;R2=

loc=SbEmp

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

設F為單個片段，共有m個站點S1,…Sm,變量X1,…,Xm取值如下：

0如果片段F不在站點Sj上存儲

1如果片段F在站點Sj上存儲則總代價為：

Totalcost=ReadCost+WriteCost+StorageCost

讀代價寫代價存儲代價

確定Xj

的值,1jm,使總代價最小。Xj=5.2數據片段位置分配的方法—分配的簡化模型5數據分布設計讀代價：

Readcost=

[

tiMINCij

]

i:

讀申請源站點；

ti:站點Si上的讀申請激活次數；

Cij:

從Si讀Sj站點上的片段F的代價。

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

FFF.12j5.2數據片段位置分配的方法—分配的簡化模型5數據分布設計寫代價：

Writecost=

XjuiC’iji:寫申請源站點

j:被更新站點

Xj:

0如果片段F不在站點Sj上存儲 1如果片段F在站點Sj上存儲ui:站點Si

上更新激活次數

C’ij:從站點Si更新

Sj

分段F的代價i=1j=1mm....iFFFUpdatesui5數據分布設計5.2數據片段位置分配的方法—分配的簡化模型存儲代價：

StoreCost=

Xidi

Xi: 0如果片段F不在站點Si上存儲

1如果片段F在站點Si上存儲di: 站點Si

存儲片段F的代價i=1m5數據分布設計5.2數據片段位置分配的方法—分配的簡化模型目標函數：確定Xj

的值,1jm,使總代價最小。min

[ti

MINCij

+

Xj

ui

C’ij

]

+

Xidi

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

i：表示片段下標；

j：表示站點下標；

k：表示應用下標；

Fkj：表示應用k在站點j上激活的頻率；

Rki：表示應用k被激活一次，對片段i檢索訪問的次數；

Uki：表示應用k被激活一次，對片段i更新訪問的次數；

Nki=Rki+Uki：表示應用k被激活一次訪問片段i的總次數；

Fkj*Nki:表示應用k在站點j上對片段i的訪問頻度；

Fkj*Rki

:表示應用k在站點j上對片段i的檢索頻度；

Fkj*Uki:表示應用k在站點j上對片段i的更新頻度。5數據分布設計5.3數據片段分配的費用和得益估算最佳適應法（非冗余分配）：

將片段Ri分配到訪問片段Ri次數最多的那個站點上。在站點j上片段Ri

的本地訪問次數(對全部應用加和)是：

Bij=

kFkj*

Nki

=

kFkj*(Rki+Uki)

(1)估算：max(Bij)=Bij’則片段Ri就分配在站點j’上。5數據分布設計5.3數據片段分配的費用和得益估算—水平分片情況j例：設有一個片段Ri,有兩個應用A1,A2

,可能在三個場地分別設定為

Site<1>,Site<2>,Site<3>，并從應用需求分析得到的頻度參數為：

應用k=A1：在j=Site<1>上訪問頻度FA1,<1>*NA1,Ri=60,

在j=Site<2>上訪問頻度FA1,<2>*NA1,Ri=30,

在j=Site<3>上訪問頻度FA1,<3>*NA1,Ri=20,

應用k=A2：在j=Site<1>上訪問頻度FA2,<1>*NA2,Ri=40,

在j=Site<2>上訪問頻度FA2,<2>*NA2,Ri=50,

在j=Site<3>上訪問頻度FA2,<3>*NA2,Ri=50.

則計算站點j上片段Ri

的本地訪問次數Bij

如下：

當j=Site<1>,

Bij=

k=A1,A2

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

當j=Site<2>,

Bij=

k=A1,A2

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

當j=Site<3>,

Bij=

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

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

應分配在Site<1>上。5數據分布設計5.3數據片段分配的費用和得益估算—水平分片情況所有得益站點法（冗余分配方法一）：將片段Ri的副本分配到所有得益站點j上。

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

5數據分布設計5.3數據片段分配的費用和得益估算—水平分片情況所有得益站點法（冗余分配方法一）：

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

Bij=

kFkj*Rki

-c*k

j’≠j

Fkj’*Uki(2)其中：

c=更新/檢索為度量更新訪問費用與檢索訪問費用之比的一個常數，因更新有大量控制信息和局部操作，所以代價較高，一般c≥1.

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

當Di=1,β(1)=0；Di=2,

β(2)=Fi/2；

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

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

At,

A1,

A2,

A3,并估算它們的得益情況。估算各個應用分組得益情況如下：

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

BAs=

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

BAt=

FktNki(kAt)5數據分布設計5.3數據片段分配的費用和得益估算—垂直分片情況rs其他站點tRtRRs網絡A1A2AsAtA3應用組A1:

由站點r發(fā)出,原先使用Rt或Rs,現在這些應用需要進行一次額外的遠程訪問，損失：

BA1=

FkrNki(kA1)應用組A2:由站點r發(fā)出,原先使用R(本地訪問),現在這些應用需要進行兩次額外的遠程訪問，損失：

BA2=

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

BA3=

FkjNki(kA3,

j≠r,s,t)5數據分布設計5.3數據片段分配的費用和得益估算—垂直分片情況rs其他站點tRtRRs網絡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)這個公式可以用在窮舉式“分裂”算法(exhaustive‘splitting’algorithm)中，以確定用試探站點s和t的全部可能組合的方法來把站點i的R分裂

成站點s的Rs和站點t的Rt是否方便。5數據分布設計5.3數據片段分配的費用和得益估算—垂直分片情況把R分成兩個片段Rs和Rt,分別分配到站點s和站點t,它們具有重疊的屬性I。因此要求重新考慮應用的分組問題：

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

(2)應用At類同應用As。

(3)應用A1含有原先局限于站點r本地的更新應用，它們對I的屬性進行更新，而現在它們需要同時訪問Rs和Rt。

(4)應用A2含有原先局限于站點r本地的查詢應用，現在它們需要同時訪問Rs和Rt。

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

DATAID-1方法有四個階段：需求分析、概念設計、邏輯設計和物理設計。擴充的DATAID-D對其增加兩個階段：分布要求分析階段和分布設計階段。6DATAID-D方法6.1DATAID-D方法概述說明：1.設計數據字典；2.全局數據模式；3.全局操作模式；4.簡化全局模式；5.邏輯訪問表；6.各站點邏輯模式；7.各站點訪問表；8.局部邏輯模式（關系或網狀）；9.局部物理模式（關系或網狀）全局邏輯設計分布設計局部邏輯設計邏輯設計需求分析概念設計分布要求分析局部物理設計187654329要求頻率表劃分表極化表6DATAID-D方法6.1DATAID-D方法概述分布要求分析用戶分布要求全局數據概念模型全局數據操作模式應用頻率表實體訪問表應用極化表

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

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

Pkji表示應用k使用站點j訪問片段i的極化值(即頻率)。于是，全部應用k從站點j訪問片段i的次數給出如下：

Nij=

kFkj*Pkji

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

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

每當一新的旅客想預定一個班機的機票時，訂票應用就被激活。1.實體左下角和右下角的數字表示：示例總數和應用選擇的平均示例數。2.訪問數據庫中①起飛與到達機場;②起飛與到達時間;③班機日期.

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

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

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

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

基本劃分表中給出實體機場和實體旅客的基本劃分表。

1.將機場的區(qū)域屬性選作為機場實體的劃分準則；

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

3.謂詞選擇性表示按照該準則劃分各類元組所占的百分數。7實例研究：飛機訂票系統(tǒng)7.2飛機訂票系統(tǒng)中的分布要求分析1.兩種方法導出劃分班機實體：應用不同的聯系“從”(起飛機場)或“到”(到達機場)和基于已把機場劃分成區(qū)域來劃分班機實體。使用兩個不同聯系于同一基本劃分，產生兩種不同導出劃分，如下表前兩行。2.下表最后兩行給出了導出劃分旅客實體的兩個方法：依據聯系訂票和班機，按班機起飛區(qū)域或第一訂票地點劃分。在這種情況下，導出機制分兩步，因為它從機場作用到班機，然后從班機作用到旅客。前一種情形，依據他們第一次訂票的班機的地點來劃分旅客；后一情形中，依據他們各次的訂票的班機起飛區(qū)域來劃分旅客。7實例研究：飛機訂票系統(tǒng)7.2飛機訂票系統(tǒng)中的分布要求分析

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

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