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

1、第三章分布式數(shù)據(jù)庫的設(shè)計第三章分布式數(shù)據(jù)庫的設(shè)計 分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用內(nèi)內(nèi) 容容 簡簡 介介 解決數(shù)據(jù)分布的問題解決數(shù)據(jù)分布的問題n如何對分布式數(shù)據(jù)庫進(jìn)行邏輯劃分如何對分布式數(shù)據(jù)庫進(jìn)行邏輯劃分n如何對邏輯劃分結(jié)果進(jìn)行實際物理分配如何對邏輯劃分結(jié)果進(jìn)行實際物理分配n3.1兩種設(shè)計策略（兩種設(shè)計策略（ Top-down 和和 Bottom-up ）n3.2分片的定義級作用分片的定義級作用n3.3水平分片水平分片n3.4垂直分片垂直分片n3.5混合分片混合分片n3.6分片的表示方法分片的表示方法n3.7分配設(shè)計分配設(shè)計分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用p Top_Down和和 Bottom-UP應(yīng)用場

2、合應(yīng)用場合n Top_Down: 適于新設(shè)計一個數(shù)據(jù)庫系統(tǒng)。適于新設(shè)計一個數(shù)據(jù)庫系統(tǒng)。 （designed from scratch）n Bottom-UP: 已存在許多數(shù)據(jù)庫系統(tǒng)，并將它已存在許多數(shù)據(jù)庫系統(tǒng)，并將它們集成為一個數(shù)據(jù)庫。典型的數(shù)據(jù)集成的研究。們集成為一個數(shù)據(jù)庫。典型的數(shù)據(jù)集成的研究。 本課程側(cè)重本課程側(cè)重 top-down 設(shè)計中存在的關(guān)鍵技術(shù)。設(shè)計中存在的關(guān)鍵技術(shù)。3.13.1兩種設(shè)計策略兩種設(shè)計策略分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.13.1兩種設(shè)計策略兩種設(shè)計策略3.1.1 Top-down 設(shè)計過程設(shè)計過程 基于五步遞歸實現(xiàn)基于五步遞歸實現(xiàn):1. 需求分析（需求分析（Requ

3、irement analysis）2. 概念設(shè)計、視圖集成、概念設(shè)計、視圖集成、E-R 表示、轉(zhuǎn)換到關(guān)表示、轉(zhuǎn)換到關(guān)系模式系模式3. 分布設(shè)計、數(shù)據(jù)分片和分配分布設(shè)計、數(shù)據(jù)分片和分配4. 物理設(shè)計物理設(shè)計5. 性能調(diào)優(yōu)（性能調(diào)優(yōu)（Tuning）分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.13.1兩種設(shè)計策略兩種設(shè)計策略需求分析系統(tǒng)需求說明書調(diào)優(yōu)概念設(shè)計外部模式定義全局概念模式視圖設(shè)計分布設(shè)計局部概念模式物理設(shè)計局部物理模式3.1.1-Top-down分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.1.2-Bottom-upDatabase 1Database 2Database nTranslator 1Translator

4、 2Translator nInS 1InS 2InS nIntegratorGCS3.13.1兩種設(shè)計策略兩種設(shè)計策略分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.2分片的定義及作用分片的定義及作用 例：某集團公司分地理位置分別在不同城市的總公司和下例：某集團公司分地理位置分別在不同城市的總公司和下屬兩個分公司組成，彼此之間靠網(wǎng)絡(luò)相連接，業(yè)務(wù)管理由屬兩個分公司組成，彼此之間靠網(wǎng)絡(luò)相連接，業(yè)務(wù)管理由分布式數(shù)據(jù)庫系統(tǒng)完成。其網(wǎng)絡(luò)結(jié)構(gòu)圖如下所示分布式數(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。 場地定義：總公

5、司為場地0，職工關(guān)系為EMP0分公司1為場地1，職工關(guān)系為EMP1分公司2為場地2，職工關(guān)系為EMP2EMP=EMP0+EMP1+EMP2為全局?jǐn)?shù)據(jù)分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.2分片的定義及作用分片的定義及作用 p數(shù)據(jù)分布要求數(shù)據(jù)分布要求 方案方案1：公司總部保留全部數(shù)據(jù)。：公司總部保留全部數(shù)據(jù)。 方案方案2：各單位只保留自己的數(shù)據(jù)。：各單位只保留自己的數(shù)據(jù)。 方案方案3：公司總部保留全部數(shù)據(jù)，各分公司只保留自己單位的數(shù)據(jù)。：公司總部保留全部數(shù)據(jù)，各分公司只保留自己單位的數(shù)據(jù)。系統(tǒng)采用以上不同方案，對應(yīng)需求不同的數(shù)據(jù)分配方案。如系統(tǒng)采用以上不同方案，對應(yīng)需求不同的數(shù)據(jù)分配方案。如:p 上面三

6、種方案中，除方案1外，均須進(jìn)行分片定義。方案3中，分公司的數(shù)據(jù)信息除本場地存儲外，總部場地也存儲一份相同信息，存在在不同場地上互稱副本。 總部（EMP）分公司1（無）分公司2（無）總部（EMP0）分公司1（EMP1）分公司2（EMP2）總部（EMP）分公司1（EMP1）分公司2（EMP2）場地場地0場地場地1場地場地2方案方案1方案方案2方案方案3分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.2分片的定義及作用分片的定義及作用 3.2.1分片的定義分片的定義n分片（分片（Fragmentation) ) 對全局?jǐn)?shù)據(jù)的劃分。對全局?jǐn)?shù)據(jù)的劃分。n片段片段 劃分的結(jié)果稱為劃分的結(jié)果稱為片段片段 是分布式數(shù)據(jù)庫中數(shù)據(jù)

7、的存儲單位。是分布式數(shù)據(jù)庫中數(shù)據(jù)的存儲單位。n分配（分配（Allocation）：）：對片段的存儲場地的指定，稱為對片段的存儲場地的指定，稱為分配分配。 數(shù)據(jù)復(fù)制：數(shù)據(jù)復(fù)制：片段存儲在一個以上場地時片段存儲在一個以上場地時 數(shù)據(jù)分割：數(shù)據(jù)分割：片段只存儲在一個場地片段只存儲在一個場地分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.2分片的定義及作用分片的定義及作用 3.2.2分片的作用分片的作用n 減少網(wǎng)絡(luò)傳輸量。減少網(wǎng)絡(luò)傳輸量。如：采用數(shù)據(jù)復(fù)制，可就近訪問所需信息。需頻如：采用數(shù)據(jù)復(fù)制，可就近訪問所需信息。需頻繁訪問的信息分片存儲在本地場地上。繁訪問的信息分片存儲在本地場地上。n 增大事務(wù)處理的局部性增大事務(wù)

8、處理的局部性。局部場地上所須數(shù)據(jù)分片分配在各自的局部場地上所須數(shù)據(jù)分片分配在各自的場地上，減少數(shù)據(jù)訪問的時間，增強局部事務(wù)效率。場地上，減少數(shù)據(jù)訪問的時間，增強局部事務(wù)效率。n 提高數(shù)據(jù)的可用性和查詢效率提高數(shù)據(jù)的可用性和查詢效率。就近訪問數(shù)據(jù)分片或副本，可提就近訪問數(shù)據(jù)分片或副本，可提高訪問效率。同時當(dāng)某一場地出故障，若存在副本，非故障場地上的高訪問效率。同時當(dāng)某一場地出故障，若存在副本，非故障場地上的數(shù)據(jù)副本均是可用的。保證了數(shù)據(jù)的可用性、數(shù)據(jù)的完整性和系統(tǒng)的數(shù)據(jù)副本均是可用的。保證了數(shù)據(jù)的可用性、數(shù)據(jù)的完整性和系統(tǒng)的可靠性。可靠性。n 使負(fù)載均衡。使負(fù)載均衡。減少數(shù)據(jù)訪問瓶頸，提高整個系

9、統(tǒng)效率。減少數(shù)據(jù)訪問瓶頸，提高整個系統(tǒng)效率。分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.2分片的定義分片的定義及作用3.2.3分片設(shè)計過程分片設(shè)計過程分片過程分片過程是將全局?jǐn)?shù)據(jù)進(jìn)行邏輯劃分和實際物理分配的過程。是將全局?jǐn)?shù)據(jù)進(jìn)行邏輯劃分和實際物理分配的過程。o全局?jǐn)?shù)據(jù)劃分為片段數(shù)據(jù)全局?jǐn)?shù)據(jù)劃分為片段數(shù)據(jù)片段數(shù)據(jù)經(jīng)過分配得到物理數(shù)據(jù)片段數(shù)據(jù)經(jīng)過分配得到物理數(shù)據(jù)GDBFDBPDB分片模式分配模式G D B ： 全 局 數(shù) 據(jù) 庫（Global DB）F D B ： 片 段 數(shù) 據(jù) 庫（Fragmentation DB）P D B ： 物 理 數(shù) 據(jù) 庫（Physical DB）分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.2分

10、片的定義及作用分片的定義及作用 p 分片模式：分片模式：定義從全局關(guān)系到片段模式的映射關(guān)系。定義從全局關(guān)系到片段模式的映射關(guān)系。p 分配模式：分配模式：定義從片段關(guān)系到物理關(guān)系的映射關(guān)系。定義從片段關(guān)系到物理關(guān)系的映射關(guān)系。1：N時為復(fù)制；時為復(fù)制；1：1時為分割時為分割。RR1R2R3R3R2R1R2R3場地1場地2場地3全局關(guān)系片段 副本分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.2分片的定義及作用分片的定義及作用 3.2.3分片設(shè)計過程分片設(shè)計過程 GDB=FDBi 表示全局?jǐn)?shù)據(jù)庫是劃分的多個片段數(shù)據(jù)庫的集合。表示全局?jǐn)?shù)據(jù)庫是劃分的多個片段數(shù)據(jù)庫的集合。 nF(GDB)=FDB F()：表示分片模式映

11、射函數(shù)；能從全局?jǐn)?shù)據(jù)庫得到片段數(shù)據(jù)庫表示分片模式映射函數(shù)；能從全局?jǐn)?shù)據(jù)庫得到片段數(shù)據(jù)庫nF-1(FDB)=GDB F-1()表示分片模式的反映射函數(shù)；能從片段數(shù)據(jù)庫得到全局?jǐn)?shù)據(jù)表示分片模式的反映射函數(shù)；能從片段數(shù)據(jù)庫得到全局?jǐn)?shù)據(jù)nP(FDB)=PDB n P-1(PDB)=FDB P()：表示分配模式映射函數(shù)，能從片段數(shù)據(jù)庫經(jīng)得到物理數(shù)據(jù)庫：表示分配模式映射函數(shù)，能從片段數(shù)據(jù)庫經(jīng)得到物理數(shù)據(jù)庫 P-1()表示分配模式的反映射函數(shù)。能從物理數(shù)據(jù)庫得到片段數(shù)據(jù)庫表示分配模式的反映射函數(shù)。能從物理數(shù)據(jù)庫得到片段數(shù)據(jù)庫。分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.2分片的定義及作用分片的定義及作用 3.2.4分片的

12、原則分片的原則n 完備性：所有全局?jǐn)?shù)據(jù)完備性：所有全局?jǐn)?shù)據(jù)必須映射到某個片段上。必須映射到某個片段上。n 可重構(gòu)性：可重構(gòu)性：所有片段必須可以重新構(gòu)成全局?jǐn)?shù)據(jù)。所有片段必須可以重新構(gòu)成全局?jǐn)?shù)據(jù)。n 不相交性：不相交性：劃分的各片段所包含的數(shù)據(jù)不允許相同。劃分的各片段所包含的數(shù)據(jù)不允許相同。分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.2分片的定義及作用分片的定義及作用3.2.4分片的原則分片的原則n完備性完備性如果全局關(guān)系R劃分的片段為R1,R2,Rn，則對于R中任意數(shù)據(jù)項d（dR），一定存在dRi（1in）。n可重構(gòu)性可重構(gòu)性如果全局關(guān)系R劃分的片段為R1,R2,Rn，則存在關(guān)系運算，使得R=R1R2Rn。

13、n不相交性不相交性如果全局關(guān)系R水平劃分的片段為R1,R2,Rn，則任意兩個不同的片段的交集為空，即RiRj=（ij, 1in, 1jn）。分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.2分片的定義及作用分片的定義及作用 3.2.5分片的種類分片的種類n水平分片水平分片：按元組進(jìn)行劃分，由分片條件決定。：按元組進(jìn)行劃分，由分片條件決定。n垂直分片垂直分片：按關(guān)系屬性劃分，除關(guān)鍵字外，同一：按關(guān)系屬性劃分，除關(guān)鍵字外，同一關(guān)系的某一屬性不允許出現(xiàn)在一個關(guān)系的多個分關(guān)系的某一屬性不允許出現(xiàn)在一個關(guān)系的多個分片中。片中。n混合分片混合分片：即包括水平分片也包括垂直分片。：即包括水平分片也包括垂直分片。屬性或元組關(guān)系

14、根據(jù)需要進(jìn)行相應(yīng)的分片分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.2分片的定義及作用分片的定義及作用3.2.6分布透明性分布透明性n透明性：透明性：指對用戶和高層系統(tǒng)隱蔽具體實現(xiàn)細(xì)節(jié)。指對用戶和高層系統(tǒng)隱蔽具體實現(xiàn)細(xì)節(jié)。n分布透明性指分片透明性、分配透明性和局部映射透分布透明性指分片透明性、分配透明性和局部映射透明性。明性。n分片透明性分片透明性：指用戶不必考慮數(shù)據(jù)屬于哪個片段。：指用戶不必考慮數(shù)據(jù)屬于哪個片段。n分配透明性分配透明性：指用戶不必考慮各個片段的存儲場地。：指用戶不必考慮各個片段的存儲場地。n局部映射透明性局部映射透明性：用戶不必考慮數(shù)據(jù)的局部存儲形式。：用戶不必考慮數(shù)據(jù)的局部存儲形式。分布式

15、數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.33.3水平分片水平分片 3.3.1 水平分片的定義水平分片的定義水平分片水平分片 是將關(guān)系的是將關(guān)系的元組集元組集劃分成若干不相交的劃分成若干不相交的子集子集。分片屬性分片屬性 用來劃分元組的屬性用來劃分元組的屬性 分片條件分片條件 用來劃分元組的條件用來劃分元組的條件n定義定義設(shè)有一個關(guān)系設(shè)有一個關(guān)系R，R1，R2，Rn為為R的子關(guān)系的集合，如果的子關(guān)系的集合，如果R1，R2，Rn滿足以下條件，則稱其為關(guān)系滿足以下條件，則稱其為關(guān)系R的水平分片，的水平分片，Ri稱為稱為R的一個水的一個水平片段。平片段。 （1）R1，R2，Rn與與R具有相同的關(guān)系模式具有相同的關(guān)系模

16、式 （2）R1R2Rn=R （3）RiRj = （ij，1in）分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.33.3水平分片水平分片按下面分片條件進(jìn)行分段：按下面分片條件進(jìn)行分段： E1：滿足（：滿足（Dno=201）的所有分組；）的所有分組； E2：滿足（：滿足（Dno=202）的所有分組；）的所有分組； E3：滿足（：滿足（Dno201 AND Dno202 ）的所有分組。的所有分組。 p例如：設(shè)有雇員關(guān)系例如：設(shè)有雇員關(guān)系 EMPENO, ENAME, SALARY, DNOENOENAMESALARYDNO001張三1500201002李四1400202003王五800203基本水平分片基本水平分片

17、 劃分關(guān)系元組的劃分關(guān)系元組的屬性屬性，屬于這個關(guān)系，屬于這個關(guān)系本身本身分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.33.3水平分片水平分片 將關(guān)系將關(guān)系EMP分成了三個子關(guān)系分成了三個子關(guān)系E1:部門編號部門編號Dno=201的元組的元組E2:部門編號部門編號Dno=202的元組的元組E3:部門編號部門編號Dno201 AND Dno202分片屬性分片屬性：部門編號：部門編號Dno分片條件分片條件： Dno=201 Dno=202 Dno201 AND Dno202003 王五1200203002 李四1400202001 張三 1500201ENOENAMESALARYDNO001張三15002010

18、02李四1400202003王五800203E1：E2：E3：分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.33.3水平分片水平分片 水平分片正確性判定水平分片正確性判定根據(jù)水平分片定義，滿足：根據(jù)水平分片定義，滿足：nE1,E2,E3和和EMP關(guān)系模式相同；關(guān)系模式相同；nE1E2E3=EMPnE1E2=，E1E3=，E2E3=因此，因此，E1、E2和和E3是是EMP的水平分片。的水平分片。 分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.33.3水平分片水平分片導(dǎo)出水平分片導(dǎo)出水平分片 一個關(guān)系的分片不是基于關(guān)系本身的屬性，而是根一個關(guān)系的分片不是基于關(guān)系本身的屬性，而是根據(jù)另一個與其有關(guān)聯(lián)性質(zhì)的關(guān)系的屬性來劃分。據(jù)另一個

19、與其有關(guān)聯(lián)性質(zhì)的關(guān)系的屬性來劃分。n 例如：例如：關(guān)系關(guān)系WORKSENO，PRJNO，HOURS關(guān)系關(guān)系EMPENO，ENAME，SALARY，DNO將將WORKS按按DNO進(jìn)行水平分片，分片條件同進(jìn)行水平分片，分片條件同EMP的水平分的水平分片條件，得到的導(dǎo)出水平分片為片條件，得到的導(dǎo)出水平分片為W1、W2和和W3。n 分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.33.3水平分片水平分片p 導(dǎo)出水平分片計算如下：導(dǎo)出水平分片計算如下：o令：令：W=WORKS EMP W： ENO，PRJNO，HOURS ，ENAME，SALARY，DNO n根據(jù)根據(jù)DNO對對W進(jìn)行水平分片進(jìn)行水平分片如：如：W1=DN

20、O=201（W）=DNO=201（WORKS EMP ）= WORKS DNO=201（EMP）= WORKS E1n只保留只保留WORKS的屬性的屬性W1= attr（WORKS) W1）= attr（WORKS） (WORKS E1）= WORKS E1 稱為半連接。稱為半連接。 同理：同理：W2= WORKS E2 W3= WORKS E3通過上述三步驟得出按關(guān)系通過上述三步驟得出按關(guān)系EMP的的DNO屬性對屬性對WORKS進(jìn)行水平劃分，進(jìn)行水平劃分，得出得出WORKS的導(dǎo)出水平分片的導(dǎo)出水平分片W1、W2和和W3。分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.33.3水平分片水平分片3.3.2 水平分

21、片的操作水平分片的操作水平分片實際上是關(guān)系的選擇操作，因此，用選擇操作水平分片實際上是關(guān)系的選擇操作，因此，用選擇操作表示，選表示，選擇條件為分片謂詞擇條件為分片謂詞q，則，則R的片段可表示為的片段可表示為 ： q(R)。例例：E1= Dno=201（EMP） SQL：SELECT * FROM EMP WHERE DNO=201E2= Dno=202（EMP） SQL：SELECT * FROM EMP WHERE DNO=202E3= Dno201 AND Dno202（EMP） SQL：SELECT * FROM EMP WHERE Dno201 AND Dno202 分布式數(shù)據(jù)庫系統(tǒng)原

22、理與應(yīng)用3.33.3水平分片水平分片3.3.3水平分片設(shè)計水平分片設(shè)計 1.水平分片設(shè)計依據(jù)水平分片設(shè)計依據(jù)n基本水平分片基本水平分片o應(yīng)用應(yīng)用需求因素：包括定性信息和定量的信息需求因素：包括定性信息和定量的信息n導(dǎo)出水平分片導(dǎo)出水平分片n應(yīng)用需求因素：包括應(yīng)用需求因素：包括定性信息定性信息和和定量的信息定量的信息。n 數(shù)據(jù)庫信息：數(shù)據(jù)庫信息：主要指全局模式中模式間的關(guān)聯(lián)關(guān)系主要指全局模式中模式間的關(guān)聯(lián)關(guān)系定性信息定性信息（Qualitative）: 查詢中的謂詞。查詢中的謂詞。簡單謂詞簡單謂詞(simple predicate):小項謂詞小項謂詞(Minterm predicate)：簡單謂

23、詞的連接。簡單謂詞的連接。定量信息定量信息（Quantitative information）小項選擇度（小項選擇度（Minterm selectivity） sel(mi)：基于小項謂詞：基于小項謂詞mi 的查詢返的查詢返回的元組個數(shù)。回的元組個數(shù)。 訪問頻率（訪問頻率（ Access frequency ） acc(mi)：用戶基于小項謂詞：用戶基于小項謂詞mi查詢訪問查詢訪問數(shù)據(jù)的頻率。數(shù)據(jù)的頻率。分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.33.3水平分片水平分片 3.3.3水平分片設(shè)計水平分片設(shè)計 1.水平分片設(shè)計依據(jù)水平分片設(shè)計依據(jù)n應(yīng)用信息應(yīng)用信息 定性信息定性信息（Qualitative）:

24、 查詢中的謂詞。分為：查詢中的謂詞。分為： 簡單謂詞簡單謂詞(simple predicate):只包含一個操作符號的查詢謂詞，稱為簡單謂詞。小項謂詞小項謂詞(Minterm predicate)：由多個簡單謂詞組成的查詢謂詞稱為小項謂詞。簡單謂詞簡單謂詞（Simple predicates）TITLE = “Elect. Eng.” TITLE = “Syst. Anal.”TITLE = “Mech. Eng.” TITLE = “Programmer”SAL 30000, SAL 30000小項謂詞（小項謂詞（Minterm predicates）TITLE=“Elect. Eng.”

25、SAL 30000TITLE=“Elect. Eng.” SAL30000 (TITLE=“Programmer”) SAL 30000 (TITLE=“Programmer”) SAL30000 等等，但有些是無意意義的。等等，但有些是無意意義的。分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.33.3水平分片水平分片 3.3.3水平分片設(shè)計水平分片設(shè)計 1.水平分片設(shè)計依據(jù)水平分片設(shè)計依據(jù)n應(yīng)用信息應(yīng)用信息n定量信息定量信息（Quantitative information）p 小項選擇度（小項選擇度（Minterm selectivity） sel(mi)指指關(guān)系關(guān)系R中滿足小項謂詞中滿足小項謂詞mi的元

26、組（的元組（ mi (R)）的數(shù)量。）的數(shù)量。p 訪問頻率（訪問頻率（ Access frequency ） acc(mi)指在一定時間段內(nèi)對應(yīng)小項謂詞指在一定時間段內(nèi)對應(yīng)小項謂詞mi的查詢的查詢qi被執(zhí)行的次數(shù)，被執(zhí)行的次數(shù)， 記為記為acc(mi)。 應(yīng)用需求:總公司管理title5的雇員信息 定性信息定性信息 總公司管理查詢結(jié)果為5條記錄的信息 定量信息定量信息分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.33.3水平分片水平分片n定義定義 最小性最小性：如果簡單謂詞集中所有簡單謂詞都是相關(guān)（：如果簡單謂詞集中所有簡單謂詞都是相關(guān)（relevant）的，）的，則該簡單謂詞集具有最小性。則該簡單謂詞集具有

27、最小性。n定義定義 相關(guān)性（相關(guān)性（relevance）：令：令mi mj是兩個小項謂詞，是兩個小項謂詞，f1, f2分別是基分別是基于于mi, mj兩個小項謂詞定義的片段（不包括兩個小項謂詞定義的片段（不包括mi包含包含pi而而 mj包含包含 pi的情的情況），則況），則pi是相關(guān)的，當(dāng)且僅當(dāng)是相關(guān)的，當(dāng)且僅當(dāng)acc(mi)/card(fi) acc(mj)/card(fj)。 說明：一個應(yīng)用或者訪問說明：一個應(yīng)用或者訪問f1或者訪問或者訪問 f2?；蛘哒f，一個簡單謂詞確定一個片。或者說，一個簡單謂詞確定一個片段，即一個簡單謂詞同一個片段相關(guān)段，即一個簡單謂詞同一個片段相關(guān)(relevanc

28、e)。3.3.3水平分片水平分片設(shè)計設(shè)計n水平分片水平分片設(shè)計準(zhǔn)則設(shè)計準(zhǔn)則n定義定義完備性完備性簡單謂詞集合簡單謂詞集合Pr是完備的，當(dāng)且僅當(dāng)：是完備的，當(dāng)且僅當(dāng)：任何應(yīng)用程序任何應(yīng)用程序訪問基于訪問基于Pr分片的分片的任任何片段何片段的機率均等。的機率均等。分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.3水平分片水平分片n 最小性最小性：Pr =LOC=“Montreal”, LOC=“New York”, LOC=“Paris”,BUDGET200000,BUDGET200000 滿足最小性Pr =LOC=“Montreal”, LOC=“New York”, LOC=“Paris”,BUDGET2000

29、00 不滿足最小性3.3.3水平分片設(shè)計水平分片設(shè)計1.水平分片設(shè)計準(zhǔn)則水平分片設(shè)計準(zhǔn)則n完備性完備性 PROJ(PNO,PNAME,BUDGET,LOC)Pr = LOC = “Montreal”, LOC = “New York”, LOC = “Paris”（1）如果有且只有一個應(yīng)用按照location訪問PROJ Pr 滿足完備性。（2）若存在一個應(yīng)用按照BUDGET 200000訪問PROJ Pr 是不完備的。 Pr = LOC = “Montreal”, LOC = “New York”,LOC = “Paris”, BUDGET 20 不滿足最小性不滿足最小性 滿足完備性滿足完備性分布式數(shù)據(jù)庫系統(tǒng)原理與應(yīng)用3.3水平分片