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

1、徐俊剛 （),分布式數(shù)據(jù)庫(kù)系統(tǒng)及其應(yīng)用,2007年2月2007年6月,分布式數(shù)據(jù)庫(kù)系統(tǒng)設(shè)計(jì)概述 自頂向下設(shè)計(jì)分布式數(shù)據(jù)庫(kù) DATAID-D方法 實(shí)例研究：飛機(jī)訂票系統(tǒng) 自底向上設(shè)計(jì)分布式數(shù)據(jù)庫(kù),分布式數(shù)據(jù)庫(kù)系統(tǒng)設(shè)計(jì),第2章,分布式數(shù)據(jù)庫(kù)設(shè)計(jì)概述,數(shù)據(jù)庫(kù)系統(tǒng)軟硬件層次關(guān)系,1,創(chuàng)建方法,組合法,剖析網(wǎng)絡(luò)功能 剖析原有數(shù)據(jù)庫(kù)系統(tǒng) 解決數(shù)據(jù)的一致性、完整性和可靠性 難度較大 通常是異構(gòu)或者同構(gòu)異質(zhì)DDBS,分布式數(shù)據(jù)庫(kù)設(shè)計(jì)概述,數(shù)據(jù)庫(kù)系統(tǒng)軟硬件層次關(guān)系,1,重構(gòu)法,根據(jù)實(shí)現(xiàn)環(huán)境和用戶需求 按照DDBS的設(shè)計(jì)思想和方法 從總體設(shè)計(jì)做起，包括LDBS,重新建立一個(gè)DDBS 可有效解決數(shù)據(jù)一致性、完整性和

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

3、局關(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 =空集,ij,i,j=1,2,n(水平分片) Ri Rj =主鍵屬性,i,j=1,2,n(垂直分片),分片原則,職工關(guān)系 E (e#, name, loc, sal,) 查詢: Qa: select * Qb: select * from E from E where loc=Sa where loc=Sb

4、 and and .,舉例,e# NM Loc Sal E,5,7,8,Sa,1000,Sally,Sb,2500,Tom,Sa,500,Joe,e# NM Loc Sal,e# NM Loc Sal,5,8,Sa,1000,Tom,Sa,500,Joe,7,Sb,2500,Sally,.,.,.,.,F,站點(diǎn)Sa,站點(diǎn) Sb,舉例,基本水平分片 以關(guān)系自身的屬性性質(zhì)為基礎(chǔ)，執(zhí)行“選擇”操作，將關(guān)系分割成若干個(gè)不相交的片段。 R = R1, R2 R1 = loc=Sa(E) R2 = loc=Sb(E),基本水平分片,若 R = R1, R2, , Rn, 則 完整性 對(duì)于每一個(gè)元組 tR,

5、 RiR 使得 tRi 不相交性 對(duì)tRi, Rj 使得 tRj, i j 可重構(gòu)性 操作是 (可以忽略, 因?yàn)橥暾跃吞N(yùn)含著) R = R1, R2, , Rn P = p1, p2, , pn是一簡(jiǎn)單謂詞集合，為保證分片的正確性，P必須是： 完整的：同一分片中的任意兩個(gè)元組被應(yīng)用同樣概率訪問(wèn)。 最小的：集合P中的所有謂詞與應(yīng)用密切相關(guān)。 具有完整性和最小性不是必要條件, 但是對(duì)于簡(jiǎn)化分配問(wèn)題有好處,基本水平分片,例子 EMP ( E#, NAME, DEPT, JOB, SAL, TEL, ) DEPT=1,2 JOB=P, -P 假定，應(yīng)用經(jīng)常查詢的內(nèi)容是屬于部門(mén)1且是程序員的職員。 則

6、可能有的水平分段限定 P= DEPT=1 （不是完整的） P=DEPT=1, JOB=P （是完整的、最小的） P=DEPT=1, JOB=P, SAL500 （完整的，不是最小的）,基本水平分片,如何保證分片原則,“手工”檢查! e.g., R1 = loc=Sa E ; R2 = loc=Sb E 生成具有滿足分段原則的限定謂詞,基本水平分片,設(shè)有關(guān)系 E (e#,name,Loc,sal,A,), 查詢使用的簡(jiǎn)單謂詞（Ai Value）是: A5, Loc = Sa, Loc = Sb 下一步: - 生成 “小項(xiàng)” 謂詞 - 消除無(wú)用謂詞 給定簡(jiǎn)單謂詞集 Pr= p1, p2,. pn

7、, 則“小項(xiàng)”謂詞（minterm predicate）形式: p1* p2* pn* 這里 pk* 是 pk 或是 pk,謂詞生成舉例,(1) A5 Loc=SA Loc=SB (2) A5 Loc=SA (Loc=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),小項(xiàng)謂詞選擇,(9) (A5 Loc=SA Loc=SB (10) (A5 Loc=S

8、A (Loc=SB) (11) (A5 (Loc=SA) Loc=SB (12) (A5 (Loc=SA) (Loc=SB) (13) (A5) Loc=SA Loc=SB (14) (A5) Loc=SA (Loc=SB) (15) (A5) (Loc=SA) Loc=SB (16) (A5) (Loc=SA) (Loc=SB),小項(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é)果,注:無(wú)用段的消除依賴于應(yīng)用的語(yǔ)義,e.g.: 如果 L

9、OC 可以是 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 SB,小項(xiàng)選擇率（minterm selectivity） 對(duì)某一給定小項(xiàng)謂詞用戶查詢可能選擇到的元組數(shù) 訪問(wèn)頻率（Access frequency）用戶應(yīng)用訪問(wèn)數(shù)據(jù)的頻率 小項(xiàng)訪問(wèn)頻率可以通過(guò)用戶查詢頻率獲得,分片數(shù)量信息,例子 E(#, NM, LOC, SAL,) 有查詢應(yīng)用 Qa: select *Qb: select * from Efrom E where LOC=Sa where LOC=Sb an

10、d and .,如何選擇小項(xiàng)謂詞舉例,(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=Sa sal1000 E, loc=Sb sal1000E, loc=Sb sal1000 E ,三種選擇,Loc=Sa sal 1000,Loc=Sa sal 1000,Loc=Sb sal 1000,Loc=Sb sal 1000,R1,R3,R2,Qa: Select loc = Sa .,Qb: Select

11、 loc = Sb .,圖示,Loc=Sa sal 1000,Loc=Sa sal 1000,Loc=Sb sal 1000,Loc=Sb sal 1000,R1,Qa: Select loc = Sa .,Qb: Select loc = Sb .,此處元組有較 高的選擇概率,此處元組選 擇概率較低,分段內(nèi)元組選擇概率不等 因此 R1 不好.,理由,Loc=Sa sal 1000,Loc=Sa sal 1000,Loc=Sb sal 1000,Loc=Sb sal 1000,R2,Qa: Select loc = Sa .,Qb: Select loc = Sb .,元組選擇 概率相等,因此

12、 R2好.,R3不好 .,理由,導(dǎo)出分片 從另一個(gè)關(guān)系的屬性性質(zhì)或水平分片推導(dǎo)出來(lái) 例子 SC(S#, C#, GRADE) S ( S#, SNAME, AGE, SEX) 要求： 將SC劃分為男生各門(mén)課成績(jī)和女生的各門(mén)成績(jī),導(dǎo)出水平分片,按S的屬性導(dǎo)出 Define fragment SC1 as Select SC.S#,C#,GRADE From SC, S Where SC.S#=S.S# and SEX=M Define fragment SC2 as Select SC.S#,C#,GRADE From SC, S Where SC.S#=S.S# and SEX=F 按S的水平

13、分片（SF/SM）導(dǎo)出 Define fragment SC1 as Select * From SC Where S# in (Select SF.S from SF) Define fragment SC2 as Select * From SC Where S# in (Select SM.S from SM),導(dǎo)出水平分片例子,通過(guò)“投影”操作把一個(gè)全局關(guān)系的屬性分成若干組，基本目標(biāo)是將使用頻繁的屬性聚集在一起 全局關(guān)系R=Ri,i=1,2,n 如果屬性AR,必有ARi,i=1,2,n,而且RiRj=Ap,ij，Ap為R的碼或元組標(biāo)識(shí)符，則稱Ri,i=1,2,n是關(guān)系R的一個(gè)垂直分片。

14、 如果屬性AR,必有ARi,i=1,2,n,而且RiRj=（Ap, A-p),ij，A-p為R的一個(gè)或多個(gè)非碼屬性時(shí)，稱Ri,i=1,2,n是關(guān)系R的一個(gè)垂直群集。,垂直分片和垂直群集,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, MAGNU

15、M, DEPT),垂直分片/垂直群集例子,E1,E,E2,垂直分片例子,例子: E1(#,NM,LOC) E2(#,SAL) E(#,NM,LOC,SAL) E1(#,NM) E2(#,LOC) E3(#,SAL),?,垂直分片設(shè)計(jì),非鍵屬性 A1, A2,An 應(yīng)用 Q1, Q2,.,Qm freq(Qi) = Qi 的訪問(wèn)頻率,屬性的親和關(guān)系,R1K,A1,A2,A3 R2K,A4,A5,屬性和矩陣,行列調(diào)整尋找分割點(diǎn),屬性和矩陣,窮舉屬性親和矩陣的列排列 行與列要同時(shí)調(diào)整 發(fā)現(xiàn)好的 “分割點(diǎn)” 極大化每個(gè)分割內(nèi)的親合力（affinity）, 極小化跨分割的訪問(wèn),垂直分片算法,水平 基本：

16、 R 根據(jù) local屬性 導(dǎo)出 根據(jù)外鍵關(guān)系 垂直 R,分片小結(jié),混合分段,R,R1,R2,R11,R12,R21,R22,水平,垂直,分片小結(jié),混合分段的重構(gòu),R11,R12,R21,R22,水平,垂直,U,在滿足用戶需求的前提下, 把設(shè)計(jì)好的數(shù)據(jù)片段分配到相應(yīng)的站點(diǎn)上存儲(chǔ) 例子: E(#,NM,LOC,SAL) R1 = loc=Sa E ; R2 = loc=Sb E Qa: select where loc=Sa. Qb: select where loc=Sb,Site a,Site b,R1,R2 存 放在哪?,?,分配方法,非冗余分配設(shè)計(jì)方法,最佳適應(yīng)法,其他方法,冗余分配的設(shè)

17、計(jì)方法,所有得益站點(diǎn)法,附加復(fù)制法,應(yīng)用需求,確定非復(fù)制問(wèn)題的解 確定一組站點(diǎn)分配副本,確定非復(fù)制問(wèn)題的解 從最有益處增加副本 到附加復(fù)制無(wú)好處為止,什么是段的最好配置/什么是最好的冗余副本數(shù): 極小化查詢響應(yīng)時(shí)間 極大化吞吐量 極小化 “代價(jià)” . 約束? 有效的存儲(chǔ)空間 有效的帶寬, 站點(diǎn)處理能力, 保持 90% 的響應(yīng)時(shí)間低于 X（如0.5秒） .,單個(gè)片段 F 站點(diǎn) S1, Sm 變量 X1, , Xm 0 如果 F 不在 Sj上存儲(chǔ) 1 如果 F 在 Sj上存儲(chǔ) Total cost = Read Cost + Write Cost + Storage Cost 確定 Xj 的值,

18、1 j m, 使總代價(jià)極小,Xj =,讀代價(jià),Read cost = ti MIN Cij i:讀申請(qǐng)?jiān)凑军c(diǎn) ti: 站點(diǎn)Si上的讀申請(qǐng)激活次數(shù) Cij: 從 Si讀Sj站點(diǎn)分段F的代價(jià),i=1,m,j,寫(xiě)代價(jià),Write cost = Xj ui Cij i: 寫(xiě)申請(qǐng)?jiān)凑军c(diǎn) j: 被更新站點(diǎn) Xj: 0 if F not stored at Sj 1 if F stored at Sj ui: 站點(diǎn) Si 上更新激活次數(shù) Cij: 從站點(diǎn) Si 更新 Sj 分段 F 的代價(jià),i=1,j=1,m,m,Updates,ui,存儲(chǔ)代價(jià),Store Cost = Xi di Xi: 0 if F not store