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

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

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

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

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

5、場(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ù)分布式數(shù)據(jù)庫(kù)系統(tǒng)原理與應(yīng)用3.2分片的定義及作用分片的定義及作用 p數(shù)據(jù)分布要求數(shù)據(jù)分布要求 方案方案1：公司總部保留全部數(shù)據(jù)。：公司總部保留全部數(shù)據(jù)。 方案方案2：各單位只保留自己的數(shù)據(jù)。：各單位只保留自己的數(shù)據(jù)。 方案方案3：公司總部保留全部數(shù)據(jù)，各分公司只保留自己?jiǎn)挝坏臄?shù)據(jù)。：公司總部保留全部數(shù)據(jù)，各分公司只保留自己?jiǎn)挝坏臄?shù)據(jù)。系統(tǒng)采用以上不同方案，對(duì)應(yīng)需求不同的數(shù)據(jù)分配方案。如系統(tǒng)采用以上不同方案，對(duì)應(yīng)需求不同的數(shù)據(jù)分配方案。如:p 上面三種方

6、案中，除方案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)地場(chǎng)地0場(chǎng)地場(chǎng)地1場(chǎng)地場(chǎng)地2方案方案1方案方案2方案方案3分布式數(shù)據(jù)庫(kù)系統(tǒng)原理與應(yīng)用3.2分片的定義及作用分片的定義及作用 3.2.1分片的定義分片的定義n分片（分片（Fragmentation) ) 對(duì)全局?jǐn)?shù)據(jù)的劃分。對(duì)全局?jǐn)?shù)據(jù)的劃分。n片段片段 劃分的結(jié)果稱為劃分的結(jié)果稱為片段片段 是分布式數(shù)據(jù)庫(kù)中數(shù)據(jù)的存

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

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

9、率。減少數(shù)據(jù)訪問(wèn)瓶頸，提高整個(gè)系統(tǒng)效率。分布式數(shù)據(jù)庫(kù)系統(tǒng)原理與應(yīng)用3.2分片的定義分片的定義及作用3.2.3分片設(shè)計(jì)過(guò)程分片設(shè)計(jì)過(guò)程分片過(guò)程分片過(guò)程是將全局?jǐn)?shù)據(jù)進(jìn)行邏輯劃分和實(shí)際物理分配的過(guò)程。是將全局?jǐn)?shù)據(jù)進(jìn)行邏輯劃分和實(shí)際物理分配的過(guò)程。全局?jǐn)?shù)據(jù)劃分為片段數(shù)據(jù)全局?jǐn)?shù)據(jù)劃分為片段數(shù)據(jù)片段數(shù)據(jù)經(jīng)過(guò)分配得到物理數(shù)據(jù)片段數(shù)據(jù)經(jīng)過(guò)分配得到物理數(shù)據(jù)GDBFDBPDB分片模式分配模式G D B ： 全 局 數(shù) 據(jù) 庫(kù)（Global DB）F D B ： 片 段 數(shù) 據(jù) 庫(kù)（Fragmentation DB）P D B ： 物 理 數(shù) 據(jù) 庫(kù)（Physical DB）分布式數(shù)據(jù)庫(kù)系統(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時(shí)為復(fù)制；時(shí)為復(fù)制；1：1時(shí)為分割時(shí)為分割。RR1R2R3R3R2R1R2R3場(chǎng)地1場(chǎng)地2場(chǎng)地3全局關(guān)系片段 副本分布式數(shù)據(jù)庫(kù)系統(tǒng)原理與應(yīng)用3.2分片的定義及作用分片的定義及作用 3.2.3分片設(shè)計(jì)過(guò)程分片設(shè)計(jì)過(guò)程 GDB=FDBi 表示全局?jǐn)?shù)據(jù)庫(kù)是劃分的多個(gè)片段數(shù)據(jù)庫(kù)的集合。表示全局?jǐn)?shù)據(jù)庫(kù)是劃分的多個(gè)片段數(shù)據(jù)庫(kù)的集合。 nF(GDB)=FDB F()：表示表示分片模式分片

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

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

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

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

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

16、2）R1R2Rn=R （3）RiRj = （ij，1in）分布式數(shù)據(jù)庫(kù)系統(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)系元組的屬性屬性，屬于這個(gè)關(guān)系，屬于這個(gè)關(guān)系本身本身分布式數(shù)據(jù)庫(kù)系統(tǒng)原理與應(yīng)用3.33.3水平分片水平分片 將關(guān)系將關(guān)系EMP分成了三個(gè)子關(guān)系分成了三個(gè)子關(guān)系E1:部門(mén)編號(hào)部門(mén)編號(hào)Dno=201的元組的元組E2:部門(mén)編號(hào)部門(mén)編號(hào)Dno=202的元組的元組E3:部門(mén)編號(hào)部門(mén)編號(hào)Dno201 AND Dno202分片屬性分片屬性：部門(mén)編號(hào)：部門(mén)編號(hào)Dno分片條件分片條件： Dno=201 Dno=202 Dno201 AND Dno202003 王五1200203002 李四1400202001 張三 1500201ENOENAMESALARYDNO001張三1500201002李

18、四1400202003王五800203E1：E2：E3：分布式數(shù)據(jù)庫(kù)系統(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ù)庫(kù)系統(tǒng)原理與應(yīng)用3.33.3水平分片水平分片導(dǎo)出水平分片導(dǎo)出水平分片 一個(gè)關(guān)系的分片不是基于關(guān)系本身的屬性，而是根一個(gè)關(guān)系的分片不是基于關(guān)系本身的屬性，而是根據(jù)另一個(gè)與其有關(guān)聯(lián)性質(zhì)的關(guān)系的屬性來(lái)劃分。據(jù)另一個(gè)與其有

19、關(guān)聯(lián)性質(zhì)的關(guān)系的屬性來(lái)劃分。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ù)庫(kù)系統(tǒng)原理與應(yīng)用3.33.3水平分片水平分片p 導(dǎo)出水平分片計(jì)算如下：導(dǎo)出水平分片計(jì)算如下：令：令：W=WORKS EMP W： ENO，PRJNO，HOURS ，ENAME，SALARY，DNO 根據(jù)根據(jù)DNO對(duì)對(duì)W進(jìn)行水平分片進(jìn)行水平分片如：如：W1=DNO=201

20、（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ò)上述三步驟得出按關(guān)系通過(guò)上述三步驟得出按關(guān)系EMP的的DNO屬性對(duì)屬性對(duì)WORKS進(jìn)行水平劃分，進(jìn)行水平劃分，得出得出WORKS的導(dǎo)出水平分片的導(dǎo)出水平分片W1、W2和和W3。分布式數(shù)據(jù)庫(kù)系統(tǒng)原理與應(yīng)用3.33.3水平分片水平分片3.3.2 水平分片的操作水平

21、分片的操作水平分片實(shí)際上是關(guān)系的選擇操作，因此，用選擇操作水平分片實(shí)際上是關(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ù)庫(kù)系統(tǒng)原理與應(yīng)用3.

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

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

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

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

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

27、則該簡(jiǎn)單謂詞集具有最小性。n定義定義 相關(guān)性（相關(guān)性（relevance）：令：令mi mj是兩個(gè)小項(xiàng)謂詞，是兩個(gè)小項(xiàng)謂詞，f1, f2分別是基分別是基于于mi, mj兩個(gè)小項(xiàng)謂詞定義的片段（不包括兩個(gè)小項(xiàng)謂詞定義的片段（不包括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)。 說(shuō)明：一個(gè)應(yīng)用或者訪問(wèn)說(shuō)明：一個(gè)應(yīng)用或者訪問(wèn)f1或者訪問(wèn)或者訪問(wèn) f2?；蛘哒f(shuō)，一個(gè)簡(jiǎn)單謂詞確定一個(gè)片?；蛘哒f(shuō)，一個(gè)簡(jiǎn)單謂詞確定一個(gè)片段，即一個(gè)簡(jiǎn)單謂詞同一個(gè)片段相關(guān)段，即一個(gè)簡(jiǎn)單謂詞同一個(gè)片段相關(guān)

28、(relevance)。3.3.3水平分片水平分片設(shè)計(jì)設(shè)計(jì)n水平分片水平分片設(shè)計(jì)準(zhǔn)則設(shè)計(jì)準(zhǔn)則n定義定義完備性完備性簡(jiǎn)單謂詞集合簡(jiǎn)單謂詞集合Pr是完備的，當(dāng)且僅當(dāng)：是完備的，當(dāng)且僅當(dāng)：任何應(yīng)用程序任何應(yīng)用程序訪問(wèn)基于訪問(wèn)基于Pr分片的分片的任任何片段何片段的機(jī)率均等。的機(jī)率均等。分布式數(shù)據(jù)庫(kù)系統(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”,B

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