第二章分布式數(shù)據(jù)庫系統(tǒng)設計-Read課件

第二章分布式數(shù)據(jù)庫系統(tǒng)設計2008.9第二章分布式數(shù)據(jù)庫系統(tǒng)設計分布式數(shù)據(jù)庫系統(tǒng)設計概述自頂而下設計分布式數(shù)據(jù)庫系統(tǒng)自頂而下設計分布式數(shù)據(jù)庫系統(tǒng)設計實例自底向上分布式數(shù)據(jù)庫系統(tǒng)設計分布式數(shù)據(jù)庫系統(tǒng)的優(yōu)點和存在的技術(shù)問題分布式數(shù)據(jù)庫系統(tǒng)設計概述分布式數(shù)據(jù)庫系統(tǒng)的構(gòu)建方法分布式數(shù)據(jù)庫設計的內(nèi)容分布式數(shù)據(jù)庫設計目標分布式數(shù)據(jù)庫設計方法分布式數(shù)據(jù)庫系統(tǒng)的構(gòu)建方法組合法：自底向上重構(gòu)法：自頂向下組合法網(wǎng)絡DBMS1DBMS2DBMSn分布式協(xié)調(diào)管理系統(tǒng)用戶1用戶2用戶m重構(gòu)法網(wǎng)絡分布式數(shù)據(jù)庫管理系統(tǒng)用戶1用戶2用戶m分布式數(shù)據(jù)庫設計的內(nèi)容集中式數(shù)據(jù)庫設計內(nèi)容數(shù)據(jù)庫設計概念模式設計（描述數(shù)據(jù)庫應用所使用的全部數(shù)據(jù)）內(nèi)模式設計（概念模式到存儲模式的映射）圍繞數(shù)據(jù)庫而展開的應用設計分布式數(shù)據(jù)庫的設計內(nèi)容分布式數(shù)據(jù)庫設計全局模式設計每個站點的局部數(shù)據(jù)庫的設計數(shù)據(jù)分片設計位置分配設計圍繞分布式數(shù)據(jù)庫而進行的應用設計，需要考慮：各應用的原發(fā)站點各應用在每個站點被激活的次數(shù)各應用對所要求訪問的每個數(shù)據(jù)對象的訪問次數(shù)、類型和統(tǒng)計分布分布式數(shù)據(jù)庫設計的目標分布式數(shù)據(jù)庫的本地性或近地性：盡量減少對網(wǎng)絡的使用，減少網(wǎng)絡通信次數(shù)和通信量，90%的數(shù)據(jù)在本地訪問控制數(shù)據(jù)的適當冗余：為提高本地性、并發(fā)度和可靠性要增加副本；為維護數(shù)據(jù)一致性，要減少副本工作負荷分布：將工作負荷分布到各個站點，充分利用每個站點的計算機能力和資源，提高并行運行程度存儲能力和費用：雖然存儲費用與CPU、I/O、以及傳輸?shù)馁M用相比不重要，但必須考慮各站點的存儲能力分布式數(shù)據(jù)庫設計的方法自頂向下設計方法：從頭開始構(gòu)建數(shù)據(jù)庫自底向上設計方法：聚集現(xiàn)存數(shù)據(jù)庫來設計分布式數(shù)據(jù)庫自頂而下設計分布式數(shù)據(jù)庫系統(tǒng)自頂向下設計分布式數(shù)據(jù)庫的步驟和內(nèi)容數(shù)據(jù)的分片設計數(shù)據(jù)庫片段的位置分配設計自頂向下設計分布式數(shù)據(jù)庫的步驟和內(nèi)容需求分析：收集用戶數(shù)據(jù)庫應用的規(guī)格說明，產(chǎn)生一種無歧義的定義和在設計數(shù)據(jù)庫中要考慮的元素分類，這些信息被收集在設計的數(shù)據(jù)字典中概念設計：產(chǎn)生全局、綜合數(shù)據(jù)庫模式的一種概念規(guī)格說明和在此模式上執(zhí)行應用的概念規(guī)格說明邏輯設計：將綜合概念模式轉(zhuǎn)換成一給定DBMS類型的數(shù)據(jù)庫模式分布設計：以全局的、與站點無關(guān)的模式作為輸入，以產(chǎn)生分布式數(shù)據(jù)庫各站點的子模式作為輸出，包括分片設計和片段的分配設計物理設計：要遵照選定DBMS的能力和特點進行數(shù)據(jù)的分片設計分片設計的基本目的產(chǎn)生一個對全局數(shù)據(jù)合適的劃分方案，使得在數(shù)據(jù)分配和存儲時減少應用中的操作量，增加應用的本地性數(shù)據(jù)分片的基本類型和方法水平分片垂直分片混合分片水平分片初級水平分片：以關(guān)系自身的屬性性質(zhì)為基礎，執(zhí)行選擇操作，將關(guān)系劃分成若干不相交的片段對全局關(guān)系進行合適的水平分片，需要確定一組不相交的、完整的限定語，即：令P={P1,P2,…,Pn}是一簡單謂詞的集合，為了正確而有效地分片，則P必須是“完整的”和“最小的”，滿足：只有當屬于同一分片中的任意兩個元組被任一應用以同等概率進行訪問時，稱謂語集合P是完整的。如果集合P的全部謂詞與應用密切相關(guān)，稱P是最小的。例：全局關(guān)系EMP(E#,NAME,DEPT,JOB,SAL,TEL,…)DEPT={1,2}JOB={‘P’,’-P’}，若應用經(jīng)常查詢的內(nèi)容是屬于部門1且是程序員的雇員。P={DEPT=1}是不完整的P={DEPT=1,JOB=‘P’}是正確的，也是合適的，因為這樣可以分為：{DEPT=1,JOB=‘P’}、{DEPT=2,JOB=‘P’}、{DEPT=1,JOB=‘-P’}、{DEPT=2,JOB=‘-P’}四個片段，滿足完整、最小、不相交P={DEPT=1,JOB=‘P’，SAL>500}是完整的，但不是最小的導出水平分片：不是以自身的屬性性質(zhì)為基礎，而是從另一個關(guān)系的屬性性質(zhì)或水平分片推導出來的，采用導出式水平分段可以使片段之間的連接變得更容易連接圖：又稱結(jié)合圖，當一個應用需要對兩個全局關(guān)系進行連接操作時，理論上應該對兩個關(guān)系的全部元組進行比較。如果R水平分片為{Ri}，i=1,2,…,n；S水平分片為{Sj}，j=1,2,…,m，需要將Ri與S進行比較，有以下可能：不相交，無相同屬性值元組存在相交，有相同屬性值元組存在當連接增多時，這種連接不容易判斷，用連接圖：圓圈表示關(guān)系的片段，小圓圈之間的無向邊表示非空片段之間的連接全連接：連接圖中包括兩個關(guān)系R和S之間的片段之間的所有連接全連接圖簡單連接圖分區(qū)連接圖分區(qū)連接圖：連接圖中不包含某些連接，且一個連接圖由兩個或多個子圖組成，而這些子圖之間無連接邊簡單連接圖：連接圖中不包含某些連接，且每個子圖只有一條邊垂直分片：確定一個全局關(guān)系R的垂直分片需要根據(jù)應用以“同樣方式”訪問的屬性來進行分組,垂直分片不同于垂直集群，垂直分片的組必須只在某個鍵屬性上重疊，其他屬性不可重疊；垂直集群的組在其他屬性上也可以重疊。垂直集群有時候更好的實現(xiàn)本地性垂直分片的基本目標：使頻繁使用的屬性聚集在一起，當各個應用只使用一個屬性子集時，存在一個理想的垂直分片垂直分片的方法分裂法：將全局關(guān)系逐漸分成片段，分成組法：將屬性逐步聚集成片段，合數(shù)據(jù)片段的位置分配設計數(shù)據(jù)片段位置分配方法分配方式非冗余分配：每個片段在一個站點上，用最佳適應法冗余分配：每個片段映射到一個或多個站點，需要確定片段復制的程度，復制的利益隨著檢索與更新間的比值而增加所有得益站點法：先確定非復制問題的解，然后在全部站點中確定一組站點，給這組站點中的每個站點分配片段的一個副本，這樣做的好處要比付出的代價大附加復制法：首先確定非復制問題的解，然后從最有益處起逐步附加復制的副本，此過程直到“附加復制”已無明顯的好處為止數(shù)據(jù)片段分配的費用和得益估算i表示片段下標J表示站點下標K表示應用下標Fkj表示應用k在站點j上被激活的頻率Rki表示應用k被激活一次，對片段i進行檢索訪問的次數(shù)Uki表示應用k被激活一次，對片段i進行更新訪問的次數(shù)Nki=Rki+Uki表示應用k被激活一次，對片段i進行訪問的總次數(shù)水平分片非冗余分配使用“最佳適應法”。將片段i分配到訪問Ri次數(shù)最多的那個站點，在站點j上Ri的本地訪問次數(shù)為：冗余分配使用“所有站點得益法”。將片段i的副本分配到所有得益站點j上，所謂得益站點是指在這些站點上，應用的檢索訪問費用總比從任何一個其他站點發(fā)出的應用對Ri的更新訪問的費用要低，估算差額：估算max（Bij）=C是更新訪問與檢索訪問的代價比，如果Bij>0則，在站點j上存放Ri的一個副本，Ri就被分配在j’上冗余分配使用“附加復制法”。另Di表示片段Ri的冗余度，（副本個數(shù)），F(xiàn)i表示Ri在每個站點全都復制的得益