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

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

tR,RiR使得tRi

不相交性對

tRi,Rj

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

R=

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

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

（Ai

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

消除可能出現的無用謂詞數據的垂直分片數據的分配設計12教學內容DATAID-D方法3教學目標難點

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

垂直分片通過“投影”操作把一個全局關系的屬性分成若干組，基本目標是將使用頻繁的屬性聚集在一起。全局關系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的一個垂直群集。2.2.2數據的分片設計垂直分片/垂直群集例子

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

主要應用: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數據的分片設計垂直分片例子E1EE22.2.2數據的分片設計垂直分片例子

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

A1,A2,…,An應用

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

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

行列調整尋找分割點，同時調整0787521A497044845A34757900A5482010050A245105096A1

A3A4A5A2A12.2.2數據的分片設計屬性和矩陣

7578021A47975400A540974845A3024810050A201455096A1

A5A4A3A2A1R1[K,A1,A2,A3]

R2[K,A4,A5]2.2.2數據的分片設計垂直分片算法窮舉屬性親和矩陣的列排列行與列要同時調整發現好的“分割點”極大化每個分割內的親合力（affinity）,極小化跨分割的訪問2.2.2數據的分片設計分片小結水平

初級：

R 根據

local屬性

導出：

根據外鍵關系垂直

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

R1=

loc=SaE;R2=

loc=SbE

Qa:select…whereloc=Sa...

Qb:select…whereloc=Sb…SiteaSiteb

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

90%的響應時間低于

X（如0.5秒）...2.2.3數據的分配設計分配的簡化模型單個片段

F；站點

S1,…Sm

；

變量

X1,…,Xm

0如果

F不在

Sj上存儲

1如果F在Sj上存儲

Totalcost=ReadCost+WriteCost+ StorageCost

確定

Xj

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

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

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

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

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

ti

FFF.12i=1mj2.2.3數據的分配設計分配的簡化模型寫代價....iFFFUpdatesui

Writecost=Xj

ui

C’ij

i:寫申請源站點

j:被更新站點

Xj:0ifFnotstoredatSj 1ifFstoredatSj

ui:站點

Si

上更新激活次數

C’ij:從站點Si

更新

Sj

分段

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

StoreCost=

Xi

di

Xi:0ifFnotstoredatSi

1ifFstoredatSi

di:

站點

Si

存儲分段

F的代價i=1m2.2.3數據的分配設計分配的簡化模型目標函數min[tiMINCij+Xj

ui

C’ij] +Xidi

i=1j=1i=1mmm2.2.3數據的分配設計分配方法“最佳適應”方法（非冗余分配）

Bij=

k

Fkj

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

Bij=

k

Fkj

Rki

-c

k

j’jFkj’

Uki

i片段下標j站點下標

k應用下標Fkj

應用k在站點j上激活的頻率

Rki

應用k被激活一次,對片段i讀的次數

Uki

應用k被激活一次,對片段i寫的次數

Nki

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

Bij=

kFkj*Nki

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

kFkj*Rki

-c*k

j’≠j

Fkj’*Uki如果Bij

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

2.2.3數據的分配設計垂直分片分配方法rs其他站點tRtRRs網絡A1A2AsAt

A32.2.3數據的分配設計垂直分片分配方法假設關系R垂直分片Rs和Rt,Rs分配到s站點,Rt分配到t站點.應用組As:自站點s發出,只使用Rs,得益

BAs=

Fks

Nki

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

BAt=

Fkt

Nki

(kAt)應用組A1:由站點r發出,原先使用Rt或Rs(本地),現在要遠程，損失

BA1=

Fkr

Nki

(kA1)應用組A2:由站點r發出,原先使用R(本地),現在要兩次遠程，損失

BA2=

Fkr

Nki

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

BA1=

Fkj

Nki

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

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