第2講分布式數(shù)據(jù)庫的設計-水平分片

第三章分布式數(shù)據(jù)庫的設計

內(nèi)容簡介

解決數(shù)據(jù)分布的問題如何對分布式數(shù)據(jù)庫進行邏輯劃分如何對邏輯劃分結(jié)果進行實際物理分配3.1兩種設計策略（Top-down和Bottom-up）3.2分片的定義級作用3.3水平分片3.4垂直分片3.5混合分片3.6分片的表示方法3.7分配設計Top_Down和

Bottom-UP應用場合

Top_Down:

適于新設計一個數(shù)據(jù)庫系統(tǒng)。（designedfromscratch）

Bottom-UP:

已存在許多數(shù)據(jù)庫系統(tǒng)，并將它們集成為一個數(shù)據(jù)庫。典型的數(shù)據(jù)集成的研究。本課程側(cè)重

top-down設計中存在的關鍵技術。3.1兩種設計策略3.1兩種設計策略3.1.1Top-down設計過程

基于五步遞歸實現(xiàn):1.需求分析（Requirementanalysis）2.概念設計、視圖集成、E-R表示、轉(zhuǎn)換到關系模式3.分布設計、數(shù)據(jù)分片和分配4.物理設計5.性能調(diào)優(yōu)（Tuning）3.1兩種設計策略需求分析系統(tǒng)需求說明書調(diào)優(yōu)概念設計外部模式定義全局概念模式視圖設計分布設計局部概念模式物理設計局部物理模式3.1.1-Top-down3.1.2-Bottom-upDatabase1Database2Databasen…Translator1Translator2Translatorn…InS1InS2InSn…IntegratorGCS3.1兩種設計策略3.2分片的定義及作用

例：某集團公司分地理位置分別在不同城市的總公司和下屬兩個分公司組成，彼此之間靠網(wǎng)絡相連接，業(yè)務管理由分布式數(shù)據(jù)庫系統(tǒng)完成。其網(wǎng)絡結(jié)構(gòu)圖如下所示總公司分公司1分公司2網(wǎng)絡假設：人事系統(tǒng)中，有職工關系，定義為：EMP{ENO，EName，Salary，DNO}。場地定義：總公司為場地0，職工關系為EMP0分公司1為場地1，職工關系為EMP1分公司2為場地2，職工關系為EMP2EMP=EMP0+EMP1+EMP2為全局數(shù)據(jù)3.2分片的定義及作用數(shù)據(jù)分布要求方案1：公司總部保留全部數(shù)據(jù)。方案2：各單位只保留自己的數(shù)據(jù)。方案3：公司總部保留全部數(shù)據(jù)，各分公司只保留自己單位的數(shù)據(jù)。 系統(tǒng)采用以上不同方案，對應需求不同的數(shù)據(jù)分配方案。如:

上面三種方案中，除方案1外，均須進行分片定義。方案3中，分公司的數(shù)據(jù)信息除本場地存儲外，總部場地也存儲一份相同信息，存在在不同場地上互稱副本。

總部（EMP）分公司1（無）分公司2（無）總部（EMP0）分公司1（EMP1）分公司2（EMP2）總部（EMP）分公司1（EMP1）分公司2（EMP2）場地0場地1場地2方案1方案2方案33.2分片的定義及作用

3.2.1分片的定義分片（Fragmentation)

對全局數(shù)據(jù)的劃分。片段

劃分的結(jié)果稱為片段

是分布式數(shù)據(jù)庫中數(shù)據(jù)的存儲單位。分配（Allocation）：對片段的存儲場地的指定，稱為分配。數(shù)據(jù)復制：片段存儲在一個以上場地時數(shù)據(jù)分割：片段只存儲在一個場地3.2分片的定義及作用

3.2.2分片的作用

減少網(wǎng)絡傳輸量。如：采用數(shù)據(jù)復制，可就近訪問所需信息。需頻繁訪問的信息分片存儲在本地場地上。增大事務處理的局部性。局部場地上所須數(shù)據(jù)分片分配在各自的場地上，減少數(shù)據(jù)訪問的時間，增強局部事務效率。

提高數(shù)據(jù)的可用性和查詢效率。就近訪問數(shù)據(jù)分片或副本，可提高訪問效率。同時當某一場地出故障，若存在副本，非故障場地上的數(shù)據(jù)副本均是可用的。保證了數(shù)據(jù)的可用性、數(shù)據(jù)的完整性和系統(tǒng)的可靠性。使負載均衡。減少數(shù)據(jù)訪問瓶頸，提高整個系統(tǒng)效率。3.2分片的定義及作用3.2.3分片設計過程分片過程是將全局數(shù)據(jù)進行邏輯劃分和實際物理分配的過程。全局數(shù)據(jù)劃分為片段數(shù)據(jù)片段數(shù)據(jù)經(jīng)過分配得到物理數(shù)據(jù)GDBFDBPDB分片模式分配模式GDB：全局數(shù)據(jù)庫（GlobalDB）FDB：片段數(shù)據(jù)庫（FragmentationDB）PDB：物理數(shù)據(jù)庫（PhysicalDB）3.2分片的定義及作用

分片模式：定義從全局關系到片段模式的映射關系。分配模式：定義從片段關系到物理關系的映射關系。1：N時為復制；1：1時為分割。RR1R2R3R3R2R1R2R3場地1場地2場地3全局關系片段

副本3.2分片的定義及作用

3.2.3分片設計過程GDB=∑FDBi

表示全局數(shù)據(jù)庫是劃分的多個片段數(shù)據(jù)庫的集合。F(GDB)=FDBF()：表示分片模式映射函數(shù)；能從全局數(shù)據(jù)庫得到片段數(shù)據(jù)庫F-1(FDB)=GDBF-1()表示分片模式的反映射函數(shù)；能從片段數(shù)據(jù)庫得到全局數(shù)據(jù)P(FDB)=PDBP-1(PDB)=FDBP()：表示分配模式映射函數(shù)，能從片段數(shù)據(jù)庫經(jīng)得到物理數(shù)據(jù)庫P-1()表示分配模式的反映射函數(shù)。能從物理數(shù)據(jù)庫得到片段數(shù)據(jù)庫。3.2分片的定義及作用

3.2.4分片的原則完備性：所有全局數(shù)據(jù)必須映射到某個片段上?？芍貥?gòu)性：所有片段必須可以重新構(gòu)成全局數(shù)據(jù)。不相交性：劃分的各片段所包含的數(shù)據(jù)不允許相同。3.2分片的定義及作用3.2.4分片的原則完備性如果全局關系R劃分的片段為R1,R2,…,Rn，則對于R中任意數(shù)據(jù)項d（d

R），一定存在dRi（1i

n）。可重構(gòu)性如果全局關系R劃分的片段為R1,R2,…,Rn，則存在關系運算，使得R=R1R2…

Rn。不相交性如果全局關系R水平劃分的片段為R1,R2,…,Rn，則任意兩個不同的片段的交集為空，即RiRj=（ij,1

i

n,1

j

n）。3.2分片的定義及作用3.2.5分片的種類水平分片：按元組進行劃分，由分片條件決定。垂直分片：按關系屬性劃分，除關鍵字外，同一關系的某一屬性不允許出現(xiàn)在一個關系的多個分片中。混合分片：即包括水平分片也包括垂直分片。屬性或元組關系根據(jù)需要進行相應的分片3.2分片的定義及作用3.2.6分布透明性透明性：指對用戶和高層系統(tǒng)隱蔽具體實現(xiàn)細節(jié)。分布透明性指分片透明性、分配透明性和局部映射透明性。分片透明性：指用戶不必考慮數(shù)據(jù)屬于哪個片段。分配透明性：指用戶不必考慮各個片段的存儲場地。局部映射透明性：用戶不必考慮數(shù)據(jù)的局部存儲形式。3.3水平分片

3.3.1水平分片的定義水平分片是將關系的元組集劃分成若干不相交的子集。分片屬性用來劃分元組的屬性分片條件

用來劃分元組的條件定義設有一個關系R，{R1，R2，…，Rn}為R的子關系的集合，如果{R1，R2，…，Rn}滿足以下條件，則稱其為關系R的水平分片，Ri稱為R的一個水平片段。（1）R1，R2，…，Rn與R具有相同的關系模式（2）R1∪R2∪…∪Rn=R

（3）Ri∩Rj=Φ（i≠j，1≤i≤n）3.3水平分片按下面分片條件進行分段：

E1：滿足（Dno=201）的所有分組；

E2：滿足（Dno=202）的所有分組；

E3：滿足（Dno〈〉201ANDDno〈〉202）的所有分組。

例如：設有雇員關系EMP{ENO,ENAME,SALARY,DNO}ENOENAMESALARYDNO001張三1500201002李四1400202003王五800203基本水平分片劃分關系元組的屬性，屬于這個關系本身3.3水平分片將關系EMP分成了三個子關系E1:部門編號Dno=201的元組E2:部門編號Dno=202的元組E3:部門編號Dno<>201ANDDno<>202分片屬性：部門編號Dno分片條件：

Dno=201Dno=202Dno<>201ANDDno<>202003王五1200203002李四1400202001張三1500201ENOENAMESALARYDNO001張三1500201002李四1400202003王五800203E1：E2：E3：3.3水平分片水平分片正確性判定根據(jù)水平分片定義，滿足：E1,E2,E3和EMP關系模式相同；E1∪E2∪E3=EMPE1∩E2=Φ，E1∩E3=Φ，E2∩E3=Φ因此，E1、E2和E3是EMP的水平分片。3.3水平分片導出水平分片一個關系的分片不是基于關系本身的屬性，而是根據(jù)另一個與其有關聯(lián)性質(zhì)的關系的屬性來劃分。例如： 關系WORKS{ENO，PRJNO，HOURS}

關系EMP{ENO，ENAME，SALARY，DNO}

將WORKS按DNO進行水平分片，分片條件同EMP的水平分片條件，得到的導出水平分片為W1、W2和W3。

3.3水平分片導出水平分片計算如下：令：W′=WORKS

EMPW′：{ENO，PRJNO，HOURS，ENAME，SALARY，DNO}根據(jù)DNO對W′進行水平分片如：W1=σDNO=201（W′）=σDNO=201（WORKS

EMP）=WORKS

σDNO=201（EMP）=WORKS

E1只保留WORKS的屬性W1=

attr（WORKS)W1）=

attr（WORKS）

(WORKS

E1）=WORKS

E1

稱為半連接。 同理：W2=WORKS

E2 W3=WORKS

E3 通過上述三步驟得出按關系EMP的DNO屬性對WORKS進行水平劃分，得出WORKS的導出水平分片W1、W2和W3。3.3水平分片3.3.2水平分片的操作水平分片實際上是關系的選擇操作，因此，用選擇操作σ表示，選擇條件為分片謂詞q，則R的片