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

1、徐俊剛徐俊剛（)20072007年年2 2月月20072007年年6 6月月分布式數(shù)據(jù)庫系統(tǒng)設(shè)計概述分布式數(shù)據(jù)庫系統(tǒng)設(shè)計概述自頂向下設(shè)計分布式數(shù)據(jù)庫自頂向下設(shè)計分布式數(shù)據(jù)庫DATAID-DDATAID-D方法方法實例研究：飛機訂票系統(tǒng)實例研究：飛機訂票系統(tǒng)自底向上設(shè)計分布式數(shù)據(jù)庫自底向上設(shè)計分布式數(shù)據(jù)庫分布式數(shù)據(jù)庫系統(tǒng)設(shè)計分布式數(shù)據(jù)庫系統(tǒng)設(shè)計 第第2章章分布式數(shù)據(jù)庫設(shè)計概述分布式數(shù)據(jù)庫設(shè)計概述1創(chuàng)建方法創(chuàng)建方法1.1 組合法組合法 剖析網(wǎng)絡(luò)剖析網(wǎng)絡(luò)功能功能剖析原有剖析原有數(shù)據(jù)庫系數(shù)據(jù)庫系統(tǒng)統(tǒng)解決數(shù)據(jù)解決數(shù)據(jù)的一致性、的一致性、完整性和完整性和可靠性可靠性難度較大難度較大 通常通常是異構(gòu)或是異構(gòu)

2、或者同構(gòu)異者同構(gòu)異質(zhì)質(zhì)DDBS用戶1用戶2用戶n分布式協(xié)調(diào)管理系統(tǒng)DBMS1DBMS2DBMSm 網(wǎng)絡(luò)分布式數(shù)據(jù)庫設(shè)計概述分布式數(shù)據(jù)庫設(shè)計概述1DDBSDDBS創(chuàng)建方法創(chuàng)建方法1.1 重構(gòu)法重構(gòu)法 根據(jù)實現(xiàn)環(huán)境根據(jù)實現(xiàn)環(huán)境和用戶需求和用戶需求按照按照DDBS的的設(shè)計思想和方設(shè)計思想和方法法從總體設(shè)計做從總體設(shè)計做起，包括起，包括LDBS,重新建重新建立一個立一個DDBS可有效解決數(shù)可有效解決數(shù)據(jù)一致性、完據(jù)一致性、完整性和可靠性整性和可靠性問題。問題。 通常是同通常是同構(gòu)異質(zhì)或同構(gòu)構(gòu)異質(zhì)或同構(gòu)同質(zhì)同質(zhì)DDBS用戶1用戶2用戶n分布式數(shù)據(jù)庫管理系統(tǒng) 網(wǎng)絡(luò)1.2 DDBS DDBS設(shè)計內(nèi)容設(shè)計內(nèi)容

3、1 1 分布式數(shù)據(jù)庫設(shè)計概述分布式數(shù)據(jù)庫設(shè)計概述DDBS設(shè)計設(shè)計DDB設(shè)計設(shè)計應(yīng)用設(shè)計應(yīng)用設(shè)計全局模式設(shè)計全局模式設(shè)計局部數(shù)據(jù)庫設(shè)計局部數(shù)據(jù)庫設(shè)計相關(guān)應(yīng)用需求相關(guān)應(yīng)用需求各個應(yīng)用的原發(fā)站點各個應(yīng)用的原發(fā)站點各個應(yīng)用在每個站點的激活頻率各個應(yīng)用在每個站點的激活頻率各個應(yīng)用對要求訪問數(shù)據(jù)對象的各個應(yīng)用對要求訪問數(shù)據(jù)對象的訪問次數(shù)、類型和統(tǒng)計分布訪問次數(shù)、類型和統(tǒng)計分布分片和分布分片和分布1.3 DDBS DDBS設(shè)計目標(biāo)設(shè)計目標(biāo)1 1 分布式數(shù)據(jù)庫設(shè)計概述分布式數(shù)據(jù)庫設(shè)計概述DDBS設(shè)計目標(biāo)設(shè)計目標(biāo)本地性或近地性本地性或近地性存儲能力和費用存儲能力和費用盡量減少通信次數(shù)和通信量，盡量減少通信次數(shù)和

4、通信量，90/10準(zhǔn)則準(zhǔn)則分片和分布方案（分片和分布方案（本地和遠(yuǎn)程訪問次數(shù)本地和遠(yuǎn)程訪問次數(shù)）擇優(yōu)）擇優(yōu)控制數(shù)據(jù)適當(dāng)冗余控制數(shù)據(jù)適當(dāng)冗余冗余增加了可靠性、可用性，提高了效率冗余增加了可靠性、可用性，提高了效率維護(hù)數(shù)據(jù)一致性開銷增加維護(hù)數(shù)據(jù)一致性開銷增加工作負(fù)荷分布工作負(fù)荷分布各站點可以分擔(dān)整個工作任務(wù)各站點可以分擔(dān)整個工作任務(wù)本地性降低本地性降低1.4 DDBS DDBS設(shè)計方法設(shè)計方法1 1 分布式數(shù)據(jù)庫設(shè)計概述分布式數(shù)據(jù)庫設(shè)計概述DDBS設(shè)計方法設(shè)計方法自頂向下方法（重構(gòu)法）自頂向下方法（重構(gòu)法）混合方法混合方法自底向上方法（組合法）自底向上方法（組合法）2.1 步驟和內(nèi)容步驟和內(nèi)容2

5、2 自頂向下設(shè)計自頂向下設(shè)計DDBDDB需求分析概念設(shè)計視圖設(shè)計分布設(shè)計物理設(shè)計觀察與監(jiān)視系統(tǒng)需求全局概念模式訪問模式外部模式定義局部概念模式物理模式用戶輸入視圖集成用戶輸入反饋反饋自頂向下設(shè)計過程 假若有全局關(guān)系R 被分片為子關(guān)系(片段)集合 R = R1, R2, , Rn, 則 R滿足 完整性?x R, Ri R 必有必有 x Ri ，i=1,2,n 可重構(gòu)性? 存在函數(shù) g 使得R = g(R1, R2, , Rn)即，R= Ri (水平分片）,R= Ri （垂直分片） 不相交性Ri Rj =空集,ij,i,j=1,2,n(水平分片)Ri Rj =主鍵屬性,i,j=1,2,n(垂直分片

6、) 2.2 數(shù)據(jù)的分片設(shè)計數(shù)據(jù)的分片設(shè)計2 2 自頂向下設(shè)計自頂向下設(shè)計DDBDDB 分片原則分片原則 職工關(guān)系 E (e#, name, loc, sal,) 查詢: Qa: select * Qb: select *from E from Ewhere loc=Sa where loc=Sband and .兩個站點 : Sa, Sb Qa QbSaSb2.2 數(shù)據(jù)的分片設(shè)計數(shù)據(jù)的分片設(shè)計2 2 自頂向下設(shè)計自頂向下設(shè)計DDBDDB 舉例舉例 e# NM Loc Sal E578Sa 1000SallySb 2500TomSa 500Joee# NM Loc Sale# NM Loc Sa

7、l58Sa 1000TomSa 500Joe7Sb 2500Sally.FF站點Sa站點 Sb2.2 數(shù)據(jù)的分片設(shè)計數(shù)據(jù)的分片設(shè)計2 2 自頂向下設(shè)計自頂向下設(shè)計DDBDDB 舉例舉例 基本水平分片 以關(guān)系自身的屬性性質(zhì)為基礎(chǔ)，執(zhí)行以關(guān)系自身的屬性性質(zhì)為基礎(chǔ)，執(zhí)行“選選擇擇”操作，將關(guān)系分割成若干個不相交的操作，將關(guān)系分割成若干個不相交的片段。片段。 RR = R1, R2 R1 = loc=Sa(E) R2 = loc=Sb(E)2.2 數(shù)據(jù)的分片設(shè)計數(shù)據(jù)的分片設(shè)計2 2 自頂向下設(shè)計自頂向下設(shè)計DDBDDB 基本水平分片基本水平分片 若 R = R1, R2, , Rn, 則 完整性 對于

8、每一個元組 t R, Ri R 使得 t Ri 不相交性 對 t Ri, Rj 使得 t Rj, i j 可重構(gòu)性 操作是 (可以忽略, 因為完整性就蘊含著) R = R1, R2, , Rn P = p1, p2, , pn是一簡單謂詞集合，為保證分片的正確性，P必須是： 完整的：同一分片中的任意兩個元組被應(yīng)用同樣概率訪問。 最小的：集合P中的所有謂詞與應(yīng)用密切相關(guān)。 具有完整性和最小性不是必要條件, 但是對于簡化分配問題有好處2.2 數(shù)據(jù)的分片設(shè)計數(shù)據(jù)的分片設(shè)計2 2 自頂向下設(shè)計自頂向下設(shè)計DDBDDB 基本水平分片基本水平分片 例子EMP ( E#, NAME, DEPT, JOB,

9、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, SAL500 （完整的，不是最小的）2.2 數(shù)據(jù)的分片設(shè)計數(shù)據(jù)的分片設(shè)計2 2 自頂向下設(shè)計自頂向下設(shè)計DDBDDB 基本水平分片基本水平分片 如何保證分片原則 “手工”檢查!e.g., R1 = loc=Sa E ; R2 = loc=Sb E 生成具有滿足分段原則的限定謂詞2.2 數(shù)據(jù)的分片設(shè)計數(shù)據(jù)的分片設(shè)計2 2 自頂向下設(shè)計自

10、頂向下設(shè)計DDBDDB 基本水平分片基本水平分片 設(shè)有關(guān)系 E (e#,name,Loc,sal,A,), 查詢使用的簡單謂詞（Ai Value）是: A5, Loc = Sa, Loc = Sb 下一步: - 生成 “小項” 謂詞- 消除無用謂詞 給定簡單謂詞集 Pr= p1, p2,. pn , 則“小項”謂詞（minterm predicate）形式:p1* p2* pn* 這里 pk* 是 pk 或是 pk2.2 數(shù)據(jù)的分片設(shè)計數(shù)據(jù)的分片設(shè)計2 2 自頂向下設(shè)計自頂向下設(shè)計DDBDDB 謂詞生成舉例謂詞生成舉例(1) A5 Loc=SA Loc=SB(2) A5 Loc=SA (Loc

11、=SB)(3) A5 (Loc=SA) Loc=SB(4) A5 (Loc=SA) (Loc=SB)(5) A5) Loc=SA Loc=SB(6) A5) Loc=SA (Loc=SB)(7) A5) (Loc=SA) Loc=SB(8) A5) (Loc=SA) (Loc=SB)2.2 數(shù)據(jù)的分片設(shè)計數(shù)據(jù)的分片設(shè)計2 2 自頂向下設(shè)計自頂向下設(shè)計DDBDDB小項謂詞選擇小項謂詞選擇 (9) (A5 Loc=SA Loc=SB(10) (A5 Loc=SA (Loc=SB)(11) (A5 (Loc=SA) Loc=SB(12) (A5 (Loc=SA) (Loc=SB)(13) (A5)

12、Loc=SA Loc=SB(14) (A5) Loc=SA (Loc=SB)(15) (A5) (Loc=SA) Loc=SB(16) (A5) (Loc=SA) (Loc=SB)2.2 數(shù)據(jù)的分片設(shè)計數(shù)據(jù)的分片設(shè)計2 2 自頂向下設(shè)計自頂向下設(shè)計DDBDDB小項謂詞選擇小項謂詞選擇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é)果分片結(jié)果2.2 數(shù)據(jù)的分片設(shè)計數(shù)據(jù)的分片設(shè)計2 2 自頂向下設(shè)計自頂向下設(shè)計DDBDDB注注: :無用段的消除依賴于應(yīng)用

13、的語義無用段的消除依賴于應(yīng)用的語義e.g.: 如果 LOC 可以是 SA, SB, 則最終分段集合應(yīng)該加上R4:5 A 10 Loc SA Loc SB R8:A 5 Loc SA Loc SB R12:A 10 Loc SA Loc SB2.2 數(shù)據(jù)的分片設(shè)計數(shù)據(jù)的分片設(shè)計2 2 自頂向下設(shè)計自頂向下設(shè)計DDBDDB 小項選擇率（minterm selectivity） 對某一給定小項謂詞用戶查詢可能選擇到的元組數(shù) 訪問頻率（Access frequency）用戶應(yīng)用訪問數(shù)據(jù)的頻率 小項訪問頻率可以通過用戶查詢頻率獲得2.2 數(shù)據(jù)的分片設(shè)計數(shù)據(jù)的分片設(shè)計2 2 自頂向下設(shè)計自頂向下設(shè)計DDB

14、DDB分片數(shù)量信息分片數(shù)量信息 例子 E(#, NM, LOC, SAL,) 有查詢應(yīng)用Qa: select *Qb: select * from Efrom E where LOC=Sa where LOC=Sb and and .2.2 數(shù)據(jù)的分片設(shè)計數(shù)據(jù)的分片設(shè)計2 2 自頂向下設(shè)計自頂向下設(shè)計DDBDDB如何選擇小項謂詞舉例如何選擇小項謂詞舉例(1) Pr = R1 = E (2) Pr = LOC=Sa, LOC=Sb R2= loc=Sa E, loc=Sb E (3) Pr = LOC=Sa, LOC=Sb, Sal1000 R3= loc=Sa sal1000 E, loc=S

15、a sal1000 E, loc=Sb sal1000E, loc=Sb sal1000 E 三種選擇三種選擇2.2 數(shù)據(jù)的分片設(shè)計數(shù)據(jù)的分片設(shè)計2 2 自頂向下設(shè)計自頂向下設(shè)計DDBDDBLoc=Sa sal 1000Loc=Sa sal 1000Loc=Sb sal 1000Loc=Sb sal 1000RR1RR3RR2Qa: Select loc = Sa .Qb: Select loc = Sb .RR2 是好的( RR1 , RR3不好 ) 2.2 數(shù)據(jù)的分片設(shè)計數(shù)據(jù)的分片設(shè)計2 2 自頂向下設(shè)計自頂向下設(shè)計DDBDDB圖示圖示Loc=Sa sal 1000Loc=Sa sal 1

16、000Loc=Sb sal 1000Loc=Sb sal 1000RR1Qa: Select loc = Sa .Qb: Select loc = Sb .此處元組有較高的選擇概率此處元組選擇概率較低分段內(nèi)元組選擇概率不等因此 RR1 不好.2.2 數(shù)據(jù)的分片設(shè)計數(shù)據(jù)的分片設(shè)計2 2 自頂向下設(shè)計自頂向下設(shè)計DDBDDB理由理由Loc=Sa sal 1000Loc=Sa sal 1000Loc=Sb sal R1在Site1, R2在Site2, R3在Site3. B R1和R2在Site1, R2和R3在Site3.另已知有如下應(yīng)用(所有應(yīng)用的頻率相同) A1: 在Site1上發(fā)出, 讀5

17、個 R1記錄, 5個 R2記錄 A2: 在Site3上發(fā)出, 讀5個R3記錄 , 5個R2記錄 A3: 在Site2上發(fā)出, 讀10個R2記錄.問: 1. 如果以本地應(yīng)用為主要設(shè)計目標(biāo), 那個分配較優(yōu)? 2. 假定A3改為要修改10個R2記錄, 并仍以本地應(yīng)用為其設(shè)計目標(biāo), 則那個分配方案較優(yōu)?站點站點1站點站點2站點站點3站點站點3站點站點2站點站點1A1R1A3R2A2R3A1R1, R2A3A2R2, R3方方案案A方方案案B讀取讀取更新更新10101055 圖2-12 COMPANY關(guān)系數(shù)據(jù)庫模式, 主碼用下劃線標(biāo)出 EMPLOYFNAMEMINIT LNAMEESSNBDATEADD

18、RESSSEXSALARYSUPERSSNDNODEPARTMENTDNAMEDNOMGRSSNMGRSTARTDATEDEPT_LOCATIONDNODLOCATIONPROJECTPNAMEPNOPLOCATIONDNO WORKS_ONESSNPNOHOURSDEPENDENTESSNDEPENDENT_NAMESEXBDATERELATIONSHIPExercise 2 三個站點A,B,C 部門1（總部），部門2，部門3 在站點B上頻繁訪問EMPLOYEE,PROJECT中有關(guān)工作在部門2的雇員和該部門管轄的項目信息 在站點C上頻繁訪問EMPLOYEE,PROJECT中有關(guān)工作在部門3

19、的雇員和該部門管轄的項目信息 雇員信息主要是指EMPLOYEE表中的FNAME,ESSN,SALARY,SUPERSSN屬性 A，B，C站點上頻繁訪問本站點所在部門的項目工時信息 站點A供公司總部使用，經(jīng)常存取為保險目的而紀(jì)錄的DEPENDENT信息外，還定期地存取所有雇員和項目的信息FNAMEMINIT LNAME ESSN SALARYSUPERSSN DNOAlicia J Zelaya 999887777 25000 987654321 2Jennifer S Wallace 987654321 43000 888665555 2Ahmad V Jabbar 987987987 250

20、00 987654321 2EMPD2DEP2DNAMEDNOMGRSSNMGRSTARTDATEAdministr 2987654321 2003-01-01DEP2_LOCSDNODLOCATION 2StatlondDEP2_WORKSON ESSNPNOHOURS333445555 10 10.0999887777 30 30.0999887777 10 10.0987987987 10 35.0987987987 30 5.0987654321 30 20.0987654321 30 15.0DEP2_PROJECTPNAMEPNOPLOCATIONDNOComputer 10 St

21、artlond 2Newbenef 30 Startlond 2圖2-13 站點的片段分配（b）站點B上的對應(yīng)于部門2的關(guān)系片段FNAMEMINIT LNAME SSN SALARYSUPERSSN DNOJohn B Smith 123456789 30000 333445555 3Franklin T Wong 333445555 40000 888665555 3Ramesh K Narayan 666884444 38000 333445555 3Joyce A English 453453453 25000 333445555 3EMPD3DEP3DNAMEDNOMGRSSNMGRS

22、TARTDATEResearch 3333445555 2003-05-22DEP3_LOCSDNODLOCATION 3Bellaire 3Sugarlnd 3HoustonDEP3_WORKSON ESSNPNOHOURS123456789 1 32.5123456789 2 7.5666884444 3 40.0453453453 1 20.0453453453 2 20.0333445555 2 10.0333445555 3 10.0 DEP3_PROJECTPNAMEPNOPLOCATIONDNOProduct X 1 Bellaire 3Product Y 2 ugarlnd 3

23、Product Z 3 Houston 3圖2-13 站點的片段分配（a）站點C上的對應(yīng)于部門3的關(guān)系片段 圖2-15 站點A上的對應(yīng)于部門1（總部）的片斷 EMPLOYEEPROJECTPNAMEPNUMERPLOCATIONDNUMDEPENDENTESSNDEPENDENT_NAMESEXBDATERELATIONSHIPFNAMEMINIT LNAME SSN SALARYSUPERSSN DNOAlicia J Zelaya 999887777 25000 987654321 2Jennifer S Wallace 987654321 43000 888665555 2Ahmad V Jabbar 987987987 25000 987654321 2John B Smith 123456789 30000 333445555 3Franklin T Wong 333445555 40000 888665555 3Ramesh K Narayan 666884444 38000 333445555 3Joyce A English 453453453 25000 333445555 3Exercise 3 建立百貨連鎖店分