第2章分布式數(shù)據(jù)庫系統(tǒng)設(shè)計褚龍現(xiàn)chulongxian@126.com回顧-自頂向下設(shè)計DDBS步驟需求分析概念設(shè)計視圖設(shè)計分布設(shè)計物理設(shè)計觀察與監(jiān)視系統(tǒng)需求全局概念模式訪問模式外部模式定義局部概念模式物理模式用戶輸入視圖集成用戶輸入反饋反饋回顧-數(shù)據(jù)的分片設(shè)計初級水平分片原則

若R={R1,R2,…,Rn},則完整性對于每一個元組

tR,RiR使得tRi

不相交性對

tRi,Rj

使得tRj,ij可重構(gòu)性操作是并∪(可忽略,因為完整性蘊含)

R=

∪{R1,R2,…,Rn}回顧-數(shù)據(jù)的分片設(shè)計初級水平分片原則

P={p1,p2,…,pn}是一簡單謂詞集合，為保證分片的正確性，P必須是：完整的：同一分片中的任意兩個元組被應(yīng)用同樣概率訪問。最小的：集合P中的所有謂詞與應(yīng)用密切相關(guān)。具有完整性和最小性不是必要條件,但是對于簡化分配問題有好處回顧-數(shù)據(jù)的分片設(shè)計謂詞的生成過程例：Emp(e#,name,Loc,sal,A,…)找到常用的AP查詢的simplepredicate

（Ai

Value）如:A<10,A>5,Loc=Sa,Loc=Sb生成“小項”謂詞

消除可能出現(xiàn)的無用謂詞數(shù)據(jù)的垂直分片數(shù)據(jù)的分配設(shè)計12教學(xué)內(nèi)容DATAID-D方法3教學(xué)目標(biāo)難點

掌握數(shù)據(jù)垂直分片的方法重點掌握數(shù)據(jù)分配設(shè)計的方法理解DATAID-D方法數(shù)據(jù)垂直分片設(shè)計方法數(shù)據(jù)分片分配的讀寫代價計算模型2.2自頂向下設(shè)計分布式數(shù)據(jù)庫系統(tǒng)設(shè)計步驟數(shù)據(jù)的分片設(shè)計水平分片（上次課程）垂直分片數(shù)據(jù)的分配設(shè)計2.2.2數(shù)據(jù)的分片設(shè)計垂直分片和垂直群集

垂直分片通過“投影”操作把一個全局關(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)識符，則稱{Ri},(i=1,2,…,n)是關(guā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)是關(guān)系R的一個垂直群集。2.2.2數(shù)據(jù)的分片設(shè)計垂直分片/垂直群集例子

EMP(E#,NAME,SAL,TEL,MAGNUM,DEPT)假定Key:E#

主要應(yīng)用:Sa站點查詢NAME,SAL,TEL;

Sb

站點查詢NAME,MAGNUM,DEPT

垂直分片:EMP1(E#,NAME,SAL,TEL)EMP2(E#,MAGNUM,DEPT)垂直群集:EMP1(E#,NAME,SAL,TEL)EMP2(E#,NAME,MAGNUM,DEPT)2.2.2數(shù)據(jù)的分片設(shè)計垂直分片例子E1EE22.2.2數(shù)據(jù)的分片設(shè)計垂直分片例子

E1(#,NM,LOC) E2(#,SAL)E(#,NM,LOC,SAL) E1(#,NM) E2(#,LOC) E3(#,SAL)?2.2.2數(shù)據(jù)的分片設(shè)計屬性的親和關(guān)系非鍵屬性

A1,A2,…,An應(yīng)用

Q1,Q2,….,Qmfreq(Qi)=Qi

的訪問頻率說明：從第一個應(yīng)用到第K個應(yīng)用，應(yīng)用本身同時訪問Ai和Aj的頻率之和2.2.2數(shù)據(jù)的分片設(shè)計屬性和矩陣

行列調(diào)整尋找分割點，同時調(diào)整0787521A497044845A34757900A5482010050A245105096A1

A3A4A5A2A12.2.2數(shù)據(jù)的分片設(shè)計屬性和矩陣

7578021A47975400A540974845A3024810050A201455096A1

A5A4A3A2A1R1[K,A1,A2,A3]

R2[K,A4,A5]2.2.2數(shù)據(jù)的分片設(shè)計垂直分片算法窮舉屬性親和矩陣的列排列行與列要同時調(diào)整發(fā)現(xiàn)好的“分割點”極大化每個分割內(nèi)的親合力（affinity）,極小化跨分割的訪問2.2.2數(shù)據(jù)的分片設(shè)計分片小結(jié)水平

初級：

R 根據(jù)

local屬性

導(dǎo)出：

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

R2.2.2數(shù)據(jù)的分片設(shè)計分片小結(jié)混合分段RR1R2R11R12R21R22水平垂直2.2.3數(shù)據(jù)的分配設(shè)計分配的概念在滿足用戶需求的前提下,把設(shè)計好的數(shù)據(jù)片段分配到相應(yīng)的站點上存儲例子:E(#,NM,LOC,SAL)

R1=

loc=SaE;R2=

loc=SbE

Qa:select…whereloc=Sa...

Qb:select…whereloc=Sb…SiteaSiteb

R1,R2存放在哪??2.2.3數(shù)據(jù)的分配設(shè)計分配方法分配方法非冗余分配設(shè)計方法最佳適應(yīng)法冗余分配的設(shè)計方法所有得益站點法附加復(fù)制法應(yīng)用需求確定非復(fù)制問題的解確定一組站點分配副本確定非復(fù)制問題的解從最有益處增加副本到附加復(fù)制無好處為止其他方法2.2.3數(shù)據(jù)的分配設(shè)計優(yōu)化問題什么是段的最好配置/什么是最好的冗余副本數(shù):極小化查詢響應(yīng)時間極大化吞吐量極小化“代價”...約束?有效的存儲空間有效的帶寬,站點處理能力,…保持

90%的響應(yīng)時間低于

X（如0.5秒）...2.2.3數(shù)據(jù)的分配設(shè)計分配的簡化模型單個片段

F；站點

S1,…Sm

；

變量

X1,…,Xm

0如果

F不在

Sj上存儲

1如果F在Sj上存儲

Totalcost=ReadCost+WriteCost+ StorageCost

確定

Xj

的值,1jm,使總代價極小。Xj=2.2.3數(shù)據(jù)的分配設(shè)計分配的簡化模型讀代價

Readcost=[tiMINCi,j]i: 讀申請源站點

ti: 站點Si上的讀申請激活次數(shù)

Ci,j:從Si讀Sj站點分段F的代價

...3ici,3ci,1ci,2

ti

FFF.12i=1mj2.2.3數(shù)據(jù)的分配設(shè)計分配的簡化模型寫代價....iFFFUpdatesui

Writecost=Xj

ui

C’ij

i:寫申請源站點

j:被更新站點

Xj:0ifFnotstoredatSj 1ifFstoredatSj

ui:站點

Si

上更新激活次數(shù)

C’ij:從站點Si

更新

Sj

分段

F的代價i=1j=1mm2.2.3數(shù)據(jù)的分配設(shè)計分配的簡化模型存儲代價

StoreCost=

Xi

di

Xi:0ifFnotstoredatSi

1ifFstoredatSi

di:

站點

Si

存儲分段

F的代價i=1m2.2.3數(shù)據(jù)的分配設(shè)計分配的簡化模型目標(biāo)函數(shù)min[tiMINCij+Xj

ui

C’ij] +Xidi

i=1j=1i=1mmm2.2.3數(shù)據(jù)的分配設(shè)計分配方法“最佳適應(yīng)”方法（非冗余分配）

Bij=

k

Fkj

Nk“所有得益站點”方法（冗余分配）

Bij=

k

Fkj

Rki

-c

k

j’jFkj’

Uki

i片段下標(biāo)j站點下標(biāo)

k應(yīng)用下標(biāo)Fkj

應(yīng)用k在站點j上激活的頻率

Rki

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

Uki

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

Nki

應(yīng)用k被激活一次,對片段i讀寫的總次數(shù)2.2.3數(shù)據(jù)的分配設(shè)計水平分片分配方法最佳適應(yīng)法將片斷Ri分配到訪問Ri次數(shù)最多的那個站點上

Bij=

kFkj*Nki

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

kFkj*Rki

-c*k

j’≠j

Fkj’*Uki如果Bij

＞0，則站點j是得益站點，放置Ri的一個副本附加復(fù)制法Di表示片斷Ri的冗余度（副本個數(shù)）,Fi表示Ri在所有站點都復(fù)制的得益

2.2.3數(shù)據(jù)的分配設(shè)計垂直分片分配方法rs其他站點tRtRRs網(wǎng)絡(luò)A1A2AsAt

A32.2.3數(shù)據(jù)的分配設(shè)計垂直分片分配方法假設(shè)關(guān)系R垂直分片Rs和Rt,Rs分配到s站點,Rt分配到t站點.應(yīng)用組As:自站點s發(fā)出,只使用Rs,得益

BAs=

Fks

Nki

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

BAt=

Fkt

Nki

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

BA1=

Fkr

Nki

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

BA2=

Fkr

Nki

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

BA1=

Fkj

Nki

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

Bist=BAs+BAt-BA1-BA2-BA32.3DATAID-D方法與集中式數(shù)據(jù)庫的異同設(shè)計步驟分布要求分析階段分布設(shè)計階段2.3.1與集中式數(shù)據(jù)庫的異同分布式數(shù)據(jù)庫設(shè)計階段需求分析概念設(shè)計分布要求設(shè)計全局邏輯設(shè)計分布設(shè)計局部邏輯設(shè)計局部物理設(shè)計收集分