第三章分布式數據庫設計

內容簡介兩種設計策略（Top-down和Bottom-up）分片的定義及作用水平分片垂直分片分片的表示方法分配設計數據復制技術Top_Down和

Bottom-UP應用場合

Top_Down:

適于新設計一個數據庫系統。（designedfromscratch）

Bottom-UP:

已存在許多數據庫系統，并將它們集成為一個數據庫。典型的數據集成的研究。本課程側重

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

基于五步遞歸實現:1.需求分析2.概念設計：E-R表示、全局概念模式和外模式3.分布設計：數據分片和分配，局部概念模式及映射4.物理設計：片段存儲和索引5.性能調優（Tuning）設計策略-Top-down需求分析系統需求說明書調優概念設計外部模式定義全局概念模式視圖設計分布設計局部概念模式物理設計局部物理模式3.2分片的定義及作用

例：某集團公司分地理位置分別在不同城市的總公司和下屬兩個分公司組成，彼此之間靠網絡相連接，業務管理由分布式數據庫系統完成。其網絡結構圖如下所示總公司分公司1分公司2網絡假設：人事系統中，有職工關系，定義為：EMP{ENO，EName，Salary，DNO}。場地定義：總公司為場地0，職工關系為EMP0分公司1為場地1，職工關系為EMP1分公司2為場地2，職工關系為EMP2EMP=EMP0+EMP1+EMP2為全局數據3.2分片的定義及作用

數據分布要求方案1：公司總部保留全部數據。方案2：各單位只保留自己的數據。方案3：公司總部保留全部數據，各分公司只保留自己單位的數據。 系統采用以上不同方案，對應需求不同的數據分配方案。如:

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

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

定義分片（Fragmentation)：對全局數據的劃分。片段（Fragment）：是分布式數據庫中數據的存儲單位。劃分的結果稱為片段。分配（Allocation）：對片段的存儲場地的指定，稱為分配。當片段存儲在一個以上場地時，稱為數據復制（Replication）。如果每個片段只存儲在一個場地，稱為數據分割（Partition）存儲。減少網絡傳輸量。如：采用數據復制，可就近訪問所需信息。需頻繁訪問的信息分片存儲在本地場地上。增大事務處理的局部性。局部場地上所須數據分片分配在各自的場地上，減少數據訪問的時間，增強局部事務效率。

提高數據的可用性和查詢效率。就近訪問數據分片或副本，可提高訪問效率。同時當某一場地出故障，若存在副本，非故障場地上的數據副本均是可用的。保證了數據的可用性、系統的可靠性。使負載均衡。減少數據訪問瓶頸，提高整個系統效率。3.2.2分片的作用3.2.3分片設計過程分片過程是將全局數據進行邏輯劃分和實際物理分配的過程。全局數據由分片模式定義分成各個片段數據，各個片段數據由分配模式定義存儲在各場地上。分片過程如下圖所示。GDBFDBPDB分片模式分配模式GDB：全局數據庫（GlobalDB）FDB：片段數據庫（FragmentationDB）PDB：物理數據庫（PhysicalDB）RR1R2R3R3R2R1R2R3場地1場地2場地3全局關系片段

副本分片設計過程3.2.4分片的原則在構成分布式數據庫系統時，對系統進行全盤考慮，使系統性能最優。但無論如何進行分片，必須遵循下面原則：完備性如果全局關系R劃分的片段為R1,R2,…,Rn，則對于R中任意數據項d（d

R），一定存在dRi（1i

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

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

i

n,1

j

n）。3.2.5分片的種類水平分片：按元組進行劃分，由分片條件決定。垂直分片：按關系屬性劃分，除關鍵字外，同一關系的某一屬性不允許出現在一個關系的多個分片中。混合分片：即包括水平分片也包括垂直分片。3.2.6分布透明性透明性：指對用戶和高層系統隱蔽具體實現細節。數據透明性：分片透明性：指用戶不必考慮數據屬于哪個片段。分配透明性：指用戶不必考慮各個片段的存儲場地。局部映射透明性：用戶不必考慮數據的局部存儲形式。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）按下面分片條件進行分片：

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

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

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

例如：設有雇員關系EMP{ENO,ENAME,SALARY,DNO}ENOENAMESALARYDNO001張三5100201002李四1400202003王五800203001張三1500201E1：002李四1400202E2：003王五1200203E3：水平分片實際上是關系的選擇操作，因此，用選擇操作σ表示，選擇條件為分片謂詞q，則R的片段可表示為：

σq(R)。例：

E1=σDno=201（EMP）3.3.2水平分片的操作SQL：SELECT*FROMEMPWHEREDNO=201導出水平分片定義

一個關系的分片不是基于關系本身的屬性，而是根據另一個與其有關聯性質的關系的屬性來劃分，這種劃分為導出水平劃分。例如： 關系WORKS{ENO，PRJNO，HOURS}

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

將WORKS按DNO進行水平分片，分片條件同EMP的水平分片條件，得到的導出水平分片為W1、W2和W3。實現過程如下：令：W′=WORKS

EMPW′：{ENO，PRJNO，HOURS，ENAME，SALARY，DNO}根據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通過上述三步驟得出按關系EMP的DNO屬性對WORKS進行水平劃分，得出WORKS的導出水平分片W1、W2和W3。3.3.3水平分片的設計

1水平分片設計的依據分片需求信息：來源于應用因素和數據庫因素數據庫因素：主要指全局模式中模式間的關聯關系

。用于導出水平分片。具有連接關系的片段應該就近存儲。應用需求因素：包括定性信息和定量的信息。定性信息（Qualitative）:查詢中的謂詞。簡單謂詞：只包括一個操作符號的查詢謂詞。小項謂詞：簡單謂詞的連接。定量信息（Quantitativeinformation）小項選擇度–sel(mi)：基于小項謂詞mi的查詢返回的元組個數。訪問頻率–acc(mi)：基于小項謂詞mi查詢訪問數據的頻率。保證水平分片設計的合理性，實際就是定義合理而有效的簡單謂詞集，并依此定義相應的小項謂詞集。3.3.3水平分片的設計2水平分片的設計準則為保證數據水平分片設計的合理性，其指導思想是定義具有完備性和最小性的一組簡單謂詞集。完備性：定義3.6最小性：定義3.7

完備性簡單謂詞集合Pr是完備的，當且僅當：任何應用程序訪問基于Pr分片得到的任何片段中的任何元組的機率均等。例如：PROJ(PNO,PNAME,BUDGET,LOC)Pr={LOC=“Montreal”,LOC=“NewYork”,LOC=“Paris”}如果有且只有一個應用按照location訪問PROJ,則Pr

是完備的。若存在一個應用按照BUDGET<200000訪問PROJ,則Pr

是不完備的。

最小性

如果簡單謂詞集Pr中的所有謂詞都是應用相關的，則Pr滿足最小性。例3.4:Pr={LOC=“Montreal”,LOC=“NewYork”,LOC=“Paris”,BUDGET≤200000,BUDGET>200000}是最小的。

若

Pr中加入PNAME=“Instrumentation”，則Pr不是最小的。（因為沒有相應的應用與謂詞“PNAME=“Instrumentation””相關）例設計水平劃分PnoPnameFundsDnoLocP1Requirements135000D2NYP2Design310000D3NYP3Code300000D1MPLSP4Documentation450000D1MPLSP5Testing250000D4LAPROJ(PNO,Pname,Funds,Dno,Loc)AP1的簡單謂詞：P1：Loc=“MPLS”P2：Loc=“NY”P3：Loc=“LA”AP2的簡單謂詞：P4：Funds<=3000001得到小項謂詞集M1={Loc=“MPLS”∧Loc=“NY”∧Loc=“LA”∧Funds<=300000}M2={Loc=“MPLS”∧Loc=“NY”∧Loc=“LA”∧Funds>300000}M3={Loc=“MPLS”∧Loc=“NY”∧Loc<>“LA”∧Funds<=300000}M4={Loc=“MPLS”∧Loc=“NY”∧Loc<>“LA”∧Funds>300000}M5={Loc=“MPLS”∧Loc<>“NY”∧Loc=“LA”∧Funds<=300000}M6={Loc=“MPLS”∧Loc<>“NY”∧Loc=“LA”∧Funds>300000}M7={Loc<>“MPLS”∧Loc=“NY”∧Loc=“LA”∧Funds<=300000}M8={Loc<>“MPLS”∧Loc=“NY”∧Loc=“LA”∧Funds>300000}M9={Loc<>“MPLS”∧Loc<>“NY”∧Loc=“LA”∧Funds<=300000}M10={Loc<>“MPLS”∧Loc<>“NY”∧Loc=“LA”∧Funds>300000}M11={Loc<>“MPLS”∧Loc=“NY”∧Loc<>“LA”∧Funds<=300000}M12={Loc<>“MPLS”∧Loc=“NY”∧Loc<>“LA”∧Funds>300000}M13={Loc=“MPLS”∧Loc<>“NY”∧Loc<>“LA”∧Funds<=300000}M14={Loc=“MPLS”∧Loc<>“NY”∧Loc<>“LA”∧Funds>300000}M15={Loc<>“MPLS”∧Loc<>“NY”∧Loc<>“LA”∧Funds<=300000}M16={Loc<>“MPLS”∧Loc<>“NY”∧Loc<>“LA”∧Funds>300000}2.篩選簡單謂詞p1,p2,p3是互斥的1得到24個最小謂詞M1={Loc=“MPLS”∧Loc=“NY”∧Loc=“LA”∧Funds<=300000}M2={Loc=“MPLS”∧Loc=“NY”∧Loc=“LA”∧Funds>300000}M3={Loc=“MPLS”∧Loc=“NY”∧Loc<>“LA”∧Funds<=300000}M4={Loc=“MPLS”∧Loc=“NY”∧Loc<>“LA”∧Funds>300000}M5={Loc=“MPLS”∧Loc<>“NY”∧Loc=“LA”∧Funds<=300000}M6={Loc=“MPLS”∧Loc<>“NY”∧Loc=“LA”∧Funds>300000}M7={Loc<>“MPLS”∧Loc=“NY”∧Loc=“LA”∧Funds<=300000}M8={Loc<>“MPLS”∧Loc=“NY”∧Loc=“LA”∧Funds>300000}M9={Loc<>“MPLS”∧Loc<>“NY”∧Loc=“LA”∧Funds<=300000}M10={Loc<>“MPLS”∧Loc<>“NY”∧Loc=“LA”∧Funds>300000}M11={Loc<>“MPLS”∧Loc=“NY”∧Loc<>“LA”∧Funds<=300000}M12={Loc<>“MPLS”∧Loc=“NY”∧Loc<>“LA”∧Funds>300000}M13={Loc=“MPLS”∧Loc<>“NY”∧Loc<>“LA”∧Funds<=300000}M14={Loc=“MPLS”∧Loc<>“NY”∧Loc<>“LA”∧Funds>300000}M15={Loc<>“MPLS”∧Loc<>“NY”∧Loc<>“LA”∧Funds<=300000}M16={Loc<>“MPLS”∧Loc<>“NY”∧Loc<>“LA”∧Funds>300000}2.篩選簡單謂詞p1,p2,p3是互斥的Loc必須有一個選擇1得到24個最小謂詞M9={Loc<>“MPLS”∧Loc<>“NY”∧Loc=“LA”∧Funds<=300000}M10={Loc<>“MPLS”∧Loc<>“NY”∧Loc=“LA”∧Funds>300000}M11={Loc<>“MPLS”∧Loc=“NY”∧Loc<>“LA”∧Funds<=300000}M12={Loc<>“MPLS”∧Loc=“NY”∧Loc<>“LA”∧Funds>300000}M13={Loc=“MPLS”∧Loc<>“NY”∧Loc<>“LA”∧Funds<=300000}M14={Loc=“MPLS”∧Loc<>“NY”∧Loc<>“LA”∧Funds>300000}M15={Loc<>“MPLS”∧Loc<>“NY”∧Loc<>“LA”∧Funds<=300000}M16={Loc<>“MPLS”∧Loc<>“NY”∧Loc<>“LA”∧Funds>300000}3.化簡M9={Loc<>“MPLS”∧Loc<>“NY”∧Loc=“LA”∧Funds<=300000}M10={Loc<>“MPLS”∧Loc<>“NY”∧Loc=“LA”∧Funds>300000}M11={Loc<>“MPLS”∧Loc=“NY”∧Loc<>“LA”∧Funds<=300000}M12={Loc<>“MPLS”∧Loc=“NY”∧Loc<>“LA”∧Funds>300000}M13={Loc=“MPLS”∧Loc<>“NY”∧Loc<>“LA”∧Funds<=300000}M14={Loc=“MPLS”∧Loc<>“NY”∧Loc<>“LA”∧Funds>300000}M9={Loc=“LA”∧Funds<=300000}M10={Loc=“LA”∧Funds>300000}M11={Loc=“NY”∧Funds<=300000}M12={Loc=“NY”∧Funds>300000}M13={Loc=“MPLS”∧Funds<=300000}M14={Loc=“MPLS”∧Funds>300000}AP1的簡單謂詞：P1：Loc=“MPLS”P2：Loc=“NY”P3：Loc=“LA”AP2的簡單謂詞：P4：Funds<=300000完全的最小的PnoPnameFundsDnoLocP1Requirements135000D2NYP2Design310000D3NYP3Code300000D1MPLSP4Documentation450000D1MPLSP5Testing250000D4LA

垂直分片是將一個關系按屬性集合分成不相交的子集（主關鍵字除外），屬性集合稱為分片屬性。即垂直分片是將關系按列縱向以屬性組劃分成若干片段。

Attr(R1)∪Attr(R2)∪…∪Attr(Rn)=Attr(R)，Attr(R)表示關系R的屬性{R1，R2，…，Rn}是關系R的無損分解Attr（Ri）∩Attr（Rj）=PK（R）PK(R)表示R主關鍵字3.4垂直分片例：一雇員關系：EMP{ENO，ENAME，BIRTH，SALARY，DNO}ENO，ENAME，BIRTH，SALARY，DNO為雇員編碼、雇員姓名、出生日期、工資、部門編號ENOENAMEBIRTHSALARYDNO001張三1960．5．21500201002李四1957．3．51400202003王五1985．2．412002033.4.1垂直分片的定義假設：E1{ENO，ENAME，BIRTH} E2{ENO，SALARY，DNO}則E1和E2元組分別為：E1元組：ENOENAMEBIRTH001張三1960．5．2002李四1957．3．5003王五1985．2．4E2元組：ENOSALARYDNO001150020100214002020031200203根據垂直分片條件，可知：E1和E2是EMP的無損分解。Attr（E1）∪Attr（E2）=Attr（EMP）Attr（E1）∩Attr（E2）={ENO}因此，E1和E2是EMP的垂直分片。3.4.2垂直分片的操作垂直分片的表示方法垂直分片是指定屬性集上的投影操作。用投影運算屬性∏表示，投影屬性為分片屬性。如上例E1、E2表示為：E1=

ENO，ENAME，BIRTH（EMP），SQL：SELECTENO，ENAME，BIRTHFROMEMPE2=

ENO，SALARY，DNO（EMP），SQL：SELECTENO，SALARY，DNOFROMEMP3.4.3垂直分片的設計影響因素應用需求:同一垂直片段中的多個屬性通常是被同一應用同時訪問.垂直分片設計的核心是根據用戶的應用需求如何正確地劃分屬性組。采用屬性緊密度（affinity）來度量屬性間的關系。緊密度：令Q={q1,q2,…,qm}是用戶的查詢應用，關系R{A1,A2,…,An}包含A1,A2,…,An屬性，則aff(Ai,Aj)表示屬性Ai,Aj的緊密度，描述為：為查詢應用qk在場地上同時訪問屬性Ai,Aj的次數為查詢應用qk在場地上的訪問頻率。復習分布庫的三個基本特點分布庫的分布透明性有哪些內容？分布庫的模式結構分片的原則和種類水平分片的表示方法、設計原則垂直分片的表示方法、設計原則3.4.3垂直分片的設計舉例：存在關系模式：T{C,C1,C2,C3,C4},存在4個場地有下面4查詢應用：AP1：selectC1fromTWhereC4=100AP2：selectC4fromTAP3：UpdateTsetC3=15whereC2=50AP4：UpdateTsetC1=5whereC3=10C1C2C3C4AP11001AP20001AP30110AP41010用例矩陣3.4.3垂直分片的設計C1C2C3C4AP11001AP20001AP30110AP41010用例矩陣C1C2C3C4S1S2S3S4AP110011020AP200010430AP301100040AP410103000C1C2C3C4親近度AP110013AP200017AP301104AP410103親近度矩陣3.4.3垂直分片的設計C1C2C3C4親近度AP110013AP200017AP301104AP410103C1C2C3C4C10033C20040C33400C43000C1C2C3C4C16033C20440C33470C43003計算對角線的親近度矩陣3.4.3垂直分片的設計C1C2C3C4C16033C20440C33470C43003計算對角線的親近度矩陣BondEnergy算法：該算法將親近度矩陣作為一個參數，產生一個聚合親近度矩陣。該矩陣對親近度矩陣的行和列重新排序，使得具有最大親近度的字段能在相同群集中“分組到一起”，然后基于此將表分裂為垂直片段。C1C2C160C206C334C430第一步，取前兩列，計算Bond（X1,X2)C1C2乘積C1600C2040C33412C4300Bond123.4.3垂直分片的設計第二步，剩余列的放置綜合貢獻值Cont(X1,X2,X3)=2*Bond(X1,X2)+2*(X2,X3)-2*(X1,X3)C0C3C1C1036C2040C3073C4003C1C2乘積C1600C2040C33412C4300Bond12C1C3C2C1630C2044C3374C4300C2C3CnC1030C2440C3470C40003.4.3垂直分片的設計第二步，剩余列的放置綜合貢獻值Cont(X1,X2,X3)=2*Bond(X1,X2)+2*(X2,X3)-2*(X1,X3)C0C3C1C1036C2040C3073C4003Bond(C0,C3)=0Bond(C3,C1)=18+21=39Bond(C0,C1)=0Cont(C0,C3,C1)=783.4.3垂直分片的設計第二步，剩余列的放置綜合貢獻值Cont(X1,X2,X3)=2*Bond(X1,X2)+2*(X2,X3)-2*(X1,X3)Bond(C1,C3)=18+21=39Bond(C3,C2)=16+28=44Bond(C1,C2)=12Cont(C0,C3,C1)=142C1C3C2C1630C2044C3374C43003.4.3垂直分片的設計第二步，剩余列的放置綜合貢獻值Cont(X1,X2,X3)=2*Bond(X1,X2)+2*(X2,X3)-2*(X1,X3)Bond(C2,C3)=16+28=44Bond(C3,Cn)=0Bond(C2,Cn)=0Cont(C0,C3,C1)=88C2C3CnC1030C2440C3470C4000綜合貢獻值Cont(X1,X2,X3)=2*Bond(X1,X2)+2*(X2,X3)-2*(X1,X3)C1C3C2C1630C2044C3374C4300C0C4C1C3C2C103630C200044C300374C403300C1C4C3C2C16330C20044C33074C43300C1C3C4C2C16330C20404C33704C43030Cont=2*0+2*27-2*0=54Cont=2*27+2*9-2*39=-6Cont=2*9+2*0-2*44=-70C1C3C2C4CnC163030C204400C337400C430030Cont=2*0+2*0-2*0=03.4.3垂直分片的設計C4C1C3C2C13630C20044C30374C43300C4C1C3C2C43300C13630C30374C20044調整3.4.3垂直分片的設計C1C2C3C4C1上半角（TC）C2C3C4下半角（BC）目標函數：Z=TCW×BCW-BOCW２第三步，將表劃分為垂直片段目標函數：Z=TCW×BCW-BOCW２C1C2C3C4親近度AP110013AP200017AP301104AP410103TCW＝AFF(AP1)＋AFF(AP2)+AFF(AP4)=3+7+3=13BCW=0BOCW=AFF(AP3)=4Z=13*0-42=-16C4C1C3C2C43300C13630C30374C20044目標函數：Z=TCW×BCW-BOCW２C4C1C3C2C43300C13630C30374C20044C1C2C3C4親近度AP110013AP200017AP301104AP410103TCW＝AFF(AP1)＋AFF(AP2)=3+7=10BCW=AFF(AP3)=4BOCW=AFF(AP4)=3Z=10*4-32=31目標函數：Z=TCW×BCW-BOCW２C4C1C3C2C43300C20044C30374C13630C1C2C3C4親近度AP110013AP200017AP301104AP410103TCW＝AFF(AP2)=7BCW=AFF(AP3)+AFF(AP4)=4+3=7BOCW=AFF(AP1)=3Z=7*7-32=40C4C1C3C2C43300C13630C30374C20044第四步，內嵌劃分的判斷C4C1C3C2C13630C30374C20044C43300C4C1C3C2C43300C13630C30374C20044C1C3C2C4C16303C33740C20440C43003C1C2C3C4親近度AP110013AP200017AP301104AP410103C1C3C2C4C16303C33740C20440C43003Z=-13Z=-5第四步，內嵌劃分的判斷C4C1C3C2C43300C13630C30374C20044正確性檢驗垂直分片的正確性檢驗同水平分片正確性檢驗一樣。垂直分片也應滿足完備性、可重構性和不相交性。以例3.3.2為例進行正確性驗證。完備性證明（Attr（E1）∪Attr（E2）=Attr（EMP））證明：{ENO，ENAME，BIRTH}∪{ENO，SALARY，DNO}={ENO，ENAME，BIRTH，SALARY，DNO}滿足完備性。3.4.4垂直分片的正確性判斷可重構性證明

通過關鍵字將各垂直分片（E1、E2）進行連接運算得到原關系EMP.

證明：E1∞E2=EMP等價于如下SQL語句：

SELECTE1.ENO，E1.ENAME，E1.BIRTH，E2.SALARY，E2.DNOFROME1、E2WHEREE1.ENO=E2.ENO可知：E1∞E2連接操作得到的關系元組同EMP相同，滿足可重構性。3.4.4垂直分片的正確性判斷不相交性證明

（Attr（E1）∩Attr（E2）=PK（EMP））3.4.4垂直分片的正確性判斷3.5混合分片例：一雇員關系EMP{ENO，ENAME，BIRTH，SALARY，DNO}，其元組同前，混合分片示意圖如下：ENOENAMEBIRTHSALARYDNOE1E21E22E23混合分片是既包括水平分片，又包括垂直分片的分片過程，稱為混合分片。3.5混合分片先進行垂直分片，分為E1和E2。然后，將E2進行水平分片，分為E21、E22和E23。分片表示為：

E1=

ENO，ENAME，BIRTH（EMP）

E2=

ENO，SALARY，DNO（EMP）

E21=

Dno=201（E2）

E22=

Dno=202（E2）

E23=

Dno<>201ANDDno<>202（E2）

3.6分片的表示方法為了直觀地描述各種分片方式及便于后續查詢處理和查詢優化方法的理解，對分片結果進行表示圖形表示法樹形表示法

3.6.1圖形表示法一個整體矩形表示為全局關系；矩形的一部分表示分段關系；按水平劃分表示水平分段；按垂直劃分表示垂直分段；混合劃分既有水平劃分，又有垂直劃分。

3.6.1圖形表示法E1E2E3E1E2E1E21E22E23E23a水平分片b垂直分片c混合分片關系E水平分片為E1、E2和E3。關系E垂直分片為E1、E2。關系E混合分片為E1（垂直分片）和對垂直分片E2的水平分片E21、E22和E23。

定義3.10：一個分片樹由以下幾部分組成：根節點表示全局關系葉子節點表示最后得到的片段中間節點表示分片過程的中間結果邊表示分片，并用h（水平）和v（垂直）表示分片類型節點名表示全局關系名和片段名3.6.2分片樹表示法

3.6.2分片樹表示法EMPhE1E2E3（a）水平分片樹EMPvE1E2（b）垂直分片樹EMPvE1E2（c）混合分片樹EMPvE1hE21E22E23練習題Student={sno,sname,sex,birth,major,class,dno}Grade={sno,cno,grade}其中sno,sname,sex,birth全學院共有8個系，dno分別為1，2，…8。其中cno為課程號，grade為考試成績。根據需要，要求將學生關系Student中的{sno,class}保存在場地0，其他屬性和成績Grade按“系號”1－4，5－6分別保存在場地1和場地2上。請根據上述敘述，完成下列題目：1.將全局模式進行分片，寫出分片定義和分片條件。2.指出各分片的類型，并畫出“分片樹”

全局數據經過分片設計，得到各個劃分的片段，片段到物理場地的存儲映射過程稱為分配設計過程。分配類型非復制分配如果每個片段只存儲在一個場地上，稱為分割式分布，對應的分布庫，稱為全分割式分布庫。復制分配如果每個片段在每個場地上存有副本，稱為全復制分配，對應的分布庫稱為全復制分布庫。如果每個片段只在部分場地上存有副本，稱為部分復制分配，對應的分布庫稱為部分復制分布庫。3.7

分配設計

例：設R為全局關系，R1、R2、R3為劃分的片段。3.7.1分配類型RR1R2R3R1R2R3場地1場地2場地3全局關系片段副本全分割數據庫

例：設R為全局關系，R1、R2、R3為劃分的片段。3.7.1分配類型部分復制數據庫RR1R2R3R3R2R1R2R3場地1場地2場地3全局關系片段副本

例：設R為全局關系，R1、R2、R3為劃分的片段。3.7.1分配類型RR1R2R3R3R2R1R1R1R2R3R2R3場地3場地2場地1全局關系片段副本全復制數據庫

系統是采用全分割數據庫或全復制數據庫或部分復制數據庫，需根據應用需求及系統運行效率等因素來綜合考慮。從應用角度出發，須考慮：增加事務處理的局部性；提高系統的可靠性和可用性；增加系統的并行性。從系統角度出發，須考慮：降低系統的運行和維護開銷；使系統負載均衡；方便一致性維護。3.7.1分配類型

如何進行分段的分配需綜合考慮應用和系統需求，以求得到一個最佳的分布式數據庫系統。

一般，如果存在只讀查詢/更新查詢>>1，則定義為復制式分配好些。3.7.1分配類型

分配設計時應考慮的具體因素。數據庫因素片段的大小；查詢對片段的選擇度（查詢結果的大小）。應用因素查詢對片段的讀頻度；查詢對片段的更新頻度；更新查詢需訪問的片段；每個查詢的啟動場地。3.7.2分配設計原則場地因素場地上存儲數據的單位代價；場地上處理數據的單位代價。網絡通訊因素網絡帶寬及網絡延遲；場地間的通信代價；

分配設計者要綜合考慮各種因素，建立多個分配模型，分別估計各種模型的代價，通過對比、分析，得出最佳的分配方案。總代價=∑Sk+∑Qi

∑Sk

為所有場地上的片段存儲代價。∑Qi

為所有場地上的查詢處理代價。3.7.3分配模型

分配模型-總代價=∑Sk+∑Qi

Sk為在場地Sk上的片段存儲代價Sk=∑Fjk

Fjk

為片段Fj在場地Sk上的存儲代價∑Fjk

為所有在場地Sk上的片段存儲代價Fjk=Ck*SIZE（Fj）*Xjk

Ck為Sk上的單位存儲代價SIZE（Fj）為Fj的大小