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

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

內(nèi)容簡介

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

Bottom-UP應(yīng)用場合

Top_Down:

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

Bottom-UP:

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

top-down設(shè)計(jì)中存在的關(guān)鍵技術(shù)。3.1兩種設(shè)計(jì)策略3.1兩種設(shè)計(jì)策略3.1.1Top-down設(shè)計(jì)過程

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

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

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

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

3.2.1分片的定義分片（Fragmentation)

對全局?jǐn)?shù)據(jù)的劃分。片段

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

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

3.2.2分片的作用

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

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

分片模式：定義從全局關(guān)系到片段模式的映射關(guān)系。分配模式：定義從片段關(guān)系到物理關(guān)系的映射關(guān)系。1：N時(shí)為復(fù)制；1：1時(shí)為分割。RR1R2R3R3R2R1R2R3場地1場地2場地3全局關(guān)系片段

副本3.2分片的定義及作用

3.2.3分片設(shè)計(jì)過程GDB=∑FDBi

表示全局?jǐn)?shù)據(jù)庫是劃分的多個(gè)片段數(shù)據(jù)庫的集合。F(GDB)=FDBF()：表示分片模式映射函數(shù)；能從全局?jǐn)?shù)據(jù)庫得到片段數(shù)據(jù)庫F-1(FDB)=GDBF-1()表示分片模式的反映射函數(shù)；能從片段數(shù)據(jù)庫得到全局?jǐn)?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分片的原則完備性：所有全局?jǐn)?shù)據(jù)必須映射到某個(gè)片段上?？芍貥?gòu)性：所有片段必須可以重新構(gòu)成全局?jǐn)?shù)據(jù)。不相交性：劃分的各片段所包含的數(shù)據(jù)不允許相同。3.2分片的定義及作用3.2.4分片的原則完備性如果全局關(guān)系R劃分的片段為R1,R2,…,Rn，則對于R中任意數(shù)據(jù)項(xiàng)d（d

R），一定存在dRi（1i

n）?？芍貥?gòu)性如果全局關(guān)系R劃分的片段為R1,R2,…,Rn，則存在關(guān)系運(yùn)算，使得R=R1R2…

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

i

n,1

j

n）。3.2分片的定義及作用3.2.5分片的種類水平分片：按元組進(jìn)行劃分，由分片條件決定。垂直分片：按關(guān)系屬性劃分，除關(guān)鍵字外，同一關(guān)系的某一屬性不允許出現(xiàn)在一個(gè)關(guān)系的多個(gè)分片中?；旌戏制杭窗ㄋ椒制舶ù怪狈制?。屬性或元組關(guān)系根據(jù)需要進(jìn)行相應(yīng)的分片3.2分片的定義及作用3.2.6分布透明性透明性：指對用戶和高層系統(tǒng)隱蔽具體實(shí)現(xiàn)細(xì)節(jié)。分布透明性指分片透明性、分配透明性和局部映射透明性。分片透明性：指用戶不必考慮數(shù)據(jù)屬于哪個(gè)片段。分配透明性：指用戶不必考慮各個(gè)片段的存儲(chǔ)場地。局部映射透明性：用戶不必考慮數(shù)據(jù)的局部存儲(chǔ)形式。3.3水平分片

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

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

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

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

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

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

例如：設(shè)有雇員關(guān)系EMP{ENO,ENAME,SALARY,DNO}ENOENAMESALARYDNO001張三1500201002李四1400202003王五800203基本水平分片劃分關(guān)系元組的屬性，屬于這個(gè)關(guān)系本身3.3水平分片將關(guān)系EMP分成了三個(gè)子關(guān)系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關(guān)系模式相同；E1∪E2∪E3=EMPE1∩E2=Φ，E1∩E3=Φ，E2∩E3=Φ因此，E1、E2和E3是EMP的水平分片。3.3水平分片導(dǎo)出水平分片一個(gè)關(guān)系的分片不是基于關(guān)系本身的屬性，而是根據(jù)另一個(gè)與其有關(guān)聯(lián)性質(zhì)的關(guān)系的屬性來劃分。例如： 關(guān)系WORKS{ENO，PRJNO，HOURS}

關(guān)系EMP{ENO，ENAME，SALARY，DNO}

將WORKS按DNO進(jìn)行水平分片，分片條件同EMP的水平分片條件，得到的導(dǎo)出水平分片為W1、W2和W3。

3.3水平分片導(dǎo)出水平分片計(jì)算如下：令：W′=WORKS

EMPW′：{ENO，PRJNO，HOURS，ENAME，SALARY，DNO}根據(jù)DNO對W′進(jìn)行水平分片如：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 通過上述三步驟得出按關(guān)系EMP的DNO屬性對WORKS進(jìn)行水平劃分，得出WORKS的導(dǎo)出水平分片W1、W2和W3。3.3水平分片3.3.2水平分片的操作水平分片實(shí)際上是關(guān)系的選擇操作，因此，用選擇操作σ表示，選擇條件為分片謂詞q，則R的片