第6章關(guān)系數(shù)據(jù)理論20142

1、1第第6章章關(guān)系數(shù)據(jù)理論關(guān)系數(shù)據(jù)理論2課課 程程 C教教 員員 T參參 考考 書(shū)書(shū) B 物理物理 數(shù)學(xué)數(shù)學(xué) 計(jì)算數(shù)學(xué)計(jì)算數(shù)學(xué)李李 勇勇王王 軍軍 李李 勇勇張張 平平 張張 平平周周 峰峰 普通物理學(xué)普通物理學(xué)光學(xué)原理光學(xué)原理 物理習(xí)題集物理習(xí)題集 數(shù)學(xué)分析數(shù)學(xué)分析微分方程微分方程高等代數(shù)高等代數(shù) 數(shù)學(xué)分析數(shù)學(xué)分析6.2.7 多值依賴多值依賴?yán)? 學(xué)校中某一門(mén)課程由多個(gè)教師講授，他們使用相同的學(xué)校中某一門(mén)課程由多個(gè)教師講授，他們使用相同的一套參考書(shū)。一套參考書(shū)。關(guān)系模式關(guān)系模式Teaching(C, T, B) 課程課程C、教師、教師T 和和 參考書(shū)參考書(shū)B(niǎo) 3普通物理學(xué)普通物理學(xué)光學(xué)原理光

2、學(xué)原理物理習(xí)題集物理習(xí)題集普通物理學(xué)普通物理學(xué)光學(xué)原理光學(xué)原理物理習(xí)題集物理習(xí)題集數(shù)學(xué)分析數(shù)學(xué)分析微分方程微分方程高等代數(shù)高等代數(shù)數(shù)學(xué)分析數(shù)學(xué)分析微分方程微分方程高等代數(shù)高等代數(shù)李李 勇勇李李 勇勇李李 勇勇王王 軍軍王王 軍軍王王 軍軍李李 勇勇李李 勇勇李李 勇勇張張 平平張張 平平張張 平平 物物 理理物物 理理物物 理理物物 理理物物 理理物物 理理數(shù)數(shù) 學(xué)學(xué)數(shù)數(shù) 學(xué)學(xué)數(shù)數(shù) 學(xué)學(xué)數(shù)數(shù) 學(xué)學(xué)數(shù)數(shù) 學(xué)學(xué)數(shù)數(shù) 學(xué)學(xué) 參考書(shū)B(niǎo)教員T課程C關(guān)系模式關(guān)系模式TEACHING（C，T，B），），它的碼它的碼是（是（C，T，B），），所以所以屬于屬于BCNF。 存在的問(wèn)題：存在的問(wèn)題：(1)插入異常：

3、插入異常：當(dāng)某門(mén)當(dāng)某門(mén)課程增加一名教員時(shí)，課程增加一名教員時(shí)，該門(mén)課程有多少本參該門(mén)課程有多少本參考書(shū)就必須插入多少考書(shū)就必須插入多少個(gè)元組；同樣當(dāng)某門(mén)個(gè)元組；同樣當(dāng)某門(mén)課程需要增加一本參課程需要增加一本參考書(shū)時(shí)，它有多少個(gè)考書(shū)時(shí)，它有多少個(gè)教員就必須插入多少教員就必須插入多少個(gè)元組。個(gè)元組。4普通物理學(xué)普通物理學(xué)光學(xué)原理光學(xué)原理物理習(xí)題集物理習(xí)題集普通物理學(xué)普通物理學(xué)光學(xué)原理光學(xué)原理物理習(xí)題集物理習(xí)題集數(shù)學(xué)分析數(shù)學(xué)分析微分方程微分方程高等代數(shù)高等代數(shù)數(shù)學(xué)分析數(shù)學(xué)分析微分方程微分方程高等代數(shù)高等代數(shù)李李 勇勇李李 勇勇李李 勇勇王王 軍軍王王 軍軍王王 軍軍李李 勇勇李李 勇勇李李 勇勇張張

4、平平張張 平平張張 平平 物物 理理物物 理理物物 理理物物 理理物物 理理物物 理理數(shù)數(shù) 學(xué)學(xué)數(shù)數(shù) 學(xué)學(xué)數(shù)數(shù) 學(xué)學(xué)數(shù)數(shù) 學(xué)學(xué)數(shù)數(shù) 學(xué)學(xué)數(shù)數(shù) 學(xué)學(xué) 參考書(shū)B(niǎo)教員T課程C存在的問(wèn)題：存在的問(wèn)題：(2)刪除異常：刪除異常：當(dāng)刪當(dāng)刪除一門(mén)課程的某個(gè)教除一門(mén)課程的某個(gè)教員或者某本參考書(shū)時(shí)，員或者某本參考書(shū)時(shí)，需要?jiǎng)h除多個(gè)元組。需要?jiǎng)h除多個(gè)元組。(3)更新異常：更新異常：當(dāng)一當(dāng)一門(mén)課程的教員或參考門(mén)課程的教員或參考書(shū)作出改變時(shí)，需要書(shū)作出改變時(shí)，需要修改多個(gè)元組。修改多個(gè)元組。(4)數(shù)據(jù)冗余：數(shù)據(jù)冗余：同一同一門(mén)課的教員與參考書(shū)門(mén)課的教員與參考書(shū)的信息被反復(fù)存儲(chǔ)多的信息被反復(fù)存儲(chǔ)多次。次。5【定義定義6

5、.9】 關(guān)系模式關(guān)系模式R(U)，X、Y、Z U， 并且并且Z = U X Y， 多值依賴多值依賴X Y 成立當(dāng)且僅當(dāng)對(duì)成立當(dāng)且僅當(dāng)對(duì)R(U) 的任一關(guān)系的任一關(guān)系r，給定的一對(duì)（，給定的一對(duì)（x，z）值有一組）值有一組y 的值，這組值僅僅決定于的值，這組值僅僅決定于x 值而與值而與z 值無(wú)關(guān)。值無(wú)關(guān)。 物物 理理,普通物理學(xué)普通物理學(xué) 李李 勇勇,王王 軍軍物物 理理,光學(xué)原理光學(xué)原理 李李 勇勇,王王 軍軍物物 理理,物理習(xí)題集物理習(xí)題集 李李 勇勇,王王 軍軍對(duì)于對(duì)于C的每一個(gè)值，的每一個(gè)值，T有一組值與之對(duì)應(yīng)，而不論有一組值與之對(duì)應(yīng)，而不論B取何值。取何值。若若XY而而Z=，則稱則稱X

6、Y為平凡的多值依賴，為平凡的多值依賴，否則稱否則稱XY為非平凡的多值依賴。為非平凡的多值依賴。6【形式化定義形式化定義】在在R（U）的任一關(guān)系）的任一關(guān)系r中，如果存中，如果存在元組在元組t、s ，使得，使得tX=sX，那么就必然存在元組，那么就必然存在元組 w，v r，（，（w，v可以與可以與s，t相同），使得相同），使得wX=vX=tX，而，而wY=tY，wZ=sZ，vY=sY，vZ=tZ（即交換（即交換s，t元組的元組的Y值所得值所得的兩個(gè)新元組必在的兩個(gè)新元組必在r中），則中），則Y多值依賴于多值依賴于X，記為，記為XY。 這里，這里，X，Y是是U的子集，的子集，Z=U-X-Y。 t

7、x y1 z2 s x y2 z1 w x y1 z1 v x y2 z2若若(C, T, B)滿足滿足CT， 含有元組含有元組t1=(C1, T1, B1)，t2=(C1, T2, B2)，則也一定含有元組，則也一定含有元組t3=(C1, T1, B2)，t4=(C1, T2, B1)。 7例如：例如：P179 關(guān)系模式關(guān)系模式WSC（ W，S，C ）中，）中，W表示倉(cāng)庫(kù)，表示倉(cāng)庫(kù)，S表示保管員，表示保管員，C表示商品。表示商品。 假設(shè)，每個(gè)倉(cāng)庫(kù)有若干個(gè)保管員，有若干種商假設(shè)，每個(gè)倉(cāng)庫(kù)有若干個(gè)保管員，有若干種商品。每個(gè)保管員包管所在倉(cāng)庫(kù)的所有商品，每種商品。每個(gè)保管員包管所在倉(cāng)庫(kù)的所有商品，

8、每種商品被該倉(cāng)庫(kù)的所有保管員包管。品被該倉(cāng)庫(kù)的所有保管員包管。 存在是函數(shù)依賴：存在是函數(shù)依賴： W S W C81. 多值依賴多值依賴的的性質(zhì)性質(zhì) （1）多值依賴具有對(duì)稱性，多值依賴具有對(duì)稱性，即即 若若XY，則，則XZ，其中，其中Z=UXY。 （2）多值依賴具有多值依賴具有傳遞傳遞性，性，即即 若若XY，則，則YZ，則，則XZ-Y 。 （3）函數(shù)依賴是多值依賴的特例，）函數(shù)依賴是多值依賴的特例，即即 若若XY， 則則XY。 若若XY，UXY=， 則稱則稱XY 為平凡的多為平凡的多值依賴值依賴 。（4） 若若XY，XZ，則，則XYZ 。（5）若若XY，XZ，則，則XYZ 。（6）若若XY，X

9、Z，則，則XY-Z ，XZ-Y 。92. 多值依賴多值依賴與函數(shù)依賴的與函數(shù)依賴的區(qū)別區(qū)別（1）XY的有效性與屬性集范圍有關(guān)的有效性與屬性集范圍有關(guān)XY在在U上成立上成立 XY在屬性集在屬性集W（XY W U）上成立。上成立。反之，反之，XY在屬性集在屬性集W（XY W U）上成立，但在）上成立，但在U上不一定成立。上不一定成立。若在若在R(U)上，上，XY在屬性集在屬性集W(XY W U)上成立，則上成立，則稱稱XY為為R(U) 的嵌入式多值依賴。的嵌入式多值依賴。XY 的的 有效性僅決定于有效性僅決定于X、Y 屬性集上的值，它在任何屬性集上的值，它在任何屬性集屬性集W（XY W U） 上都

10、成立。上都成立。（2）若）若XY 在在R(U) 上成立，則對(duì)于任何上成立，則對(duì)于任何Y Y， 均有均有XY 成立。成立。 若若XY在在R(U)上成立，則不能斷言對(duì)于上成立，則不能斷言對(duì)于Y Y，是，是否有否有XY 成立。成立。10【定義定義6.10】 關(guān)系模式關(guān)系模式R 1NF， 若若XY（Y X） 是非平凡的多值依賴，且是非平凡的多值依賴，且X 含有含有碼，則稱碼，則稱R 4NF。 如關(guān)系模式如關(guān)系模式CTB，CT，CB， 碼為碼為(C, T , B)，C不是候選碼，所以不是候選碼，所以CTB 4NF。 如果一門(mén)課如果一門(mén)課Ci 有有m 個(gè)個(gè) 教員，教員，n 本本 參考書(shū)，則關(guān)參考書(shū)，則關(guān)系

11、中分量為系中分量為Ci 的元組共有的元組共有mn 個(gè)，數(shù)據(jù)冗余非常個(gè)，數(shù)據(jù)冗余非常大。大。 規(guī)范化：規(guī)范化： 4NF的要求是：消除非平凡且非函數(shù)依賴的多值的要求是：消除非平凡且非函數(shù)依賴的多值依賴。依賴。 將將CTB 分解為分解為CT（C，T），），CB（C，B），）， 在分解后的關(guān)系中分量為在分解后的關(guān)系中分量為Ci 的元組共有的元組共有m + n 個(gè)。個(gè)。 116.3 數(shù)據(jù)依賴的蘊(yùn)涵與公理系統(tǒng)數(shù)據(jù)依賴的蘊(yùn)涵與公理系統(tǒng)1. 函數(shù)依賴的邏輯蘊(yùn)含定義函數(shù)依賴的邏輯蘊(yùn)含定義 已經(jīng)討論了函數(shù)依賴的類(lèi)型及其對(duì)數(shù)據(jù)庫(kù)模式已經(jīng)討論了函數(shù)依賴的類(lèi)型及其對(duì)數(shù)據(jù)庫(kù)模式設(shè)計(jì)的影響和處理方法；設(shè)計(jì)的影響和處理方法；

12、 關(guān)于關(guān)于“處理方法處理方法”即范式設(shè)計(jì)，事實(shí)上是由模即范式設(shè)計(jì)，事實(shí)上是由模式分解而得，而模式分解的理論與方法是以數(shù)據(jù)依式分解而得，而模式分解的理論與方法是以數(shù)據(jù)依賴?yán)碚摓榛A(chǔ)理論的，所以需要較全面的討論數(shù)據(jù)賴?yán)碚摓榛A(chǔ)理論的，所以需要較全面的討論數(shù)據(jù)依賴?yán)碚摚灰蕾嚴(yán)碚摚?數(shù)據(jù)庫(kù)專(zhuān)家數(shù)據(jù)庫(kù)專(zhuān)家Armstrong等提出一組定義和推理規(guī)等提出一組定義和推理規(guī)則，并形成了一個(gè)有效而完備的理論體系，即則，并形成了一個(gè)有效而完備的理論體系，即Armstrong公理系統(tǒng)。公理系統(tǒng)。 數(shù)據(jù)依賴的公理系統(tǒng)是模式分解的理論基礎(chǔ)。數(shù)據(jù)依賴的公理系統(tǒng)是模式分解的理論基礎(chǔ)。12 函數(shù)依賴函數(shù)依賴F是很大的，如果依靠

13、語(yǔ)義分析方法是很大的，如果依靠語(yǔ)義分析方法找出一個(gè)關(guān)系模式的所有函數(shù)依賴，是一件很不找出一個(gè)關(guān)系模式的所有函數(shù)依賴，是一件很不容易的事。實(shí)際上，也是沒(méi)有必要的，因?yàn)橐唤M容易的事。實(shí)際上，也是沒(méi)有必要的，因?yàn)橐唤M函數(shù)依賴的存在，必定引起另外一組函數(shù)依賴的函數(shù)依賴的存在，必定引起另外一組函數(shù)依賴的出現(xiàn)。因此，出現(xiàn)。因此，可以用推理的方法，從一組已知的可以用推理的方法，從一組已知的函數(shù)依賴推導(dǎo)出另外一組函數(shù)依賴，而不必完全函數(shù)依賴推導(dǎo)出另外一組函數(shù)依賴，而不必完全用語(yǔ)義分析方法找出一個(gè)關(guān)系模式的所有函數(shù)依用語(yǔ)義分析方法找出一個(gè)關(guān)系模式的所有函數(shù)依賴賴。13【例例】關(guān)系模式關(guān)系模式 R=(A,B,C)

14、函數(shù)依賴集函數(shù)依賴集F=AB,BC, 則：必存在則：必存在AC。 這個(gè)例子說(shuō)明：函數(shù)依賴集這個(gè)例子說(shuō)明：函數(shù)依賴集F=AB,BC與與F=AB,BC ,AC之間存在著某種因果關(guān)之間存在著某種因果關(guān)系，即從系，即從F可以推導(dǎo)出可以推導(dǎo)出F，反之亦然。，反之亦然。 兩個(gè)函數(shù)依賴集之間的這種互為因果關(guān)系稱兩個(gè)函數(shù)依賴集之間的這種互為因果關(guān)系稱為邏輯蘊(yùn)涵，即一個(gè)函數(shù)依賴集邏輯蘊(yùn)涵另外一為邏輯蘊(yùn)涵，即一個(gè)函數(shù)依賴集邏輯蘊(yùn)涵另外一個(gè)函數(shù)依賴集。個(gè)函數(shù)依賴集。 F=AB,BC與與F=AB,BC ,AC相相互邏輯蘊(yùn)涵?；ミ壿嬏N(yùn)涵。14【定義定義6.11】對(duì)于滿足一組函數(shù)依賴對(duì)于滿足一組函數(shù)依賴F的關(guān)系模式的關(guān)系

15、模式RU,F,其任何一個(gè)關(guān)系其任何一個(gè)關(guān)系r,若函數(shù)依賴若函數(shù)依賴XY都成立都成立(即即r中任意兩元組中任意兩元組t,s,若若tX=sX,則則tY=sY),則稱則稱F邏輯蘊(yùn)含邏輯蘊(yùn)含XY，或稱，或稱XY 可從可從F中推出。中推出?！纠?】關(guān)系模式關(guān)系模式 R=(A,B,C),函數(shù)依賴集函數(shù)依賴集F=AB,BC, 則：則：F邏輯蘊(yùn)涵邏輯蘊(yùn)涵AC。證：設(shè)證：設(shè)u,v為為r中任意兩個(gè)元組：若中任意兩個(gè)元組：若AC不成立，不成立，則有則有uA=vA,而而uCvC 而而AB, BC,知知 uA=vA, uB=vB, uC=vC,即若即若uA=vA則則uC=vC，和假設(shè)矛，和假設(shè)矛盾。故盾。故F邏輯蘊(yùn)涵

16、邏輯蘊(yùn)涵AC。15【例例2】給定給定U=X，Y，Z，W，函數(shù)依賴集，函數(shù)依賴集F=XY，YZ，給定下列的關(guān)系實(shí)例，給定下列的關(guān)系實(shí)例r如表如表1所示，顯然，滿足函數(shù)依賴集所示，顯然，滿足函數(shù)依賴集F。元組號(hào)元組號(hào)XYZWt1adbat2adbbt3bcbct4bcbdt5ceae 例例2中，可觀察到中，可觀察到r還滿足還滿足XZ，但在函數(shù)依，但在函數(shù)依賴集賴集F中沒(méi)有中沒(méi)有XZ。那么，就需要考慮。那么，就需要考慮r除滿足除滿足F之外，是否還會(huì)滿足一些其它的函數(shù)依賴？之外，是否還會(huì)滿足一些其它的函數(shù)依賴？ 16 在上面的例子中，在上面的例子中，r實(shí)例滿足實(shí)例滿足F外，還滿足外，還滿足F所不所不包

17、括的包括的XZ，這就產(chǎn)生一個(gè)問(wèn)題，如何從，這就產(chǎn)生一個(gè)問(wèn)題，如何從F=XY，YZ推導(dǎo)得出推導(dǎo)得出XZ ? 這需要一套規(guī)則這需要一套規(guī)則從給定的函數(shù)依賴集推出其蘊(yùn)涵的函數(shù)依賴。從給定的函數(shù)依賴集推出其蘊(yùn)涵的函數(shù)依賴。 一套推理規(guī)則：是模式分解算法的理論基礎(chǔ)一套推理規(guī)則：是模式分解算法的理論基礎(chǔ)用途：用途：l從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴l這組推理規(guī)則是這組推理規(guī)則是l974年首先由年首先由Armstrong提出來(lái)的提出來(lái)的 172. Armstrong公理系統(tǒng)公理系統(tǒng) 若若U為關(guān)系模式為關(guān)系模式R的屬性全集，的屬性全集，F(xiàn)為為U上的一組上的一組函數(shù)依賴，設(shè)函數(shù)依

18、賴，設(shè)X、Y、Z、W均為均為R的子集，對(duì)的子集，對(duì)R(U,F)有以下的推理規(guī)則：有以下的推理規(guī)則：（1）A1(自反律自反律)：若：若Y X U ，則，則XY為為F所所蘊(yùn)涵；蘊(yùn)涵；（注意，由自反律所得到的函數(shù)依賴均是平（注意，由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴，自反律的使用并不依賴于凡的函數(shù)依賴，自反律的使用并不依賴于F。 ）（2）A2(增廣律增廣律): 若若XY為為F所蘊(yùn)涵，且所蘊(yùn)涵，且 Z U，則則XZYZ為為F所蘊(yùn)涵；所蘊(yùn)涵； （YZ表示并集）表示并集） （3）A3(傳遞律傳遞律): 若若XY,YZ為為F所蘊(yùn)涵，則所蘊(yùn)涵，則XZ為為F所蘊(yùn)涵。所蘊(yùn)涵。18【定理定理6.l】Armst

19、rong推理規(guī)則是正確的。推理規(guī)則是正確的。證明：證明： (1) 設(shè)設(shè)Y X U 。 對(duì)對(duì)RU,F的任一關(guān)系的任一關(guān)系r中的中的任意兩個(gè)元組任意兩個(gè)元組t，s： 若若tX=sX，由于，由于Y X，有，有tY=sY, 所以所以XY成立，自反律得證。成立，自反律得證。 (2) 設(shè)設(shè)XY為為F所蘊(yùn)含所蘊(yùn)含,且且Z U。 設(shè)設(shè)RU,F的任一關(guān)系的任一關(guān)系r中任意的兩個(gè)元組中任意的兩個(gè)元組t,s； 若若tXZ=sXZ，則有，則有tX=sX和和tZ=sZ； 由由XY,于是有于是有tY=sY，所以，所以tYZ=sYZ，所，所以以XZYZ為為F所蘊(yùn)含，增廣律得證。所蘊(yùn)含，增廣律得證。19(3) 設(shè)設(shè)XY及及Y

20、Z為為F所蘊(yùn)含。所蘊(yùn)含。 對(duì)對(duì)RU,F的任一關(guān)系的任一關(guān)系r中的任意兩個(gè)元組中的任意兩個(gè)元組t,s 。 若若tX=sX,由于由于XY,有有tY=sY； 再由再由YZ,有有tZ=sZ,所以所以XZ為為F所蘊(yùn)含，傳所蘊(yùn)含，傳遞律得證。遞律得證。 人們把自反律人們把自反律,傳遞律和增廣律稱為傳遞律和增廣律稱為Armstrong公公理系統(tǒng)。理系統(tǒng)。 20Armstrong公理的有效性及完備性公理的有效性及完備性A = f | 可用可用Armstrong公理從公理從F中導(dǎo)出的函數(shù)依賴中導(dǎo)出的函數(shù)依賴f B = f | 被被F所邏輯蘊(yùn)涵的函數(shù)依賴所邏輯蘊(yùn)涵的函數(shù)依賴f l有效性：用有效性：用Armstro

21、ng公理從公理從F中導(dǎo)出的函數(shù)依賴中導(dǎo)出的函數(shù)依賴必為必為F所蘊(yùn)涵。所蘊(yùn)涵。 A Bl完備性：完備性：F所蘊(yùn)涵的函數(shù)依賴都能用所蘊(yùn)涵的函數(shù)依賴都能用Armstrong公公理從理從F中導(dǎo)出。中導(dǎo)出。 B A21 由由A1、A2和和A3推理規(guī)則，可以得到下面推理規(guī)則，可以得到下面3條推條推理規(guī)則：理規(guī)則：（1）合并規(guī)則：）合并規(guī)則：若若XY,XZ為為F所蘊(yùn)涵，則所蘊(yùn)涵，則XYZ為為F所蘊(yùn)涵；所蘊(yùn)涵； （2）偽傳遞規(guī)則：）偽傳遞規(guī)則：若若XY，WYZ為為F所蘊(yùn)涵所蘊(yùn)涵, 則則XWZ為為F所蘊(yùn)涵；所蘊(yùn)涵；（3）分解性規(guī)則）分解性規(guī)則: 若若XY，Z Y 為為F所蘊(yùn)涵，則所蘊(yùn)涵，則XZ為為F所蘊(yùn)涵。所蘊(yùn)

22、涵。 22證明：證明： （1）推論）推論1顯然成立。顯然成立。 （2）推論）推論2的證明。的證明。由由XY，利用增廣律可得，利用增廣律可得XWYW。由。由YWZ，利用傳遞律得到利用傳遞律得到XWZ。 （3）推論）推論3的證明。的證明。 由由Z Y，利用自返律得到，利用自返律得到Y(jié)Z。由。由XY，利用，利用傳遞律得到傳遞律得到XZ。23【例例3】 R, U = (A, B, C, D, E), F = ABCD, AB, DE, 求證，求證， AE。證明：證明：（1） AB， AAB（增廣律）（增廣律）（2） AAB,ABCD, A CD （傳遞律）（傳遞律）（3） ACD, A C , AD

23、（分解規(guī)則）（分解規(guī)則）（4） AD, DE A E （傳遞律）（傳遞律）24 根據(jù)合并規(guī)則和分解規(guī)則，很容易得到這樣一根據(jù)合并規(guī)則和分解規(guī)則，很容易得到這樣一個(gè)重要事實(shí)：個(gè)重要事實(shí)： 【引理引理6.1】X A1A2Ak成立的充分必要條件是成立的充分必要條件是X Ai成立（成立（i1，2，k）。）?！纠?】R, U = (A, B, C, G, H, I), F = AB, AC, CGH, CGI, BH, A H？CG HI？AG I？問(wèn)題：?jiǎn)栴}：有沒(méi)有一般性的算法判定有沒(méi)有一般性的算法判定XY是否能由是否能由F 根據(jù)根據(jù)Armstrong 公理導(dǎo)出？公理導(dǎo)出？253. 函數(shù)依賴的閉包理

24、論函數(shù)依賴的閉包理論（1）函數(shù)依賴閉包、屬性集閉包）函數(shù)依賴閉包、屬性集閉包【定義定義6.12】在關(guān)系模式在關(guān)系模式R（U，F(xiàn)）中為）中為F所邏輯所邏輯蘊(yùn)涵的函數(shù)依賴的全體稱為蘊(yùn)涵的函數(shù)依賴的全體稱為F的閉包，記作的閉包，記作F+。【定義定義6.13】設(shè)設(shè)F為屬性集為屬性集U上的一組函數(shù)依賴，上的一組函數(shù)依賴，X U， XF+ = A | XA能由能由F根據(jù)根據(jù)Armstrong公理導(dǎo)公理導(dǎo)出出，XF+ 稱為屬性集稱為屬性集X關(guān)于函數(shù)依賴集關(guān)于函數(shù)依賴集F的閉包。的閉包。 26【例例5】 R, U = (A, B, C), F = AB,BC, 分別求分別求A、B、C的閉包。的閉包。解：（解：

25、（1）若）若X=A A B,BC AC（傳遞律）（傳遞律） AA XF+ =A,B,C（2）若）若X=B BB,BC, XF+ =B,C（3）若）若X=C CC XF+ =C 可見(jiàn)，計(jì)算屬性集閉包要比直接計(jì)算函數(shù)依賴可見(jiàn)，計(jì)算屬性集閉包要比直接計(jì)算函數(shù)依賴集閉包簡(jiǎn)單的多。能否通過(guò)計(jì)算屬性集閉包來(lái)計(jì)算集閉包簡(jiǎn)單的多。能否通過(guò)計(jì)算屬性集閉包來(lái)計(jì)算函數(shù)依賴集閉包？函數(shù)依賴集閉包？可行可行27【引理引理6.2】設(shè)設(shè)F為屬性集為屬性集U上的一組函數(shù)依賴，上的一組函數(shù)依賴，X U ，Y U，XY能由能由F根據(jù)根據(jù)Armstrong公理導(dǎo)公理導(dǎo)出的充分必要條件是出的充分必要條件是Y XF+。 于是，判定于是

26、，判定XY 是否能由是否能由F根據(jù)根據(jù)Armstrong公公理導(dǎo)出的問(wèn)題，就轉(zhuǎn)化為求出理導(dǎo)出的問(wèn)題，就轉(zhuǎn)化為求出XF+，判定，判定Y是否為是否為XF+的子集的問(wèn)題。的子集的問(wèn)題。 28【算法算法6.1】（求屬性集（求屬性集X(X U)關(guān)于關(guān)于U上的函數(shù)依賴上的函數(shù)依賴集集F的閉包的閉包XF+）l輸入輸入 ：X，F(xiàn)l輸出輸出 ： XF+l步驟：步驟：(l) 令令X(0)=X，i=0 (2) 求求B，這里，這里B = A |( V)( W)(VW F V X（i）A W)； X(i)AW)； (3) X(i+1)=BX(i) (4) 判斷判斷X(i+1)=x(i)嗎嗎? (5) 若相等或若相等或X

27、(i)=U 則則X(i)就是就是XF+，算法終止。，算法終止。 (6) 若否，則若否，則i=i+l，返回第，返回第(2)步。步。 29【例例1】U=A,B,C,D,E；F=ABC，BD，CE，ECB，ACB。計(jì)算。計(jì)算 (AB)F+ 。解：解： 由算法由算法6.1，設(shè)，設(shè)X(0)=AB； 計(jì)算計(jì)算X(1)； 逐一的掃描逐一的掃描F集合中各個(gè)函數(shù)依賴集合中各個(gè)函數(shù)依賴,找左部為找左部為A、B或或AB的函數(shù)依賴。得到兩個(gè)：的函數(shù)依賴。得到兩個(gè)：ABC，BD。于是于是X(1)=ABCD=ABCD。 因?yàn)橐驗(yàn)閄(0)X(1)，所以再找出左部為，所以再找出左部為ABCD子集的那些函子集的那些函數(shù)依賴，又

28、得到數(shù)依賴，又得到CE，ACB，于是，于是X(2)=X(1)BE=ABCDE。 因?yàn)橐驗(yàn)閄(2)已等于全部屬性集合已等于全部屬性集合,所以所以(AB)F+=ABCDE 。30【例例2】 U = (A, B, C, G, H, I), F = AB, AC, CGH, CGI, BH, 計(jì)算計(jì)算 (AG)F+ 。解：解：由算法由算法6.1，設(shè)，設(shè)X(0)=AG；計(jì)算計(jì)算X(1)； 逐一的掃描逐一的掃描F集合中各個(gè)函數(shù)依賴集合中各個(gè)函數(shù)依賴,找左部為找左部為A、G、AG的函數(shù)依賴。得到兩個(gè)：的函數(shù)依賴。得到兩個(gè)：AB，AC。于是。于是X(1)=AG BC=AGBC; 因?yàn)橐驗(yàn)閄(1)X(0)，所以

29、再找出左部為，所以再找出左部為AGBC子集的那些函數(shù)依子集的那些函數(shù)依賴，又得到賴，又得到CGH, CGI , BH，于是，于是X(2)=X(1)HI=AGBCHI;因?yàn)橐驗(yàn)閄(2)已等于全部屬性集合已等于全部屬性集合,所以所以(AG)F+=AGBCHI 。31【例例3】 U = (A, B, C, D, E,G), F = ABC, CA, BCD, ACDB, DEG , BEC , CGBD, CEAG , 計(jì)算計(jì)算 (BD)F+ 。解：解：X(3)已等于全部屬性集合已等于全部屬性集合,所以所以(BD)F+=ABCDEG 。324. 函數(shù)依賴集的覆蓋問(wèn)題函數(shù)依賴集的覆蓋問(wèn)題(1) 函數(shù)依

30、賴集的等價(jià)函數(shù)依賴集的等價(jià) 從蘊(yùn)含從蘊(yùn)含(或?qū)С龌驅(qū)С?的概念出發(fā)，又引出了兩個(gè)函的概念出發(fā)，又引出了兩個(gè)函數(shù)依賴集的等價(jià)和最小依賴集的概念。數(shù)依賴集的等價(jià)和最小依賴集的概念。 【定義定義6.14】 如果如果G+=F+，就說(shuō)函數(shù)依賴集，就說(shuō)函數(shù)依賴集F覆蓋覆蓋G(F是是G的覆蓋，或的覆蓋，或G是是F的覆蓋的覆蓋)，或，或F與與G等價(jià)。等價(jià)。 引理引理6.3： F+=G+ 的充分必要條件是的充分必要條件是F G+ ,和和G F+ 。33 要判定要判定F G+，只須逐一對(duì)，只須逐一對(duì)F中的函數(shù)依賴中的函數(shù)依賴XY，考察，考察 Y 是否屬于是否屬于XG+ 就行了。就行了。 因此引理因此引理6.3 給

31、出了判斷兩個(gè)函數(shù)依賴集等價(jià)的給出了判斷兩個(gè)函數(shù)依賴集等價(jià)的可行算法。可行算法。34【例例4】U = (A, B, C, D), F = AB, BC, CD, CB, G = AC, BD, BC, CB,問(wèn)，問(wèn)，F(xiàn)與與G是否等價(jià)。是否等價(jià)。解：解：(1) AB，AG+=ACBD,B AG+, ABG+(2) BC，BG+=BDC,C BG+, BCG+(3) CD，CG+=CBD,D CG+, CDG+(4) CB，CG+=CBD,B CG+, CBG+F G+35【例例4】U = (A, B, C, D), F = AB, BC, CD, CB, G = AC, BD, BC, CB,問(wèn)，

32、問(wèn)，F(xiàn)與與G是否等價(jià)。是否等價(jià)。同理：同理：(1) AC，AF+=ABCD,C AF+, ACF+(2) BD，BF+=BCD,D BF+, BDF+(3) BC，BF+=BCD,C BG+, BCF+(4) CB，CF+=CDB,B CF+, CBF+G F+ F G36（2） 最小函數(shù)依賴集最小函數(shù)依賴集 【定義定義6.15】 如果函數(shù)依賴集如果函數(shù)依賴集F滿足下列條件，則滿足下列條件，則稱稱F為一個(gè)極小函數(shù)依賴集。亦稱為最小依賴集或?yàn)橐粋€(gè)極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。最小覆蓋。 lF中任一函數(shù)依賴的右部?jī)H含有一個(gè)屬性。中任一函數(shù)依賴的右部?jī)H含有一個(gè)屬性。 lF中不存在這樣的

33、函數(shù)依賴中不存在這樣的函數(shù)依賴XA，使得，使得 F與與F-XA等價(jià)。等價(jià)。 lF中不存在這樣的函數(shù)依賴中不存在這樣的函數(shù)依賴XA, X有真子集有真子集Z使使得得F-XAZA與與F等價(jià)。等價(jià)。37三個(gè)條件的作用：三個(gè)條件的作用：（1）單屬性化：）單屬性化：保證每個(gè)函數(shù)依賴保證每個(gè)函數(shù)依賴X A，A不不會(huì)是組合的屬性會(huì)是組合的屬性 。 （2）無(wú)冗余化：）無(wú)冗余化：保證保證F中沒(méi)有重復(fù)的函數(shù)依賴。中沒(méi)有重復(fù)的函數(shù)依賴。 （3）既約化：）既約化：保證每個(gè)函數(shù)依賴左部的屬性最小保證每個(gè)函數(shù)依賴左部的屬性最小化化 。 38【例例5】 考察考察6.l節(jié)中的關(guān)系模式節(jié)中的關(guān)系模式SU,F,其中：其中： U=S

34、NO，SDEPT，MN，CNAME，G, F=SNOSDEPT，SDEPTMN，(SNO,CNAME)G設(shè)設(shè)F=SNOSDEPT，SNOMN，SDEPTMN，(SNO，CNAME)G，(SNO，SDEPT)SDEPT 根據(jù)定義根據(jù)定義6.15可以驗(yàn)證可以驗(yàn)證F是最小覆蓋，而是最小覆蓋，而F不是。不是。因?yàn)橐驗(yàn)镕-SNOMN與與F 等價(jià)等價(jià), F-(SNO,SDEPT)SDEPT與與F 等價(jià)。等價(jià)。39【定理定理6.3】 每一個(gè)函數(shù)依賴集每一個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)極小均等價(jià)于一個(gè)極小函數(shù)依賴集函數(shù)依賴集Fm。此。此Fm稱為稱為F的最小依賴集。的最小依賴集。求函數(shù)依賴集求函數(shù)依賴集F的最小覆蓋

35、的方法：的最小覆蓋的方法：(1) 檢查檢查F中每個(gè)函數(shù)依賴中每個(gè)函數(shù)依賴FDi：XA， 若若A=A1,A2, ,Ak，k 2，根據(jù)分解原則，根據(jù)分解原則， 用用 XAj |j=1，2， k 來(lái)取代來(lái)取代XA。 (2) 檢查檢查F中每個(gè)函數(shù)依賴中每個(gè)函數(shù)依賴FDi：XA， 令令G=F-XA， 若若A XG+， 則從則從F中去掉此函數(shù)依賴。中去掉此函數(shù)依賴。 由于由于F與與G =F-XA等價(jià)的充要條件是等價(jià)的充要條件是A XG+ 因此因此F變換前后是等價(jià)的。變換前后是等價(jià)的。40(3)檢查檢查F中各函數(shù)依賴中各函數(shù)依賴FDi：XA， 設(shè)設(shè)X=B1,B2,Bm， 檢查檢查Bi （i=l，2，m），）

36、， 若若A (X-Bi) F+ ， 則以則以X-Bi 替換替換X。 由于由于F與與F-XAZA等價(jià)的充要條件是等價(jià)的充要條件是A ZF+ ，其中，其中Z=X-Bi 因此因此F變換前后是等價(jià)的。變換前后是等價(jià)的。41【例例6】 F = AB，BA，BC，AC，CA Fm1= AB，BC，CA Fm2= AB，BA，AC，CA (1) F中任一函數(shù)依賴的右部?jī)H含有一個(gè)屬性。中任一函數(shù)依賴的右部?jī)H含有一個(gè)屬性。(2) AB，令，令G=F-AB AG+=AC, B AG+，保留，保留ABBA，令，令G=F-BA BG+=BCA,ABG+，從，從F中去掉中去掉BAF = AB，BC，AC，CA BC，令

37、，令G=F-BC BG+=B,C BG+，在，在F中保留中保留BCAC，令，令G=F-AC AG+=ABC,CAG+，從，從F中去掉中去掉AC F = AB，BC，CA CA，令，令G=F-CA CG+=C,C CG+，在，在F中保留中保留CA F等價(jià)于等價(jià)于Fm142【例例6】 F = AB，BA，BC，AC，CA Fm2= AB，BA，AC，CA (1) F中任一函數(shù)依賴的右部?jī)H含有一個(gè)屬性。中任一函數(shù)依賴的右部?jī)H含有一個(gè)屬性。(2) BC，令，令G=F-BC BG+=BAC,CBG+，從，從F中去掉中去掉BCF = AB，BA，AC，CA AB，令，令G=F-AB AG+=AC,B AG

38、+，保留，保留ABBA，令，令G=F-BA BG+=B, A BG+，在，在F中保留中保留BAAC，令，令G=F-AC AG+=AB,C AG+，在，在F中保留中保留ACCA，令，令G=F-CA CG+=C,A CG+，在，在F中保留中保留CAF等價(jià)于等價(jià)于Fm243【說(shuō)明說(shuō)明】F的最小依賴集的最小依賴集Fm不一定是唯一的，不一定是唯一的，它和對(duì)各函數(shù)依賴它和對(duì)各函數(shù)依賴FDi 及及XA中中X各屬性的處置各屬性的處置順序有關(guān)。順序有關(guān)。44(1)判斷判斷CGB，G=F CGB= CA，AG，BA (CG)G+=A，C，G，B A，C，G檢查檢查 CA , G=F CA = AG，CGB，BA

39、(C)G+= C A C 檢查檢查 AG , G=F AG = CA，CGB ，BA (A)G+= A G A檢查檢查 BA , G=F BA = CA，AG，CGB (B)G+= B A B(2)檢查檢查 CGB (CG-C)F+ =(G)F+ = G B G 檢查檢查 CGB (CG-G)F+ =(C)F+ = CAGB BCAGB所以：所以： 以以C 代替代替CG最后，最后，F(xiàn)m = CA，AG，CB，BA例如：例如：F = CA，AG，CGB，BA， 求最小覆蓋求最小覆蓋Fm。456.4 模式的分解模式的分解解決的問(wèn)題：解決的問(wèn)題：(1)什么叫模式的分解？什么叫模式的分解？(2)分解后

40、，原關(guān)系中的信息和語(yǔ)義分解后，原關(guān)系中的信息和語(yǔ)義(是否會(huì)丟失是否會(huì)丟失)？ 把低一級(jí)的關(guān)系模式分解為若干個(gè)高一級(jí)的關(guān)系把低一級(jí)的關(guān)系模式分解為若干個(gè)高一級(jí)的關(guān)系模式的方法并不是唯一的。模式的方法并不是唯一的。 只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價(jià)，分解方法才有意義。價(jià)，分解方法才有意義。46【定義定義6.16 】關(guān)系模式關(guān)系模式R的一個(gè)分解：的一個(gè)分解：= R1，R2，Rn其中：其中：（1）U=U1U2Un，（2）且不存在）且不存在 Ui Uj，1i，j n，F(xiàn)i 為為 F在在 Ui 上上的投影。的投影?！径x定義6.17】 函數(shù)依賴集合函數(shù)

41、依賴集合XY | XY F+XY Ui 的一個(gè)覆蓋的一個(gè)覆蓋 Fi 叫作叫作 F 在屬性在屬性 Ui 上的投影。上的投影。47 例例: SL（Sno， Sdept， Sloc） F= SnoSdept,SdeptSloc,SnoSloc SL2NF 存在問(wèn)題存在問(wèn)題插入異常插入異常刪除異常刪除異常冗余度大冗余度大修改復(fù)雜修改復(fù)雜分解方法分解方法可以有多種可以有多種SL Sno SdeptSloc 95001 CS A 95002 IS B 95003 MA C 95004 IS B 95005 PH B 48SN SD SO Sno Sdept Sloc 95001 CS A 95002 IS

42、 B 95003 MA C 95004 PH 95005 分解后數(shù)據(jù)庫(kù)丟失了許多信息分解后數(shù)據(jù)庫(kù)丟失了許多信息例如無(wú)法查詢例如無(wú)法查詢95001學(xué)生所學(xué)生所在系或所在宿舍。如果分解后在系或所在宿舍。如果分解后的關(guān)系可以通過(guò)自然連接恢復(fù)的關(guān)系可以通過(guò)自然連接恢復(fù)為原來(lái)的關(guān)系，那么這種分解為原來(lái)的關(guān)系，那么這種分解就沒(méi)有丟失信息。就沒(méi)有丟失信息。希望在分解過(guò)程中不丟失希望在分解過(guò)程中不丟失信息，這個(gè)問(wèn)題稱為信息，這個(gè)問(wèn)題稱為無(wú)損連接無(wú)損連接或連接不失真或連接不失真。（1） SL分解為下面三個(gè)關(guān)系分解為下面三個(gè)關(guān)系模式：模式： SN(Sno) SD(Sdept) SO(Sloc)49NL DL Sn

43、o Sloc Sdept Sloc 95001 A CS A 95002 B IS B 95003 C MA C 95004 B PH B 95005 B （2） SL分解為下面二個(gè)關(guān)系模式：分解為下面二個(gè)關(guān)系模式： NL(Sno, Sloc) F1=Sno Sloc DL(Sdept, Sloc) F2=Sdept Sloc50NLDL Sno Sloc Sdept 95001 A CS 95002 B IS 95002 B PH 95003 C MA 95004 B IS 95004 B PH 95005 B IS 95005 B PH NL DL比原來(lái)的比原來(lái)的SL關(guān)系多了關(guān)系多了3個(gè)元

44、組個(gè)元組 無(wú)法知道無(wú)法知道95002、95004、95005 究竟是哪個(gè)系的學(xué)生。究竟是哪個(gè)系的學(xué)生。 元組增加了，信息丟失了。元組增加了，信息丟失了。51F1F2=SnoSloc, SdeptSlocF= SnoSdept,SdeptSloc,SnoSloc(F1F2)+=SnoSloc, SdeptSlocF+= SnoSdept,SdeptSloc,SnoSloc(F1F2)+ F+ ，說(shuō)明分解后，有些函數(shù)依賴丟失，說(shuō)明分解后，有些函數(shù)依賴丟失了。了。希望在分解過(guò)程中不丟失函數(shù)依賴，這個(gè)問(wèn)希望在分解過(guò)程中不丟失函數(shù)依賴，這個(gè)問(wèn)題稱為分解的依賴保持性。題稱為分解的依賴保持性。52ND NL

45、 Sno Sdept Sno Sloc 95001 CS 95001 A 95002 IS 95002 B 95003 MA 95003 C 95004 IS 95004 B 95005 PH 95005 B （3） 將將SL分解為下面二個(gè)關(guān)系模式：分解為下面二個(gè)關(guān)系模式： ND(Sno, Sdept) F1=Sno Sdept NL(Sno, Sloc) F2=Sno Sloc53NDNL Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 CS A 95005 PH B 與與SL關(guān)系一樣，因此關(guān)系一樣，因此沒(méi)有丟失信息沒(méi)有丟失信息F+

46、= SnoSdept,SdeptSloc,SnoSloc(F1F2)+=SnoSdept, SnoSloc(F1F2)+ F+ ，說(shuō)明分解后，說(shuō)明分解后，有些函數(shù)依賴丟失了有些函數(shù)依賴丟失了。54ND DL Sno Sdept Sdept Sloc 95001 CS CS A 95002 IS IS B 95003 MA MA C 95004 IS PH B 95005 PH （4） 將將SL分解為下面二個(gè)關(guān)系模式：分解為下面二個(gè)關(guān)系模式： ND(Sno, Sdept) F1=Sno Sdept DL(Sdept, Sloc) F2=Sdept Sloc55NDDL Sno Sdept Slo

47、c 95001 CS A 95002 IS B 95003 MA C 95004 CS A 95005 PH B 與與SL關(guān)系一樣，因此關(guān)系一樣，因此沒(méi)有丟失信息沒(méi)有丟失信息F+= SnoSdept,SdeptSloc,SnoSloc(F1F2)+=SnoSdept, SdeptSloc,SnoSloc(F1F2)+ = F+ ，說(shuō)明分解后，說(shuō)明分解后，函數(shù)依賴沒(méi)有丟失。函數(shù)依賴沒(méi)有丟失。566.4.1 三種模式分解的等價(jià)定義三種模式分解的等價(jià)定義（1）分解具有無(wú)損連接性）分解具有無(wú)損連接性（2） 分解要保持函數(shù)依賴分解要保持函數(shù)依賴（3）分解既要保持函數(shù)依賴，又要具有無(wú)損連接性）分解既要保持

48、函數(shù)依賴，又要具有無(wú)損連接性l如果一個(gè)分解具有無(wú)損連接性，則它能夠保證不丟如果一個(gè)分解具有無(wú)損連接性，則它能夠保證不丟失信息。失信息。l如果一個(gè)分解保持了函數(shù)依賴，則它可以減輕或解如果一個(gè)分解保持了函數(shù)依賴，則它可以減輕或解決各種異常情況。決各種異常情況。l分解具有無(wú)損連接性和分解保持函數(shù)依賴是兩個(gè)互分解具有無(wú)損連接性和分解保持函數(shù)依賴是兩個(gè)互相獨(dú)立的標(biāo)準(zhǔn)。具有無(wú)損連接性的分解不一定能夠相獨(dú)立的標(biāo)準(zhǔn)。具有無(wú)損連接性的分解不一定能夠保持函數(shù)依賴。同樣，保持函數(shù)依賴的分解也不一保持函數(shù)依賴。同樣，保持函數(shù)依賴的分解也不一定具有無(wú)損連接性。定具有無(wú)損連接性。576.4.2 具有無(wú)損連接性的模式分解具

49、有無(wú)損連接性的模式分解【定義定義】關(guān)系模式關(guān)系模式R的一個(gè)分解的一個(gè)分解 = R1，R2， ，Rn若若R與與R1、R2、Rn自然連接的結(jié)果相等，則稱自然連接的結(jié)果相等，則稱關(guān)系模式關(guān)系模式R的這個(gè)分解的這個(gè)分解具有無(wú)損連接性（具有無(wú)損連接性（Lossless join） 具有無(wú)損連接性的分解保證不丟失信息。具有無(wú)損連接性的分解保證不丟失信息。 無(wú)損連接性不一定能解決插入異常、刪除異常、無(wú)損連接性不一定能解決插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問(wèn)題。修改復(fù)雜、數(shù)據(jù)冗余等問(wèn)題。58連接不失真的檢驗(yàn)連接不失真的檢驗(yàn)關(guān)系模式關(guān)系模式R ,U = Ai ，(i=1,2,n) = R1 , R2, ,

50、 Rk是是R的的一個(gè)分解，一個(gè)分解，（1）構(gòu)造一個(gè)）構(gòu)造一個(gè)n列列k行的一個(gè)表，第行的一個(gè)表，第i行對(duì)應(yīng)行對(duì)應(yīng)Ri，第，第j列對(duì)應(yīng)列對(duì)應(yīng)Aj；RI AJA1A2AnR1R2Rk59連接不失真的檢驗(yàn)連接不失真的檢驗(yàn)（2）填表，第）填表，第i行第行第j列上填寫(xiě)列上填寫(xiě)aj；否則填寫(xiě)；否則填寫(xiě)bi,j（3）修改表：逐一掃描函數(shù)依賴，在）修改表：逐一掃描函數(shù)依賴，在x列上相同，列上相同，y上必定相上必定相同；同；（4）重復(fù)（）重復(fù)（3），直至，掃描完所有的函數(shù)依賴。），直至，掃描完所有的函數(shù)依賴。RI AJA1A2AnR1R2Rk60【例例1】U=A,B,C,D,E, F=ABC, CD,DE =(A

51、, B, C), (C, D), (D, E)RI AJABCDER1a1a2a3b14 a4b15 a5R2b21b22a3a4b25 a5R3b31b32b33a4a5 =(A, B, C), (C, D), (D, E)為無(wú)損分解。為無(wú)損分解。61分解分解1具有無(wú)損連接性，具有無(wú)損連接性， 分解分解2不具有無(wú)損連接性不具有無(wú)損連接性ABCa1a2a1a3ABACABCa1a2a2a3ABBC【例例2】R(A,B,C), F=AB, C B 分解分解1=(A,B) AB, (A,C) 分解分解2=(A,B) AB, (B,C) CB分析兩種分解的無(wú)損連接性？分析兩種分解的無(wú)損連接性？62【

52、定理定理6.5 】關(guān)系模式關(guān)系模式R(U)的一個(gè)分解，的一個(gè)分解， = R1 , R2, 如 果如 果 U1 U2 U1 U2 F+， 或， 或U1U2U2 U1F+，則，則 具有無(wú)損連接性。具有無(wú)損連接性。63【例例3】U=S#，SD，MN，C#，GF=S#SD，S#MN，SDMN，(S#,C#)G U1=S#，SD , F1=S#SD U2=S#, MN, C#, G, F2=S#MN, (S#,C#)G解：解： U1U2= S# U1-U2= SD U1U2U1 U2F+該分解該分解 具有無(wú)損連接性。具有無(wú)損連接性。 如果兩個(gè)關(guān)系模式之間的公共屬性集至少包含如果兩個(gè)關(guān)系模式之間的公共屬性

53、集至少包含其中一個(gè)關(guān)系模式的碼，則此分解具有無(wú)損連接其中一個(gè)關(guān)系模式的碼，則此分解具有無(wú)損連接性。性。64【例例4】U=A，B，C F=AB，CB U1=A，B , F1=AB U2=B, C, F2=CB解：解： U1U2= B U1-U2= A , U2-U1= C BA, BC F+該分解該分解 不不具有無(wú)損連接性。具有無(wú)損連接性。656.4.3 保持函數(shù)依賴的模式分解保持函數(shù)依賴的模式分解【定義定義6.19】設(shè)關(guān)系模式設(shè)關(guān)系模式R被分解為若干個(gè)被分解為若干個(gè)關(guān)系模式關(guān)系模式R1，R2，Rn 若若F+ = ( Fi)+， 則稱則稱R 的分解的分解 = R1 , , Rn 保持函數(shù)依賴。保

54、持函數(shù)依賴。 即即F所邏輯蘊(yùn)含的函數(shù)依賴一定也由分解得到所邏輯蘊(yùn)含的函數(shù)依賴一定也由分解得到的某個(gè)關(guān)系模式中的函數(shù)依賴的某個(gè)關(guān)系模式中的函數(shù)依賴Fi所邏輯蘊(yùn)含，則所邏輯蘊(yùn)含，則稱關(guān)系模式稱關(guān)系模式R的這個(gè)分解是保持函數(shù)依賴的的這個(gè)分解是保持函數(shù)依賴的（Preserve dependency）。）。66【例例1】 SL（Sno， Sdept， Sloc） F= SnoSdept,SdeptSloc,SnoSloc分解：分解： ND(Sno, Sdept) F1=Sno Sdept NL(Sdept, Sloc) F2=Sdept SlocF+= SnoSdept,SdeptSloc,SnoSlo

55、c(F1F2)+=SnoSdept, SdeptSloc,SnoSloc(F1F2)+ = F+ ，說(shuō)明分解后，函數(shù)依賴沒(méi)有丟失。，說(shuō)明分解后，函數(shù)依賴沒(méi)有丟失。67【例例2】 R(A,B,C), F=AB, C B分解分解1=(A,B) AB, (A,C) 分解分解2=(A,B) AB), (B,C) CB分析兩種分解的依賴保持性？分析兩種分解的依賴保持性？分解分解1：只有：只有AB，顯然，分解，顯然，分解1不具有依賴保不具有依賴保持性持性分解分解2：保留了所有函數(shù)依賴，具有依賴保持性：保留了所有函數(shù)依賴，具有依賴保持性68【例如例如】 SL（Sno， Sdept， Sloc）第一種分解方法

56、既不具有無(wú)損連接性，也未保持函數(shù)第一種分解方法既不具有無(wú)損連接性，也未保持函數(shù)依賴，它不是原關(guān)系模式的一個(gè)等價(jià)分解；依賴，它不是原關(guān)系模式的一個(gè)等價(jià)分解；SN(Sno)，SD(Sdept)，SO(Sloc)第二種分解方法沒(méi)有保持函數(shù)依賴，也不具有無(wú)損連第二種分解方法沒(méi)有保持函數(shù)依賴，也不具有無(wú)損連接性；接性；NL(Sno, Sloc)，DL(Sdept, Sloc)第三種分解方法具有無(wú)損連接性，但未保持函數(shù)依賴；第三種分解方法具有無(wú)損連接性，但未保持函數(shù)依賴；ND(Sno, Sdept)，NL(Sno, Sloc)第四種分解方法既具有無(wú)損連接性，又保持了函數(shù)依第四種分解方法既具有無(wú)損連接性，又

57、保持了函數(shù)依賴；賴；ND(Sno, Sdept) ，NL(Sdept, Sloc) 69【例例3】U=A，B，C F=AB，CB U1=A，B , F1=AB U2=A, C, F2=AC解：解： U1U2= A U1-U2= B , U2-U1= C U1U2- U1-U2 F+即：即：AB F+ 該分解該分解 具有無(wú)損連接性。具有無(wú)損連接性。(F1F2)+=AB ,AC(F1F2)+ F+ ，說(shuō)明分解后，不具有依賴保持性。，說(shuō)明分解后，不具有依賴保持性。70【例例4】U=A，B，C，D R1=A，B， R2=B，C， R3=C，D F1=BC，CD F2=AB，CD試問(wèn)：分解相對(duì)于試問(wèn)：分

58、解相對(duì)于F1和和F2是否無(wú)損分解？是否無(wú)損分解？71 幾個(gè)命題幾個(gè)命題（1）一個(gè)無(wú)損連接的分解不一定具有依賴保持性，）一個(gè)無(wú)損連接的分解不一定具有依賴保持性，反之亦然。反之亦然。（2）若要求模式分解保持函數(shù)依賴，則模式分離總）若要求模式分解保持函數(shù)依賴，則模式分離總能達(dá)到能達(dá)到3NF，但不一定能達(dá)到，但不一定能達(dá)到BCNF。（3）若要求分解既保持函數(shù)依賴，又具有無(wú)損連接）若要求分解既保持函數(shù)依賴，又具有無(wú)損連接性，則模式分離可以達(dá)到性，則模式分離可以達(dá)到3NF，但不一定能達(dá)到，但不一定能達(dá)到BCNF。（4）若要求分解具有無(wú)損連接性，則模式分離一定）若要求分解具有無(wú)損連接性，則模式分離一定可以達(dá)

59、到可以達(dá)到4NF。72補(bǔ)充：求解關(guān)系模式的候選碼補(bǔ)充：求解關(guān)系模式的候選碼屬性分類(lèi)：屬性分類(lèi)：L類(lèi)：只出現(xiàn)在函數(shù)依賴的左邊的屬性類(lèi)：只出現(xiàn)在函數(shù)依賴的左邊的屬性R類(lèi)：只出現(xiàn)在函數(shù)依賴的右邊的屬性類(lèi)：只出現(xiàn)在函數(shù)依賴的右邊的屬性N類(lèi)：在函數(shù)依賴的兩邊均未出現(xiàn)的屬性類(lèi)：在函數(shù)依賴的兩邊均未出現(xiàn)的屬性LR類(lèi)：出現(xiàn)在函數(shù)依賴的兩邊的屬性類(lèi)：出現(xiàn)在函數(shù)依賴的兩邊的屬性73一、快速求解候選碼的方法一、快速求解候選碼的方法【定理定理1】對(duì)于給定的關(guān)系模式對(duì)于給定的關(guān)系模式R及其函數(shù)依賴集及其函數(shù)依賴集F,若若X(XR)是是L類(lèi)屬性類(lèi)屬性,則則X必為必為R的任一候選碼的任一候選碼的成員。的成員?！就普撏普?】

60、對(duì)于給定的關(guān)系模式對(duì)于給定的關(guān)系模式R及其函數(shù)依賴集及其函數(shù)依賴集F,若若X(XR)是是L類(lèi)屬性類(lèi)屬性,且且X+包含了包含了R的全部屬的全部屬性性,則則X必為必為R的唯一候選碼。的唯一候選碼。 74快速求解候選碼的方法快速求解候選碼的方法【定理定理2】對(duì)于給定的關(guān)系模式對(duì)于給定的關(guān)系模式R及其函數(shù)依賴集及其函數(shù)依賴集F,若若X(XR)是是R類(lèi)屬性類(lèi)屬性,則則X不在任何候選碼中。不在任何候選碼中?！径ɡ矶ɡ?】設(shè)有關(guān)系模式設(shè)有關(guān)系模式R及其函數(shù)依賴集及其函數(shù)依賴集F,如果如果X是是R的的N類(lèi)屬性類(lèi)屬性,則則X必包含在必包含在R的任一候選碼中。的任一候選碼中。【推論推論2】對(duì)于給定的關(guān)系模式對(duì)于給