第3章 分布式數(shù)據(jù)庫系統(tǒng)的設(shè)計(jì)

分布式數(shù)據(jù)庫系統(tǒng)及其應(yīng)用分布式數(shù)據(jù)庫系統(tǒng)設(shè)計(jì)的目標(biāo)分布式數(shù)據(jù)庫系統(tǒng)設(shè)計(jì)的內(nèi)容分布式數(shù)據(jù)庫的設(shè)計(jì)方法數(shù)據(jù)分片設(shè)計(jì)數(shù)據(jù)分布設(shè)計(jì)DATAID-D方法分布式數(shù)據(jù)庫系統(tǒng)中數(shù)據(jù)的獨(dú)立性與分布透明性實(shí)例研究：飛機(jī)訂票系統(tǒng)分布式數(shù)據(jù)庫系統(tǒng)設(shè)計(jì)

第3章1分布式數(shù)據(jù)庫設(shè)計(jì)目標(biāo)DDBS設(shè)計(jì)目標(biāo)本地性或近地性存儲(chǔ)能力和費(fèi)用盡量減少通信次數(shù)和通信量，90/10準(zhǔn)則分片和分布方案（本地和遠(yuǎn)程訪問次數(shù)）擇優(yōu)控制數(shù)據(jù)適當(dāng)冗余冗余增加了可靠性、可用性，提高了效率維護(hù)數(shù)據(jù)一致性開銷增加工作負(fù)荷分布各站點(diǎn)可以分擔(dān)整個(gè)工作任務(wù)本地性降低2分布式數(shù)據(jù)庫設(shè)計(jì)內(nèi)容DDBS設(shè)計(jì)DDB設(shè)計(jì)應(yīng)用設(shè)計(jì)全局模式設(shè)計(jì)局部數(shù)據(jù)庫設(shè)計(jì)相關(guān)應(yīng)用需求各個(gè)應(yīng)用的原發(fā)站點(diǎn)各個(gè)應(yīng)用在每個(gè)站點(diǎn)的激活頻率各個(gè)應(yīng)用對(duì)要求訪問數(shù)據(jù)對(duì)象的訪問次數(shù)、類型和統(tǒng)計(jì)分布分片和分布3.1DDBS設(shè)計(jì)方法3分布式數(shù)據(jù)庫設(shè)計(jì)方法DDBS設(shè)計(jì)方法自頂向下方法（重構(gòu)法）混合方法自底向上方法（組合法）3分布式數(shù)據(jù)庫設(shè)計(jì)方法DDBS設(shè)計(jì)方法3.1

組合法剖析網(wǎng)絡(luò)功能剖析原有數(shù)據(jù)庫系統(tǒng)解決數(shù)據(jù)的一致性、完整性和可靠性難度較大

通常是異構(gòu)或者同構(gòu)異質(zhì)DDBS用戶1用戶2用戶n分布式協(xié)調(diào)管理系統(tǒng)DBMS1DBMS2DBMSm

網(wǎng)絡(luò)3分布式數(shù)據(jù)庫設(shè)計(jì)方法DDBS設(shè)計(jì)方法3.1

重構(gòu)法根據(jù)實(shí)現(xiàn)環(huán)境和用戶需求按照DDBS的設(shè)計(jì)思想和方法從總體設(shè)計(jì)做起，包括LDBS,重新建立一個(gè)DDBS可有效解決數(shù)據(jù)一致性、完整性和可靠性問題。

通常是同構(gòu)異質(zhì)或同構(gòu)同質(zhì)DDBS用戶1用戶2用戶n分布式數(shù)據(jù)庫管理系統(tǒng)

網(wǎng)絡(luò)3.2自頂向下設(shè)計(jì)DDB步驟和內(nèi)容3分布式數(shù)據(jù)庫設(shè)計(jì)方法需求分析概念設(shè)計(jì)視圖設(shè)計(jì)分布設(shè)計(jì)物理設(shè)計(jì)觀察與監(jiān)視系統(tǒng)需求全局概念模式訪問模式外部模式定義局部概念模式物理模式用戶輸入視圖集成用戶輸入反饋反饋?zhàn)皂斚蛳略O(shè)計(jì)過程將現(xiàn)有的各種不同的數(shù)據(jù)庫模式集成為全局模式.三個(gè)問題選擇公用數(shù)據(jù)庫模型來描述數(shù)據(jù)庫的全局模式把每個(gè)站點(diǎn)上的本地模式翻譯成公用數(shù)據(jù)模型把各站點(diǎn)上的本地?cái)?shù)據(jù)模式集成為一公用的全局模式3.3自底向上設(shè)計(jì)方法3分布式數(shù)據(jù)庫設(shè)計(jì)方法自底向上設(shè)計(jì)方法要解決的問題自底向上方法主要問題是構(gòu)造一個(gè)全局模式（超視圖）.把各站點(diǎn)上的數(shù)據(jù)庫模式看成是全局模式的一個(gè)視圖這個(gè)問題就可看作是視圖綜合問題概括分層結(jié)構(gòu)支持視圖綜合經(jīng)典方法就是生成三個(gè)實(shí)體：一個(gè)具有共同屬性（超類型），兩個(gè)具有不相交屬性（子類型）視圖綜合次序一次把一個(gè)視圖和全局模式進(jìn)行綜合，逐步構(gòu)造起全局視圖通常，最好首先綜合最大的或最重要的視圖，然后跟著綜合小的或者不重要的視圖3.3自底向上設(shè)計(jì)方法3分布式數(shù)據(jù)庫設(shè)計(jì)方法構(gòu)造全局模式問題和解決方法班機(jī)機(jī)號(hào)日期可用座位出入口座位圖延期班機(jī)機(jī)號(hào)日期可用座位機(jī)型座位圖班機(jī)班機(jī)1班機(jī)2機(jī)號(hào)日期可用座位座位圖出入口延期機(jī)型3.3自底向上設(shè)計(jì)方法3分布式數(shù)據(jù)庫設(shè)計(jì)方法3.3自底向上設(shè)計(jì)方法3分布式數(shù)據(jù)庫設(shè)計(jì)方法識(shí)別相似性模式命名相似性模式結(jié)構(gòu)相似性不同Site上有相似應(yīng)用,使用各自DB的數(shù)據(jù)副本,則這兩Site之間有某些相似點(diǎn).識(shí)別沖突命名沖突：同物異名（EMP,EMPLOYEE），異物同名域差異定標(biāo)差異：計(jì)量單位不同(天、小時(shí)、分鐘、秒）結(jié)構(gòu)差異：同一對(duì)象有的用實(shí)體描述,有的用屬性描述.處理操作期間不一致的數(shù)據(jù)策略（5種，p64-65）4.1分片設(shè)計(jì)的基本目的4數(shù)據(jù)分片設(shè)計(jì)在自頂向下的數(shù)據(jù)分布設(shè)計(jì)中，必須要解決的第一個(gè)問題是數(shù)據(jù)的分片設(shè)計(jì)。在數(shù)據(jù)分片設(shè)計(jì)時(shí)，是從分配的觀點(diǎn)來看，根據(jù)具有“相同性質(zhì)”的元組（在水平分片的情況下）或?qū)傩裕ㄔ诖怪狈制那闆r下）進(jìn)行分組，使具有“相同性質(zhì)（例如訪問頻率相同）”的元組或?qū)傩詣澐衷谝粋€(gè)組中，每組就構(gòu)成一個(gè)片段分片設(shè)計(jì)的基本目的是產(chǎn)生一個(gè)對(duì)全局?jǐn)?shù)據(jù)合適的劃分方案，將使用這種方案得到的數(shù)據(jù)片段作為分布式數(shù)據(jù)庫中數(shù)據(jù)的分配和存儲(chǔ)單位時(shí)，不但能夠減少應(yīng)用中的操作量，而且對(duì)于應(yīng)用具有最大可能的本地性但是，不是所有的全局?jǐn)?shù)據(jù)都必須進(jìn)行分片，應(yīng)考慮到有可能一個(gè)全局關(guān)系根本不需要分片。假若有全局關(guān)系R被分片為子關(guān)系(片段)集合

R={R1,R2,…,Rn},則R滿足完整性?x

R,RiR必有

xRi

，i=1,2,…,n可重構(gòu)性存在函數(shù)g使得R=g(R1,R2,…,Rn)即，R=∪Ri(水平分片）,R=∞

Ri

（垂直分片）不相交性Ri

∩

Rj

=空集,i≠j,i,j=1,2,…,n(水平分片)Ri

∩

Rj

=主鍵屬性,i,j=1,2,…,n(垂直分片)4.3數(shù)據(jù)分片的基本類型和方法4數(shù)據(jù)分片設(shè)計(jì)

分片原則

分片方法水平分片

垂直分片職工關(guān)系E(e#,name,loc,sal,…)

查詢:

Qa:select* Qb:select* fromE fromE whereloc=Sa whereloc=Sb and… and...兩個(gè)站點(diǎn):Sa,SbQa

QbSaSb4.3數(shù)據(jù)分片的基本類型和方法4數(shù)據(jù)分片設(shè)計(jì)

舉例 e#NMLocSal E578Sa1000SallySb2500TomSa500Joee#NMLocSale#NMLocSal58Sa1000TomSa500Joe7Sb2500Sally........F站點(diǎn)Sa站點(diǎn)Sb4.3數(shù)據(jù)分片的基本類型和方法4數(shù)據(jù)分片設(shè)計(jì)

舉例基本水平分片以關(guān)系自身的屬性性質(zhì)為基礎(chǔ)，執(zhí)行“選擇”操作，將關(guān)系分割成若干個(gè)不相交的片段。

R={R1,R2}R1=

loc=Sa(E)R2=

loc=Sb(E)4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)

基本水平分片若R={R1,R2,…,Rn},則完整性對(duì)于每一個(gè)元組

t

R,RiR使得

tRi

不相交性對(duì)

tRi,Rj

使得

tRj,ij可重構(gòu)性操作是∪

(可以忽略,因?yàn)橥暾跃吞N(yùn)含著)R=

∪{R1,R2,…,Rn}P={p1,p2,…,pn}是一簡單謂詞集合，為保證分片的正確性，P必須是：完整的：同一分片中的任意兩個(gè)元組被應(yīng)用同樣概率訪問。最小的：集合P中的所有謂詞與應(yīng)用密切相關(guān)。具有完整性和最小性不是必要條件,但是對(duì)于簡化分配問題有好處4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)

基本水平分片例子EMP(E#,NAME,DEPT,JOB,SAL,TEL,…)DEPT={1,2}JOB={‘P’,‘-P’}假定，應(yīng)用經(jīng)常查詢的內(nèi)容是屬于部門1且是程序員的職員。則可能有的水平分段限定

P={DEPT=1}（不是完整的）

P={DEPT=1,JOB=‘P’}（是完整的、最小的）

P={DEPT=1,JOB=‘P’,SAL>500}（完整的，不是最小的）4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)

基本水平分片如何保證分片原則“手工”檢查! e.g.,R1=

loc=‘Sa’E;R2=

loc=‘Sb’E生成具有滿足分段原則的限定謂詞4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)

基本水平分片設(shè)有關(guān)系E(e#,name,Loc,sal,A,…),查詢使用的簡單謂詞（Ai

Value）是:A<10,A>5,Loc=Sa,Loc=Sb下一步: -生成“小項(xiàng)”謂詞

-消除無用謂詞給定簡單謂詞集Pr={p1,p2,..pn},則“小項(xiàng)”謂詞（mintermpredicate）形式:

p1*

p2*…pn*

這里pk*是pk

或是?pk4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)

謂詞生成舉例(1)A<10

A>5

Loc=SA

Loc=SB(2)

A<10

A>5

Loc=SA

?(Loc=SB)(3)

A<10

A>5

?(Loc=SA)

Loc=SB(4)A<10

A>5

?(Loc=SA)

?(Loc=SB)(5)A<10

?(A>5)

Loc=SA

Loc=SB(6)

A<10

?(A>5)

Loc=SA

?(Loc=SB)(7)

A<10

?(A>5)

?(Loc=SA)

Loc=SB(8)A<10

?(A>5)

?(Loc=SA)

?(Loc=SB)4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)小項(xiàng)謂詞選擇(9)?(A<10)

A>5

Loc=SA

Loc=SB(10)?(A<10)

A>5

Loc=SA

?(Loc=SB)(11)?(A<10)

A>5

?(Loc=SA)

Loc=SB(12)?(A<10)

A>5

?(Loc=SA)

?(Loc=SB)(13)?(A<10)

?(A>5)

Loc=SA

Loc=SB(14)?(A<10)

?(A>5)

Loc=SA

?(Loc=SB)(15)?(A<10)

?(A>5)

?(Loc=SA)

Loc=SB(16)?(A<10)

?(A>5)

?(Loc=SA)

?(Loc=SB)4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)小項(xiàng)謂詞選擇R2: 5<A<10

Loc=SA

R3: 5<A<10

Loc=SB

R6: A

5

Loc=SA

R7: A

5

Loc=SB

R10: A

10

Loc=SA

R11: A

10

Loc=SB

分片結(jié)果4.4數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)注:無用段的消除依賴于應(yīng)用的語義e.g.:

如果LOC可以是

SA,SB,則最終分段集合應(yīng)該加上R4: 5<A<10

LocSA

LocSB

R8: A

5

LocSA

LocSB

R12: A

10

LocSA

LocSB4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)小項(xiàng)選擇率（mintermselectivity）

對(duì)某一給定小項(xiàng)謂詞用戶查詢可能選擇到的元組數(shù)訪問頻率（Accessfrequency）用戶應(yīng)用訪問數(shù)據(jù)的頻率小項(xiàng)訪問頻率可以通過用戶查詢頻率獲得4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)分片數(shù)量信息例子

E(#,NM,LOC,SAL,…)

有查詢應(yīng)用

Qa:select* Qb:select* fromE fromE whereLOC=Sa whereLOC=Sb and… and...4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)如何選擇小項(xiàng)謂詞舉例(1)Pr={}R1={E}(2)Pr={LOC=Sa,LOC=Sb} R2={

loc=SaE,loc=SbE}(3)Pr={LOC=Sa,LOC=Sb,Sal<1000} R3={

loc=Sa

sal<1000E,loc=Sa

sal1000E,

loc=Sb

sal<1000E,loc=Sb

sal1000E}三種選擇4數(shù)據(jù)分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)Loc=Sa

sal<1000Loc=Sa

sal

1000Loc=Sb

sal<1000Loc=Sb

sal

1000R1R3R2Qa:Select…loc=Sa...Qb:Select…loc=Sb...R2是好的…(R1,R3不好

)4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)圖示Loc=Sa

sal<1000Loc=Sa

sal

1000Loc=Sb

sal<1000Loc=Sb

sal

1000R1Qa:Select…loc=Sa...Qb:Select…loc=Sb...此處元組有較高的選擇概率此處元組選擇概率較低分段內(nèi)元組選擇概率不等因此R1不好...4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)理由Loc=Sa

sal<1000Loc=Sa

sal

1000Loc=Sb

sal<1000Loc=Sb

sal

1000R2Qa:Select…loc=Sa...Qb:Select…loc=Sb...元組選擇概率相等因此R2好...R3不好

...理由4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)導(dǎo)出分片從另一個(gè)關(guān)系的屬性性質(zhì)或水平分片推導(dǎo)出來例子

SC(S#,C#,GRADE)S(S#,SNAME,AGE,SEX)要求：將SC劃分為男生各門課成績和女生的各門成績4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)

導(dǎo)出水平分片按S的屬性導(dǎo)出

DefinefragmentSC1asSelectSC.S#,C#,GRADEFromSC,SWhereSC.S#=S.S#andSEX=‘M’DefinefragmentSC2asSelectSC.S#,C#,GRADEFromSC,SWhereSC.S#=S.S#andSEX=‘F’按S的水平分片（SF/SM）導(dǎo)出DefinefragmentSC1asSelect*FromSCWhereS#in(SelectSF.SfromSF)DefinefragmentSC2asSelect*FromSCWhereS#in(SelectSM.SfromSM)

4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)

導(dǎo)出水平分片例子通過“投影”操作把一個(gè)全局關(guān)系的屬性分成若干組，基本目標(biāo)是將使用頻繁的屬性聚集在一起全局關(guān)系R={Ri},i=1,2,…,n如果屬性A∈R,必有A∈Ri,i=1,2,…,n,而且Ri∩Rj=Ap,i≠j，Ap為R的碼或元組標(biāo)識(shí)符，則稱{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è)垂直群集。4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)

垂直分片和垂直群集EMP(E#,NAME,SAL,TEL,MAGNUM,DEPT)假定Key:E#主要應(yīng)用:Sa站點(diǎn)查詢NAME,SAL,TEL;Sb站點(diǎn)查詢NAME,MAGNUM,DEPT垂直分片:EMP1(E#,NAME,SAL,TEL)EMP2(E#,MAGNUM,DEPT)垂直群集:EMP1(E#,NAME,SAL,TEL)EMP2(E#,NAME,MAGNUM,DEPT)4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)

垂直分片/垂直群集例子4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)E1EE2

垂直分片例子

例子: E1(#,NM,LOC) E2(#,SAL)E(#,NM,LOC,SAL) E1(#,NM) E2(#,LOC) E3(#,SAL)?4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)

垂直分片設(shè)計(jì)非鍵屬性A1,A2,…,An應(yīng)用Q1,Q2,….,Qmfreq(Qi)=Qi

的訪問頻率4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)

屬性的親和關(guān)系7578021A47975400A540974845A3024810050A201455096A1

A5A4A3A2A1R1[K,A1,A2,A3]R2[K,A4,A5]4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)

屬性親和矩陣0787521A497044845A34757900A5482010050A245105096A1

A3A4A5A2A1行列調(diào)整尋找分割點(diǎn)4.4數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)

屬性和矩陣窮舉屬性親和矩陣的列排列行與列要同時(shí)調(diào)整發(fā)現(xiàn)好的“分割點(diǎn)”極大化每個(gè)分割內(nèi)的親合力（affinity）,極小化跨分割的訪問4.4數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)垂直分片算法水平 基本：

R 根據(jù)local屬性

導(dǎo)出

根據(jù)外鍵關(guān)系垂直

R4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)分片小結(jié)混合分段RR1R2R11R12R21R22水平垂直4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)分片小結(jié)混合分段的重構(gòu)R11R12R21R22水平垂直U4.4

數(shù)據(jù)的分片設(shè)計(jì)4數(shù)據(jù)分片設(shè)計(jì)分片小結(jié)在滿足用戶需求的前提下,把設(shè)計(jì)好的數(shù)據(jù)片段分配到相應(yīng)的站點(diǎn)上存儲(chǔ)例子:E(#,NM,LOC,SAL)

R1=

loc=SaE;R2=

loc=SbE

Qa:select…whereloc=Sa... Qb:select…whereloc=Sb…SiteaSiteb

R1,R2

存放在哪??5.1

數(shù)據(jù)分布概念5數(shù)據(jù)分布設(shè)計(jì)分布的概念集中式分割式復(fù)制式混合式5.2

數(shù)據(jù)的分布策略5數(shù)據(jù)分布設(shè)計(jì)分配的策略5.3數(shù)據(jù)片段位置分配的方法5數(shù)據(jù)分布設(shè)計(jì)分配方法分配方法非冗余分配設(shè)計(jì)方法最佳適應(yīng)法其他方法冗余分配的設(shè)計(jì)方法所有得益站點(diǎn)法附加復(fù)制法應(yīng)用需求確定非復(fù)制問題的解確定一組站點(diǎn)分配副本確定非復(fù)制問題的解從最有益處增加副本到附加復(fù)制無好處為止什么是段的最好配置/什么是最好的冗余副本數(shù):極小化查詢響應(yīng)時(shí)間極大化吞吐量極小化“代價(jià)”...約束?有效的存儲(chǔ)空間有效的帶寬,站點(diǎn)處理能力,…保持90%的響應(yīng)時(shí)間低于X（如0.5秒）...5.4數(shù)據(jù)片段分配的費(fèi)用和得益估算5數(shù)據(jù)的分配設(shè)計(jì)優(yōu)化問題

單個(gè)片段F站點(diǎn)S1,…Sm

變量X1,…,Xm0如果F不在Sj上存儲(chǔ)

1如果F在Sj上存儲(chǔ)

Totalcost=ReadCost+WriteCost+ StorageCost

確定Xj的值,1jm,使總代價(jià)極小Xj=分配的簡化模型讀代價(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.12j寫代價(jià)

Writecost=

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

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

Xj:0ifFnotstoredatSj 1ifFstoredatSjui:站點(diǎn)Si上更新激活次數(shù)

C’ij:從站點(diǎn)Si更新Sj分段F的代價(jià)i=1j=1mm分配的簡化模型....iFFFUpdatesui存儲(chǔ)代價(jià)

StoreCost=

Xidi

Xi: 0ifFnotstoredatSi

1ifFstoredatSidi:

站點(diǎn)Si存儲(chǔ)分段F的代價(jià)i=1m分配的簡化模型目標(biāo)函數(shù)min

[tiMINCij

+

XjuiC’ij]

+

Xidi

ji=1j=1i=1mmm分配的簡化模型即使最簡單的公式也是NP-完全問題通常,使用方法盡可能將片段分配在被局部訪問位置“最佳適應(yīng)”方法（非冗余分配）

Bij=

kFkjNki“所有得益站點(diǎn)”方法（冗余分配）

Bij=

kFkjRki-c

k

j’jFkj’Uki

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讀的次數(shù)

Uki應(yīng)用k被激活一次,對(duì)片段i寫的次數(shù)

Nki應(yīng)用k被激活一次,對(duì)片段i讀寫的總次數(shù)分配方法最佳適應(yīng)法將片斷Ri分配到訪問Ri次數(shù)最多的那個(gè)站點(diǎn)上Bij=

kFkj*Nki

所有得益站點(diǎn)法將片斷Ri的副本分配到所有得益站點(diǎn)j上Bij=

kFkj*Rki-c*k

j’≠jFkj’*Uki如Bij＞0，則站點(diǎn)j是得益站點(diǎn)，放置Ri的一個(gè)副本附加復(fù)制法Di表示片斷Ri的冗余度（副本個(gè)數(shù)）,Fi表示Ri在所有站點(diǎn)都復(fù)制的得益

水平分片情況假設(shè)關(guān)系R垂直分片R1和R2,R1分配到s站點(diǎn),R2分配到t站點(diǎn).應(yīng)用組As:自站點(diǎn)s發(fā)出,只使用Rs,得益

BAs=FksNki(kAs)應(yīng)用組Ar:自站點(diǎn)t發(fā)出,只使用Rt,得益

BAt=FktNki(kAt)應(yīng)用組A1:由站點(diǎn)r發(fā)出,原先使用Rt或Rs(本地),現(xiàn)在要一次遠(yuǎn)程，損失

BA1=FkrNki(kA1)應(yīng)用組A2:由站點(diǎn)r發(fā)出,原先使用R(本地),現(xiàn)在要兩次遠(yuǎn)程，損失

BA2=FkrNki(kA2)應(yīng)用組A3:由不同于站點(diǎn)r,s,t的站點(diǎn)發(fā)出,要訪問Rt和Rs,損失

BA3=FkjNki(kA3,j≠r,s,t)分配得益

Bist=BAs+BAt-BA1-BA2-BA3垂直分片情況垂直分片情況rs其他站點(diǎn)tRtRRs網(wǎng)絡(luò)A1A2AsAtA3分布式數(shù)據(jù)庫設(shè)計(jì)階段需求分析概念設(shè)計(jì)分布要求設(shè)計(jì)全局邏輯設(shè)計(jì)分布設(shè)計(jì)局部邏輯設(shè)計(jì)局部物理設(shè)計(jì)6.1與集中式數(shù)據(jù)庫的異同6DATAID-D方法收集分布信息水平分片謂詞每一應(yīng)用在各站點(diǎn)激活頻率概念設(shè)計(jì)之后進(jìn)行收集分布信息分布要求和全局邏輯模式作為輸入形式為全局?jǐn)?shù)據(jù)庫模式和邏輯訪問表輸出為分片模式和分配模式全局邏輯設(shè)計(jì)之后進(jìn)行說明：1.設(shè)計(jì)數(shù)據(jù)字典；2.全局?jǐn)?shù)據(jù)模式；3.全局操作模式；4.簡化全局模式；5.邏輯訪問表；6.各站點(diǎn)邏輯模式；7.各站點(diǎn)訪問表；8.局部邏輯模式（關(guān)系或Codasyl）；9.局部物理模式（關(guān)系或Codasyl）全局邏輯設(shè)計(jì)分布設(shè)計(jì)局部邏輯設(shè)計(jì)邏輯設(shè)計(jì)需求分析概念設(shè)計(jì)分布要求分析局部物理設(shè)計(jì)187654329要求頻率表劃分表極化表6.2設(shè)計(jì)步驟6DATAID-D方法分布要求分析階段頻率表：各站點(diǎn)上每一應(yīng)用激活次數(shù)（假設(shè)所有應(yīng)用在所有站點(diǎn)上都能執(zhí)行）劃分表：可用于模式中各實(shí)體的潛在水平分片規(guī)則極化表：指明由一個(gè)站點(diǎn)發(fā)出的一給定應(yīng)用訪問一給定片段的頻率（定量分析方法）分布要求分析用戶分布要求全局?jǐn)?shù)據(jù)概念模型全局?jǐn)?shù)據(jù)操作模式應(yīng)用頻率表實(shí)體劃分表應(yīng)用極化表6.3分布要求分析階段6DATAID-D方法分布設(shè)計(jì)階段分片設(shè)計(jì)非冗余分配冗余分配局部模式的重新構(gòu)造分布設(shè)計(jì)全局?jǐn)?shù)據(jù)模式邏輯訪問表分布要求站點(diǎn)邏輯模式站點(diǎn)邏輯訪問表6.4分布設(shè)計(jì)階段6DATAID-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ù)模型等在分布式數(shù)據(jù)庫中，分布獨(dú)立性也稱為分布透明性（DistributionTransparency）。分布透明性包括三個(gè)層次：分片透明性、位置透明性局部數(shù)據(jù)模型透明性7.1分布式數(shù)據(jù)庫系統(tǒng)中數(shù)據(jù)的獨(dú)立性與分布透明性概述7分布式數(shù)據(jù)庫系統(tǒng)中數(shù)據(jù)的獨(dú)立性與分布透明性最高級(jí)別透明性：分片透明性全局概念模式以下的任何改變，都不會(huì)影響到這個(gè)應(yīng)用程序。若DDBMS具有分片透明性，用戶只要知道全局關(guān)R就可編寫程序中等級(jí)別透明性：位置透明性若DDBMS提供位置透明性而不提供分片透明性，用戶編寫這個(gè)應(yīng)用程序就要知道全局關(guān)系的分片情況，但不必知道片段的位置分配細(xì)節(jié)。最低級(jí)別透明性：局部數(shù)據(jù)模型透明性若DDBMS只提供局部數(shù)據(jù)模型透明性，不提供位置透明性（當(dāng)然也不具有分片透明性）時(shí)，用戶編寫應(yīng)用程序不但要知道全局?jǐn)?shù)據(jù)的分片細(xì)節(jié)，還必須知道片段或其副本存放在哪些站點(diǎn)上7.2分布式數(shù)據(jù)庫簡單查詢與分布透明性7分布式數(shù)據(jù)庫系統(tǒng)中數(shù)據(jù)的獨(dú)立性與分布透明性最高級(jí)別透明性：分片透明性全局概念模式以下的任何改變，都不會(huì)影響到這個(gè)應(yīng)用程序。若DDBMS具有分片透明性，用戶只要知道全局關(guān)R就可編寫程序中等級(jí)別透明性：位置透明性若DDBMS提供位置透明性而不提供分片透明性，用戶編寫這個(gè)應(yīng)用程序就要知道全局關(guān)系的分片情況，但不必知道片段的位置分配細(xì)節(jié)。最低級(jí)別透明性：局部數(shù)據(jù)模型透明性若DDBMS只提供局部數(shù)據(jù)模型透明性，不提供位置透明性（當(dāng)然也不具有分片透明性）時(shí)，用戶編寫應(yīng)用程序不但要知道全局?jǐn)?shù)據(jù)的分片細(xì)節(jié)，還必須知道片段或其副本存放在哪些站點(diǎn)上無分布透明性7.2