分布式數(shù)據(jù)庫(kù)原理與應(yīng)用課件PPT1第3章

第三章分布式數(shù)據(jù)庫(kù)設(shè)計(jì)3.1關(guān)系運(yùn)算關(guān)系代數(shù)的運(yùn)算按運(yùn)算符的不同可分為傳統(tǒng)的集合運(yùn)算和專(zhuān)門(mén)的關(guān)系運(yùn)算兩類(lèi)。傳統(tǒng)的集合運(yùn)算包括并、交、差和笛卡爾積；專(zhuān)門(mén)的關(guān)系運(yùn)算包括選擇部分?jǐn)?shù)據(jù)的運(yùn)算和組合兩個(gè)關(guān)系的操作。3.1.1傳統(tǒng)的集合運(yùn)算1.并假設(shè)關(guān)系R和關(guān)系S的并(Union)運(yùn)算產(chǎn)生一個(gè)新的關(guān)系R'，則R'由屬于關(guān)系R或S的所有不同元組組成，記為R'=R∪S。

R∪S3.1.1傳統(tǒng)的集合運(yùn)算學(xué)生基本信息表S1學(xué)生基本信息表S2學(xué)生基本信息表S1∪S2學(xué)號(hào)姓名性別年級(jí)學(xué)院專(zhuān)業(yè)0501001張昊男2020計(jì)算機(jī)計(jì)算機(jī)科學(xué)與技術(shù)0501010李穎女2020計(jì)算機(jī)計(jì)算機(jī)科學(xué)與技術(shù)0501206王婷女2020計(jì)算機(jī)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)號(hào)姓名性別年級(jí)學(xué)院專(zhuān)業(yè)0501008趙娜女2020計(jì)算機(jī)計(jì)算機(jī)科學(xué)與技術(shù)0501019李浩男2020計(jì)算機(jī)計(jì)算機(jī)科學(xué)與技術(shù)0501206王婷女2020計(jì)算機(jī)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)號(hào)姓名性別年級(jí)學(xué)院專(zhuān)業(yè)0501001張昊男2020計(jì)算機(jī)計(jì)算機(jī)科學(xué)與技術(shù)0501010李穎女2020計(jì)算機(jī)計(jì)算機(jī)科學(xué)與技術(shù)0501206王婷女2020計(jì)算機(jī)計(jì)算機(jī)科學(xué)與技術(shù)0501008趙娜女2020計(jì)算機(jī)計(jì)算機(jī)科學(xué)與技術(shù)0501019李浩男2020計(jì)算機(jī)計(jì)算機(jī)科學(xué)與技術(shù)3.1.1傳統(tǒng)的集合運(yùn)算2.交假設(shè)關(guān)系R和關(guān)系S的交(Intersection)運(yùn)算產(chǎn)生一個(gè)新的關(guān)系R'，則R'由既屬于R又屬于S的元組組成，記為R'=R∩S。

R∩S3.1.1傳統(tǒng)的集合運(yùn)算學(xué)生基本信息表S1∩S2學(xué)號(hào)姓名性別年級(jí)學(xué)院專(zhuān)業(yè)0501206王婷女2020計(jì)算機(jī)計(jì)算機(jī)科學(xué)與技術(shù)3.1.1傳統(tǒng)的集合運(yùn)算3.差假設(shè)關(guān)系R和關(guān)系S的差(Difference)運(yùn)算產(chǎn)生一個(gè)新的關(guān)系R'，則R'由屬于R但不屬S的元組組成，記為R-S。

R-S3.1.1傳統(tǒng)的集合運(yùn)算學(xué)生基本信息表S1-S2學(xué)號(hào)姓名性別年級(jí)學(xué)院專(zhuān)業(yè)0501001張昊男2020計(jì)算機(jī)計(jì)算機(jī)科學(xué)與技術(shù)0501010李穎女2020計(jì)算機(jī)計(jì)算機(jī)科學(xué)與技術(shù)3.1.1傳統(tǒng)的集合運(yùn)算4.笛卡爾積設(shè)R為m元關(guān)系，S為n元關(guān)系，R和S的笛卡兒積(ExtendedCartesianProduct)產(chǎn)生一個(gè)新關(guān)系R'，記為R'=RXS。R'由R和S的所有元組連接而成的具有m+n個(gè)分量的元組組成，新關(guān)系中元組的前m個(gè)分量為R的一個(gè)元組，后n個(gè)分量為S的一個(gè)元組。3.1.1傳統(tǒng)的集合運(yùn)算學(xué)生信息表S3

課程信息表S4S3XS4學(xué)號(hào)姓名年級(jí)0501001張昊20200501010李穎2020課程代碼課程名稱(chēng)教室0501001數(shù)據(jù)庫(kù)原理B010501002C語(yǔ)言B02學(xué)號(hào)姓名年級(jí)課程代碼課程名稱(chēng)教室0501001張昊20200501001數(shù)據(jù)庫(kù)原理B010501001張昊20200501002C語(yǔ)言B020501010李穎20200501001數(shù)據(jù)庫(kù)原理B010501010李穎20200501002C語(yǔ)言B023.1.2專(zhuān)門(mén)的關(guān)系運(yùn)算1.選擇運(yùn)算選擇運(yùn)算是一個(gè)單目運(yùn)算，它是從一個(gè)關(guān)系R中選取滿(mǎn)足給定條件的元組構(gòu)成一個(gè)新的關(guān)系，選擇運(yùn)算記為：σF(R)={t|t∈R∧F(t)=’真’}其中σ是選擇運(yùn)算符，F(xiàn)表示選擇條件，是由邏輯運(yùn)算符┑、∧、∨等連接算術(shù)表達(dá)式組成的條件表達(dá)式。F(t)是一個(gè)邏輯表達(dá)式，結(jié)果取邏輯值’真’或’假’。3.1.2專(zhuān)門(mén)的關(guān)系運(yùn)算算術(shù)表達(dá)式的基本形式為XθY，其中X、Y是屬性名、常量或簡(jiǎn)單函數(shù)，屬性名也可以用它的序號(hào)來(lái)代替。θ是比較運(yùn)算符，θ∈{﹥、≧、﹤、≦、＝、≠}。選擇運(yùn)算實(shí)際上是從關(guān)系R中選取使邏輯表達(dá)式F為真的元組。這是從行的角度進(jìn)行的運(yùn)算。3.1.2專(zhuān)門(mén)的關(guān)系運(yùn)算從學(xué)生信息表S1中選擇學(xué)號(hào)為“0501010”的學(xué)生，表示為σ學(xué)號(hào)=“0501010”(S1)。σ學(xué)號(hào)=“0501010”(S1)結(jié)果關(guān)系表學(xué)號(hào)姓名性別年級(jí)學(xué)院專(zhuān)業(yè)0501010李穎女2020計(jì)算機(jī)計(jì)算機(jī)科學(xué)與技術(shù)3.1.2專(zhuān)門(mén)的關(guān)系運(yùn)算2.投影運(yùn)算投影運(yùn)算也是一個(gè)單目運(yùn)算，它是從一個(gè)關(guān)系R中選取所需要的列組成一個(gè)新關(guān)系，投影運(yùn)算記為：∏A(R)=∏i1,i2,….ik(R)={t[A]|t∈R}其中∏是投影運(yùn)算符，A為關(guān)系R屬性的子集，t[A]為R中元組相應(yīng)于屬性集A的分量，i1,i2,….ik表示A中屬性在關(guān)系R中的順序號(hào)。3.1.2專(zhuān)門(mén)的關(guān)系運(yùn)算投影運(yùn)算是從列的角度進(jìn)行的運(yùn)算，投影取消了原關(guān)系中的某些列后，可能出現(xiàn)重復(fù)行,投影后也會(huì)取消這些完全相同的重復(fù)行。從學(xué)生信息表S1中投影學(xué)號(hào)、姓名、年級(jí)，表示為∏學(xué)號(hào)，姓名，年級(jí)(S1)，其結(jié)果如下表所示∏學(xué)號(hào)，姓名，年級(jí)(S1)學(xué)號(hào)姓名年級(jí)0501001張昊20200501010李穎20200501206王婷20203.1.2專(zhuān)門(mén)的關(guān)系運(yùn)算3.連接運(yùn)算從兩個(gè)關(guān)系R和S的廣義笛卡兒積中選取滿(mǎn)足給定條件F的元組組成新的關(guān)系的操作稱(chēng)為R和S的連接(Join)，其形式為:JON關(guān)系名1AND關(guān)系名2WHERE條件記作R∞FS，其中，條件F=AθB是由算術(shù)比較符θ∈{﹥、≧、﹤、≦、＝、≠}和屬性名或列號(hào)組成的條件表達(dá)式。A和B分別代表R的第A列和S的第B列屬性。3.1.2專(zhuān)門(mén)的關(guān)系運(yùn)算3.連接運(yùn)算當(dāng)連接運(yùn)算的條件為等號(hào)時(shí)，連接稱(chēng)為等值連接。連接后的結(jié)果包括R和S的所有字段，即結(jié)果中有重復(fù)字段。3.1.2專(zhuān)門(mén)的關(guān)系運(yùn)算當(dāng)連接運(yùn)算中的比較符為“="，且參與比較的兩個(gè)關(guān)系中用于比較的兩個(gè)屬性相同時(shí)，該連接稱(chēng)為自然連接(NaturalJoin)，自然連接運(yùn)算所產(chǎn)生的新關(guān)系由參與連接運(yùn)算的兩個(gè)關(guān)系中的所有屬性組成，但在兩個(gè)關(guān)系中都含有的作為等值比較對(duì)象的兩個(gè)屬性只出現(xiàn)一次，所以它不同于一般的等值連接。對(duì)于自然連接，無(wú)須標(biāo)明條件表達(dá)式F，只需在結(jié)果中把重復(fù)的屬性去掉，如關(guān)系R和關(guān)系S的自然連接記為R∞S。3.1.2專(zhuān)門(mén)的關(guān)系運(yùn)算學(xué)生基本信息表S5學(xué)生選課信息表S6

S5∞S6結(jié)果關(guān)系表學(xué)號(hào)姓名年級(jí)0501001張昊20200501010李穎20200501206王婷2020學(xué)號(hào)課程教室0501001數(shù)據(jù)庫(kù)B010501030C語(yǔ)言B020501010C語(yǔ)言B02學(xué)號(hào)姓名年級(jí)課程教室0501001張昊2020數(shù)據(jù)庫(kù)B010501010李穎2020C語(yǔ)言B023.1.2專(zhuān)門(mén)的關(guān)系運(yùn)算4.除運(yùn)算除運(yùn)算的含義是給定關(guān)系R(X，Y)和S(Y，Z)，其中X，Y，Z為屬性組。R中的Y與S中的Y可以有不同的屬性名，但必須出自相同的域集。R與S的除運(yùn)算得到一個(gè)新的關(guān)系P(X)，P是R中滿(mǎn)足下列條件的元組在X屬性列上的投影，元組在X上分量值x的象集Yx包含S在Y上投影的集合。3.1.2專(zhuān)門(mén)的關(guān)系運(yùn)算ABCa1b1c2a2b3c7a3b4c6a1b2c3a4b6c6a2b2c3a1b2c1R1BCDb1c2d1b2c1d1b2c3d2R2Aa1R1÷R2R1÷R2分析，在關(guān)系R1中，A可以取四個(gè)值{a1,a2,a3,a4}，其中：a1的象集為：{（b1,c2），（b2,c3），（b2,c1）}；a2的象集為：{（b3,c7），（b2,c3）}；a3的象集為：{（b4,c6）}；a4的象集為：{（b6,c6）}；R2在（B,C）上的投影為{(b1,c2),(b2,c3),(b2,c1)}。顯然只有R1的象集a1包含R2在（B,C）屬性組上的投影，所以R1÷R2={a1}。3.2設(shè)計(jì)方法與分布設(shè)計(jì)的目標(biāo)分布式數(shù)據(jù)庫(kù)的設(shè)計(jì)存在兩種設(shè)計(jì)方法，一種自上而下（Top-Down）的設(shè)計(jì)方法，另一種是自下而上（Bottom-Up）的設(shè)計(jì)方法，Bottom-Up的設(shè)計(jì)方法是多數(shù)據(jù)庫(kù)集成的核心研究?jī)?nèi)容，分布式數(shù)據(jù)庫(kù)的設(shè)計(jì)主要是與Top-Down的設(shè)計(jì)方法相關(guān)的內(nèi)容。3.2設(shè)計(jì)方法與分布設(shè)計(jì)的目標(biāo)Top-Down設(shè)計(jì)過(guò)程：3.2設(shè)計(jì)方法與分布設(shè)計(jì)的目標(biāo)Bottom-Up設(shè)計(jì)過(guò)程：3.2設(shè)計(jì)方法與分布設(shè)計(jì)的目標(biāo)數(shù)據(jù)庫(kù)分布設(shè)計(jì)的目標(biāo)：?降低費(fèi)用；?提高系統(tǒng)可靠性；?處理局部性；?易于擴(kuò)展處理能力和系統(tǒng)規(guī)模；?負(fù)載分布；3.3分片的定義及分類(lèi)分片的定義：分布式數(shù)據(jù)庫(kù)中數(shù)據(jù)的存儲(chǔ)單位稱(chēng)為片段。對(duì)全局?jǐn)?shù)據(jù)庫(kù)的劃分叫做分片。劃分的結(jié)果就是片段。每個(gè)片段可以保存在一個(gè)以上的場(chǎng)地（服務(wù)器）上。3.3分片的定義及分類(lèi)分片主要作用：?減少網(wǎng)絡(luò)傳輸量；?增大事務(wù)處理的局部性；?提高數(shù)據(jù)的可用性和查詢(xún)效率；?負(fù)載均衡；3.3分片的定義及分類(lèi)分片設(shè)計(jì)過(guò)程：3.3分片的定義及分類(lèi)分片原則：1.完備性條件必須把全局關(guān)系的所有數(shù)據(jù)映射到片段中，決不允許有屬于全局關(guān)系的數(shù)據(jù)卻不屬于它的任何一個(gè)片段。3.3分片的定義及分類(lèi)分片原則：2.可重構(gòu)條件必須保證能夠由同一個(gè)全局關(guān)系的各個(gè)片段來(lái)重建該全局關(guān)系。劃分所采用的方法必須確保能夠由全局關(guān)系的各個(gè)片段來(lái)重建該全局關(guān)系。3.3分片的定義及分類(lèi)分片原則：3.不相交條件：要求一個(gè)全局關(guān)系被分割后所得的各個(gè)數(shù)據(jù)片段互不重疊。之所以要施加這個(gè)限制，其目的是為了在數(shù)據(jù)分配時(shí)易于控制數(shù)據(jù)的復(fù)制。3.3分片的定義及分類(lèi)分片的類(lèi)型：?水平分片；?垂直分片；?導(dǎo)出分片；?混合分片；3.3分片的定義及分類(lèi)分布透明性的定義：指用戶(hù)或用戶(hù)程序使用分布式數(shù)據(jù)庫(kù)如同使用集中式數(shù)據(jù)庫(kù)那樣，不必關(guān)心全局?jǐn)?shù)據(jù)的分布情況，包括全局?jǐn)?shù)據(jù)的邏輯分片情況、邏輯片段的站點(diǎn)位置分配情況，各站點(diǎn)數(shù)據(jù)庫(kù)的數(shù)據(jù)模型等情況對(duì)用戶(hù)和用戶(hù)程序是透明的。3.3分片的定義及分類(lèi)分布透明性的三個(gè)層次：?分片透明性；?位置透明性；?局部數(shù)據(jù)模型透明性；3.4水平分片水平分片是按照一定的條件對(duì)全局關(guān)系元組的劃分，即把全局關(guān)系的所有元組劃分成若干不相交的子集。3.4.1水平分片的概念定義：設(shè)有一個(gè)關(guān)系R，{R1,R2…….Rn}為R的子關(guān)系的集合，如果{R1,R2…….Rn}滿(mǎn)足以下條件，則稱(chēng)其為關(guān)系R的水平分片，稱(chēng)Ri為R的一個(gè)水平片段。（1）R1,R2…….Rn與R具有相同的關(guān)系模式。（2）R1∪R2….∪Rn=R（3）Ri∩Rj=φ(i≠j,1≤i≤n,1≤j≤n)3.4.1水平分片的概念從水平分片的定義可以看出，所謂水平分片，就是按某種特定條件把一全局關(guān)系的所有元組劃分成若干不相交的子集。每個(gè)水平片段由關(guān)系中的某個(gè)屬性上的條件來(lái)定義，該屬性稱(chēng)為分片屬性。該條件稱(chēng)為分片條件。不相交的子集滿(mǎn)足完備性條件、可重構(gòu)條件和不相交條件。3.4.1水平分片的概念例有一個(gè)全局關(guān)系模式為：student(snum,name,college)，其中snum為學(xué)生編號(hào)，name為學(xué)生姓名，college為學(xué)生所在的學(xué)院，并假定學(xué)生所在學(xué)院的只有兩個(gè)即”計(jì)算機(jī)”和”數(shù)學(xué)”。按下面的條件進(jìn)行水平分片：student1：滿(mǎn)足college＝”計(jì)算機(jī)”的所有元組；student2：滿(mǎn)足college＝”數(shù)學(xué)”的所有元組；3.4.1水平分片的概念在該分片中college為分片屬性，分為兩個(gè)片段student1和student2，用選擇操作可以表示為：student1=σcollege=”計(jì)算機(jī)”(student)；student2=σcollege=”數(shù)學(xué)”(student)；全局關(guān)系student的這種水平分片如下圖表示。3.4.1水平分片的概念3.4.1水平分片的概念1.滿(mǎn)足完備性條件由于”計(jì)算機(jī)”與”數(shù)學(xué)”是college屬性的所有可能取值，所以上面的分片無(wú)疑是滿(mǎn)足完備性條件的。如果college的屬性還可能有其它取值，則上述的分片就不滿(mǎn)足完備住條件。因?yàn)檫@些其它c(diǎn)ollege值的元組屬于全局關(guān)系student，但確既不屬于student1也不屬于student2。3.4.1水平分片的概念2.滿(mǎn)足可重構(gòu)條件重構(gòu)條件是易于驗(yàn)證的，因?yàn)榭偸悄芡ㄟ^(guò)下列運(yùn)算來(lái)重構(gòu)student全局關(guān)系：student=student1∪student2。3.4.1水平分片的概念3.滿(mǎn)足不相交條件Student的水平分片Student1、Student2，不相交條件總是滿(mǎn)足的。因?yàn)閟num作為全局關(guān)系student關(guān)鍵字，它唯一地標(biāo)識(shí)了一個(gè)學(xué)生。這個(gè)學(xué)生的college值或取”計(jì)算機(jī)”，或取”數(shù)學(xué)”，因此，student關(guān)系中的每一個(gè)元組只能分在一個(gè)片段中。3.4.2水平分片的操作水平分片是針對(duì)該關(guān)系的選擇操作，用σ表示，假設(shè)選擇條件為分片謂詞q,則關(guān)系的R的分片操作可表示為：σq（R）。例設(shè)有雇員關(guān)系EMP{ENO,ENAME,SALARY,DNO}，其中ENO為雇員編號(hào)，ENAME為雇員姓名，SALARY為雇員工資，DNO為雇員所在部門(mén)的部門(mén)編號(hào)，其取值為“101”、“201”“、“301”。3.4.2水平分片的操作按下面的條件進(jìn)行水平分片：E1：滿(mǎn)足DNO=”101”的所有元組；E2：滿(mǎn)足DNO=”201”的所有元組；E3：滿(mǎn)足DNO=”301”的所有元組；雇員關(guān)系EMP的水平分片E1、E2、E3用選擇操作描述如下：E1=σDNO=”101”(EMP)；E2=σDNO=”201”(EMP)；E3=σDNO=”301”(EMP)；3.4.3水平分片的原理對(duì)全局進(jìn)行水平分片時(shí)，必須遵守完備性、可重構(gòu)性和不相交性條件，以保證分布式數(shù)據(jù)庫(kù)中數(shù)據(jù)的完整性和一致性。由于全局關(guān)系的水平分片可以由選擇運(yùn)算中的限定的集合（既謂詞集）唯一的決定，因此，謂詞集P也必須遵守完備性、可重構(gòu)性和不相交性條件。3.4.3水平分片的原理定義1：若全局關(guān)系R中屬性X具有地理分布特征或?qū)傩訶的域的任一劃分都構(gòu)成全局關(guān)系的元組的不同的聚集，則稱(chēng)屬性X具有分類(lèi)特征。定義2：若全局關(guān)系R中的屬性X滿(mǎn)足：（1）DOM(X)是可數(shù)有限集合（2）屬性X具有分類(lèi)特征；則稱(chēng)屬性X為關(guān)系R的分類(lèi)屬性。3.4.3水平分片的原理命題1：對(duì)于關(guān)系R的水平分片謂詞集P，如果對(duì)P中出現(xiàn)的分類(lèi)屬性集{X1，X2，…，xn)的域DOM(X1)、DOM(X2)，……DOM(Xn)構(gòu)成劃分，則謂詞集P對(duì)分類(lèi)屬性集{X1，X2，…，xn)是完備的。3.4.3水平分片的原理命題2：如果謂詞集P={P1，P2，…，Pn)中的謂問(wèn)兩兩互斥，即Pi∧Pj=FALSE（i≠j），且Pi（1≤i≤n）不為永假，則每一謂詞Pi都構(gòu)成一個(gè)片段。3.4.3水平分片的原理定理如果謂詞集P={P1，P2，…，Pn)是基于關(guān)系R中分類(lèi)屬性集{X1，X2，…，xn)的，且P中的謂詞兩兩互斥并對(duì){X1，X2，…，xn)是完備的，則謂詞集P決定關(guān)系R的一種水平分片。3.4.3水平分片的原理水平分片謂詞集P生成方法：（1）根據(jù)查詢(xún)模型選取關(guān)系R中合適的分類(lèi)屬性集{X1，X2，…，xn)，并確定各自的域DOM(X1)、DOM(X2)、…、DOM(Xn)。（2）根據(jù)查詢(xún)對(duì)分片的要求，選取一個(gè)適當(dāng)?shù)闹^詞P1，令P＝{P1}。（3）選取新的適當(dāng)謂詞Pi，Pi與P中謂詞互斥，置P←P∪{Pi}，直至P構(gòu)成DOM(X1)、DOM(X2)…、DOM(Xn)的劃分。3.5導(dǎo)出水平分片若一個(gè)關(guān)系的分片不是基于關(guān)系本身的屬性，而是根據(jù)另一個(gè)與其有關(guān)聯(lián)的屬性來(lái)劃分，這種劃分為導(dǎo)出水平劃分。3.5.1導(dǎo)出水平分片的概念定義：如果一個(gè)關(guān)系的水平分片的分片屬性屬于另一個(gè)關(guān)系，則該分片稱(chēng)為導(dǎo)出水平分片。3.5.1導(dǎo)出水平分片的概念例有雇員關(guān)系EMP{ENO,ENAME,SALARY,DNO}，其中ENO為雇員編號(hào)，ENAME為雇員姓名，SALARY為雇員工資，DNO為雇員所在的部門(mén)編號(hào)。其元組如下表1所示。關(guān)系WORKS{ENO,PRJNO,HOURS}，其中ENO為雇員編號(hào)，PRJNO為雇員參與的項(xiàng)目編號(hào)，HOURS為雇員參與項(xiàng)目的小時(shí)數(shù)，其元組如表2所示。3.5.1導(dǎo)出水平分片的概念表1EMP關(guān)系表表2WORKS元組內(nèi)容ENOENAMESALARYDNO001張穎2000101002李強(qiáng)3000201003王麗4000301ENOPRJNOHOURS0011200002130000325003.5.1導(dǎo)出水平分片的概念要求將WORKS按DNO進(jìn)行水平分片，得到的導(dǎo)出水平分片記為W1、W2、W3，要求如下：W1：滿(mǎn)足DNO=”101”的所有元組，既：W1=∏ATTR(WORKS)(σDNO=”101”(WORKS∞EMP))W2：滿(mǎn)足DNO=”201”的所有元組，既：W2=∏ATTR(WORKS)(σDNO=”201”(WORKS∞EMP))W3：滿(mǎn)足DNO=”301”的所有元組，既：W3=∏ATTR(WORKS)(σDNO=”301”(WORKS∞EMP))其中ATTR(WORKS)為WORKS的屬性組。3.5.1導(dǎo)出水平分片的概念分片屬性為：部門(mén)編號(hào)DNO.分片條件為：W1:DNO=”101”；W2:DNO=”201”；W3:DNO=”301”；3.5.1導(dǎo)出水平分片的概念根據(jù)水平分片定義，滿(mǎn)足：（1）W1、W2、W3和WORKS具有相同的關(guān)系模式；（2）W1∪W2∪W3=WORKS；（3）W1∩W2=φ，W1∩W3=φ，W2∩W3=φ。因此，W1、W2、W3滿(mǎn)足完備性條件、可重構(gòu)條件和不相交條件，是WORKS的水平分片。由于該分片屬性為DNO，是WORKS關(guān)系相關(guān)聯(lián)關(guān)系EMP的屬性，因此該水平分片為導(dǎo)出水平分片。3.5.2導(dǎo)出水平分片的操作導(dǎo)出水平分片操作不是基于關(guān)系本身的屬性，而是根據(jù)另一個(gè)與其有關(guān)聯(lián)關(guān)系的屬性來(lái)劃分的。因此導(dǎo)出水平分片可以用連接操作和選擇操作來(lái)表示。上面例子中的導(dǎo)出水平分片，具體操作表示如下：1.求出WORKS中DNO，采用自然連接∞。令：W’=WORKS∞EMP，w’=(ENO,PRJNO,HOURS,ENAME,SALARY,DNO)。3.5.2導(dǎo)出水平分片的操作2.根據(jù)DNO對(duì)W’進(jìn)行水平分片。W1’=σDNO=”101”(W’)=σDNO=”101”(WORKS∞EMP)；W2’=σDNO=”201”(W’)=σDNO=”201”(WORKS∞EMP)；W3’=σDNO=”301”(W’)=σDNO=”301”(WORKS∞EMP)。3.5.2導(dǎo)出水平分片的操作3.只保留WORKS的屬性W1=∏ATTR(WORKS)(W1’)=∏ATTR(WORKS)(σDNO=”101”(WORKS∞EMP))；W2=∏ATTR(WORKS)(W2’)=∏ATTR(WORKS)(σDNO=”201”(WORKS∞EMP))；W3=∏ATTR(WORKS)(W3’)=∏ATTR(WORKS)(σDNO=”301”(WORKS∞EMP))。3.5.3導(dǎo)出水平分片的作用在兩個(gè)關(guān)系間存在相關(guān)屬性并滿(mǎn)足關(guān)聯(lián)完整性約束時(shí)，一個(gè)關(guān)系的水平分片常常可以導(dǎo)出另一個(gè)關(guān)系的水平分片，導(dǎo)出分片可以用來(lái)簡(jiǎn)化片段間的連接運(yùn)算。3.6.1垂直分片的概念定義：設(shè)有一個(gè)關(guān)系R，{R1,R2…….Rn}為R的子關(guān)系的集合，如果{R1,R2…….Rn}滿(mǎn)足以下條件，則稱(chēng)其為關(guān)系R的垂直分片，稱(chēng)Ri為R的一個(gè)垂直片段。（1）Attr(R1)∪Attr(R2)…..∪Attr(R1)=Attr(R)，其中Attr(R)表示關(guān)系R的屬性集；（2）{R1,R2…….Rn}為關(guān)系R的無(wú)損分解；（3）Attr(Ri)∩Attr(Rj)=PK(R)(i≠j,1≤i≤n,1≤j≤n)，其中PK(R)表示關(guān)系R的主關(guān)鍵字。3.6.1垂直分片的概念例設(shè)有雇員關(guān)系EMP(ENO,ENAME,SALARY,DNO)，其中ENO為雇員編號(hào)，ENAME為雇員姓名，SALARY為雇員工資，DNO為雇員所在部門(mén)的部門(mén)編號(hào)。元組內(nèi)容如下表所示。關(guān)系EMP元組內(nèi)容ENOENAMESALARYDNO001張穎2000101002李強(qiáng)3000201003王麗40003013.6.1垂直分片的概念今有兩種應(yīng)用，一是檢索關(guān)于雇員的姓名、部門(mén)編號(hào)等信息的管理；二是關(guān)于職工工資情況的管理。在這種情況下，這個(gè)全局關(guān)系可采用垂直分片，在屬性組ENO,ENAME,DNO和ENO、SALARY上進(jìn)行垂直分片，可用如下的投影運(yùn)算來(lái)實(shí)現(xiàn)：EMP1=∏ENO,ENAME,DNO(EMP)；EMP2=∏ENO,SALARY(EMP)；3.6.1垂直分片的概念全局關(guān)系EMP(ENO,ENAME,SALARY,DNO)垂直劃分為兩個(gè)片段EMP1、EMP2，如下圖所示。劃分滿(mǎn)足完備性、重構(gòu)性和不相交性。3.6.2垂直分片的操作垂直分片是針對(duì)該關(guān)系的投影操作，用∏表示，假設(shè)分片的屬性組為A，,則關(guān)系的R的分片操作可表示為：∏A（R）。3.6.3垂直分片的設(shè)計(jì)方法目前主要有兩種垂直分片的設(shè)計(jì)方法，這兩種方法都必須滿(mǎn)足垂直分片的定義。（1）分裂法。把全局關(guān)系的屬性逐個(gè)分離。然后根據(jù)查詢(xún)的要求把每個(gè)屬性放入一個(gè)或多個(gè)片段屬性集中。（2）組合法。把屬性聚集成各片段的屬性集。3.7混合分片在水平分片和垂直分片及導(dǎo)出分片的基礎(chǔ)上，可以進(jìn)行更加復(fù)雜的分片，混合分片過(guò)程中既包括水平分片又包括垂直分片?；旌戏制梢韵冗M(jìn)行水平分片再進(jìn)行垂直分片，或先進(jìn)行垂直分片再進(jìn)行水平分片，或其它形式，但它們的結(jié)果是不相同的。3.7混合分片例設(shè)有一個(gè)學(xué)生關(guān)系STUDENT(SNO,SNAME,BIRTH,SORE,DNO)，其中SNO為學(xué)生學(xué)號(hào)，NAME為學(xué)生姓名，BIRTH為生日，SORE為總成績(jī)，DNO為學(xué)生所在學(xué)院編號(hào)。元組內(nèi)容如下表所示：SNOSNAMBIRTHSOREDNO10001張三1999.02.2165010120001李四1999.07.2667620130001王五1999.03.206983013.7混合分片對(duì)關(guān)系STUDENT先進(jìn)性垂直分片，得到子關(guān)系STUDENT1和STUDENT2,再對(duì)STUDENT2按照DNO進(jìn)行水平分片，得到子關(guān)系STUDENT21、STUDENT22,、STUDENT23，既：STUDENT1=∏SNO,SNAME,BIRTH(STUDENT)；STUDENT2=∏SNO,SORE,,DNO(STUDENT)；STUDENT21=σDNO=”101”(STUDENT2)；STUDENT22=σDNO=”201”(STUDENT2)；STUDENT23=σDNO=”301”(STUDENT2)；3.7混合分片關(guān)系STUDENT的混合分片示意圖如下圖所示：3.8分片的表示方法為直觀地描述各種分片方式及便于對(duì)后續(xù)查詢(xún)處理和查詢(xún)優(yōu)化方法的理解，對(duì)水平分片、垂直分片和混合分片可采用直觀的圖形表示法和基于樹(shù)型結(jié)構(gòu)的分片樹(shù)表示法。3.8.1圖形表示法圖形表示法是用圖形直觀描述，其描述規(guī)則如下：（1）用一個(gè)整體矩形來(lái)表示全局關(guān)系。（2）用矩形的一部分來(lái)表示片段關(guān)系。（3）按水平劃分的部分表示水平分段。（4）按垂直劃分的部分表示垂直分段。（5）混合劃分既有水平劃分，又有垂直劃分。3.8.1圖形表示法表示關(guān)系E水平分片為E1、E2、E3的圖形表示如圖所示：表示關(guān)系E垂直分片為E1、E2圖形表示如圖所示：3.8.1圖形表示法表示關(guān)系E混合分片為E1(垂直分片)和對(duì)垂直分片E2的水平分片E21、E22、E23的圖形表示如圖所示：3.8.2分片樹(shù)表示方法全局關(guān)系的分片可用分片樹(shù)表示，分片樹(shù)包括水平分片樹(shù)、垂直分片樹(shù)和混合分片樹(shù)，分片樹(shù)由以下幾部分構(gòu)成：（1）根節(jié)點(diǎn)表示全局關(guān)系。（2）葉子結(jié)點(diǎn)表示最后得到的片段關(guān)系。（3）中間節(jié)點(diǎn)表示分片過(guò)程的中間結(jié)果。（4）邊表示分片操作，并用h（水平）和v（垂直）表示分片類(lèi)型。（5）節(jié)點(diǎn)名表示全局關(guān)系名和片段名。3.8.2分片樹(shù)表示方法表示關(guān)系EMP水平分片為E1、E2、E3的分片樹(shù)如圖：3.8.2分片樹(shù)表示方法表示關(guān)系EMP垂直分片為E1、E2的分片樹(shù)如圖：3.8.2分片樹(shù)表示方法表示關(guān)系EMP混合分片為E1(垂直分片)和對(duì)垂直分片E2水平分片為E21、E22、E23的分片樹(shù)如圖：3.9分布式數(shù)據(jù)庫(kù)數(shù)據(jù)分配設(shè)計(jì)類(lèi)型全局?jǐn)?shù)據(jù)經(jīng)過(guò)分片設(shè)計(jì)，得到各個(gè)劃分的片段，片段到物理場(chǎng)地的存儲(chǔ)映射過(guò)程稱(chēng)為分配設(shè)計(jì)過(guò)程。數(shù)據(jù)分配問(wèn)題就是給定一組數(shù)據(jù)片段，并針對(duì)這些數(shù)據(jù)片段的操作及其使用頻率，分配這組數(shù)據(jù)到網(wǎng)絡(luò)的各個(gè)節(jié)點(diǎn)，使得總代價(jià)最小。3.9.1分配設(shè)計(jì)的概念定義：設(shè)有一個(gè)由站點(diǎn)集S=(S1，S2，?，Sm)構(gòu)成的網(wǎng)絡(luò)，該網(wǎng)絡(luò)上運(yùn)行一個(gè)事務(wù)集T=(T1，T2，?，Tq)，存儲(chǔ)著一個(gè)片段集F=(F1，F(xiàn)2，?，F(xiàn)n)。按照一定的方式將每個(gè)片段Fi的不同副本分配到不同的站點(diǎn)Sj上的分配方案，表示為A<F，S，T>，就是所謂的片段分配問(wèn)題。3.9.2數(shù)據(jù)分配的準(zhǔn)則數(shù)據(jù)分配的準(zhǔn)則主要有以下三個(gè)方面的內(nèi)容：1.分布式數(shù)據(jù)庫(kù)的本地性或近地性2.系統(tǒng)任務(wù)的均衡性3.數(shù)據(jù)可用性和可靠性3.9.3分配類(lèi)型數(shù)據(jù)分配中主要分為冗余分配和非冗余分配，非冗余分配即每個(gè)片段只是分配到一個(gè)站點(diǎn)上，片段與站點(diǎn)間是一對(duì)一的關(guān)系。冗余分配即每個(gè)片段分配到多個(gè)站點(diǎn)，片段與站點(diǎn)之間是多對(duì)一的關(guān)系。非冗余分配為非復(fù)制分配，包括集中式分配和分割式分配，冗余分配為復(fù)制分配，包括全復(fù)制分配和部分復(fù)制分配。3.9.3分配類(lèi)型1.集中式分配數(shù)據(jù)有劃分，但是劃分后的邏輯片段依然完全集中在一個(gè)節(jié)點(diǎn)，即有分片無(wú)分配，且沒(méi)有數(shù)據(jù)副本存在。嚴(yán)格說(shuō)來(lái)，這不能算作是分布式數(shù)據(jù)庫(kù)；3.9.3分配類(lèi)型2.分割式分配數(shù)據(jù)分布在各個(gè)節(jié)點(diǎn)上，彼此之間沒(méi)有重復(fù)數(shù)據(jù)；每個(gè)片段只存儲(chǔ)在一個(gè)場(chǎng)地上，稱(chēng)為分割式分配，對(duì)應(yīng)的分布式數(shù)據(jù)庫(kù)稱(chēng)為全分割式數(shù)據(jù)庫(kù)。設(shè)R為全局關(guān)系，R1、R2、R3為劃分的片段，分割式分配如圖所示。3.9.3分配類(lèi)型3.9.3分配類(lèi)型3.全復(fù)制分配數(shù)據(jù)分布在各個(gè)節(jié)點(diǎn)上，如果每個(gè)片段在每個(gè)場(chǎng)地上都存有副本，則稱(chēng)為全復(fù)制分配，對(duì)應(yīng)的分布式數(shù)據(jù)庫(kù)稱(chēng)為全復(fù)制式數(shù)據(jù)庫(kù)。設(shè)R為全局關(guān)系，R1、R2、R3為劃分的片段，全復(fù)制分配如圖所示。3.9.3分配類(lèi)型3.9.3分配類(lèi)型4.部分復(fù)制分配數(shù)據(jù)分布在各個(gè)節(jié)點(diǎn)上，如果每個(gè)片段只在部分場(chǎng)地上存有副本，則稱(chēng)為部分復(fù)制分配，對(duì)應(yīng)的分布式數(shù)據(jù)庫(kù)稱(chēng)為部分復(fù)制式數(shù)據(jù)庫(kù)。設(shè)R為全局關(guān)系，R1、R2、R3為劃分的片段，部分復(fù)制分配如圖所示。3.9.3分配類(lèi)型3.10分配設(shè)計(jì)算法數(shù)據(jù)分配問(wèn)題其實(shí)就是要解決以一種怎樣的方式將所有的數(shù)據(jù)片段分布到分布式數(shù)據(jù)庫(kù)系統(tǒng)的各個(gè)站點(diǎn)上，使得代價(jià)最小，這是分布式數(shù)據(jù)庫(kù)的設(shè)計(jì)者們?cè)诳紤]數(shù)據(jù)分配問(wèn)題時(shí)不變的準(zhǔn)則。3.10.1數(shù)據(jù)分配方法優(yōu)劣的度量不同的分配方法所使用的最優(yōu)化模型中采用不同的優(yōu)化度量，但是嚴(yán)格來(lái)說(shuō)，考慮最優(yōu)化問(wèn)題應(yīng)該兼顧優(yōu)化和性能兩個(gè)因素，即分配結(jié)果能使分布式數(shù)據(jù)庫(kù)系統(tǒng)達(dá)到最小的響應(yīng)時(shí)間或最大系統(tǒng)吞吐量而同時(shí)又保持處理代價(jià)最小。因此關(guān)于優(yōu)化通常有兩個(gè)度量標(biāo)準(zhǔn)。1.最小代價(jià)2.性能3.10.2非冗余分配算法常用的數(shù)據(jù)分配方法有非冗余分配方法和冗余分配方法兩種。非冗余分配方法是將每個(gè)數(shù)據(jù)片段都無(wú)冗余地分配到網(wǎng)絡(luò)中的某個(gè)場(chǎng)地上。這種方法相對(duì)比較簡(jiǎn)單。冗余分配方法允許將一個(gè)數(shù)據(jù)片段同時(shí)分配到多個(gè)不同的場(chǎng)地上，這種分配方法由于涉及到查詢(xún)或