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

1、1 第第6章章 關(guān)系數(shù)據(jù)理論關(guān)系數(shù)據(jù)理論 2 課課 程程 C教教 員員 T參參 考考 書書 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 多值依賴多值依賴 例例: 學(xué)校中某一門課程由多個(gè)教師講授，他們使用相同的學(xué)校中某一門課程由多個(gè)教師講授，他們使用相同的 一套參考書。一套參考書。 關(guān)系模式關(guān)系模式Teaching(C, T, B) 課程課程C、教師、教師T 和和 參考書參考書B 3

2、 普通物理學(xué)普通物理學(xué) 光學(xué)原理光學(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），），它

3、的碼它的碼 是（是（C，T，B），），所以所以 屬于屬于BCNF。 存在的問(wèn)題：存在的問(wèn)題： (1)插入異常：插入異常：當(dāng)某門當(dāng)某門 課程增加一名教員時(shí)，課程增加一名教員時(shí)， 該門課程有多少本參該門課程有多少本參 考書就必須插入多少考書就必須插入多少 個(gè)元組；同樣當(dāng)某門個(gè)元組；同樣當(dāng)某門 課程需要增加一本參課程需要增加一本參 考書時(shí)，它有多少個(gè)考書時(shí)，它有多少個(gè) 教員就必須插入多少教員就必須插入多少 個(gè)元組。個(gè)元組。 4 普通物理學(xué)普通物理學(xué) 光學(xué)原理光學(xué)原理 物理習(xí)題集物理習(xí)題集 普通物理學(xué)普通物理學(xué) 光學(xué)原理光學(xué)原理 物理習(xí)題集物理習(xí)題集 數(shù)學(xué)分析數(shù)學(xué)分析 微分方程微分方程 高等代數(shù)高等代

4、數(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 存在的問(wèn)題：存在的問(wèn)題： (2)刪除異常：刪除異常：當(dāng)刪當(dāng)刪 除一門課程的某個(gè)教除一門課程的某個(gè)教 員或者某本參考書時(shí)，員或者某本參考書時(shí)， 需要?jiǎng)h除多個(gè)元組。需要?jiǎng)h除多個(gè)元組。 (3)更新異常：更新異常：當(dāng)一當(dāng)一 門課程的教員或參

5、考門課程的教員或參考 書作出改變時(shí)，需要書作出改變時(shí)，需要 修改多個(gè)元組。修改多個(gè)元組。 (4)數(shù)據(jù)冗余：數(shù)據(jù)冗余：同一同一 門課的教員與參考書門課的教員與參考書 的信息被反復(fù)存儲(chǔ)多的信息被反復(fù)存儲(chǔ)多 次。次。 5 【定義定義6.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é) 李李 勇勇,王王 軍軍 物物

6、理理,光學(xué)原理光學(xué)原理 李李 勇勇,王王 軍軍 物物 理理,物理習(xí)題集物理習(xí)題集 李李 勇勇,王王 軍軍 對(duì)于對(duì)于C的每一個(gè)值，的每一個(gè)值，T有一組值與之對(duì)應(yīng)，而不論有一組值與之對(duì)應(yīng)，而不論B 取何值。取何值。 若若XY而而Z=，則稱則稱XY為平凡的多值依賴，為平凡的多值依賴， 否則稱否則稱XY為非平凡的多值依賴。為非平凡的多值依賴。 6 【形式化定義形式化定義】在在R（U）的任一關(guān)系）的任一關(guān)系r中，如果存中，如果存 在元組在元組t、s ，使得，使得tX=sX，那么就必然存在元組，那么就必然存在元組 w，v r，（，（w，v可以與可以與s，t相同），使得相同），使得 wX=vX=tX，而，而

7、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 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)系模式WS

8、C（ 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ù)的所有商品，每種商 品被該倉(cāng)庫(kù)的所有保管員包管。品被該倉(cāng)庫(kù)的所有保管員包管。 存在是函數(shù)依賴：存在是函數(shù)依賴： W S W C 8 1. 多值依賴多值依賴的的性質(zhì)性質(zhì) （1）多值依賴具有對(duì)稱性，多值依賴具有對(duì)稱性，即即 若若XY，則，則XZ，其中，其中Z=UXY。 （2）多值依賴具有多值依賴具有傳遞傳遞性，性，即即 若若XY，則，則YZ，則，

9、則XZ-Y 。 （3）函數(shù)依賴是多值依賴的特例，）函數(shù)依賴是多值依賴的特例，即即 若若XY， 則則XY。 若若XY，UXY=， 則稱則稱XY 為平凡的多為平凡的多 值依賴值依賴 。 （4） 若若XY，XZ，則，則XYZ 。 （5）若若XY，XZ，則，則XYZ 。 （6）若若XY，XZ，則，則XY-Z ， XZ-Y 。 9 2. 多值依賴多值依賴與函數(shù)依賴的與函數(shù)依賴的區(qū)別區(qū)別 （1）XY的有效性與屬性集范圍有關(guān)的有效性與屬性集范圍有關(guān) XY在在U上成立上成立 XY在屬性集在屬性集W（XY W U） 上成立。上成立。 反之，反之，XY在屬性集在屬性集W（XY W U）上成立，但在）上成立，但在U

10、 上不一定成立。上不一定成立。 若在若在R(U)上，上，XY在屬性集在屬性集W(XY W U)上成立，則上成立，則 稱稱XY為為R(U) 的嵌入式多值依賴。的嵌入式多值依賴。 XY 的的 有效性僅決定于有效性僅決定于X、Y 屬性集上的值，它在任何屬性集上的值，它在任何 屬性集屬性集W（XY W U） 上都成立。上都成立。 （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， 若

11、若 XY（Y X） 是非平凡的多值依賴，且是非平凡的多值依賴，且X 含有含有 碼，則稱碼，則稱R 4NF。 如關(guān)系模式如關(guān)系模式CTB，CT，CB， 碼為碼為(C, T , B)，C不是候選碼，所以不是候選碼，所以CTB 4NF。 如果一門課如果一門課Ci 有有m 個(gè)個(gè) 教員，教員，n 本本 參考書，則關(guān)參考書，則關(guān) 系中分量為系中分量為Ci 的元組共有的元組共有mn 個(gè)，數(shù)據(jù)冗余非常個(gè)，數(shù)據(jù)冗余非常 大。大。 規(guī)范化：規(guī)范化： 4NF的要求是：消除非平凡且非函數(shù)依賴的多值的要求是：消除非平凡且非函數(shù)依賴的多值 依賴。依賴。 將將CTB 分解為分解為CT（C，T），），CB（C，B），）， 在

12、分解后的關(guān)系中分量為在分解后的關(guān)系中分量為Ci 的元組共有的元組共有m + n 個(gè)。個(gè)。 11 6.3 數(shù)據(jù)依賴的蘊(yùn)涵與公理系統(tǒng)數(shù)據(jù)依賴的蘊(yùn)涵與公理系統(tǒng) 1. 函數(shù)依賴的邏輯蘊(yùn)含定義函數(shù)依賴的邏輯蘊(yùn)含定義 已經(jīng)討論了函數(shù)依賴的類型及其對(duì)數(shù)據(jù)庫(kù)模式已經(jīng)討論了函數(shù)依賴的類型及其對(duì)數(shù)據(jù)庫(kù)模式 設(shè)計(jì)的影響和處理方法；設(shè)計(jì)的影響和處理方法； 關(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)碚?/p>

13、；依賴?yán)碚摚?數(shù)據(jù)庫(kù)專家數(shù)據(jù)庫(kù)專家Armstrong等提出一組定義和推理規(guī)等提出一組定義和推理規(guī) 則，并形成了一個(gè)有效而完備的理論體系，即則，并形成了一個(gè)有效而完備的理論體系，即 Armstrong公理系統(tǒng)。公理系統(tǒng)。 數(shù)據(jù)依賴的公理系統(tǒng)是模式分解的理論基礎(chǔ)。數(shù)據(jù)依賴的公理系統(tǒng)是模式分解的理論基礎(chǔ)。 12 函數(shù)依賴函數(shù)依賴F是很大的，如果依靠語(yǔ)義分析方法是很大的，如果依靠語(yǔ)義分析方法 找出一個(gè)關(guān)系模式的所有函數(shù)依賴，是一件很不找出一個(gè)關(guān)系模式的所有函數(shù)依賴，是一件很不 容易的事。實(shí)際上，也是沒有必要的，因?yàn)橐唤M容易的事。實(shí)際上，也是沒有必要的，因?yàn)橐唤M 函數(shù)依賴的存在，必定引起另外一組函數(shù)依賴

14、的函數(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) 函數(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)出

15、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)系模式R U,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中

16、推出。中推出。 【例例1】關(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)涵邏輯蘊(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

17、。 元組號(hào)元組號(hào)XYZW t1adba t2adbb t3bcbc t4bcbd t5ceae 例例2中，可觀察到中，可觀察到r還滿足還滿足XZ，但在函數(shù)依，但在函數(shù)依 賴集賴集F中沒有中沒有XZ。那么，就需要考慮。那么，就需要考慮r除滿足除滿足F 之外，是否還會(huì)滿足一些其它的函數(shù)依賴？之外，是否還會(huì)滿足一些其它的函數(shù)依賴？ 16 在上面的例子中，在上面的例子中，r實(shí)例滿足實(shí)例滿足F外，還滿足外，還滿足F所不所不 包括的包括的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ù)依賴。從

18、給定的函數(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)的 17 2. Armstrong公理系統(tǒng)公理系統(tǒng) 若若U為關(guān)系模式為關(guān)系模式R的屬性全集，的屬性全集，F(xiàn)為為U上的一組上的一組 函數(shù)依賴，設(shè)函數(shù)依賴，設(shè)X、Y、Z、W均為均為R的子集，對(duì)的子集，對(duì) R(U,F)有以下的推理規(guī)則：有以下的推理規(guī)則： （1）A1(自反律自反律)：若：若Y X U ，則，則XY為為F

19、所所 蘊(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】Armstrong推理規(guī)則是正確的。推理規(guī)則是正確的。 證明：證明： (1) 設(shè)設(shè)Y X U 。 對(duì)對(duì)RU,F的任一關(guān)系的任一關(guān)系r中的中的 任意兩個(gè)元組任意

20、兩個(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及及YZ為為F所蘊(yùn)含。所蘊(yùn)含。 對(duì)對(duì)RU,F的任一關(guān)系的任一關(guān)系r中的任意兩個(gè)元組中的任意兩個(gè)元組t,s 。 若若tX=sX,由于由于XY,有

21、有tY=sY； 再由再由YZ,有有tZ=sZ,所以所以XZ為為F所蘊(yùn)含，傳所蘊(yùn)含，傳 遞律得證。遞律得證。 人們把自反律人們把自反律,傳遞律和增廣律稱為傳遞律和增廣律稱為Armstrong公公 理系統(tǒng)。理系統(tǒng)。 20 Armstrong公理的有效性及完備性公理的有效性及完備性 A = f | 可用可用Armstrong公理從公理從F中導(dǎo)出的函數(shù)依賴中導(dǎo)出的函數(shù)依賴f B = f | 被被F所邏輯蘊(yùn)涵的函數(shù)依賴所邏輯蘊(yùn)涵的函數(shù)依賴f l有效性：用有效性：用Armstrong公理從公理從F中導(dǎo)出的函數(shù)依賴中導(dǎo)出的函數(shù)依賴 必為必為F所蘊(yùn)涵。所蘊(yùn)涵。 A B l完備性：完備性：F所蘊(yùn)涵的函數(shù)依賴都能

22、用所蘊(yùn)涵的函數(shù)依賴都能用Armstrong公公 理從理從F中導(dǎo)出。中導(dǎo)出。 B A 21 由由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 證明：證明： （1）推論）推論1顯然成立。顯然成立。 （2）推論）推論2的證明。的證明。 由由XY

23、，利用增廣律可得，利用增廣律可得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 （分解規(guī)則）（分解規(guī)則） （4） AD, DE A E （傳遞律）（傳遞律） 24 根據(jù)合

24、并規(guī)則和分解規(guī)則，很容易得到這樣一根據(jù)合并規(guī)則和分解規(guī)則，很容易得到這樣一 個(gè)重要事實(shí)：個(gè)重要事實(shí)： 【引理引理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？ 問(wèn)題：?jiǎn)栴}：有沒有一般性的算法判定有沒有一般性的算法判定XY是否能由是否能由F 根據(jù)根據(jù)Armstrong 公理導(dǎo)出？公理導(dǎo)出？ 25 3. 函數(shù)依賴的閉包理論函數(shù)依賴的閉包理論 （1）函數(shù)依賴閉包、屬性集閉包）函數(shù)依賴閉包、屬性集

25、閉包 【定義定義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的閉包。的閉包。 解：（解：（1）若）若X=A A B,BC AC（傳遞律）（傳遞律）

26、AA XF+ =A,B,C （2）若）若X=B BB,BC, XF+ =B,C （3）若）若X=C CC XF+ =C 可見，計(jì)算屬性集閉包要比直接計(jì)算函數(shù)依賴可見，計(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+。 于是，判定于是，判定XY 是否能由是否能由F根據(jù)根據(jù)Arms

27、trong公公 理導(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(i)=U 則則X(i)就是就

28、是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ù)依賴，又得到數(shù)依賴，又得到

29、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)，所以再找

30、出左部為，所以再找出左部為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 。 32 4. 函數(shù)依賴集的覆蓋問(wèn)題函數(shù)依賴集的覆蓋問(wèn)題

31、 (1) 函數(shù)依賴集的等價(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+ 就行了。就行了。 因

32、此引理因此引理6.3 給出了判斷兩個(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, C

33、B, G = AC, BD, BC, CB,問(wèn)，問(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 G 36 （2） 最小函數(shù)依賴集最小函數(shù)依賴集 【定義定義6.15】 如果函數(shù)依賴集如果函數(shù)依賴集F滿足下列條件，則滿足下列條件，則 稱稱F為一個(gè)極小函數(shù)依賴集。亦稱為最小依賴集或?yàn)橐粋€(gè)極小函數(shù)依賴集。亦稱為最小依賴集或 最小覆蓋。最小覆蓋。 lF中任一函數(shù)依賴的右部?jī)H

34、含有一個(gè)屬性。中任一函數(shù)依賴的右部?jī)H含有一個(gè)屬性。 lF中不存在這樣的函數(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中沒有重復(fù)的函數(shù)依賴。中沒有重復(fù)的函數(shù)依賴。 （3）既約化：）既約化：保證每個(gè)函數(shù)依賴左部的屬性最小保證每個(gè)函數(shù)依賴左部的屬性最小 化化 。 38

35、【例例5】 考察考察6.l節(jié)中的關(guān)系模式節(jié)中的關(guān)系模式SU,F,其中：其中： U=SNO，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ù)

36、依賴集Fm。此。此Fm稱為稱為F的最小依賴集。的最小依賴集。 求函數(shù)依賴集求函數(shù)依賴集F的最小覆蓋的方法：的最小覆蓋的方法： (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

37、中各函數(shù)依賴中各函數(shù)依賴FDi：XA， 設(shè)設(shè)X=B1,B2,Bm， 檢查檢查Bi （i=l，2，m），）， 若若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+，保留，保留AB B

38、A，令，令G=F-BA BG+=BCA,ABG+，從，從F中去掉中去掉BA F = AB，BC，AC，CA BC，令，令G=F-BC BG+=B,C BG+，在，在F中保留中保留BC AC，令，令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à)于Fm1 42 【例例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+

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

40、判斷CGB，G=F CGB= CA，AG，BA (CG)G+=A，C，G，B A，C，G 檢查檢查 CA , G=F CA = AG，CGB，BA (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，

41、AG，CGB，BA， 求最小覆蓋求最小覆蓋 Fm。 45 6.4 模式的分解模式的分解 解決的問(wèn)題：解決的問(wèn)題： (1)什么叫模式的分解？什么叫模式的分解？ (2)分解后，原關(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，R

42、2，Rn 其中：其中： （1）U=U1U2Un， （2）且不存在）且不存在 Ui Uj，1i，j n，F(xiàn)i 為為 F在在 Ui 上上 的投影。的投影。 【定義定義6.17】 函數(shù)依賴集合函數(shù)依賴集合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 SdeptSl

43、oc 95001 CS A 95002 IS B 95003 MA C 95004 IS B 95005 PH B 48 SN SD SO Sno Sdept Sloc 95001 CS A 95002 IS 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)系，那么這種分解 就沒有丟失信息。就沒有丟失信息。 希望在分解過(guò)程中不丟失希望在分解過(guò)程

44、中不丟失 信息，這個(gè)問(wèn)題稱為信息，這個(gè)問(wèn)題稱為無(wú)損連接無(wú)損連接 或連接不失真或連接不失真。 （1） SL分解為下面三個(gè)關(guān)系分解為下面三個(gè)關(guān)系 模式：模式： SN(Sno) SD(Sdept) SO(Sloc) 49 NL DL Sno 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 Sloc 50 NLDL Sno Sloc Sd

45、ept 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è)元組個(gè)元組 無(wú)法知道無(wú)法知道95002、95004、95005 究竟是哪個(gè)系的學(xué)生。究竟是哪個(gè)系的學(xué)生。 元組增加了，信息丟失了。元組增加了，信息丟失了。 51 F1F2=SnoSloc, SdeptSloc F= SnoSdept,SdeptSloc,SnoSloc (F1F2)+=SnoSloc, SdeptSloc F+= SnoSdept,SdeptSlo

46、c,SnoSloc (F1F2)+ F+ ，說(shuō)明分解后，有些函數(shù)依賴丟失，說(shuō)明分解后，有些函數(shù)依賴丟失 了。了。 希望在分解過(guò)程中不丟失函數(shù)依賴，這個(gè)問(wèn)希望在分解過(guò)程中不丟失函數(shù)依賴，這個(gè)問(wèn) 題稱為分解的依賴保持性。題稱為分解的依賴保持性。 52 ND NL 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(Sn

47、o, Sloc) F2=Sno Sloc 53 NDNL Sno Sdept Sloc 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, SnoSloc (F1F2)+ F+ ，說(shuō)明分解后，說(shuō)明分解后，有些函數(shù)依賴丟失了有些函數(shù)依賴丟失了。 54 ND DL Sno Sdept Sdept Sloc 95001 CS CS A 95002 IS IS B 95003 MA MA

48、 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 Sloc 55 NDDL Sno Sdept Sloc 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)+

49、 = F+ ，說(shuō)明分解后，說(shuō)明分解后，函數(shù)依賴沒有丟失。函數(shù)依賴沒有丟失。 56 6.4.1 三種模式分解的等價(jià)定義三種模式分解的等價(jià)定義 （1）分解具有無(wú)損連接性）分解具有無(wú)損連接性 （2） 分解要保持函數(shù)依賴分解要保持函數(shù)依賴 （3）分解既要保持函數(shù)依賴，又要具有無(wú)損連接性）分解既要保持函數(shù)依賴，又要具有無(wú)損連接性 l如果一個(gè)分解具有無(wú)損連接性，則它能夠保證不丟如果一個(gè)分解具有無(wú)損連接性，則它能夠保證不丟 失信息。失信息。 l如果一個(gè)分解保持了函數(shù)依賴，則它可以減輕或解如果一個(gè)分解保持了函數(shù)依賴，則它可以減輕或解 決各種異常情況。決各種異常情況。 l分解具有無(wú)損連接性和分解保持函數(shù)依賴是兩

50、個(gè)互分解具有無(wú)損連接性和分解保持函數(shù)依賴是兩個(gè)互 相獨(dú)立的標(biāo)準(zhǔn)。具有無(wú)損連接性的分解不一定能夠相獨(dú)立的標(biāo)準(zhǔn)。具有無(wú)損連接性的分解不一定能夠 保持函數(shù)依賴。同樣，保持函數(shù)依賴的分解也不一保持函數(shù)依賴。同樣，保持函數(shù)依賴的分解也不一 定具有無(wú)損連接性。定具有無(wú)損連接性。 57 6.4.2 具有無(wú)損連接性的模式分解具有無(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ú)損

51、連接性的分解保證不丟失信息。具有無(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, , 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 AJA1A2An R1 R2 Rk 59 連接不失真的檢驗(yàn)連接不失真的檢驗(yàn) （2）填表，第）填表，第i行第行第j列上填

52、寫列上填寫aj；否則填寫；否則填寫bi,j （3）修改表：逐一掃描函數(shù)依賴，在）修改表：逐一掃描函數(shù)依賴，在x列上相同，列上相同，y上必定相上必定相 同；同； （4）重復(fù)（）重復(fù)（3），直至，掃描完所有的函數(shù)依賴。），直至，掃描完所有的函數(shù)依賴。 RI AJA1A2An R1 R2 Rk 60 【例例1】U=A,B,C,D,E, F=ABC, CD,DE =(A, B, C), (C, D), (D, E) RI AJ ABCDE R1 a1a2a3b14 a4b15 a5 R2 b21b22a3a4b25 a5 R3 b31b32b33a4a5 =(A, B, C), (C, D), (D,

53、 E)為無(wú)損分解。為無(wú)損分解。 61 分解分解1具有無(wú)損連接性，具有無(wú)損連接性， 分解分解2不具有無(wú)損連接性不具有無(wú)損連接性 ABC a1a2 a1a3 AB AC ABC a1a2 a2a3 AB BC 【例例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 【定理定理6.5 】關(guān)系模式關(guān)系模式R(U)的一個(gè)分解，的一個(gè)分解， = R1 , R2, 如 果如 果 U 1 U 2 U 1 U 2 F + ， 或， 或 U1U2U2 U1F+，則，則

54、 具有無(wú)損連接性。具有無(wú)損連接性。 63 【例例3】U=S#，SD，MN，C#，G F=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)系模式之間的公共屬性集至少包含 其中一個(gè)關(guān)系模式的碼，則此分解具有無(wú)損連接其中一個(gè)關(guān)系模式的碼，則此分解具有無(wú)損連接 性。性。 64 【例例4】U=A，B，C F=AB，CB U1=A

55、，B , F1=AB U2=B, C, F2=CB 解：解： U1U2= B U1-U2= A , U2-U1= C BA, BC F+ 該分解該分解 不不具有無(wú)損連接性。具有無(wú)損連接性。 65 6.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ù)依賴。保持函數(shù)依賴。 即即F所邏輯蘊(yùn)含的函數(shù)依賴一定也由分解得到所邏輯蘊(yùn)含的函數(shù)依賴一定也由分解得到 的某個(gè)關(guān)系模式中的函數(shù)依賴的某個(gè)關(guān)系模式中的函數(shù)依

56、賴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 Sloc F+= SnoSdept,SdeptSloc,SnoSloc (F1F2)+=SnoSdept, SdeptSloc,SnoSloc (F1F2)+ = F+ ，說(shuō)明分解后，函數(shù)依賴沒有丟

57、失。，說(shuō)明分解后，函數(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） 第一種分解方法既不具有無(wú)損連接性，也未保持函數(shù)第一種分解方法既不具有無(wú)損連接性，也未保持函數(shù) 依賴，它不是原關(guān)系模式的一

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

59、【例例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)：分解相對(duì)于F1和和F2是否無(wú)損分解？是否無(wú)損分解？ 71 幾個(gè)命題幾個(gè)命題

60、（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á)到可以達(dá)到4NF。 72 補(bǔ)充：求解關(guān)系模式的候選碼補(bǔ)