研究生課程《分布式數(shù)據(jù)庫技術(shù)》課件

1、廈門大學(xué)計算機(jī)科學(xué)系 2011年10月林子雨廈門大學(xué)計算機(jī)科學(xué)系E-mail: 分布式數(shù)據(jù)庫技術(shù)專題二 數(shù)據(jù)分布 專題二 數(shù)據(jù)分布廈門大學(xué)計算機(jī)科學(xué)系研究生課程分布式數(shù)據(jù)庫技術(shù)專題二 數(shù)據(jù)分布第3章 數(shù)據(jù)分布3.1 數(shù)據(jù)分布概念3.2 數(shù)據(jù)劃分原則及分片方法3.3 數(shù)據(jù)分配原則及方法3.4 數(shù)據(jù)分布結(jié)構(gòu)模式定義3.1 數(shù)據(jù)分布概念3.1.1. 分布式數(shù)據(jù)庫設(shè)計的任務(wù)3.1.2. 數(shù)據(jù)分布概念3.1.3 集中式數(shù)據(jù)庫的關(guān)系模式及形式化定義3.1.4. 分布式數(shù)據(jù)庫的模式定義3.1.1 分布式數(shù)據(jù)庫設(shè)計的任務(wù) （1）數(shù)據(jù)庫設(shè)計 數(shù)據(jù)庫設(shè)計是指：對于一個給定的應(yīng)用環(huán)境，構(gòu)造最優(yōu)的數(shù)據(jù)庫模式，建立數(shù)據(jù)

2、庫及其應(yīng)用系統(tǒng)，使之能夠有效地存儲數(shù)據(jù)，滿足各種用戶的應(yīng)用需求（信息要求和處理要求）。3.1.1 分布式數(shù)據(jù)庫設(shè)計的任務(wù)（2）分布式數(shù)據(jù)庫設(shè)計的任務(wù)分布式數(shù)據(jù)庫設(shè)計包含以下任務(wù)：定義全局?jǐn)?shù)據(jù)庫的概念模式設(shè)計分片設(shè)計片段的分配設(shè)計物理數(shù)據(jù)庫，將概念模式映射到存儲區(qū)域，并確定適當(dāng)?shù)拇鎯Ψ椒ㄔ诜植际綌?shù)據(jù)庫設(shè)計過程中，必須考慮分布式數(shù)據(jù)庫應(yīng)用的需求，包括：應(yīng)用提交的場地、應(yīng)用執(zhí)行的頻度、每個應(yīng)用所存取數(shù)據(jù)的類型、次數(shù)及統(tǒng)計分布等信息應(yīng)該明確分布式數(shù)據(jù)庫系統(tǒng)設(shè)計的基本策略：從頂向下的設(shè)計處理或者從下向上的設(shè)計處理3.1.2 數(shù)據(jù)分布概念 數(shù)據(jù)分布的概念 邏輯上將全局概念模式（即全局關(guān)系模式），劃分成若干

3、邏輯片段（子關(guān)系）；再按一定的冗余度將片段分配到各個節(jié)點上，這時邏輯片段就成為具體的物理片段。 3.1.3 集中數(shù)據(jù)庫的關(guān)系模式及形式化定義為了討論分布式數(shù)據(jù)庫的模式定義，首先復(fù)習(xí)相關(guān)知識點。（1）關(guān)系 定義3.1：域是一組具有相同數(shù)據(jù)類型的值的集合。用 表示。 定義3.2：給定一組域D1，D2，Dn，這些域中，可以有相同的。其中 D1，D2，Dn的笛卡兒積為： D1D2 Dn = （ d1, d2 , , dn）| di Di，i=1, 2, , n 其中每一個元素（ d1, d2 , , dn）叫做一個 n 元組（或元組）， 元素中的每一個值di叫做一個分量笛卡兒積的基數(shù)為|D1|D2 |

4、 |Dn | 定義3.3： D1D2 Dn的子集叫做在D1，D2，Dn域上的關(guān)系，表示為： R（ D1，D2，Dn） 其中 ，R表示關(guān)系名，n是關(guān)系的目（或稱為度）。 3.1.3 集中數(shù)據(jù)庫的關(guān)系模式及形式化定義笛卡爾積可表示為一個二維表。表中每行對應(yīng)一個元組，表中的每列對應(yīng)一個域。例1：給出三個域：D1 =導(dǎo)師集合SUPERVISOR=張清玫，劉逸D2 =專業(yè)集合SPECIALITY=計算機(jī)專業(yè)，信息專業(yè)D3=研究生集合POSTGRADUATE=李勇，劉晨，王敏 則D1 ，D2，D3的笛卡爾積為：D1D2D3=（張清玫，計算機(jī)專業(yè),李勇），（張清玫，計算機(jī)專業(yè)，劉晨）， （張清玫，計算機(jī)專業(yè)

5、，王敏），（張清玫，信息專業(yè)，李勇）， （張清玫，信息專業(yè)，劉晨），（張清玫，信息專業(yè)，王敏）， （劉逸，計算機(jī)專業(yè)，李勇），（劉逸，計算機(jī)專業(yè)，劉晨）， （劉逸，計算機(jī)專業(yè)，王敏），（劉逸，信息專業(yè)，李勇）， （劉逸，信息專業(yè)，劉晨），（劉逸，信息專業(yè)，王敏）其中（張清玫，計算機(jī)專業(yè)，李勇）、（張清玫，計算機(jī)專業(yè)，劉晨）等都是元組。張清玫、計算機(jī)專業(yè)、李勇、劉晨等都是分量。3.1.3 集中數(shù)據(jù)庫的關(guān)系模式及形式化定義該笛卡爾積的基數(shù)為223=12，也就是說，D1D2D3一共有223=12個元組。這12個元組可列成一張二維表，如下：D1，D2，D3的笛卡爾積SUPERVISORSPECIALI

6、TYPOSTGRADUATE張清玫張清玫張清玫張清玫張清玫張清玫劉逸劉逸劉逸劉逸劉逸劉逸計算機(jī)專業(yè)計算機(jī)專業(yè)計算機(jī)專業(yè)信息專業(yè)信息專業(yè)信息專業(yè)計算機(jī)專業(yè)計算機(jī)專業(yè)計算機(jī)專業(yè)信息專業(yè)信息專業(yè)信息專業(yè)李勇劉晨王敏李勇劉晨王敏李勇劉晨王敏李勇劉晨王敏3.1.3 集中數(shù)據(jù)庫的關(guān)系模式及形式化定義定義3.3說明：若關(guān)系中的某一屬性組的值能唯一地標(biāo)識一個元組，則稱該屬性組為侯選碼。若一個關(guān)系有多個侯選碼，則選定其中一個為主碼（Primary Key）。主碼的諸屬性稱為主屬性（Prime attribute）。不包含在任何侯選碼中的屬性稱為非碼屬性（Non-key attribute）。在最簡單的情況下，侯

7、選碼只包含一個屬性；在最極端的情況下，關(guān)系模式的所有屬性組是這個關(guān)系模式的侯選碼；上述稱為全碼（All-key）。關(guān)系是一個二維表，表的每行對應(yīng)一個元組，表的每一列對應(yīng)一個域。3.1.3 集中數(shù)據(jù)庫的關(guān)系模式及形式化定義（2）關(guān)系模式 定義3.4：關(guān)系的描述稱為關(guān)系模式。它可以形式化地表示為： R（U，D，dom，F(xiàn)） 其中：R 為關(guān)系名， U 為組成該關(guān)系的屬性名集合， D 為屬性組U中屬性所來自的域， dom 為屬性向域的映象的集合， F 為屬性間數(shù)據(jù)的依賴關(guān)系集合。 （3）關(guān)系數(shù)據(jù)庫 定義3.5：在一個給定的應(yīng)用領(lǐng)域中，所有實體及實體之間聯(lián)系的關(guān)系 的集合構(gòu)成一個關(guān)系數(shù)據(jù)庫。3.1.4

8、分布式數(shù)據(jù)庫的模式定義 3.1.4.1 全局關(guān)系模式及關(guān)系 3.1.4.2 DDB中的三種關(guān)系 3.1.4.3 DDB中的三種數(shù)據(jù)庫 3.1.4.4 分片模式（FS）定義 3.1.4.5 分配模式（AS）定義 3.1.4.6 關(guān)系的分布結(jié)構(gòu) S 3.1.4.7 組合關(guān)系 3.1.4.1 全局關(guān)系模式及關(guān)系全局關(guān)系模式是一個多元組，表示為：R（U，D，dom，I，F(xiàn)，Q，S），其中：R是關(guān)系名； U是組成R的有限屬性集；D是U中屬性的值域； dom是屬性列到域的所有映射的集合；I 是一組完整性約束條件； Q是關(guān)系所滿足的限定條件（謂詞）；F是屬性間的一組數(shù)據(jù)依賴； S是關(guān)系的分布結(jié)構(gòu)。一個關(guān)系r

9、是相應(yīng)于全局關(guān)系模式R（U，D，dom，I，F(xiàn)，Q，S）按分布結(jié)構(gòu)S組織起來的從屬性集U到值域D上所有滿足Q的映射的集合。其中，每個元素稱為元組；每個關(guān)系有主鍵 。關(guān)系和關(guān)系模式有以下關(guān)系：關(guān)系模式描述關(guān)系的結(jié)構(gòu)及語義約束，對于全局關(guān)系模式，同時還具有按一定謂詞條件Q劃分成子關(guān)系（局部關(guān)系）模式和子關(guān)系物理存儲模式的約束關(guān)系是關(guān)系模式在某一時刻的“當(dāng)前值”全局關(guān)系被劃分以后，按分布結(jié)構(gòu)組成子關(guān)系，以呈現(xiàn)現(xiàn)實世界某一時刻的狀態(tài)。所有關(guān)系的當(dāng)前值就是關(guān)系數(shù)據(jù)庫為了把問題集中于數(shù)據(jù)分布，可以把全局關(guān)系模式簡化成R（U，Q，S）3.1.4.2 DDB中的三種關(guān)系全局關(guān)系：當(dāng)一個關(guān)系R（U，Q，S）稱為

10、全局關(guān)系（GR），是指在分布式數(shù)據(jù)庫系統(tǒng)中對用戶是可見的，實際上是由若干子關(guān)系的邏輯片段和物理片段按分布結(jié)構(gòu)S組成，具有Q=TRUE，S的特點，且GR是虛擬的。邏輯片段：當(dāng)一個關(guān)系R（U，Q，S）稱為邏輯片段，是指這個關(guān)系在DDB中是實際存在的關(guān)系，不需要由其它關(guān)系組成，因而它是基本關(guān)系，即是構(gòu)成DDB的實體。它是全局關(guān)系在某個場地上的子關(guān)系的邏輯成分，所以邏輯片段可簡稱為GR的邏輯關(guān)系，而全局關(guān)系與邏輯關(guān)系間有一定的映射，用分片模式定義，它們之間的映射性質(zhì)為 1：n 。物理片段：當(dāng)一個關(guān)系R（U，Q，S）稱為物理片段，是指這個關(guān)系是在某一場地上的邏輯片段，即是在某場地上的基本關(guān)系，其特點是S

11、=。|物理片段由分配模式定義。邏輯片段映射為某個場地上的物理片段，亦可稱為某個場地的副本，或直接稱物理關(guān)系，其映射有 1：1 和 1：n性質(zhì)（因而一個邏輯關(guān)系可以對應(yīng)一個物理關(guān)系，也可對應(yīng)多個物理關(guān)系）。結(jié)論：一個全局關(guān)系由分片操作（分片模式定義）分解成多個邏輯關(guān)系；一個邏輯關(guān)系在幾個場地上放置副本（分配模式定義）就產(chǎn)生幾個物理關(guān)系。這些分片信息和分配信息構(gòu)成了全局關(guān)系的分布結(jié)構(gòu)S。 3.1.4.2 DDB中的三種關(guān)系集中式三層摸式結(jié)構(gòu)圖分布式四層摸式結(jié)構(gòu)圖問題：DDB三種關(guān)系分別屬于哪一層？3.1.4.3 DDB中的三種數(shù)據(jù)庫全局（虛擬）數(shù)據(jù)庫：由所有全局關(guān)系組成的數(shù)據(jù)庫稱為全局（或虛擬）數(shù)

12、據(jù)庫GDB。邏輯數(shù)據(jù)庫：由所有邏輯片段（基本關(guān)系）組成的數(shù)據(jù)庫稱為邏輯數(shù)據(jù)庫LgDB。物理數(shù)據(jù)庫：由所有物理關(guān)系組成的數(shù)據(jù)庫稱為物理數(shù)據(jù)庫PDB。 三種數(shù)據(jù)庫之間的關(guān)系可表示如下： 分片模式 分配模式GDB LgDB PDB當(dāng)用戶查詢或更新操作分布式數(shù)據(jù)庫時，只是對虛擬的全局?jǐn)?shù)據(jù)庫操作，它并不實際存在，而是由若干“片段”組成的（由若干片段的并行操作和自然聯(lián)接操作實現(xiàn)的），這些片段映射為一個“物理關(guān)系”存在于物理數(shù)據(jù)庫中。三種數(shù)據(jù)庫是通過分片模式定義和分配模式定義聯(lián)系起來的。3.1.4.4 分片模式（FS）定義分片模式FS定義為一組操作，它將GDB中每個GR分解成LgDB中的片段，即： FS（G

13、DB）= LgDB這種操作還應(yīng)具有可逆性，這是分布式數(shù)據(jù)庫系統(tǒng)的基本要求：FS-1（LgDB）GDB 3.1.4.5 分配模式（AS）定義分配模式定義為一組操作，它將LgDB中每個邏輯關(guān)系映射到PDB中的一組物理關(guān)系上，即： AS（LgDB）= PDB分配模式的逆操作含義是，從PDB中選擇出適當(dāng)?shù)奈锢黻P(guān)系作為邏輯關(guān)系，從而構(gòu)成LgDB，即有： AS-1（PDB）=LgDB。 3.1.4.6 關(guān)系的分布結(jié)構(gòu)S關(guān)系R（U，Q，S）的分布結(jié)構(gòu)S是有關(guān)R被劃分和分配的信息的集合如果R是物理關(guān)系，那么它無需劃分和分配，因此S=如果R是邏輯關(guān)系，那么它還需分配場地，因此S記載R的分配信息如果R是全局關(guān)系，

14、那么S記載了R如何分解成邏輯關(guān)系和物理關(guān)系3.1.4.7 組合關(guān)系在全局關(guān)系與邏輯關(guān)系之間，事實上還存在若干關(guān)系，我們可稱它為中間關(guān)系。只是起過渡作用。用組合關(guān)系表示。 組合關(guān)系R（U，Q，S）是由若干邏輯關(guān)系和物理關(guān)系按分布結(jié)構(gòu)S組成的關(guān)系。它可以是全局關(guān)系，或者也可以是中間關(guān)系?；咎攸c為S。3.2 數(shù)據(jù)劃分原則及分片方法3.2.1 分片操作原則3.2.2 分片操作3.2.3 分片操作的正確性3.2.1 分片操作原則（1）數(shù)據(jù)劃分的基本思路：首先按DDB外部特征劃分?jǐn)?shù)據(jù)，然后根據(jù)DDB的內(nèi)部特征，提出應(yīng)遵守的基本原則以檢驗數(shù)據(jù)劃分的正確性。 所謂“外部特征”是指構(gòu)成DDB的屬性群集特性，包

15、括屬性值集和數(shù)據(jù)項集等。 例1：某公司數(shù)據(jù)庫中有部門關(guān)系Dept，便于管理可按部門性質(zhì)或部門所在地將部門關(guān)系Dept劃分成若干片段（如部門號DNO，或部門所在地區(qū)AREA的屬性值集劃分）。這是一種按屬性值集的劃分。 例2：而上述數(shù)據(jù)庫中有職員關(guān)系Emp，通?？砂礃I(yè)務(wù)管理性質(zhì)將Emp的屬性組合值集劃分（如財務(wù)部門對稅收TAX、工資SAL等屬性項有興趣，行政部門對Emp承擔(dān)工作業(yè)務(wù)的屬性項有興趣等）。這是按數(shù)據(jù)項集劃分。 內(nèi)部特征是指DDB的組成性質(zhì)。（2）基本原則：當(dāng)對DDB劃分后，仍應(yīng)保持DDB原有的特質(zhì)，所以劃分后的各邏輯關(guān)系之間應(yīng)遵守下列原則： 完整性原則、重構(gòu)性原則、不相交原則3.2.2

16、 分片操作3.2.2.1 水平分片3.2.2.2 垂直分片3.2.2.3 混合分片3.2.2.4 誘導(dǎo)分片3.2.2.5 四種分片操作的統(tǒng)一表示3.2.2.1 水平分片水平分片是將關(guān)系按行橫向以某些條件劃分成元組的子集，（即：滿足條件的記錄的集合）每個子集含有一定的邏輯意義，稱邏輯片段。定義1：組合關(guān)系R（U，Q，S）上的水平分片（H）是一操作，它將R按照一組給定的謂詞 P1，P2，Pn，劃分成一組關(guān)系模式：R1（U1，Q1，S1），Rn（Un，Qn，Sn）滿足：1）U1U2UnU； 2）K1K2KnK； 3）QiQ Pi； 4）Si 其中：i，jl，n，Pi Pj=， Pi=True，記為：

17、R（H） = R1，Rn 式中P=P1，Pn。由定義可得出：水平分片實際上是關(guān)系的選擇操作。即屬性=“值”的具體條件的子關(guān)系Ri，因此片段可用q(R)表示。 3.2.2.1 水平分片例1：供應(yīng)商全局關(guān)系Supplier（SNO，SNAME，SCITY）按供應(yīng)商所在地SCITY 屬性值劃分。假設(shè)只有兩個城市London和Paris，則按上述定義，其水平分片為： Supplier1scityLondon（Supplier） Supplier2scityParis（Supplier） 3.2.2.2 垂直分片垂直分片是將關(guān)系按列縱向以屬性組劃分成若干片段。在垂直分片時，為了保證片段的重構(gòu)性，應(yīng)將“鍵

18、屬性”屬于各個片段中（放松的不相交性）。 定義2：組合關(guān)系R（U，Q，S）上垂直分片（V）是一操作，它將R按照一組給定的屬性A1，An劃分成一組關(guān)系模式：R1（U1，Q1，S1），Rn（Un，Qn，Sn）滿足：1）K1=K2=Kn=K；2）Ui=Ai； 3）Q1=Q2=Qn=Q；4）k1（R1）=k2（R2）=kn（Rn）= k（R）；5）Si其中：i，j 1，n ， Ai U,AiAj =K，Ai =U 記為：R（V）= R1，Rn 式中A= A1，An 由定義可得出，關(guān)系的垂直分片實際上是對指定屬性集上的投影操作。所以，R關(guān)系的垂直分片片段是R的部分屬性組合子關(guān)系Ri，可用i(R)表示，其

19、中K Ai。3.2.2.2 垂直分片例：職員關(guān)系mp（ENO,ENAME,SAL,TAX,MGRSSN,DNO）劃分成兩個子關(guān)系：一個包括財務(wù)信息，對SAL,TAX屬性感興趣；一個包括工作信息，對ENO,ENAME,MGRSSN,DNO屬性感興趣。為了保證劃分后重構(gòu)，可將ENO作為公共屬性分別包括在二個片段中。這樣Emp可劃分： Emp1=ENO,SAL,TAX（Emp）Emp2=ENO,ENAME,MGRSSN,DNO（Emp）定義3：組合關(guān)系（U，Q，）上的混合分片（M）是一操作，它將關(guān)系按照一組屬性A1 , An和一組謂詞P1 ,Pn劃分成：1(U1,Q1,S1)，n(Un,Qn,Sn,

20、)滿足：1）Ui= Ai2）K1=K2=Kn=K;3）Qi=QPi;4）Si。其中：i，jl，n，Ai3.2.2.3 混合分片混合分片是水平分片和垂直分片的內(nèi)部混合。U，AiAj =K，Ai =U，PiPj=，Pj=True，記為：R (M) = R1, ,Rn 式中AP= | i=1,n 。上述定義說明混合分片是水平分片和垂直分片的混合操作，即對關(guān)系的選擇和投影。當(dāng)要重構(gòu)混合分片的各片段，可按相應(yīng)次序做合并（UNION）操作和聯(lián)接（JOIN）操作。3.2.2.3 混合分片例3：將例2的Emp劃分成Emp1,Emp2后，對Emp2可按部門號DNO=1、DNO=3分在一個片段，而DNO=2在另一

21、片段，則Emp可劃分為： Emp1=ENO，SAL，TAX（Emp） Emp2=DNO=“D1”or DNO=“D3” (ENO,ENAME,MGRSSN,DNO Emp) Emp3=DNO=“D2”(ENO,ENAME,MGRSSN,DNO Emp)定義4：組合關(guān)系R（U,Q,S），按另一個組合關(guān)系T （T是已經(jīng)水平分片成T1（U1，Q1，S1）,，Tn（Un,Qn, Sn） ）在公共屬性A上的誘導(dǎo)分片（DH）是一操作，它將R劃分為： R1（ ） , Rn（ ）3.2.2.4 誘導(dǎo)分片一個關(guān)系的分片不是基于關(guān)系本身的屬性，而是根據(jù)另一個與其有關(guān)聯(lián)性質(zhì)的關(guān)系的屬性來劃分。這種劃分是只基于水平分

22、片的誘導(dǎo) 滿足： 1） 2）3）4）5）Si記為：R（DH）= R1，Rn 式中：T= T1，Tn 誘導(dǎo)分片是一種相關(guān)分片操作，它是一種半聯(lián)接操作誘導(dǎo)分片實例 3.2.2.4 誘導(dǎo)分片關(guān)于半聯(lián)接操作關(guān)系代數(shù)操作中的聯(lián)接（JOIN）操作包括-聯(lián)接和自然聯(lián)接半聯(lián)接操作是關(guān)系代數(shù)操作中聯(lián)接（JOIN）操作的一種縮減：關(guān)系R和S的半聯(lián)接記為RS，其結(jié)果關(guān)系是R和S自然聯(lián)接（Natural JOIN）后在R的屬性上的投影，可用下述表達(dá)式表示： RS=R（RS）（實例）計算RS的另一種等價的方法是：將S中與R有相同屬性名的屬性集投影出來，然后與R完成自然聯(lián)接半聯(lián)接操作是一種不對稱操作，即RSSR在分布式數(shù)

23、據(jù)庫的查詢優(yōu)化中，常常用半聯(lián)接操作實現(xiàn)聯(lián)接操作的操作數(shù)（關(guān)系）的縮減（歸約）3.2.2.4 誘導(dǎo)分片圖 自然聯(lián)接實例自然聯(lián)接的結(jié)果是在 R 和 S 中的在它們的公共屬性名字上相等的所有元組的組合。例如下面是表格“雇員”和“部門”和它們的自然聯(lián)接:3.2.2.4 誘導(dǎo)分片圖 -聯(lián)接實例-聯(lián)接（等值聯(lián)接是它的特例）如果我們要組合來自兩個關(guān)系的元組，而組合條件不是簡單的共享屬性上的相等，則有一種更一般形式的聯(lián)接算子才方便，這就是 -聯(lián)接(或 theta-聯(lián)接)。 是在集合 , 中的二元關(guān)系。的結(jié)果由在 R 和 S 中滿足關(guān)系 的元素的所有組合構(gòu)成。只有 S 和 R 的表頭是不相交的，即不包含公共屬性

24、的情況下，-聯(lián)接的結(jié)果才是有定義的。實例：考慮分別列出車模和船模的價格的表“車”和“船”。假設(shè)一個顧客要購買一個車模和一個船模，但不想為船花費比車更多的錢。在關(guān)系上的-聯(lián)接 CarPrice BoatPrice 生成所有可能選項的一個表。3.2.2.4 誘導(dǎo)分片圖 半聯(lián)接實例半聯(lián)接的結(jié)果只是在 S 中有在公共屬性名字上相等的元組的所有 R 中的元組。實例：“雇員”和“部門”和它們的半聯(lián)接的表: RS=R（RS）RSManagerHarrietCharies半聯(lián)接結(jié)果自然聯(lián)接結(jié)果3.2.2.4 誘導(dǎo)分片例4：設(shè)供應(yīng)關(guān)系Supply(SNO,PNO,QTY)，它的劃分要求按供應(yīng)商所在地SCITY屬

25、性值劃分。分析：雖然SCITY不是Supply關(guān)系的屬性，但Supply是Supplier與另一個零件關(guān)系Part的關(guān)聯(lián)（這種關(guān)聯(lián)描述了供應(yīng)商供應(yīng)零件的細(xì)節(jié)）。Supply與Supplier和Part分別通過SNO和PNO建立聯(lián)系，就Supply與Supplier而言，SNO是它們的公共的屬性，充當(dāng)Supply的外鍵（foreign key）。所以，Supply的劃分可以通過公共屬性SNO實現(xiàn)，在SCITY屬性值上完成水平誘導(dǎo)劃分。這時，SCITY屬性稱為Supply的誘導(dǎo)屬性。3.2.2.4 誘導(dǎo)分片前例已有：Supplier1=SCITY=LondonSupplier Supplier2=

26、SCITY=ParisSupplier 通過半聯(lián)接操作實現(xiàn)對Supply的劃分，則Supply1=Supply Supplier1 Supply2=Supply Supplier2 根據(jù)半聯(lián)接表達(dá)式，則上式分別為：Supply1=SNO,PNO,QTY(Supply(SCITY=LondonSupplier) Supply2=SNO,PNO,QTY(Supply(SCITY=ParisSupplier) 從式中可看出：Supply誘導(dǎo)水平分片的謂詞有兩部分，一部分是它與關(guān)聯(lián)關(guān)系的公共屬性；另一部分是它應(yīng)滿足的關(guān)于誘導(dǎo)屬性的謂詞?？杀硎緸椋?Q1：Supply.SNO=Supplier. SNO

27、 and SCITY=London Q2：Supply.SNO=Supplier.SNO and SCITY=Paris 注：RS=R（RS）3.2.2.4 誘導(dǎo)分片3.2.2.5 四種分片操作的統(tǒng)一表示四種分片操作可以用一個統(tǒng)一的形式描述：R（Oj），=R1，Rn其中，Oj H,V,M,DH , C= C1,，Cn 。當(dāng)Oj=DH時，Ci表示關(guān)系；當(dāng)OjDH時，Ci=|如果Oj=H,則Ai=U；如果Oj=V，則Pi=True。操作的作用是將組合關(guān)系R（U,Q,S）按操作Oj分解成一組滿足條件的片段（子關(guān)系）：R1（U1,Q1,S1），Rn(Un,Qn,Sn)，其中，當(dāng)Oj DH時， Ui=A

28、i，Ki=K, Qi=QPi ，Si ，i=1，n；當(dāng)Oj=DH時，Ui=U, Ki=K, Qi=Ci， Si ，i=1，n。3.2.3 分片操作的正確性 四種分片操作均是建立在關(guān)系代數(shù)基礎(chǔ)上的。一個關(guān)系經(jīng)過選擇操作分成若干子關(guān)系，子關(guān)系間遵守三個內(nèi)部特征原則。 一個關(guān)系經(jīng)過投影操作劃分成若干子關(guān)系，它們共享關(guān)系的主鍵屬性，且相交屬性只允許是主鍵。這種劃分后的內(nèi)部特征的檢查如下：完整性檢查：垂直分片定義中已定義了子關(guān)系屬性項，并是關(guān)系的屬性項（Ai=U），即不會出現(xiàn)游離的屬性項；重構(gòu)性檢查：將子關(guān)系做自然聯(lián)接則還原成關(guān)系；不相交性檢查：對于垂直分片是允許在鍵屬性上相交。 一個關(guān)系的混合分片的檢

29、查，實際上是重復(fù)上述兩種分片的檢查。兩個關(guān)系間的誘導(dǎo)分片的檢查，主要是對半聯(lián)接作的檢查，半聯(lián)接操作是一種基于關(guān)系基本操作的導(dǎo)出操作（選擇、投影、聯(lián)接的復(fù)合操作）。 3.2.3 分片操作的正確性 例1：檢查Supplier被水平劃分成Supplier1和Supplier2兩個子關(guān)系的分片正確性。完整性檢查：選擇操作包括了所有 SCITY值，即不出現(xiàn)游離的元組項；重構(gòu)性檢查：將兩個子關(guān)系做并操作還原為原來的Suppler關(guān)系；不相交性檢查：選擇操作的兩個謂詞為： Q1：SCITY=London， Q2：SCITY=Paris，它們之間是互斥的，所以片段中不存在相同的元組項3.3 數(shù)據(jù)分配原則及方法

30、3.3.2 分配操作定義3.3.1 數(shù)據(jù)分配的一般準(zhǔn)則3.3.3 分配操作方法3.3.1 數(shù)據(jù)分配的一般準(zhǔn)則分配 4 種類型：集中型、分割型、全復(fù)制型、混合型評估 4 個因素：存儲代價、可靠性、檢索代價、更新代價存儲代價沒有增加可靠性比集中型好沒有通訊代價問題不存在副本同步更新- 沒有片段間 的通訊；- 存儲代價沒有額外開銷；- 可靠性差；- 檢索代價猛增；- 沒有同步更新的開銷。 可靠性好 存儲代價劇增- 檢索代價隨更新同步機(jī)制而變化（分析集中式更新同步技術(shù)和全局鎖技術(shù)的檢索代價與更新復(fù)雜性）上述三種的綜合設(shè)置，考慮更新/檢索比數(shù)據(jù)分配一般準(zhǔn)則：處理局部性數(shù)據(jù)的可用性和可靠性工作負(fù)載分布的均

31、勻性集中型評估分割型評估全復(fù)制型評估混合型評估評估分析3.3.2 分配操作定義 定義1： 對于邏輯片段R（U，Q，S）的分配操作（AO），是將R分配到一組場地r1，rn上，使得每個ri上有一個相應(yīng)的物理關(guān)系 Rri（Uri，Qri，Sri），滿足： Uri=U； Qri=Q； Sri=。 記為： R(AO)r= Rr1, Rr2Rrn， r=r1, , rn 3.3.3 分配操作方法 總體思路和參考方法： 利用大量的性能測試和“應(yīng)用”優(yōu)化。即：分別根據(jù)需求，使用以下三種方法求出收益值，分析最佳分配。 方法1：非冗余分配“最佳”法 方法2：冗余分配“選擇所有收益場地法” 方法3：冗余分配“添加副

32、本”法3.4 數(shù)據(jù)分布結(jié)構(gòu)模式定義3.4.2 用分解樹理論討論分布結(jié)構(gòu)的定義3.4.1 概述3.4.3 數(shù)據(jù)分布模式定義3.4 用分解樹理論討論分布結(jié)構(gòu)的定義3.4.1 概述全局關(guān)系模式： R（U，D，dom，I，F(xiàn)，Q，S） 或簡化成： R（U，Q，S）， 其中，S是關(guān)系的分布結(jié)構(gòu) ，是有關(guān)R被劃分和分配的信息的集合。如果R是全局關(guān)系，那么S記載了R如何分解成邏輯關(guān)系和物理關(guān)系；如果R是邏輯關(guān)系，那么它還需分配場地，因此S記載R的分配信息； 如果R是物理關(guān)系，那么它無需劃分和分配，因此S=； 本節(jié)討論如下要點：如何將分片和分配的信息在一個分布結(jié)構(gòu)S中進(jìn)行描述表示“數(shù)據(jù)分布的模式定義”的語句格

33、式，即以語句格式表現(xiàn)數(shù)據(jù)分布的實際操作3.4 數(shù)據(jù)分布結(jié)構(gòu)模式定義3.4.2.1 分布結(jié)構(gòu)的粗定義 3.4.2.2 關(guān)于獨立分片的分解樹定義3.4.2.3 包含相關(guān)分片的分解樹定義3.4.2.4 包含分配操作的分解樹定義3.4.2 用分解樹理論討論分布結(jié)構(gòu)的定義3.4.2.1 分布結(jié)構(gòu)的粗定義定義1：一個分布結(jié)構(gòu)是一個有向圖G=（V，E，L），其中：1） V是節(jié)點集：每個節(jié)點由關(guān)系模式和在相應(yīng)關(guān)系上的操作所組成，用Ri(Ui,Qi,Si)(Oj)表示；2） E是邊集：如果有任意分片操作R（Oj）=R1,，Rn，則有從節(jié)點R（U,Q,S）（Oj）到R1（U1,Q1,S1）(O1),，Rn（Un,

34、Qn,Sn）(On)的n條有向邊R（R,Q,S）（Oj），Ri（Ui,Qi,Si）(Oi),每條邊上有符號Ci，i=1,2,，n。3） L是符號集：它由所有邊上的Ci所組成。如果一個分布結(jié)構(gòu)是一棵樹，就稱它為分解樹。 3.4.2.1 分布結(jié)構(gòu)的粗定義圖 分解樹結(jié)構(gòu)3.4.2.2 關(guān)于獨立分片的分解樹定義定理1：在分解樹中對任一符號為Ci=的有向邊R（U,Q,S）(O)，R（U,Q,S）(O) ,都有：Q=QPi，U=Ai，K=K 。定理2：在分解樹中，設(shè)任意兩節(jié)點R0(U0,Q0,S0)(O0)到Rf(Uf,Qf,Sf)(Of)間的所有邊上的符號為,有：1）2）3）4）為根節(jié)點的子樹.3.4.

35、2.2 關(guān)于獨立分片的分解樹定義定義2： 分解樹是一棵樹T=（V，E），其中：1）V是節(jié)點集：每個節(jié)點結(jié)構(gòu)為Ri (Ui,Qi,Si)(Oj)，Qi是一謂詞，Oj表示操作集H，V，M，對于根節(jié)點，有Qi=True，Si=T;2）E是邊集：對于任一獨立分片操作，R（Oj）=R1，Rn，其中，C=C1，Cn，Ci=,（i=1,n）。則在分解樹中，有節(jié)點R（U,Q,S）(Oj)到Ri(Ui,Qi,Si)( )的邊，其中，i=1,n，且Ui=Ai，Ki=K， Qi=QPi 。這個定義就是非常重要的獨立分片的分解樹定義 表示操作集3.4.2.3 包含相關(guān)分片的分解樹定義定義3： 分解樹是一棵樹 1）V是節(jié)點集：每個節(jié)點結(jié)構(gòu)為 是一謂詞或是關(guān)系名， 根節(jié)點 2）E是邊集：對于任一分片操作，在分解樹中有從節(jié)點到Ri(Ui,Qi,Si)(Oj )的，且Ui=Ai，Ki=K，Qi=QPi；，那么一定是關(guān)系名，這時，在分解樹T中有從節(jié)點到節(jié)點的幾條邊，且對每個，有 ，其中：如果，如果表示操作集3.4.2.4 包含分配操作的分解樹定