1、1第第6章章關(guān)系數(shù)據(jù)理論關(guān)系數(shù)據(jù)理論2課課 程程 C教教 員員 T參參 考考 書書 B 物理物理 數(shù)學(xué)數(shù)學(xué) 計算數(shù)學(xué)計算數(shù)學(xué)李李 勇勇王王 軍軍 李李 勇勇張張 平平 張張 平平周周 峰峰 普通物理學(xué)普通物理學(xué)光學(xué)原理光學(xué)原理 物理習(xí)題集物理習(xí)題集 數(shù)學(xué)分析數(shù)學(xué)分析微分方程微分方程高等代數(shù)高等代數(shù) 數(shù)學(xué)分析數(shù)學(xué)分析6.2.7 多值依賴多值依賴例例: 學(xué)校中某一門課程由多個教師講授，他們使用相同的學(xué)校中某一門課程由多個教師講授，他們使用相同的一套參考書。一套參考書。關(guān)系模式關(guān)系模式Teaching(C, T, B) 課程課程C、教師、教師T 和和 參考書參考書B 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é) 參考書B教員T課程C關(guān)系模式關(guān)系模式TEACHING（C，T，B），），它的碼它的碼是（是（C，T，B），），所以所以屬于屬于BCNF。 存在的問題：存在的問題：(1)插入異常：

3、插入異常：當某門當某門課程增加一名教員時，課程增加一名教員時，該門課程有多少本參該門課程有多少本參考書就必須插入多少考書就必須插入多少個元組；同樣當某門個元組；同樣當某門課程需要增加一本參課程需要增加一本參考書時，它有多少個考書時，它有多少個教員就必須插入多少教員就必須插入多少個元組。個元組。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é) 參考書B教員T課程C存在的問題：存在的問題：(2)刪除異常：刪除異常：當刪當刪除一門課程的某個教除一門課程的某個教員或者某本參考書時，員或者某本參考書時，需要刪除多個元組。需要刪除多個元組。(3)更新異常：更新異常：當一當一門課程的教員或參考門課程的教員或參考書作出改變時，需要書作出改變時，需要修改多個元組。修改多個元組。(4)數(shù)據(jù)冗余：數(shù)據(jù)冗余：同一同一門課的教員與參考書門課的教員與參考書的信息被反復(fù)存儲多的信息被反復(fù)存儲多次。次。5【定義定義6

5、.9】 關(guān)系模式關(guān)系模式R(U)，X、Y、Z U， 并且并且Z = U X Y， 多值依賴多值依賴X Y 成立當且僅當對成立當且僅當對R(U) 的任一關(guān)系的任一關(guān)系r，給定的一對（，給定的一對（x，z）值有一組）值有一組y 的值，這組值僅僅決定于的值，這組值僅僅決定于x 值而與值而與z 值無關(guān)。值無關(guān)。 物物 理理,普通物理學(xué)普通物理學(xué) 李李 勇勇,王王 軍軍物物 理理,光學(xué)原理光學(xué)原理 李李 勇勇,王王 軍軍物物 理理,物理習(xí)題集物理習(xí)題集 李李 勇勇,王王 軍軍對于對于C的每一個值，的每一個值，T有一組值與之對應(yīng)，而不論有一組值與之對應(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值所得值所得的兩個新元組必在的兩個新元組必在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表示倉庫，表示倉庫，S表示保管員，表示保管員，C表示商品。表示商品。 假設(shè)，每個倉庫有若干個保管員，有若干種商假設(shè)，每個倉庫有若干個保管員，有若干種商品。每個保管員包管所在倉庫的所有商品，每種商品。每個保管員包管所在倉庫的所有商品，

8、每種商品被該倉庫的所有保管員包管。品被該倉庫的所有保管員包管。 存在是函數(shù)依賴：存在是函數(shù)依賴： W S W C81. 多值依賴多值依賴的的性質(zhì)性質(zhì) （1）多值依賴具有對稱性，多值依賴具有對稱性，即即 若若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) 上成立，則對于任何上成立，則對于任何Y Y， 均有均有XY 成立。成立。 若若XY在在R(U)上成立，則不能斷言對于上成立，則不能斷言對于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。 如果一門課如果一門課Ci 有有m 個個 教員，教員，n 本本 參考書，則關(guān)參考書，則關(guān)系

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

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

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

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

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

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

17、括的包括的XZ，這就產(chǎn)生一個問題，如何從，這就產(chǎn)生一個問題，如何從F=XY，YZ推導(dǎo)得出推導(dǎo)得出XZ ? 這需要一套規(guī)則這需要一套規(guī)則從給定的函數(shù)依賴集推出其蘊涵的函數(shù)依賴。從給定的函數(shù)依賴集推出其蘊涵的函數(shù)依賴。 一套推理規(guī)則：是模式分解算法的理論基礎(chǔ)一套推理規(guī)則：是模式分解算法的理論基礎(chǔ)用途：用途：l從一組函數(shù)依賴求得蘊含的函數(shù)依賴從一組函數(shù)依賴求得蘊含的函數(shù)依賴l這組推理規(guī)則是這組推理規(guī)則是l974年首先由年首先由Armstrong提出來的提出來的 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的子集，對的子集，對R(U,F)有以下的推理規(guī)則：有以下的推理規(guī)則：（1）A1(自反律自反律)：若：若Y X U ，則，則XY為為F所所蘊涵；蘊涵；（注意，由自反律所得到的函數(shù)依賴均是平（注意，由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴，自反律的使用并不依賴于凡的函數(shù)依賴，自反律的使用并不依賴于F。 ）（2）A2(增廣律增廣律): 若若XY為為F所蘊涵，且所蘊涵，且 Z U，則則XZYZ為為F所蘊涵；所蘊涵； （YZ表示并集）表示并集） （3）A3(傳遞律傳遞律): 若若XY,YZ為為F所蘊涵，則所蘊涵，則XZ為為F所蘊涵。所蘊涵。18【定理定理6.l】Armst

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

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

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

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ī)則，很容易得到這樣一個重要事實：個重要事實： 【引理引理6.1】X A1A2Ak成立的充分必要條件是成立的充分必要條件是X Ai成立（成立（i1，2，k）。）。【例例4】R, U = (A, B, C, G, H, I), F = AB, AC, CGH, CGI, BH, A H？CG HI？AG 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所邏輯所邏輯蘊涵的函數(shù)依賴的全體稱為蘊涵的函數(shù)依賴的全體稱為F的閉包，記作的閉包，記作F+?！径x定義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 可見，計算屬性集閉包要比直接計算函數(shù)依賴可見，計算屬性集閉包要比直接計算函數(shù)依賴集閉包簡單的多。能否通過計算屬性集閉包來計算集閉包簡單的多。能否通過計算屬性集閉包來計算函數(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)出的問題，就轉(zhuǎn)化為求出理導(dǎo)出的問題，就轉(zhuǎn)化為求出XF+，判定，判定Y是否為是否為XF+的子集的問題。的子集的問題。 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。計算。計算 (AB)F+ 。解：解： 由算法由算法6.1，設(shè)，設(shè)X(0)=AB； 計算計算X(1)； 逐一的掃描逐一的掃描F集合中各個函數(shù)依賴集合中各個函數(shù)依賴,找左部為找左部為A、B或或AB的函數(shù)依賴。得到兩個：的函數(shù)依賴。得到兩個：ABC，BD。于是于是X(1)=ABCD=ABCD。 因為因為X(0)X(1)，所以再找出左部為，所以再找出左部為ABCD子集的那些函子集的那些函數(shù)依賴，又

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

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

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

31、出了判斷兩個函數(shù)依賴集等價的給出了判斷兩個函數(shù)依賴集等價的可行算法。可行算法。34【例例4】U = (A, B, C, D), F = AB, BC, CD, CB, G = AC, BD, BC, CB,問，問，F(xiàn)與與G是否等價。是否等價。解：解：(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,問，

32、問，F(xiàn)與與G是否等價。是否等價。同理：同理：(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為一個極小函數(shù)依賴集。亦稱為最小依賴集或為一個極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。最小覆蓋。 lF中任一函數(shù)依賴的右部僅含有一個屬性。中任一函數(shù)依賴的右部僅含有一個屬性。 lF中不存在這樣的

33、函數(shù)依賴中不存在這樣的函數(shù)依賴XA，使得，使得 F與與F-XA等價。等價。 lF中不存在這樣的函數(shù)依賴中不存在這樣的函數(shù)依賴XA, X有真子集有真子集Z使使得得F-XAZA與與F等價。等價。37三個條件的作用：三個條件的作用：（1）單屬性化：）單屬性化：保證每個函數(shù)依賴保證每個函數(shù)依賴X A，A不不會是組合的屬性會是組合的屬性 。 （2）無冗余化：）無冗余化：保證保證F中沒有重復(fù)的函數(shù)依賴。中沒有重復(fù)的函數(shù)依賴。 （3）既約化：）既約化：保證每個函數(shù)依賴左部的屬性最小保證每個函數(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可以驗證可以驗證F是最小覆蓋，而是最小覆蓋，而F不是。不是。因為因為F-SNOMN與與F 等價等價, F-(SNO,SDEPT)SDEPT與與F 等價。等價。39【定理定理6.3】 每一個函數(shù)依賴集每一個函數(shù)依賴集F均等價于一個極小均等價于一個極小函數(shù)依賴集函數(shù)依賴集Fm。此。此Fm稱為稱為F的最小依賴集。的最小依賴集。求函數(shù)依賴集求函數(shù)依賴集F的最小覆蓋

35、的方法：的最小覆蓋的方法：(1) 檢查檢查F中每個函數(shù)依賴中每個函數(shù)依賴FDi：XA， 若若A=A1,A2, ,Ak，k 2，根據(jù)分解原則，根據(jù)分解原則， 用用 XAj |j=1，2， k 來取代來取代XA。 (2) 檢查檢查F中每個函數(shù)依賴中每個函數(shù)依賴FDi：XA， 令令G=F-XA， 若若A XG+， 則從則從F中去掉此函數(shù)依賴。中去掉此函數(shù)依賴。 由于由于F與與G =F-XA等價的充要條件是等價的充要條件是A XG+ 因此因此F變換前后是等價的。變換前后是等價的。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等價的充要條件是等價的充要條件是A ZF+ ，其中，其中Z=X-Bi 因此因此F變換前后是等價的。變換前后是等價的。41【例例6】 F = AB，BA，BC，AC，CA Fm1= AB，BC，CA Fm2= AB，BA，AC，CA (1) F中任一函數(shù)依賴的右部僅含有一個屬性。中任一函數(shù)依賴的右部僅含有一個屬性。(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等價于等價于Fm142【例例6】 F = AB，BA，BC，AC，CA Fm2= AB，BA，AC，CA (1) F中任一函數(shù)依賴的右部僅含有一個屬性。中任一函數(shù)依賴的右部僅含有一個屬性。(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等價于等價于Fm243【說明說明】F的最小依賴集的最小依賴集Fm不一定是唯一的，不一定是唯一的，它和對各函數(shù)依賴它和對各函數(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 模式的分解模式的分解解決的問題：解決的問題：(1)什么叫模式的分解？什么叫模式的分解？(2)分解后

40、，原關(guān)系中的信息和語義分解后，原關(guān)系中的信息和語義(是否會丟失是否會丟失)？ 把低一級的關(guān)系模式分解為若干個高一級的關(guān)系把低一級的關(guān)系模式分解為若干個高一級的關(guān)系模式的方法并不是唯一的。模式的方法并不是唯一的。 只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價，分解方法才有意義。價，分解方法才有意義。46【定義定義6.16 】關(guān)系模式關(guān)系模式R的一個分解：的一個分解：= 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 的一個覆蓋的一個覆蓋 Fi 叫作叫作 F 在屬性在屬性 Ui 上的投影。上的投影。47 例例: SL（Sno， Sdept， Sloc） F= SnoSdept,SdeptSloc,SnoSloc SL2NF 存在問題存在問題插入異常插入異常刪除異常刪除異常冗余度大冗余度大修改復(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ù)庫丟失了許多信息分解后數(shù)據(jù)庫丟失了許多信息例如無法查詢例如無法查詢95001學(xué)生所學(xué)生所在系或所在宿舍。如果分解后在系或所在宿舍。如果分解后的關(guān)系可以通過自然連接恢復(fù)的關(guān)系可以通過自然連接恢復(fù)為原來的關(guān)系，那么這種分解為原來的關(guān)系，那么這種分解就沒有丟失信息。就沒有丟失信息。希望在分解過程中不丟失希望在分解過程中不丟失信息，這個問題稱為信息，這個問題稱為無損連接無損連接或連接不失真或連接不失真。（1） SL分解為下面三個關(guān)系分解為下面三個關(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分解為下面二個關(guān)系模式：分解為下面二個關(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比原來的比原來的SL關(guān)系多了關(guān)系多了3個元

44、組個元組 無法知道無法知道95002、95004、95005 究竟是哪個系的學(xué)生。究竟是哪個系的學(xué)生。 元組增加了，信息丟失了。元組增加了，信息丟失了。51F1F2=SnoSloc, SdeptSlocF= SnoSdept,SdeptSloc,SnoSloc(F1F2)+=SnoSloc, SdeptSlocF+= SnoSdept,SdeptSloc,SnoSloc(F1F2)+ F+ ，說明分解后，有些函數(shù)依賴丟失，說明分解后，有些函數(shù)依賴丟失了。了。希望在分解過程中不丟失函數(shù)依賴，這個問希望在分解過程中不丟失函數(shù)依賴，這個問題稱為分解的依賴保持性。題稱為分解的依賴保持性。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分解為下面二個關(guān)系模式：分解為下面二個關(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)系一樣，因此沒有丟失信息沒有丟失信息F+

46、= SnoSdept,SdeptSloc,SnoSloc(F1F2)+=SnoSdept, SnoSloc(F1F2)+ F+ ，說明分解后，說明分解后，有些函數(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分解為下面二個關(guān)系模式：分解為下面二個關(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)系一樣，因此沒有丟失信息沒有丟失信息F+= SnoSdept,SdeptSloc,SnoSloc(F1F2)+=SnoSdept, SdeptSloc,SnoSloc(F1F2)+ = F+ ，說明分解后，說明分解后，函數(shù)依賴沒有丟失。函數(shù)依賴沒有丟失。566.4.1 三種模式分解的等價定義三種模式分解的等價定義（1）分解具有無損連接性）分解具有無損連接性（2） 分解要保持函數(shù)依賴分解要保持函數(shù)依賴（3）分解既要保持函數(shù)依賴，又要具有無損連接性）分解既要保持

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

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

50、 Rk是是R的的一個分解，一個分解，（1）構(gòu)造一個）構(gòu)造一個n列列k行的一個表，第行的一個表，第i行對應(yīng)行對應(yīng)Ri，第，第j列對應(yīng)列對應(yīng)Aj；RI AJA1A2AnR1R2Rk59連接不失真的檢驗連接不失真的檢驗（2）填表，第）填表，第i行第行第j列上填寫列上填寫aj；否則填寫；否則填寫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)為無損分解。為無損分解。61分解分解1具有無損連接性，具有無損連接性， 分解分解2不具有無損連接性不具有無損連接性ABCa1a2a1a3ABACABCa1a2a2a3ABBC【例例2】R(A,B,C), F=AB, C B 分解分解1=(A,B) AB, (A,C) 分解分解2=(A,B) AB, (B,C) CB分析兩種分解的無損連接性？分析兩種分解的無損連接性？62【

52、定理定理6.5 】關(guān)系模式關(guān)系模式R(U)的一個分解，的一個分解， = R1 , R2, 如 果如 果 U1 U2 U1 U2 F+， 或， 或U1U2U2 U1F+，則，則 具有無損連接性。具有無損連接性。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+該分解該分解 具有無損連接性。具有無損連接性。 如果兩個關(guān)系模式之間的公共屬性集至少包含如果兩個關(guān)系模式之間的公共屬性

53、集至少包含其中一個關(guān)系模式的碼，則此分解具有無損連接其中一個關(guān)系模式的碼，則此分解具有無損連接性。性。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+該分解該分解 不不具有無損連接性。具有無損連接性。656.4.3 保持函數(shù)依賴的模式分解保持函數(shù)依賴的模式分解【定義定義6.19】設(shè)關(guān)系模式設(shè)關(guān)系模式R被分解為若干個被分解為若干個關(guān)系模式關(guān)系模式R1，R2，Rn 若若F+ = ( Fi)+， 則稱則稱R 的分解的分解 = R1 , , Rn 保持函數(shù)依賴。保

54、持函數(shù)依賴。 即即F所邏輯蘊含的函數(shù)依賴一定也由分解得到所邏輯蘊含的函數(shù)依賴一定也由分解得到的某個關(guān)系模式中的函數(shù)依賴的某個關(guān)系模式中的函數(shù)依賴Fi所邏輯蘊含，則所邏輯蘊含，則稱關(guān)系模式稱關(guān)系模式R的這個分解是保持函數(shù)依賴的的這個分解是保持函數(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+ ，說明分解后，函數(shù)依賴沒有丟失。，說明分解后，函數(shù)依賴沒有丟失。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、既不具有無損連接性，也未保持函數(shù)第一種分解方法既不具有無損連接性，也未保持函數(shù)依賴，它不是原關(guān)系模式的一個等價分解；依賴，它不是原關(guān)系模式的一個等價分解；SN(Sno)，SD(Sdept)，SO(Sloc)第二種分解方法沒有保持函數(shù)依賴，也不具有無損連第二種分解方法沒有保持函數(shù)依賴，也不具有無損連接性；接性；NL(Sno, Sloc)，DL(Sdept, Sloc)第三種分解方法具有無損連接性，但未保持函數(shù)依賴；第三種分解方法具有無損連接性，但未保持函數(shù)依賴；ND(Sno, Sdept)，NL(Sno, Sloc)第四種分解方法既具有無損連接性，又保持了函數(shù)依第四種分解方法既具有無損連接性，又

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+ 該分解該分解 具有無損連接性。具有無損連接性。(F1F2)+=AB ,AC(F1F2)+ F+ ，說明分解后，不具有依賴保持性。，說明分解后，不具有依賴保持性。70【例例4】U=A，B，C，D R1=A，B， R2=B，C， R3=C，D F1=BC，CD F2=AB，CD試問：分解相對于試問：分

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

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

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