數(shù)據(jù)庫原理與設(shè)計課件：第10章 關(guān)系數(shù)據(jù)庫設(shè)計理論

1、第10章 關(guān)系數(shù)據(jù)庫設(shè)計理論22022/7/18第10章 關(guān)系數(shù)據(jù)庫設(shè)計理論10.1 關(guān)系模型的存儲異常10.2 函數(shù)依賴10.5 關(guān)系模式的規(guī)范化10.6 多值依賴和4NF10.3 函數(shù)依賴公理10.4* 模式分解10.8 小結(jié)32022/7/1810.1 關(guān)系模型的存儲異常數(shù)據(jù)庫模式的設(shè)計是數(shù)據(jù)庫應(yīng)用系統(tǒng)開發(fā)的核心問題由于認(rèn)識或看問題的方法不同，一個數(shù)據(jù)庫可以設(shè)計出不同的數(shù)據(jù)庫模式。針對具體問題，如何構(gòu)造一個適合于它的數(shù)據(jù)模式?即構(gòu)造幾個關(guān)系模式，每個關(guān)系有哪些屬性這是數(shù)據(jù)庫設(shè)計的問題,是關(guān)系數(shù)據(jù)庫的邏輯設(shè)計關(guān)系數(shù)據(jù)庫模式的設(shè)計，即數(shù)據(jù)庫的邏輯設(shè)計就是要從各種可能的關(guān)系模式組合中選取一組關(guān)

2、系模式來構(gòu)成一個數(shù)據(jù)庫模式。 42022/7/1810.1 關(guān)系模型的存儲異常某學(xué)校圖書館要建一個圖書數(shù)據(jù)庫，其中借閱管理包括借書證號(CARDNO)、借書人姓名(NAME)、借書人所在單位(DEPT)、單位負(fù)責(zé)人(MN)、圖書編號(BNO)、借閱日期(DATE)等信息。借閱圖書登記可以用如下關(guān)系模式來描述：BORROW（CARDNO，NAME，DEPT，MN，BNO，DATE）CARDNONAMEDEPTMNBNODATER001李曉鵬計算機(jī)張宏軍TP31-12520070123R001李曉鵬計算機(jī)張宏軍TP32-00720061112R001李曉鵬計算機(jī)張宏軍TP12-2332007040

3、5R002王一鳴計算機(jī)張宏軍TP51-21120080209R003劉明川無線電范和平TP23-12620071011R003劉明川無線電范和平TP23-02320080321R003劉明川無線電范和平TP25-04520080321 1. 數(shù)據(jù)冗余借書人每借一本書，很多信息重復(fù)存儲大量的數(shù)據(jù)冗余不僅造成存儲空間的浪費(fèi),而且存在著潛在的數(shù)據(jù)不一致。 52022/7/182. 插入異常BORROW（CARDNO，NAME，DEPT，MN，BNO，DATE）CARDNONAMEDEPTMNBNODATER001李曉鵬計算機(jī)張宏軍TP31-12520070123R001李曉鵬計算機(jī)張宏軍TP32-0

4、0720061112R001李曉鵬計算機(jī)張宏軍TP12-23320070405R002王一鳴計算機(jī)張宏軍TP51-21120080209R003劉明川無線電范和平TP23-12620071011R003劉明川無線電范和平TP23-02320080321R003劉明川無線電范和平TP25-04520080321 2. 插入異常關(guān)鍵字是由CARDNO和BNO組成的聯(lián)合鍵,根據(jù)實體完整性規(guī)則，關(guān)鍵字不能為空如果要插入一個借書人的信息是不能進(jìn)行的62022/7/18 3. 刪除異常BORROW（CARDNO，NAME，DEPT，MN，BNO，DATE）CARDNONAMEDEPTMNBNODATER0

5、01李曉鵬計算機(jī)張宏軍TP31-12520070123R001李曉鵬計算機(jī)張宏軍TP32-00720061112R001李曉鵬計算機(jī)張宏軍TP12-23320070405R002王一鳴計算機(jī)張宏軍TP51-21120080209R003劉明川無線電范和平TP23-12620071011R003劉明川無線電范和平TP23-02320080321R003劉明川無線電范和平TP25-04520080321 3. 刪除異常當(dāng)借書人歸還所借的書后，需要從借閱關(guān)系中刪除相關(guān)信息如果借閱人把所借的書全部還清了，則連同借閱人及所在單位的所有信息都一起刪除72022/7/184.更新異常BORROW（CARDN

6、O，NAME，DEPT，MN，BNO，DATE）CARDNONAMEDEPTMNBNODATER001李曉鵬計算機(jī)張宏軍TP31-12520070123R001李曉鵬計算機(jī)張宏軍TP32-00720061112R001李曉鵬計算機(jī)張宏軍TP12-23320070405R002王一鳴計算機(jī)張宏軍TP51-21120080209R003劉明川無線電范和平TP23-12620071011R003劉明川無線電范和平TP23-02320080321R003劉明川無線電范和平TP25-045200803214. 更新異常如果所在單位或單位負(fù)責(zé)人變了，需要修改該借書人在DEPT或MN屬性上的值。但由于數(shù)據(jù)冗

7、余，有關(guān)借書人所有元組中的單位或單位負(fù)責(zé)人的信息都要修改。這不僅增加了更新代價，而且存在著潛在的不一致性82022/7/1810.1 關(guān)系模型的存儲異常E.F.Codd把這些問題統(tǒng)稱為存儲異常這些問題不希望出現(xiàn)，這樣設(shè)計的數(shù)據(jù)庫不好為什么會出現(xiàn)存儲異常呢？因為在數(shù)據(jù)間存在著一定的依賴關(guān)系如借書關(guān)系中，借閱人和借閱人所在單位單位負(fù)責(zé)人與借書證號之間以及借書證號、書號與借閱日期之間存在著依存關(guān)系。但BORROW模式?jīng)]有很好地反映這些關(guān)系。在現(xiàn)實世界中，實體和實體間及實體內(nèi)部的屬性值之間存在著相互依賴又相互制約的關(guān)系，稱為數(shù)據(jù)依賴92022/7/18第10章 關(guān)系數(shù)據(jù)庫設(shè)計理論10.1 關(guān)系模型的存

8、儲異常10.2 函數(shù)依賴10.5 關(guān)系模式的規(guī)范化10.6 多值依賴和4NF10.3 函數(shù)依賴公理10.4* 模式分解10.8 小結(jié)102022/7/1810.2.1 函數(shù)依賴的定義函數(shù)依賴(Functional Dependency, FD)是現(xiàn)實世界中最廣泛存在的一種數(shù)據(jù)依賴，是現(xiàn)實世界屬性間相互聯(lián)系的抽象;是數(shù)據(jù)內(nèi)在的性質(zhì);它表示了關(guān)系中屬性間的一種制約關(guān)系。一、函數(shù)依賴二、平凡函數(shù)依賴與非平凡函數(shù)依賴三、完全函數(shù)依賴與部分函數(shù)依賴四、傳遞函數(shù)依賴112022/7/1810.2.1 函數(shù)依賴的定義定義10.1 設(shè)關(guān)系模式R(U)，X,YU，r是R(U)上的任一關(guān)系。對任意元組t1 、t2

9、r, 如果t1、t2在X上的屬性值相等， t1、t2在Y上的屬性值亦相等，則稱X函數(shù)決定Y,或Y函數(shù)依賴于X，記為FD XY稱X為決定因素，或稱X為函數(shù)依賴的左部，稱Y為函數(shù)依賴的右部。 BORROW（CARDNO，NAME，DEPT，MN，BNO，DATE）CARDNONAME；每個借書證號可以唯一確定一個讀者 CARDNODEPT；每個借書證號可以唯一確定讀者所在單位 CARDNOMN；借書證號可以唯一確定讀者所在單位負(fù)責(zé)人 DEPTMN；單位可以唯一確定單位負(fù)責(zé)人 (CARDNO,BNO)DATE 借閱日期由證號和圖書編號共同決定122022/7/1810.2.1 函數(shù)依賴的定義函數(shù)依賴

10、是指R的所有關(guān)系實例均要滿足的約束條件, 而不是指關(guān)系模式R的某個或某些關(guān)系實例滿足的約束條件。函數(shù)依賴是語義范疇的概念，只能根據(jù)現(xiàn)實世界中數(shù)據(jù)間的語義確定函數(shù)依賴 如函數(shù)依賴：姓名年齡，只有規(guī)定不允許有同名同姓的人的情況下才成立。 為滿足這種語義約束，當(dāng)裝入元組到數(shù)據(jù)庫時,就要檢查這種約束條件，使相應(yīng)元組上的屬性值滿足規(guī)定的函數(shù)依賴。 在模式設(shè)計中，設(shè)計者對需要處理的數(shù)據(jù)間的約束關(guān)系要非常清楚,才能根據(jù)實際情況確定屬性間的函數(shù)依賴,從而設(shè)計出滿足要求的數(shù)據(jù)庫模式 132022/7/1810.2.1 函數(shù)依賴的定義定義10.2 設(shè)FD XY，如果YX，則稱FD XY為非平凡的函數(shù)依賴；否則，若

11、YX，稱FD XY為平凡的函數(shù)依賴。平凡的函數(shù)依賴是對模式R上的所有關(guān)系都成立的函數(shù)依賴。 例：在關(guān)系SC(Sno, Cno, Grade)中， 非平凡函數(shù)依賴： (Sno, Cno) Grade 平凡函數(shù)依賴： (Sno, Cno) Sno (Sno, Cno) Cno對于任一關(guān)系模式，平凡函數(shù)依賴都是必然成立的，它不反映新的語義，因此若不特別聲明， 總是討論非平凡函數(shù)依賴。142022/7/1810.2.1 函數(shù)依賴的定義定義10.3 設(shè)FD XY，如果對任意的X X，XY都不成立,則稱FD XY是完全函數(shù)依賴；若對X的真子集X有XX，而X Y成立，則稱FD XY是部分函數(shù)依賴，即Y函數(shù)依

12、賴于X的一部分在借閱關(guān)系BORROW中，存在著完全函數(shù)依賴：(CARDNO, BNO)DATE，CARDNONAME，CARDNODEPT，CARDNOMN，DEPTMN。而以下函數(shù)依賴是部分函數(shù)依賴：(CARDNO, BNO)NAME，(CARDNO, BNO)DEPT，(CARDNO, BNO)MN。 152022/7/1810.2.1 函數(shù)依賴的定義定義10.4 設(shè)關(guān)系模式R，X、Y、Z是R的屬性子集，若FD XY，Y X，YZ，則必有FD XZ，稱FD XZ為傳遞函數(shù)依賴。例如，在借閱關(guān)系BORROW中，存在函數(shù)依賴CARDNODEPT，DEPTMN，而DEPT CARDNO ，則有傳

13、遞依賴CARDNOMN 注: 如果YX, 已知XY，則XY,又因為YZ，則有XZ, 稱Z直接依賴于X。162022/7/1810.2.1 函數(shù)依賴的定義一、函數(shù)依賴二、平凡函數(shù)依賴與非平凡函數(shù)依賴三、完全函數(shù)依賴與部分函數(shù)依賴四、傳遞函數(shù)依賴了解現(xiàn)實世界中數(shù)據(jù)間的依存和制約關(guān)系，正確確定屬性間的函數(shù)依賴關(guān)系，對設(shè)計一個好的數(shù)據(jù)庫模式是很重要的 172022/7/18第10章 關(guān)系數(shù)據(jù)庫設(shè)計理論10.1 關(guān)系模型的存儲異常10.2 函數(shù)依賴10.5 關(guān)系模式的規(guī)范化10.6 多值依賴和4NF10.3 函數(shù)依賴公理10.4 模式分解10.8 小結(jié)182022/7/1810.5 關(guān)系模式的規(guī)范化研究

14、了規(guī)范化理論的目的設(shè)計好的數(shù)據(jù)模式 用規(guī)范化理論改造關(guān)系模式通過分解關(guān)系模式, 消除關(guān)系模式中不合適的數(shù)據(jù)依賴，解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問題1971年，E.F.Codd首先提出了規(guī)范化的問題，給出了范式(Normal Form, NF)的概念 根據(jù)關(guān)系模式所達(dá)到的不同約束提出了1NF、2NF、3NF的概念 1974年Codd和Boyce提出BCNF(Boyce-Codd Normal Form) 之后又研究了4NF、5NF 192022/7/1810.5 關(guān)系模式的規(guī)范化所謂范式就是規(guī)范化的關(guān)系模式。范式是符合某一種級別的關(guān)系模式的集合。關(guān)系數(shù)據(jù)庫中的關(guān)系必須滿足一定的要求。

15、滿足不同程度要求的為不同范式。范式的種類：根據(jù)規(guī)范化程度的不同，數(shù)據(jù)庫范式從低到高有1NF、 2NF、3NF、BC范式(BCNF)、 4NF一個數(shù)據(jù)庫模式從低一級的范式，可以通過模式分解轉(zhuǎn)化為若干個高一級的范式的關(guān)系模式的集合從低一級的范式通過分解達(dá)到高一級范式的過程稱為關(guān)系模式的規(guī)范化 202022/7/1810.5.1 第一范式第一范式是最低級別的關(guān)系模式，關(guān)系數(shù)據(jù)庫中的關(guān)系模式至少都應(yīng)是第一范式的定義10. 15 如果關(guān)系模式R的每一個屬性對應(yīng)的域值都是不可再分的，稱模式R屬于第一范式，簡記為R1NF若數(shù)據(jù)庫模式R中的每個關(guān)系模式都是1NF，數(shù)據(jù)庫模式R1NF。一個數(shù)據(jù)庫系統(tǒng)中的關(guān)系至少

16、應(yīng)該是1NF的，是關(guān)系作為二維表的起碼的要求。不滿足1NF的數(shù)據(jù)庫模式不能稱為關(guān)系數(shù)據(jù)庫但是滿足1NF的關(guān)系模式不一定是好的關(guān)系模式212022/7/1810.5.2 第二范式(2NF)定義10.16 設(shè)關(guān)系模式R，A是R中的屬性，F(xiàn)是R上的函數(shù)依賴集。如果A包含在R的某個候選鍵中，稱A為主屬性，否則稱A為非主屬性。定義10.17 如果一個關(guān)系模式R1NF，且所有非主屬性都完全依賴于R的每個候選鍵，則R2NF。 判定一個關(guān)系模式是否屬于2NF，需要了解關(guān)系模式的屬性間存在哪些依賴 根據(jù)數(shù)據(jù)依賴關(guān)系，找出關(guān)系模式的候選鍵， 確定哪些屬性是主屬性，哪些屬性是非主屬性， 確定非主屬性與候選鍵之間是否

17、存在完全函數(shù)依賴關(guān)系，以判定該模式是否屬于2NF 222022/7/1810.5.2 第二范式(2NF)借書關(guān)系BORROW(CARDNO, NAME, DEPT, MN, BNO, DATE)是1NF的，但不是2NF 函數(shù)依賴： CARDNONAME，CARDNODEPT, CARDNOMN， DEPTMN， (CARDNO、BNO)DATE 屬性NAME、DEPT和MN部分依賴于BORROW的候選鍵。因此，BORROW2NF BORROW不是一個好的關(guān)系模式(插入異常、刪除異常、數(shù)據(jù)冗余、修改復(fù)雜)原因: NAME、DEPT和MN部分函數(shù)依賴于候選鍵232022/7/1810.5.2 第二

18、范式(2NF)解決方法: BORROW分解為兩個關(guān)系模式，以消除這些部分函數(shù)依賴LOANS(CARDNO，NAME，DEPT，MN) 2NF BORROW (CARDNO，BNO，DATE) 2NF CARDNONAMEDEPTMNR001李曉鵬計算機(jī)系張宏軍R002王一鳴計算機(jī)系張宏軍R003劉明川無線電系范和平CARDNOBNODATER001TP31-12520070123R001TP32-00720061112R001TP12-23320070405R002TP51-21120080209將一個1NF的關(guān)系分解為多個2NF的關(guān)系，可以在一定程度上減輕原1NF關(guān)系中存在的插入異常、刪除異

19、常、數(shù)據(jù)冗余度大、修改復(fù)雜等問題。并不能完全消除關(guān)系模式中的各種存儲異常情況242022/7/1810.5.3 第三范式LOANS(CARDNO，NAME，DEPT，MN) 2NF函數(shù)依賴：CARDNODEPT，DEPTMN，且DEPT CARDNO ，則FD CARDNOMN是傳遞依賴存在非主屬性對候選鍵的傳遞函數(shù)依賴解決方法，把LOANS分解為兩個關(guān)系模式，以消除傳遞函數(shù)依賴CARDNONAMEDEPTMNR001李曉鵬計算機(jī)系張宏軍R002王一鳴計算機(jī)系張宏軍R003劉明川無線電系范和平CARDNONAMEDEPTR001李曉鵬計算機(jī)系R002王一鳴計算機(jī)系R003劉明川無線電系DEPT

20、MN計算機(jī)系張宏軍無線電系范和平252022/7/1810.5.3 第三范式定義10.18 設(shè)R1NF，若在R中沒有非主屬性傳遞依賴于R的候選鍵，則關(guān)系模式R3NF 。如果數(shù)據(jù)庫模式R中每一關(guān)系模式都是3NF，則數(shù)據(jù)庫模式R3NF 結(jié)論一個2NF的關(guān)系模式不一定屬于3NF. 但是，一個關(guān)系模式若是3NF的，則一定屬于2NF。 262022/7/1810.5.3 第三范式定理10.6 若任一關(guān)系模式R3NF，則R2NF。 證明：用反證法。設(shè)R上的函數(shù)依賴集為F，R的鍵為K.假設(shè)R3NF但R2NF,則有R中非主屬性A部分依賴于關(guān)鍵字K。那么，存在K的真子集K ，使得F|=KA。由于KK, 有FD

21、KK, 但K K. 于是, KK, K K，KA，并且AK，因而A傳遞依賴于K，即R3NF，與假設(shè)矛盾。證畢若R3NF，則R的每一個非主屬性既不部分函數(shù)依賴于候選鍵也不傳遞函數(shù)依賴于候選鍵。272022/7/1810.5.4 Boyce-Codd范式(BCNF)第三范式消除了非主屬性和主屬性間的部分函數(shù)依賴和傳遞函數(shù)依賴，在一定程度上解決了存儲異常問題但只是涉及非主屬性和主屬性間的函數(shù)依賴，而沒有考慮主屬性間的函數(shù)依賴問題。 282022/7/1810.5.4 Boyce-Codd范式(BCNF)實際上，在主屬性間也存在著部分函數(shù)依賴和傳遞函數(shù)依賴，同樣會出現(xiàn)存儲異常問題 。例如，關(guān)系模式R(

22、City, Street, Zip)，R上的函數(shù)依賴為 (City,Street)Zip, Zip City候選鍵為(City, Street)或(Street, Zip)R中沒有非主屬性，因而也不存在非主屬性與主屬性間的部分函數(shù)依賴和傳遞函數(shù)依賴，R3NF但由于有Zip City，對候選鍵(Street, Zip)，(Street, Zip) City為部分函數(shù)依賴,造成C值多次重復(fù)，同樣會引起更新異常如若要修改北京對應(yīng)的郵政編碼為110000，必須修改北京地區(qū)的所有郵政編碼 292022/7/1810.5.4 Boyce-Codd范式(BCNF)定義10.19 若R1NF，而且R中沒有任何

23、屬性傳遞依賴于R中的任一關(guān)鍵字，則關(guān)系模式R屬于Boyce-Codd范式（BCNF）。如果數(shù)據(jù)庫模式R中的每個關(guān)系模式R都屬于BCNF，則數(shù)據(jù)庫模式RBCNF BCNF不但排除了非主屬性對主屬性的傳遞依賴，也排除了主屬性間的傳遞依賴 一個更直觀的等價的BCNF的定義 定義10.20 設(shè)關(guān)系模式R1NF，F(xiàn)是R上的函數(shù)依賴集,對于F中的每一個函數(shù)依賴XY，必有X是R的一個候選鍵，則RBCNF 如果RBCNF，則R上的每一個函數(shù)依賴中的,每個決定因素都包含侯選鍵 302022/7/1810.5.4 Boyce-Codd范式(BCNF)3NF與BCNF的關(guān)系若RBCNF 每一個決定屬性集（因素）都包

24、含（候選）鍵R中的所有屬性(主，非主屬性)都完全函數(shù)依賴于鍵所以R3NF若R3NF, R不一定BCNF如果R3NF，且R只有一個候選鍵，則R必屬于BCNFBCNF比3NF嚴(yán)格，3NF僅消除了非主屬性的存儲異常，3NF的“不徹底”性表現(xiàn)在可能存在主屬性對鍵的部分依賴和傳遞依賴。而BCNF消除了整個關(guān)系模式的存儲異常。312022/7/1810.5.4 Boyce-Codd范式(BCNF)BCNF的關(guān)系模式所具有的性質(zhì) 所有非主屬性都完全函數(shù)依賴于每個候選碼 所有主屬性都完全函數(shù)依賴于每個不包含它的候選碼 沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性在函數(shù)依賴的范圍內(nèi)，BCNF已達(dá)到了關(guān)系模式的最

25、大分離，已經(jīng)消除了插入、刪除異常，是函數(shù)依賴范圍內(nèi)能夠達(dá)到的最高范式322022/7/18第10章 關(guān)系數(shù)據(jù)庫設(shè)計理論10.1 關(guān)系模型的存儲異常10.2 函數(shù)依賴10.5 關(guān)系模式的規(guī)范化10.6 多值依賴和4NF10.3 函數(shù)依賴公理10.4 模式分解10.8 小結(jié)332022/7/1810.6 多值依賴和4NF屬于BCNF的關(guān)系模式是否完美？例: 學(xué)校中某一門課程由多個教師講授，他們使用相同的一套參考書。關(guān)系模式Teaching(C, T, B)課 程 C教 員 T參 考 書 B物理數(shù)學(xué)計算數(shù)學(xué)李 勇王 軍李 勇張 平張 平周 峰 普通物理學(xué)光學(xué)原理 物理習(xí)題集數(shù)學(xué)分析微分方程高等代數(shù)數(shù)

26、學(xué)分析342022/7/18普通物理學(xué)光學(xué)原理物理習(xí)題集普通物理學(xué)光學(xué)原理物理習(xí)題集數(shù)學(xué)分析微分方程高等代數(shù)數(shù)學(xué)分析微分方程高等代數(shù)李 勇李 勇李 勇王 軍王 軍王 軍李 勇李 勇李 勇張 平張 平張 平 物 理物 理物 理物 理物 理物 理數(shù) 學(xué)數(shù) 學(xué)數(shù) 學(xué)數(shù) 學(xué)數(shù) 學(xué)數(shù) 學(xué) 參考書B教員T課程C10.6 多值依賴和4NF用二維表表示Teaching352022/7/1810.6 多值依賴和4NFTeachingBCNF:Teaching具有唯一候選鍵(課程C,教師T,參考書B), 即全鍵362022/7/1810.6 多值依賴和4NFTeaching模式中存在的問題 (1)數(shù)據(jù)冗余度大：有

27、多少名任課教師，參考書就要存儲多少次(2)插入操作復(fù)雜：當(dāng)某課程增加一名任課教師時，該課程有多少本參照書，就必須插入多少個元組 例如物理課增加一名教師劉關(guān)，需要插入兩個元組：（物理，劉關(guān)，普通物理學(xué)） （物理，劉關(guān)，光學(xué)原理）(3) 刪除操作復(fù)雜：某一門課要去掉一本參考書，該課程有多少名教師，就必須刪除多少個元組(4) 修改操作復(fù)雜：某一門課要修改一本參考書，該課程有多少名教師，就必須修改多少個元組 產(chǎn)生原因存在多值依賴 課程教員 課程參考書372022/7/18uts10.6.1 多值依賴定義10.21 設(shè)R(U)是一個關(guān)系模式，X和Y是U的子集,且Z=U(XY)。如果對于關(guān)系r(R)中的任

28、意兩個元組s和t,若sX=tX，在r中存在元組u，有： uX=sX，uY=sY，且uZ=tZ， 則關(guān)系r(R)滿足多值依賴(MVD) XY，稱X多值決定Y或Y多值依賴于X。 Teaching(X,Y,Z) 對于X的每一個值，Y有一組值與之對應(yīng)，而不論Z取何值存在多值依賴 課程教員 課程參考書普通物理學(xué)光學(xué)原理物理習(xí)題集普通物理學(xué)光學(xué)原理物理習(xí)題集李 勇李 勇李 勇王 軍王 軍王 軍物 理物 理物 理物 理物 理物 理參考書Z教員Y課程X382022/7/1810.6.1 多值依賴等價的多值依賴的另一個定義 定義10.22設(shè)R(U)是一個關(guān)系模式，X,Y和Z是U的子集,且Z=UX Y。r是R上的

29、一個關(guān)系。當(dāng)且僅當(dāng)對于給定的一個x值，有一組y的值，且這組y值僅僅決定于x值，而與r中的其它屬性 z 無關(guān)，則稱X多值決定Y或Y多值依賴于X，記為XY 普通物理學(xué)光學(xué)原理物理習(xí)題集普通物理學(xué)光學(xué)原理物理習(xí)題集李 勇李 勇李 勇王 軍王 軍王 軍物 理物 理物 理物 理物 理物 理參考書Z教員Y課程X存在多值依賴 課程教員 課程參考書392022/7/1810.6.1 多值依賴平凡多值依賴和非平凡的多值依賴若XY,而Z,則稱 XY為平凡的多值依賴否則稱XY為非平凡的多值依賴402022/7/18多值依賴的性質(zhì)(1) 多值依賴具有對稱性若XY，則XZ，其中ZUXY多值依賴的對稱性可以用完全二分圖直

30、觀表示XiZi1 Zi2 ZimYi1 Yi2 Yin 物 理普通物理學(xué) 光學(xué)原理 物理習(xí)題集李勇 王軍412022/7/18多值依賴的性質(zhì)(2) 多值依賴具有傳遞性若XY、YZ，則XZY(3) 函數(shù)依賴是多值依賴的特殊情況若XY，則XY這是因為當(dāng)XY時，對X的每一個值x，Y有確定的值y與之對應(yīng)，所以XY422022/7/1810.6.1 多值依賴設(shè)r是模式R上的關(guān)系，且W、X、Y、Z是R的子集。多值依賴的推理公理為：M1：自反律 若Y X 則XY。M2：增廣律 若XY，W Z，則XZYW。M3：相加律 若XY、XZ，則XYZ。M4：投影律 若XY、XZ， 則XYZ、 XYZ。M5：傳遞律 若

31、XY、YZ，則XZY。M6：偽傳遞律 若XY、YWZ， 則XWZ(YW)M7：互補(bǔ)律 若XY、ZR(XY)，則XZM8：重復(fù)律 若XY，則XY。 M9：結(jié)合律 若XY，ZW，其中W Y和YZ，則XW。 432022/7/1810.6.2 4NF若關(guān)系模式存在多值依賴時，還需要進(jìn)一步規(guī)范化 定義10.23 設(shè)關(guān)系模式R1NF，F(xiàn)是R上的FD和MVD集。如果對于R上的任何一個非平凡的多值依賴XY，X都含有鍵(碼)，則R4NF。如果數(shù)據(jù)庫模式R中的每一個關(guān)系模式R都屬于4NF，那么，數(shù)據(jù)庫模式R4NF。 定義3.3 設(shè)關(guān)系模式R ( U )，K U，r是R上的任一關(guān)系，若對r中的任意二個不同的元組滿

32、足：t1 K t2K, 則稱K是R的超鍵( superkey ) 。 若不存在K K, 使得t1 K t2 K成立, 稱K是R的鍵(碼)442022/7/1810.6.2 4NF根據(jù)4NF的定義，關(guān)系模式R1NF，如果對于R的每個非平凡多值依賴XY(Y X)，X都含有候選鍵，則必然有XY，所以4NF所允許的非平凡多值依賴實際上是函數(shù)依賴。如果R 4NF， 則R BCNF函數(shù)依賴是多值依賴的特殊情況若XY，則XY這是因為當(dāng)XY時，對X的每一個值x，Y有確定的值y與之對應(yīng)，所以XY定義10.20 設(shè)關(guān)系模式R1NF，F(xiàn)是R上的函數(shù)依賴集,對于F中的每一個函數(shù)依賴XY，必有X是R的一個候選鍵，則RB

33、CNF 452022/7/1810.6.2 4NF可采用分解的方法消去非平凡非函數(shù)依賴的多值依賴?yán)?Teaching(C,T,B) 4NF 存在非平凡的多值依賴CT，且C不是候選碼用投影分解法把Teaching分解為如下兩個關(guān)系模式 CT(課程C,教師T) 4NF CB(課程C,參考書B) 4NF CT， CB是平凡多值依賴只考慮函數(shù)依賴，BCNF是關(guān)系模式規(guī)范化的最高程度考慮多值依賴，4NF是關(guān)系模式規(guī)范化的最高程度462022/7/18規(guī)范化小結(jié)關(guān)系數(shù)據(jù)庫的規(guī)范化理論是數(shù)據(jù)庫邏輯設(shè)計的工具。一個關(guān)系只要其分量都是不可分的數(shù)據(jù)項，它就是規(guī)范化的關(guān)系，但這只是最基本的規(guī)范化。規(guī)范化程度可以有

34、多個不同的級別,規(guī)范化程度過低的關(guān)系不一定能夠很好地描述現(xiàn)實世界，可能存在插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問題一個低一級范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換為若干個高一級范式的關(guān)系模式集合，這種過程就叫關(guān)系模式的規(guī)范化472022/7/18規(guī)范化小結(jié)關(guān)系模式規(guī)范化的基本步驟 1NF 消除非主屬性對候選鍵的部分函數(shù)依賴消除決定屬性 2NF集非碼的非平 消除非主屬性對候選鍵的傳遞函數(shù)依賴凡函數(shù)依賴 3NF 消除主屬性對候選鍵的部分和傳遞函數(shù)依賴 BCNF 消除非平凡且非函數(shù)依賴的多值依賴 4NF482022/7/18規(guī)范化的基本思想所謂規(guī)范化實質(zhì)上是概念的單一化消除不合適的數(shù)據(jù)依賴,使模式

35、中的各關(guān)系模式達(dá)到某種程度的“分離”采用“一事一地”的模式設(shè)計原則,讓一個關(guān)系描述一個概念、一個實體或者實體間的一種聯(lián)系。若多于一個概念就把它“分離”出去上面的規(guī)范化步驟可以在其中任何一步終止不能說規(guī)范化程度越高的關(guān)系模式就越好在設(shè)計數(shù)據(jù)庫模式結(jié)構(gòu)時，必須對實際情況和用戶需求作進(jìn)一步分析，確定合適的的模式規(guī)范化是范式的升高，而連接的本質(zhì)是范式的降低。492022/7/18第10章 關(guān)系數(shù)據(jù)庫設(shè)計理論10.1 關(guān)系模型的存儲異常10.2 函數(shù)依賴10.5 關(guān)系模式的規(guī)范化10.6 多值依賴和4NF10.3 函數(shù)依賴公理10.4 模式分解10.8 小結(jié)502022/7/1810.2.1 函數(shù)依賴的

36、定義(回顧)一、函數(shù)依賴二、平凡函數(shù)依賴與非平凡函數(shù)依賴三、完全函數(shù)依賴與部分函數(shù)依賴四、傳遞函數(shù)依賴512022/7/1810.2.2 函數(shù)依賴的蘊(yùn)涵性一個關(guān)系模式R上的任一關(guān)系r(R)，在任意給定的時刻都有它所滿足的一組函數(shù)依賴集F。若關(guān)系模式R上的任一關(guān)系都能滿足一個確定的函數(shù)依賴集F，則稱F為R滿足的函數(shù)依賴集 對于給定的一組函數(shù)依賴，需要判斷另外一些函數(shù)依賴是否成立。例如,已知關(guān)系模式R上的函數(shù)依賴集為F, F中有函數(shù)依賴XY，XZ，問XYZ是否成立。這是函數(shù)依賴的邏輯蘊(yùn)涵所要研究的問題定義10.5 設(shè)函數(shù)依賴集F和關(guān)系模式R(U)，屬性集X,YU，關(guān)系模式R滿足F 。如果關(guān)系模式R

37、滿足FD XY，則稱F邏輯蘊(yùn)涵FD XY，或稱XY邏輯蘊(yùn)涵于F。記為 F |= XY。 522022/7/1810.2.2 函數(shù)依賴的蘊(yùn)涵性定義10.6 設(shè)函數(shù)依賴集F，所有被F邏輯蘊(yùn)涵的函數(shù)依賴稱為F的閉包，記為F+。F+ 可表示為：F+ = XY| 所有F 蘊(yùn)涵的FD XY 例: F=ABC, CB是R(A, B, C)上的一組函數(shù)依賴F+ =AA，ABA，ACA，ABCA， BB，ABB，BCB，ABCB， CC，ACC，BCC，ABCC， ABAB，ABCAB， ACAC，ABCAC， BCBC，ABCBC， ABCABC， ABC，ABAC，ABBC，ABABC， CB，CBC，AC

38、B，ACAB，ACABC 532022/7/1810.2.2 函數(shù)依賴的蘊(yùn)涵性定義10.7 設(shè)關(guān)系模式R（U，F(xiàn)），U是R的屬性全集，F(xiàn)是R的函數(shù)依賴集，X是U的子集。如果滿足條件：(1) XU F+；(2) 不存在XX且XU F+成立。則稱X為模式R的一個候選鍵。要確定關(guān)系模式的關(guān)鍵字,需要確定模式中屬性間的依賴關(guān)系 為了從一組函數(shù)依賴求得蘊(yùn)涵的函數(shù)依賴，例如已知函數(shù)依賴集F，求FD XY是否為F所蘊(yùn)涵，就需要一套推理規(guī)則，這組推理規(guī)則是1974年首先由Armstrong提出來的。542022/7/1810.3.1 Armstrong公理函數(shù)依賴的公理系統(tǒng)是模式分解算法的理論基礎(chǔ)， Arms

39、trong公理 設(shè)關(guān)系模式R(U，F(xiàn))，并且X、Y、Z和W是U的子集A1 自反律(Reflexivity)若YXU, 則 F |= XY；A2 增廣律(Augmentation) 若XY且ZU，則 F |= XZYZ；A3 傳遞律(Transitivity)若XY, YZ，則 F |= XZ.552022/7/1810.3.1 Armstrong公理證明：自反律(Reflexivity)若YXU, 則 F|=XY；(1) 若t1X=t2X，則X的任意子集在t1、t2上的屬性值相同， 因YX，即有t1Y = t2Y。 根據(jù)函數(shù)依賴的定義，XY成立 。則 F|=XY在一個關(guān)系中，兩個元組不可能在屬

40、性集X上的值相同、而在X的子集Y上的值不同。所以，公理A1是平凡的。 562022/7/1810.3.1 Armstrong公理證明：增廣律(Augmentation) 若XY且ZU，則 F |= XZYZ(2) 設(shè)t1XZ=t2XZ，則有t1Xt1Z=t2Xt2Z，則t1X=t2X，t1Z=t2Z由已知條件XY可知，t1Y=t2Y。因此，有t1YZ=t1Yt1Z=t2Yt2Z=t2YZ根據(jù)函數(shù)依賴的定義，若t1XZ=t2XZ，有t1YZ=t2YZ時，XZYZ成立增廣律表明，在一個函數(shù)依賴的左部增加R的屬性，所得函數(shù)依賴亦成立。公理A2還可以寫為：若XY且WZU，則 F|=XZYW。 5720

41、22/7/1810.3.1 Armstrong公理證明：傳遞律(Transitivity) 若XY, YZ，則 F|=XZ ；(3) 已知XY，則t1X=t2X時，有t1Y=t2Y。又已知YZ，則t1Y=t2Y時, 有t1Z=t2Z。顯然，XZ 成立 582022/7/18導(dǎo)出推論 根據(jù)A1，A2，A3這三條推理規(guī)則可以得到下面三條很有用的推論： 合成規(guī)則由XY, XZ, 則XYZ （A2， A3）分解規(guī)則由XY及 ZY,則XZ （A1， A3） 偽傳遞規(guī)則由XY, YZW,則XZW （A2， A3） Al. 自反律若Y X U,則X Y為F所蘊(yùn)含 A2. 增廣律若XY為F所蘊(yùn)含，且Z U，則

42、XZYZ為F所蘊(yùn)含。 A3. 傳遞律若XY及YZ為F所蘊(yùn)含，則XZ為F所蘊(yùn)含。592022/7/18導(dǎo)出推論 合成規(guī)則由XY,XZ,則XYZ （A2， A3）證明： 若XY,由公理A2， 有XXXY。 若XZ,同理有XYYZ 由公理A3，有XXYZ， 即XYZ。 Al. 自反律若Y X U,則X Y為F所蘊(yùn)含 A2. 增廣律若XY為F所蘊(yùn)含，且Z U，則XZYZ為F所蘊(yùn)含。 A3. 傳遞律若XY及YZ為F所蘊(yùn)含，則XZ為F所蘊(yùn)含。602022/7/18導(dǎo)出推論分解規(guī)則由XY及 ZY,則XZ （A1， A3）證明：若ZY， 由公理A1, 有YZ， 又已知XY， 由公理A3，XZ成立 Al. 自反

43、律若Y X U,則X Y為F所蘊(yùn)含 A2. 增廣律若XY為F所蘊(yùn)含，且Z U，則XZYZ為F所蘊(yùn)含。 A3. 傳遞律若XY及YZ為F所蘊(yùn)含，則XZ為F所蘊(yùn)含。612022/7/18導(dǎo)出推論 偽傳遞規(guī)則由XY, YZW,則XZW （A2， A3）證明： 若XY， 由公理A2有XZYZ， 又有YZW， 根據(jù)公理A3， XZW成立。 Al. 自反律若Y X U,則X Y為F所蘊(yùn)含 A2. 增廣律若XY為F所蘊(yùn)含，且Z U，則XZYZ為F所蘊(yùn)含。 A3. 傳遞律若XY及YZ為F所蘊(yùn)含，則XZ為F所蘊(yùn)含。622022/7/18導(dǎo)出推論 根據(jù)A1，A2，A3可以得到下面三條推論： 合成規(guī)則 由XY,XZ,

44、則XYZ 分解規(guī)則 由XY及 ZY,則XZ 偽傳遞規(guī)則 由XY, YZW,則XZW根據(jù)合成規(guī)則和分解規(guī)則，可得 XA1 A2Ak 成立的充分必要條件是 XAi 成立 （i=l，2，k）。 632022/7/18Armstrong公理用途Armstrong公理系統(tǒng)是一套推理規(guī)則從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴是模式分解算法的理論基礎(chǔ)求給定關(guān)系模式的關(guān)鍵字642022/7/18Armstrong公理完備性Armstrong公理是正確的、完備的?正確性 利用該公理系統(tǒng)，如果能從函數(shù)依賴集F推出FD XY成立，則F蘊(yùn)涵 XY完備性用公理可以從已知的一組函數(shù)依賴F推出它所蘊(yùn)涵的所有函數(shù)依賴 。要說明公理

45、的完備性，可以對已知函數(shù)依賴集F求F+。如果可以用公理推導(dǎo)出F+中所有的函數(shù)依賴,則可以證明公理是完備的。由F=XA1, XAn出發(fā)可以推導(dǎo)出2n個不同的函數(shù)依賴。該問題屬于NP完全問題。由F求F+ 是行不通的可以用窮舉法得到答案，計算的時間隨問題的復(fù)雜程度成指數(shù)的增長，很快便變得不可計算了652022/7/18屬性閉包定義10.8 設(shè)關(guān)系模式R(U, F)，U=A1,A2,An，XU。所有用公理推出的函數(shù)依賴XAi中Ai的屬性集合稱為屬性集X關(guān)于函數(shù)依賴集F的閉包，記為XF+。 XF+=Ai | 所有用公理由F推出的XAi。 顯然，由自反律知道XXF+ 。例如，設(shè)R(A, B, D, E,

46、H)， R上的函數(shù)依賴集F=AD，ABDE，EH若X=A，(A)F+ =AD。 若X=AB，(AB)F+ =ABDEH。有了屬性閉包的概念，就可以從XF+中看出某個函數(shù)依賴XY是否能夠用公理從F中推出。662022/7/18屬性閉包定理10.1 設(shè)關(guān)系模式R(U, F), X,YU。能夠由Armstrong公理從F導(dǎo)出XY成立的充要條件是Y XF+ 證明：設(shè)Y= A1,A2,Ak ，AiU (i=1,2, ,k)。先證充分性。設(shè)Y XF+ ，由XF+的定義知，XAi (i=1,2, , k)是由Armstrong公理從F中導(dǎo)出的，根據(jù)合成規(guī)則，XY成立。證必要性。設(shè)XY是用Armstrong公

47、理從F推導(dǎo)出的。根據(jù)分解規(guī)則，有XAi (i=1,2, ,k)成立，由XF+的定義知， Ai XF+ (i=1,2, ,k)，即Y XF+ 。 證畢。用途： 將判定XY是否能由F根據(jù)Armstrong公理導(dǎo)出的問題，轉(zhuǎn)化為求出XF+ ，判定Y是否為XF+的子集的問題672022/7/18Armstrong公理完備性的思路證明完備性：用公理可以從已知的一組函數(shù)依賴F推出它所蘊(yùn)涵的所有函數(shù)依賴(1) 對已知函數(shù)依賴集F求F+。如果可以用公理推導(dǎo)出F+中所有的函數(shù)依賴,則可以證明公理是完備的定義10.6 設(shè)函數(shù)依賴集F，所有被F邏輯蘊(yùn)涵的函數(shù)依賴稱為F的閉包，記為F+。F+ 可表示為：F+ = XY

48、| 所有F 蘊(yùn)涵的FD XY(2) 有了屬性閉包的概念，就可以從X+中看出某個函數(shù)依賴XY是否能夠用公理從F中推出。將判定XY是否能由F根據(jù)Armstrong公理導(dǎo)出的問題，轉(zhuǎn)化為求出XF+, 判定Y是否為XF+的子集的問題682022/7/18Armstrong公理完備性定理10.2 Armstrong公理是正確的，完備的 正確性：由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來的每一個函數(shù)依賴一定在F+中（ Armstrong公理的正確性已在前面證明）完備性：F+中的每一個函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來只需證明逆否命題: 若函數(shù)依賴XY不能由F從Armstrong公

49、理導(dǎo)出，那么它必然不為F所蘊(yùn)含思路：給出關(guān)系r(R)，如果能夠證明以下兩點(diǎn)則完備性得證 存在r(R)滿足F中的所有函數(shù)依賴 不能用Armstrong公理推導(dǎo)出來的XY , 在r(R)上不成立692022/7/18Armstrong公理完備性證明證明：先證明 r(R)滿足F中的所有函數(shù)依賴 構(gòu)造一張二維表r，它由下列兩個元組構(gòu)成，可以證明r必是R(U, F)的一個關(guān)系，即滿足F中的所有函數(shù)依賴 。 設(shè)FD WZF，W在r中有兩種情況：(1) W XF+ 。根據(jù)屬性閉包的定義，有XW，又因WZ，由函數(shù)依賴的傳遞性得FD XZ成立。根據(jù)屬性閉包的定義，有Z XF+ 。由r的構(gòu)造知WZ在r上成立。(2

50、) W XF+ 。則在r中有tWtW，因此，WZ在r上總是成立的。由(1)和(2)知，對F中的任意函數(shù)依賴在r上都是成立的,即r滿足F。 XF+U- XF+A1A2.An111000111111702022/7/18Armstrong公理完備性證明：(續(xù)) 再證明不能用Armstrong公理推導(dǎo)出來的XY , 在r(R)上不成立 因為XY不能由F從公理推出,由定理10.1知,Y XF+tX=tX，而Y XF+ ，則tYtY，即r不滿足XY。證畢 定理10.1 設(shè)關(guān)系模式R(U, F), X,YU。能夠由Armstrong公理從F導(dǎo)出XY成立的充要條件是YXF+ XF+U- XF+A1A2.An

51、111000111111712022/7/18Armstrong公理完備性說明“蘊(yùn)含” 和 “導(dǎo)出”的等價“通過F推導(dǎo)出的函數(shù)依賴”“F所蘊(yùn)涵的函數(shù)依賴”這兩種說法是等價的 屬性閉包XF+和函數(shù)依賴集的閉包F+的等價 XF+= Ai | 所有F|= XAi。 F+ = XY| 用公理從F導(dǎo)出的所有FD XY對于一個給定的關(guān)系模式R以及R的函數(shù)依賴集F，經(jīng)常需要判斷某一個函數(shù)依賴XY是否被F所邏輯蘊(yùn)涵判斷XY是否是F+ 中的成員 F+很大 求XF+然后判斷Y X+是否成立 計算XF+不困難 722022/7/18求屬性閉包的算法算法10.1 計算屬性集X關(guān)于F的閉包XF+ 輸入:模式R的屬性全集

52、U,U上的函數(shù)依賴集F,屬性集X輸出：屬性集X的閉包XF+方法：計算X(i)（i=0, 1, ）(1) 初值 X(0) = X，i=0；(2) X(i+1) = X(i) Z；其中，屬性集Z=A | 存在VWF，VX(i)且AW而A X(i)(3) 判斷X(i+1) = X(i)或X(i+1) =U是否成立，若成立轉(zhuǎn)(5)(4) i=i+1，轉(zhuǎn)(2)；輸出XF+的結(jié)果X(i+1)只要F中的函數(shù)依賴的左部屬性包含在中間結(jié)果X(i)中，就可以將沒有出現(xiàn)在X(i)中的右部屬性A并入X(i)中。XA顯然成立732022/7/18求屬性閉包的算法【例10-1】設(shè)關(guān)系模式R(U,F), U=A,B,C,D

53、,E,G, F= ABC,BCD,ACDB,DEG,BEC,CEAG,求 (BD)+解：令X=BD (1) 初值 (X)(0)=BD (2) 在F中尋找左部是BD子集的函數(shù)依賴，DEG滿足條件。結(jié)果為：(X)(1)=BDEG。X(0) X(1)。 在F中繼續(xù)尋找左部是BDEG子集的函數(shù)依賴，得 BEC，C不包含在BDEG中，結(jié)果為(X)(2)=BCDEG在F中繼續(xù)尋找左部是BCDEG子集的函數(shù)依賴，得BCD，CEAG。這里僅有右部屬性A是未出現(xiàn)在(X)(2) 中的屬性，結(jié)果為 (X)(3)=ABCDEG。X(3) X(2)，雖然F中還有未考察過的函數(shù)依賴，但X(3) 已包含了R中的所有屬性，結(jié)

54、束。輸出結(jié)果：(BD)+ = ABCDEG 只要F中的函數(shù)依賴的左部屬性包含在中間結(jié)果X(i)中，就可以將沒有出現(xiàn)在X(i)中的右部屬性A并入X(i)中。XA顯然成立742022/7/1810.3.2 函數(shù)依賴集的等價和覆蓋定義10.9 如果G+=F+，就說函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價。函數(shù)依賴集等價的充要條件引理10.1 F+ = G+ 的充分必要條件是F G+ ，同時G F+ 證: 必要性顯然，只證充分性。（1）若FG+ ，則XF+ XG+ 。（2）任取XYF+ 則有 Y XF+ XG+ 。 所以XY (G+)+= G+。即F+ G+。（3）同理可證G+

55、 F+ ，所以F+ = G+。要判定F G+，只須逐一對F中的函數(shù)依賴XY，考察 Y 是否屬于XG+ 就行了。 引理10.1 給出了判斷兩個函數(shù)依賴集等價的可行算法。752022/7/18最小依賴集定義10.10 如果函數(shù)依賴集F滿足下列條件，則稱F為一個最小函數(shù)依賴集 或 最小覆蓋(1) F中的所有函數(shù)依賴其右部都是單屬性 (2)對F中的任一函數(shù)依賴XA, FXA與F不等價(3)對F中的任一函數(shù)依賴XA，F(xiàn)XAZA 與F不等價。其中，Z是X的真子集762022/7/18最小依賴集例 對于關(guān)系模式S，其中： U= Sno，Sdept，Mname，Cno，Grade ， F= SnoSdept，

56、SdeptMname， （Sno，Cno）Grade 設(shè)F=Sno Sdept ，SnoMname， Sdept Mname ，(Sno ， Cno) Grade ， (SNO，Sdept)SdeptF是最小覆蓋，而F 不是。因為：F - SnoMname與F 等價 F - (Sno，Sdept)Sdept也與F 等價 F - (Sno，Sdept)Sdept SnoSdept也與F 等價772022/7/18最小依賴集定理10.3 每一個函數(shù)依賴集F均等價于一個最小 函數(shù)依賴集Fm證: 構(gòu)造性證明，找出F的一個最小依賴集。(1)逐一檢查F中各函數(shù)依賴FDi：XA，令G=F-XA，若AXG+，

57、 則從F中去掉此函數(shù)依賴由于F與G =F-XA等價的充要條件是AXG+ 因此F變換前后是等價的。(2) 逐一檢查F中各函數(shù)依賴FDi：XY， 若Y=A1A2 Ak，k 2， 則用 XAj | j=1，2， k 來取代XY。782022/7/18最小依賴集(3)逐一取出F中各函數(shù)依賴FDi：XA， 設(shè)X=B1B2Bm， 逐一考查Bi (i=l，2，m)， 若A (X-Bi )F+ ， 則以X-Bi 取代X。由于F與F-XAZA等價的充要條件是AZF+ ，其中Z=X-Bi 因此F變換前后是等價的。由定義，最后剩下的F就一定是極小依賴集。 過程的每一步都保證了改造前后的兩個函數(shù)依賴集等價,因此剩下的

58、F與原來的F等價。 證畢792022/7/18極小化過程F的最小函數(shù)依賴集Fm不一定是唯一的。它與對各函數(shù)依賴集FDi中X各屬性的處置順序有關(guān)若改造后的F與原來的F相同，說明F本身就是一個最小依賴集定理10.3的證明過程 是求F最小依賴集的過程，也可以驗證F是否為最小依賴集802022/7/18極小化過程例 由關(guān)系模式R(U, F), 其中UA,B,C,D,E， F=ABC，BD，CE，ECB，ACB, 求Fm 解：(1)將F中的所有函數(shù)依賴轉(zhuǎn)換為右部為單屬性的。本題目F中函數(shù)依賴右部都僅含有一個屬性，得Fm = F(2)分別去掉一個函數(shù)依賴XA后求關(guān)于X的閉包，去掉多余的函數(shù)依賴令F=F-A

59、BC,求AB的閉包，得ABF+ =ABD,不包含C，故ABC不能去掉令F=F-BD,求B的閉包，得BF+ =B,不包含D，故BD不能去掉令F=F-CE,求C的閉包，得CF+ =C,不包含E，故CE不能去掉812022/7/18極小化過程例 由關(guān)系模式R(U, F), 其中UA,B,C,D,E， F=ABC，BD，CE，ECB，ACB, 求Fm 解：(2)分別去掉一個函數(shù)依賴XA后求關(guān)于X的閉包,去掉多余的函數(shù)依賴（續(xù)）令F=F-ECB,求EC的閉包，得ECF+ =EC, 不包含B，故ECB不能去掉令F=F-ACB,求AC的閉包,得ACF+ =ABCDE, 包含B，故ACB可以去掉則在F中去掉函

60、數(shù)依賴ACB，得Fm ABC，BD，CE，ECB,822022/7/18極小化過程例 由關(guān)系模式R(U, F), 其中UA,B,C,D,E， F=ABC，BD，CE，ECB，ACB, 求Fm 解: (續(xù))(3)去掉函數(shù)依賴左部多余的屬性 檢查形如B1B2BmA的函數(shù)依賴,若A (X-Bi )F+ , 則以X-Bi 取代X檢查函數(shù)依賴ABC令BiA，BF+=B,D: ABC中A不能去掉令BiB，AF+=A: ABC中B不能去掉檢查函數(shù)依賴ECB令BiE,CF+=CEB: ECB中E可以去掉(包含B)令BiC，EF+=E: ECB中C不能去掉得Fm ABC，BD，CE，CB, 解畢832022/7