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

內(nèi)容簡(jiǎn)介兩種設(shè)計(jì)策略（Top-down和Bottom-up）分片的定義及作用水平分片垂直分片分片的表示方法分配設(shè)計(jì)數(shù)據(jù)復(fù)制技術(shù)Top_Down和

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

Top_Down:

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

Bottom-UP:

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

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

基于五步遞歸實(shí)現(xiàn):1.需求分析2.概念設(shè)計(jì)：E-R表示、全局概念模式和外模式3.分布設(shè)計(jì)：數(shù)據(jù)分片和分配，局部概念模式及映射4.物理設(shè)計(jì)：片段存儲(chǔ)和索引5.性能調(diào)優(yōu)（Tuning）設(shè)計(jì)策略-Top-down需求分析系統(tǒng)需求說明書調(diào)優(yōu)概念設(shè)計(jì)外部模式定義全局概念模式視圖設(shè)計(jì)分布設(shè)計(jì)局部概念模式物理設(shè)計(jì)局部物理模式3.2分片的定義及作用

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

數(shù)據(jù)分布要求方案1：公司總部保留全部數(shù)據(jù)。方案2：各單位只保留自己的數(shù)據(jù)。方案3：公司總部保留全部數(shù)據(jù)，各分公司只保留自己?jiǎn)挝坏臄?shù)據(jù)。 系統(tǒng)采用以上不同方案，對(duì)應(yīng)需求不同的數(shù)據(jù)分配方案。如:

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

總部（EMP）分公司1（無(wú)）分公司2（無(wú)）總部（EMP0）分公司1（EMP1）分公司2（EMP2）總部（EMP）分公司1（EMP1）分公司2（EMP2）場(chǎng)地0場(chǎng)地1場(chǎng)地2方案1方案2方案33.2.1分片的定義

定義分片（Fragmentation)：對(duì)全局?jǐn)?shù)據(jù)的劃分。片段（Fragment）：是分布式數(shù)據(jù)庫(kù)中數(shù)據(jù)的存儲(chǔ)單位。劃分的結(jié)果稱為片段。分配（Allocation）：對(duì)片段的存儲(chǔ)場(chǎng)地的指定，稱為分配。當(dāng)片段存儲(chǔ)在一個(gè)以上場(chǎng)地時(shí)，稱為數(shù)據(jù)復(fù)制（Replication）。如果每個(gè)片段只存儲(chǔ)在一個(gè)場(chǎng)地，稱為數(shù)據(jù)分割（Partition）存儲(chǔ)。減少網(wǎng)絡(luò)傳輸量。如：采用數(shù)據(jù)復(fù)制，可就近訪問所需信息。需頻繁訪問的信息分片存儲(chǔ)在本地場(chǎng)地上。增大事務(wù)處理的局部性。局部場(chǎng)地上所須數(shù)據(jù)分片分配在各自的場(chǎng)地上，減少數(shù)據(jù)訪問的時(shí)間，增強(qiáng)局部事務(wù)效率。

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

副本分片設(shè)計(jì)過程3.2.4分片的原則在構(gòu)成分布式數(shù)據(jù)庫(kù)系統(tǒng)時(shí)，對(duì)系統(tǒng)進(jìn)行全盤考慮，使系統(tǒng)性能最優(yōu)。但無(wú)論如何進(jìn)行分片，必須遵循下面原則：完備性如果全局關(guān)系R劃分的片段為R1,R2,…,Rn，則對(duì)于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.5分片的種類水平分片：按元組進(jìn)行劃分，由分片條件決定。垂直分片：按關(guān)系屬性劃分，除關(guān)鍵字外，同一關(guān)系的某一屬性不允許出現(xiàn)在一個(gè)關(guān)系的多個(gè)分片中。混合分片：即包括水平分片也包括垂直分片。3.2.6分布透明性透明性：指對(duì)用戶和高層系統(tǒng)隱蔽具體實(shí)現(xiàn)細(xì)節(jié)。數(shù)據(jù)透明性：分片透明性：指用戶不必考慮數(shù)據(jù)屬于哪個(gè)片段。分配透明性：指用戶不必考慮各個(gè)片段的存儲(chǔ)場(chǎng)地。局部映射透明性：用戶不必考慮數(shù)據(jù)的局部存儲(chǔ)形式。3.3水平分片3.3.1水平分片的定義水平分片是將關(guān)系的元組集劃分成若干不相交的子集。每個(gè)水平片段由關(guān)系中的某個(gè)屬性上的條件來定義，該屬性稱為分片屬性，該條件稱為分片條件。

定義設(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）按下面分片條件進(jìn)行分片：

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

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

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

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

σq(R)。例：

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

一個(gè)關(guān)系的分片不是基于關(guān)系本身的屬性，而是根據(jù)另一個(gè)與其有關(guān)聯(lián)性質(zhì)的關(guān)系的屬性來劃分，這種劃分為導(dǎo)出水平劃分。例如： 關(guān)系WORKS{ENO，PRJNO，HOURS}

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

將WORKS按DNO進(jìn)行水平分片，分片條件同EMP的水平分片條件，得到的導(dǎo)出水平分片為W1、W2和W3。實(shí)現(xiàn)過程如下：令：W′=WORKS

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

1水平分片設(shè)計(jì)的依據(jù)分片需求信息：來源于應(yīng)用因素和數(shù)據(jù)庫(kù)因素?cái)?shù)據(jù)庫(kù)因素：主要指全局模式中模式間的關(guān)聯(lián)關(guān)系

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

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

是完備的。若存在一個(gè)應(yīng)用按照BUDGET<200000訪問PROJ,則Pr

是不完備的。

最小性

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

若

Pr中加入PNAME=“Instrumentation”，則Pr不是最小的。（因?yàn)闆]有相應(yīng)的應(yīng)用與謂詞“PNAME=“Instrumentation””相關(guān)）例設(shè)計(jì)水平劃分PnoPnameFundsDnoLocP1Requirements135000D2NYP2Design310000D3NYP3Code300000D1MPLSP4Documentation450000D1MPLSP5Testing250000D4LAPROJ(PNO,Pname,Funds,Dno,Loc)AP1的簡(jiǎn)單謂詞：P1：Loc=“MPLS”P2：Loc=“NY”P3：Loc=“LA”AP2的簡(jiǎn)單謂詞：P4：Funds<=3000001得到小項(xiàng)謂詞集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.篩選簡(jiǎn)單謂詞p1,p2,p3是互斥的1得到24個(gè)最小謂詞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.篩選簡(jiǎn)單謂詞p1,p2,p3是互斥的Loc必須有一個(gè)選擇1得到24個(gè)最小謂詞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.化簡(jiǎn)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的簡(jiǎn)單謂詞：P1：Loc=“MPLS”P2：Loc=“NY”P3：Loc=“LA”AP2的簡(jiǎn)單謂詞：P4：Funds<=300000完全的最小的PnoPnameFundsDnoLocP1Requirements135000D2NYP2Design310000D3NYP3Code300000D1MPLSP4Documentation450000D1MPLSP5Testing250000D4LA

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

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

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

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

通過關(guān)鍵字將各垂直分片（E1、E2）進(jìn)行連接運(yùn)算得到原關(guān)系EMP.

證明：E1∞E2=EMP等價(jià)于如下SQL語(yǔ)句：

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

（Attr（E1）∩Attr（E2）=PK（EMP））3.4.4垂直分片的正確性判斷3.5混合分片例：一雇員關(guān)系EMP{ENO，ENAME，BIRTH，SALARY，DNO}，其元組同前，混合分片示意圖如下：ENOENAMEBIRTHSALARYDNOE1E21E22E23混合分片是既包括水平分片，又包括垂直分片的分片過程，稱為混合分片。3.5混合分片先進(jìn)行垂直分片，分為E1和E2。然后，將E2進(jìn)行水平分片，分為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分片的表示方法為了直觀地描述各種分片方式及便于后續(xù)查詢處理和查詢優(yōu)化方法的理解，對(duì)分片結(jié)果進(jìn)行表示圖形表示法樹形表示法

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

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

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

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

全局?jǐn)?shù)據(jù)經(jīng)過分片設(shè)計(jì)，得到各個(gè)劃分的片段，片段到物理場(chǎng)地的存儲(chǔ)映射過程稱為分配設(shè)計(jì)過程。分配類型非復(fù)制分配如果每個(gè)片段只存儲(chǔ)在一個(gè)場(chǎng)地上，稱為分割式分布，對(duì)應(yīng)的分布庫(kù)，稱為全分割式分布庫(kù)。復(fù)制分配如果每個(gè)片段在每個(gè)場(chǎng)地上存有副本，稱為全復(fù)制分配，對(duì)應(yīng)的分布庫(kù)稱為全復(fù)制分布庫(kù)。如果每個(gè)片段只在部分場(chǎng)地上存有副本，稱為部分復(fù)制分配，對(duì)應(yīng)的分布庫(kù)稱為部分復(fù)制分布庫(kù)。3.7

分配設(shè)計(jì)

例：設(shè)R為全局關(guān)系，R1、R2、R3為劃分的片段。3.7.1分配類型RR1R2R3R1R2R3場(chǎng)地1場(chǎng)地2場(chǎng)地3全局關(guān)系片段副本全分割數(shù)據(jù)庫(kù)

例：設(shè)R為全局關(guān)系，R1、R2、R3為劃分的片段。3.7.1分配類型部分復(fù)制數(shù)據(jù)庫(kù)RR1R2R3R3R2R1R2R3場(chǎng)地1場(chǎng)地2場(chǎng)地3全局關(guān)系片段副本

例：設(shè)R為全局關(guān)系，R1、R2、R3為劃分的片段。3.7.1分配類型RR1R2R3R3R2R1R1R1R2R3R2R3場(chǎng)地3場(chǎng)地2場(chǎng)地1全局關(guān)系片段副本全復(fù)制數(shù)據(jù)庫(kù)

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

如何進(jìn)行分段的分配需綜合考慮應(yīng)用和系統(tǒng)需求，以求得到一個(gè)最佳的分布式數(shù)據(jù)庫(kù)系統(tǒng)。

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

分配設(shè)計(jì)時(shí)應(yīng)考慮的具體因素。數(shù)據(jù)庫(kù)因素片段的大小；查詢對(duì)片段的選擇度（查詢結(jié)果的大小）。應(yīng)用因素查詢對(duì)片段的讀頻度；查詢對(duì)片段的更新頻度；更新查詢需訪問的片段；每個(gè)查詢的啟動(dòng)場(chǎng)地。3.7.2分配設(shè)計(jì)原則場(chǎng)地因素場(chǎng)地上存儲(chǔ)數(shù)據(jù)的單位代價(jià)；場(chǎng)地上處理數(shù)據(jù)的單位代價(jià)。網(wǎng)絡(luò)通訊因素網(wǎng)絡(luò)帶寬及網(wǎng)絡(luò)延遲；場(chǎng)地間的通信代價(jià)；

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

∑Sk

為所有場(chǎng)地上的片段存儲(chǔ)代價(jià)。∑Qi

為所有場(chǎng)地上的查詢處理代價(jià)。3.7.3分配模型

分配模型-總代價(jià)=∑Sk+∑Qi

Sk為在場(chǎng)地Sk上的片段存儲(chǔ)代價(jià)Sk=∑Fjk

Fjk

為片段Fj在場(chǎng)地Sk上的存儲(chǔ)代價(jià)∑Fjk

為所有在場(chǎng)地Sk上的片段存儲(chǔ)代價(jià)Fjk=Ck*SIZE（Fj）*Xjk

Ck為Sk上的單位存儲(chǔ)代價(jià)SIZE（Fj）為Fj的大小