第六章關系數(shù)據(jù)庫設計理論(2014)

1、第六章 關系數(shù)據(jù)庫設計理論12問題的提出基本概念34規(guī)范化函數(shù)依賴的公理系統(tǒng)5模式分解6.1 6.1 問題的提出問題的提出v 針對一個具體問題，設計一個好的關系數(shù)據(jù)庫系針對一個具體問題，設計一個好的關系數(shù)據(jù)庫系統(tǒng)，關鍵是要構造一個適合于它的數(shù)據(jù)模式（統(tǒng)，關鍵是要構造一個適合于它的數(shù)據(jù)模式（數(shù)據(jù)數(shù)據(jù)庫邏輯設計問題庫邏輯設計問題）v 數(shù)據(jù)庫邏輯設計主要解決的問題：數(shù)據(jù)庫邏輯設計主要解決的問題：n 應該構造幾個關系模式應該構造幾個關系模式n 每個關系模式包括哪些屬性每個關系模式包括哪些屬性v 數(shù)據(jù)庫邏輯設計工具數(shù)據(jù)庫邏輯設計工具關系數(shù)據(jù)庫的關系數(shù)據(jù)庫的規(guī)范化理論規(guī)范化理論6.1 6.1 問題的提出問

2、題的提出例：描述例：描述電力設備存放管理的數(shù)據(jù)庫電力設備存放管理的數(shù)據(jù)庫數(shù)據(jù)庫：數(shù)據(jù)庫：WAE(WAE(倉庫號，所在區(qū)域，區(qū)域主管，設備號，數(shù)量倉庫號，所在區(qū)域，區(qū)域主管，設備號，數(shù)量) )語義語義： 一個區(qū)域有多個倉庫，一個倉庫只能屬于一個區(qū)域；一個區(qū)域有多個倉庫，一個倉庫只能屬于一個區(qū)域； 一個區(qū)域只有一個區(qū)域主管；一個區(qū)域只有一個區(qū)域主管； 一個倉庫可以存放多種設備，每種設備可以存放在一個倉庫可以存放多種設備，每種設備可以存放在多個倉庫中；多個倉庫中；每個倉庫的每種設備都有一個庫存數(shù)量。每個倉庫的每種設備都有一個庫存數(shù)量。6.1 6.1 問題的提出問題的提出 數(shù)據(jù)冗余太大數(shù)據(jù)冗余太大浪費

3、大量的存儲空間浪費大量的存儲空間 更新異常更新異常更新代價大，可能導致數(shù)據(jù)不一致更新代價大，可能導致數(shù)據(jù)不一致 插入異常插入異常該插的數(shù)據(jù)插不進去該插的數(shù)據(jù)插不進去 刪除異常刪除異常不該刪除的數(shù)據(jù)不得不刪，造成某些數(shù)據(jù)丟失不該刪除的數(shù)據(jù)不得不刪，造成某些數(shù)據(jù)丟失存在的問題：存在的問題：6.1 6.1 問題的提出問題的提出結論：結論： WAE關系模式不是一個好的模式。關系模式不是一個好的模式。 “好好”的模式：不會發(fā)生插入異常、刪除異常、的模式：不會發(fā)生插入異常、刪除異常、更新異常，數(shù)據(jù)冗余應盡可能少。更新異常，數(shù)據(jù)冗余應盡可能少。原因：由存在于模式中的某些原因：由存在于模式中的某些數(shù)據(jù)依賴數(shù)據(jù)

4、依賴引起的引起的解決方法：通過解決方法：通過分解關系模式分解關系模式來消除其中不合適的來消除其中不合適的數(shù)據(jù)依賴。數(shù)據(jù)依賴。6.1 6.1 問題的提出問題的提出 分解成三個關系模式即可：分解成三個關系模式即可： W(W(倉庫號，所在區(qū)域倉庫號，所在區(qū)域) )； A( A(區(qū)域，區(qū)域主管區(qū)域，區(qū)域主管) )； WE( WE(倉庫號，設備號，數(shù)量倉庫號，設備號，數(shù)量) )6.2 6.2 基本概念基本概念 規(guī)范化理論規(guī)范化理論正是用來改造關系模式，正是用來改造關系模式，通過分解關系模式來消除其中不合適的數(shù)通過分解關系模式來消除其中不合適的數(shù)據(jù)依賴，以解決插入異常、刪除異常、更據(jù)依賴，以解決插入異常、

5、刪除異常、更新異常和數(shù)據(jù)冗余等問題。新異常和數(shù)據(jù)冗余等問題。6.2.1 6.2.1 函數(shù)依賴函數(shù)依賴定義定義6.16.1 設設R(U)R(U)是一個屬性集是一個屬性集U U上的關系模式，上的關系模式，X X和和Y Y是是U U的子集。若對于的子集。若對于R(U)R(U)的任意一個可能的關系的任意一個可能的關系r r，對對 t t1,1,t2t2 r r，若，若t1X=t2Xt1X=t2X，則，則t1Y=t2Yt1Y=t2Y則稱則稱X X函數(shù)決定函數(shù)決定Y Y或或Y Y函數(shù)依賴函數(shù)依賴X X，記作，記作XYXY。 如：如：倉庫號倉庫號 所在區(qū)域所在區(qū)域 所在區(qū)域所在區(qū)域 區(qū)域主管區(qū)域主管 （倉庫

6、號，設備號）（倉庫號，設備號） 數(shù)量數(shù)量若若Y不函數(shù)依賴于不函數(shù)依賴于X, 則記為則記為X Y若若XY，并且，并且YX, 則記為則記為XY若若XY，則稱，則稱X為這個函數(shù)依賴的決定因素為這個函數(shù)依賴的決定因素。6.2.1 6.2.1 函數(shù)依賴函數(shù)依賴1. 1. 函數(shù)依賴是函數(shù)依賴是語義范疇語義范疇的概念，只能根據(jù)數(shù)據(jù)的語的概念，只能根據(jù)數(shù)據(jù)的語義來確定函數(shù)依賴。義來確定函數(shù)依賴。 例：例：“區(qū)域主管區(qū)域主管所在區(qū)域所在區(qū)域” ” 只有在不允許有同只有在不允許有同名人的條件下成立名人的條件下成立2. 2. 函數(shù)依賴不是指關系模式函數(shù)依賴不是指關系模式R R的某個或某些關系實的某個或某些關系實例滿

7、足的約束條件，而是指例滿足的約束條件，而是指R R的所有關系實例均要的所有關系實例均要滿足的約束條件。滿足的約束條件。3.3.函數(shù)依賴存在的時間無關性函數(shù)依賴存在的時間無關性。說明說明:6.2.1 6.2.1 函數(shù)依賴函數(shù)依賴 函數(shù)依賴與屬性間的聯(lián)系類型有關函數(shù)依賴與屬性間的聯(lián)系類型有關(1) (1) 若屬性若屬性X X和和Y Y之間有之間有“一對一一對一”的聯(lián)系的聯(lián)系 則：則：X Y,Y X,X YX Y,Y X,X Y(2) (2) 若屬性若屬性X X和和Y Y之間有之間有“多對一多對一”的聯(lián)系的聯(lián)系 則：則：X Y,X Y,但但Y X Y X (3)(3)若屬性若屬性X X和和Y Y之間

8、有之間有“多對多多對多”的聯(lián)系的聯(lián)系 則：則：X X與與Y Y之間不存在任何函數(shù)依賴之間不存在任何函數(shù)依賴注：當確定函數(shù)依賴關系時注：當確定函數(shù)依賴關系時, ,可從屬性間的聯(lián)系入手可從屬性間的聯(lián)系入手6.2.1 6.2.1 函數(shù)依賴函數(shù)依賴 平凡函數(shù)依賴與非平凡函數(shù)依賴平凡函數(shù)依賴與非平凡函數(shù)依賴定義定義6.2 在關系模式在關系模式R(U)R(U)中，對于中，對于U U的子集的子集X X和和Y Y：若若XYXY，但，但Y Y X X，則稱，則稱XYXY是是非平凡函數(shù)依賴非平凡函數(shù)依賴. .若若XYXY，但，但Y Y X X，則稱，則稱XYXY是是平凡函數(shù)依賴平凡函數(shù)依賴. .例：在關系例：在關

9、系WAEWAE中，中， 非平凡函數(shù)依賴：非平凡函數(shù)依賴：（倉庫號，設備號）（倉庫號，設備號） 數(shù)量數(shù)量 平凡函數(shù)依賴：平凡函數(shù)依賴： （倉庫號，設備號）（倉庫號，設備號）倉庫號倉庫號 （倉庫號，設備號）（倉庫號，設備號）設備號設備號注：對任一關系模式，平凡函數(shù)依賴必然存在，則一般討論非平凡函注：對任一關系模式，平凡函數(shù)依賴必然存在，則一般討論非平凡函數(shù)依賴。數(shù)依賴。6.2.1 函數(shù)依賴函數(shù)依賴 完全函數(shù)依賴與部分函數(shù)依賴完全函數(shù)依賴與部分函數(shù)依賴定義定義6.3 在在R(U)中，如果中，如果XY，并且對于，并且對于X的任何的任何一個真子集一個真子集X ，都有，都有X Y, 則稱則稱Y對對X完全函

10、數(shù)依完全函數(shù)依賴，記作賴，記作X Y。 若若XY，但，但Y不完全函數(shù)依賴于不完全函數(shù)依賴于X，則稱，則稱Y對對X部分函數(shù)依賴，記作部分函數(shù)依賴，記作X P Y。例：在關系例：在關系WAE中，中， 由于：由于： （倉庫號，設備號）（倉庫號，設備號） 數(shù)量數(shù)量, 但倉庫號但倉庫號數(shù)量數(shù)量, 設設備號備號 數(shù)量數(shù)量 因此：因此： （倉庫號，設備號）（倉庫號，設備號）數(shù)量數(shù)量6.2.1 函數(shù)依賴函數(shù)依賴 傳遞函數(shù)依賴與直接函數(shù)依賴傳遞函數(shù)依賴與直接函數(shù)依賴 如果如果YX， 即即XY，則，則Z對對X直接函數(shù)依賴。直接函數(shù)依賴。例：在關系例：在關系waewae中有：中有：定義定義6.4 在在R(U)中，如

11、果中，如果XY，YZ，且，且Y X，YX，則稱，則稱Z對對X傳遞函數(shù)依賴傳遞函數(shù)依賴,記作記作X t Z 。倉庫號倉庫號所在區(qū)域，所在區(qū)域所在區(qū)域，所在區(qū)域區(qū)域主管區(qū)域主管可可得到傳遞函數(shù)依賴：倉庫號得到傳遞函數(shù)依賴：倉庫號 t 區(qū)域主管區(qū)域主管6.2.2 碼碼定義定義6.5 設設K為為R中的屬性或?qū)傩越M合。若中的屬性或?qū)傩越M合。若K F U，則，則K稱為稱為R的一個的一個侯選碼侯選碼。 若關系模式若關系模式R有多個候選碼，則選定其中的一有多個候選碼，則選定其中的一個做為個做為主碼主碼。 主屬性：主屬性：包含在任何一個候選碼中的屬性包含在任何一個候選碼中的屬性 非主屬性：非主屬性：不包含在任何

12、一個碼中的屬性不包含在任何一個碼中的屬性 全碼：全碼：整個屬性組全是碼整個屬性組全是碼6.2.2 碼碼定義定義6.56.5 關系模式關系模式R R中屬性或?qū)傩越M中屬性或?qū)傩越MX X并非并非R R的碼，的碼，但但X X是另一個關系模式的碼，則稱是另一個關系模式的碼，則稱X X是是R R的外部碼，的外部碼，也稱也稱外碼外碼。注：主碼和外碼一起提供了表示關系間聯(lián)系的手段。注：主碼和外碼一起提供了表示關系間聯(lián)系的手段。例：在關系例：在關系SC(Sno, Cno, Grade)中，中， 由于：由于：Sno不是不是SC的碼，但是另一個關系的碼，但是另一個關系S的碼的碼 因此：因此：Sno是是SC的外碼的外

13、碼6.3 規(guī)范化規(guī)范化 范式是對關系數(shù)據(jù)庫的規(guī)范化過程中為范式是對關系數(shù)據(jù)庫的規(guī)范化過程中為不同不同程度的規(guī)范化要求程度的規(guī)范化要求設立的不同標準。設立的不同標準。 范式是符合某一種級別的關系模式的集合。范式是符合某一種級別的關系模式的集合。 范式的種類：范式的種類： 第一范式第一范式(1NF) 第二范式第二范式(2NF) 第三范式第三范式(3NF) BC范式范式(BCNF) 第四范式第四范式(4NF) 第五范式第五范式(5NF)6.3 規(guī)范化規(guī)范化 各種范式之間存在聯(lián)系：各種范式之間存在聯(lián)系：5NF 4NF BCNF 3NF 2NF 1NF 某一關系模式某一關系模式R為第為第n范式，可簡記為

14、范式，可簡記為RnNF。 通過模式分解將一個低級范式的關系模式轉(zhuǎn)換為若通過模式分解將一個低級范式的關系模式轉(zhuǎn)換為若干個高級范式的關系模式的過程稱作干個高級范式的關系模式的過程稱作規(guī)范化規(guī)范化。 6.3.1 第一范式（第一范式（1NF） 定義定義6.7 滿足最低要求的范式。滿足最低要求的范式。 如果一個關系模式如果一個關系模式R的所有屬性都是不可分的所有屬性都是不可分的基本數(shù)據(jù)項，則的基本數(shù)據(jù)項，則R1NF。 第一范式是對關系模式的最起碼要求。第一范式是對關系模式的最起碼要求。 不滿足第一范式的數(shù)據(jù)庫模式不能稱為關系數(shù)據(jù)庫。不滿足第一范式的數(shù)據(jù)庫模式不能稱為關系數(shù)據(jù)庫。 但滿足第一范式的關系模式

15、并不一定是一個好的關系模式。但滿足第一范式的關系模式并不一定是一個好的關系模式。6.3.2 第二范式（第二范式（2NF）定義定義6.8 若關系模式若關系模式R1NF，并且每一個非主屬，并且每一個非主屬性都完全函數(shù)依賴于性都完全函數(shù)依賴于R的碼，則的碼，則R2NF。即：即：消除非主屬性對碼的部分依賴消除非主屬性對碼的部分依賴 如果一個數(shù)據(jù)庫模式中的每個關系模式都是第二范式的，如果一個數(shù)據(jù)庫模式中的每個關系模式都是第二范式的，則稱此數(shù)據(jù)庫模式屬于第二范式的數(shù)據(jù)庫模式。則稱此數(shù)據(jù)庫模式屬于第二范式的數(shù)據(jù)庫模式。 從從1NF1NF中消除非主屬性對候選碼的部分函數(shù)依賴中消除非主屬性對候選碼的部分函數(shù)依賴

16、, ,則獲得則獲得2NF2NF。6.3.2 第二范式（第二范式（2NF）例例: 關系模式關系模式WAE中中: WAE(WAE(倉庫號，所在區(qū)域，區(qū)域倉庫號，所在區(qū)域，區(qū)域主管，設備號，數(shù)量主管，設備號，數(shù)量) ) 碼碼： (倉庫號倉庫號, 設備號設備號) 主屬性主屬性:倉庫號倉庫號, 設備號設備號 非主屬性非主屬性: 所在區(qū)域、區(qū)域主管和數(shù)量所在區(qū)域、區(qū)域主管和數(shù)量 函數(shù)依賴：函數(shù)依賴：6.3.2 第二范式（第二范式（2NF）倉庫號倉庫號 設備號設備號數(shù)量數(shù)量 所在區(qū)域所在區(qū)域 區(qū)域主管區(qū)域主管關系關系WAE碼為碼為(倉庫號倉庫號, 設備號設備號)非主屬性所在區(qū)域和區(qū)域主管部分函數(shù)依賴于碼非主

17、屬性所在區(qū)域和區(qū)域主管部分函數(shù)依賴于碼WAE滿足第一范式，但不滿足第二范式。滿足第一范式，但不滿足第二范式。6.3.2 第二范式（第二范式（2NF） 解決方法：將解決方法：將WAE分解為兩個關系模式，消除這些部分函分解為兩個關系模式，消除這些部分函數(shù)依賴：數(shù)依賴： 即：即： WE（倉庫號，設備號，數(shù)量倉庫號，設備號，數(shù)量） WA（倉庫號，所在區(qū)域，區(qū)域主管倉庫號，所在區(qū)域，區(qū)域主管）倉庫號倉庫號設備號設備號數(shù)量數(shù)量關系關系WE關系關系WA倉庫號倉庫號所在區(qū)域所在區(qū)域區(qū)域主管區(qū)域主管WE2NF, WA2NF6.3.2 第二范式（第二范式（2NF）注：注： 采用投影分解法將一個采用投影分解法將一個

18、1NF的關系分解為多個的關系分解為多個2NF的關系，的關系，可以在可以在一定程度上減輕一定程度上減輕原原1NF關系中存在的插入異常、刪關系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復雜等問題。除異常、數(shù)據(jù)冗余度大、修改復雜等問題。 將一個將一個1NF關系分解為多個關系分解為多個2NF的關系，的關系，并不能完全消除并不能完全消除關系模式中的各種異常情況和數(shù)據(jù)冗余。關系模式中的各種異常情況和數(shù)據(jù)冗余。 如：如：(1) (1) 若某個區(qū)域剛剛設立還沒有倉庫，則所在區(qū)域和若某個區(qū)域剛剛設立還沒有倉庫，則所在區(qū)域和區(qū)域主管的值無法插入，造成區(qū)域主管的值無法插入，造成插入異常插入異常。 (2) (2)

19、 有一定的有一定的數(shù)據(jù)冗余數(shù)據(jù)冗余，當多個倉庫處于同一個區(qū)域，當多個倉庫處于同一個區(qū)域時，區(qū)域主管的值被多次存儲。時，區(qū)域主管的值被多次存儲。 (3) (3) 若某區(qū)域要更換區(qū)域主管，則要逐一地修改該區(qū)若某區(qū)域要更換區(qū)域主管，則要逐一地修改該區(qū)域的所有區(qū)域主管記錄，稍有不慎，就有可能漏改某些記域的所有區(qū)域主管記錄，稍有不慎，就有可能漏改某些記錄，造成錄，造成更新異常更新異常。6.3.3 第三范式（第三范式（3NF）如果一個數(shù)據(jù)庫模式中的每個關系模式都是第三范如果一個數(shù)據(jù)庫模式中的每個關系模式都是第三范式的，則稱此數(shù)據(jù)庫模式屬于第三范式的數(shù)據(jù)庫模式的，則稱此數(shù)據(jù)庫模式屬于第三范式的數(shù)據(jù)庫模式。式

20、。從從2NF2NF中消除非主屬性對候選碼的傳遞依賴中消除非主屬性對候選碼的傳遞依賴, ,則獲得則獲得3NF3NF。定義定義6.9 如果關系模式如果關系模式R2NF，且每個非主屬性都不，且每個非主屬性都不傳遞函數(shù)依賴于傳遞函數(shù)依賴于R的候選碼，則稱的候選碼，則稱R屬于第三范式，簡稱屬于第三范式，簡稱3NF，記作，記作R3NF。 即：消除非主屬性對碼的即：消除非主屬性對碼的部分依賴部分依賴和和傳遞依賴傳遞依賴6.3.3 第三范式（第三范式（3NF）例例: WE（倉庫號，設備號，數(shù)量倉庫號，設備號，數(shù)量） WA（倉庫號，所在區(qū)域，區(qū)域主管倉庫號，所在區(qū)域，區(qū)域主管） 函數(shù)依賴：函數(shù)依賴： WE中中：

21、 (倉庫號，設備號倉庫號，設備號) f 數(shù)量數(shù)量 WA中：中：倉庫號倉庫號所在區(qū)域，所在區(qū)域所在區(qū)域，所在區(qū)域區(qū)域主管區(qū)域主管 可可得到傳遞函數(shù)依賴：倉庫號得到傳遞函數(shù)依賴：倉庫號 區(qū)域主管區(qū)域主管 因此：因此： WE 3NF，而，而WA 3NF6.3.3 第三范式（第三范式（3NF） 原因原因:區(qū)域主管傳遞依賴于碼。區(qū)域主管傳遞依賴于碼。 解決方法：將解決方法：將WA分解為兩個關系模式，消除這些分解為兩個關系模式，消除這些傳遞依賴：傳遞依賴： 即：即： W（倉庫號，所在區(qū)域倉庫號，所在區(qū)域） A（所在區(qū)域，區(qū)域主管所在區(qū)域，區(qū)域主管）倉庫號倉庫號所在區(qū)域所在區(qū)域關系關系W關系關系A所在區(qū)域所

22、在區(qū)域區(qū)域主管區(qū)域主管W3NF, A3NF6.3.3 第三范式（第三范式（3NF）注：注： 采用采用投影分解法投影分解法將一個將一個2NF的關系分解為多個的關系分解為多個3NF的的關系，可以在關系，可以在一定程度上減輕一定程度上減輕原原2NF關系中存在的關系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復雜等插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復雜等問題。問題。 將一個將一個2NF關系分解為多個關系分解為多個3NF的關系，的關系，并不能完全并不能完全消除消除關系模式中的各種異常情況和數(shù)據(jù)冗余。表現(xiàn)關系模式中的各種異常情況和數(shù)據(jù)冗余。表現(xiàn)在可能存在主屬性對碼的部分和傳遞依賴。在可能存在主屬性對

23、碼的部分和傳遞依賴。6.3.4 BC范式（范式（BCNF） BCNF范式是第三范式的改進形式，建立在第一范范式是第三范式的改進形式，建立在第一范式的基礎上，消除了主屬性對碼的部分和傳遞依賴。式的基礎上，消除了主屬性對碼的部分和傳遞依賴。定義定義6.10 設關系模式設關系模式R1NF，若對于，若對于R的每個函的每個函數(shù)依賴數(shù)依賴XY，若，若Y不屬于不屬于X，則，則X必含有候選碼，那必含有候選碼，那么么RBCNF。即：每一個決定因素（決定屬性集）都包含碼即：每一個決定因素（決定屬性集）都包含碼6.3.4 BC范式（范式（BCNF）證明：證明：BCNF 3NF反證：若反證：若R BCNF， 但但R

24、3NF，則按，則按3NF定義，定義，一定有非主屬性對碼的傳遞依賴。一定有非主屬性對碼的傳遞依賴。 于是存在：于是存在：R的碼的碼X ，屬性組，屬性組Y，以及非主屬，以及非主屬性性Z（Z Y），使得），使得XY， Y Z，YX成立。成立。 由由YZ，按，按BCNF定義，定義，Y含有碼，則是含有碼，則是YX成成立，這與立，這與YX矛盾。矛盾。 所以：所以：R 3NF。6.3.4 BC范式（范式（BCNF）注意：注意： 若若RBCNF ，則，則R3NF 若若R3NF ，則，則R不一定屬于不一定屬于BCNF若若RBCNF 所有非主屬性對每一個候選碼都是完全函數(shù)依賴；所有非主屬性對每一個候選碼都是完全函

25、數(shù)依賴； 所有主屬性對所有主屬性對每一個不包含它的候選碼每一個不包含它的候選碼都是完全函數(shù)都是完全函數(shù)依賴；依賴； 沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性。沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性。6.3.4 BC范式（范式（BCNF）例例1: Course（Cno, Creidt, Pcno） 函數(shù)依賴函數(shù)依賴： Cno Credit, Cno Pcno 即：無部分依賴和傳遞依賴，且即：無部分依賴和傳遞依賴，且Cno是唯一決定因素是唯一決定因素 因此：因此： Course 3NF，且，且Course BCNF 碼碼： Cno 即為主屬性，決定因素即為主屬性，決定因素6.3.4 BC

26、范式（范式（BCNF）例例2：在關系模式：在關系模式SCP（S, C, P）中，）中，S表示學生，表示學生，C表示課程，表示課程， P表示名次。表示名次。說明：說明： 每一個學生選修每一門課程都有一個固定的名每一個學生選修每一門課程都有一個固定的名次：次： 每一門課程中每一名次只對應一個學生（假設每一門課程中每一名次只對應一個學生（假設沒有相同名次的學生）沒有相同名次的學生） ：(S，C)P(C，P)S6.3.4 BC范式（范式（BCNF）SCPCPS關系關系SCP 候選碼候選碼： (S，C) 和和(C，P)即：即：S，C和和P都是主屬性都是主屬性 決定因素決定因素： (S，C)和和(C，P)

27、 結論結論：SCPBCNF 只有只有(S，C)和和(C，P)決定因素且包含候選碼，決定因素且包含候選碼，無其他決定因素無其他決定因素SCP3NF S、C、P都是主屬性都是主屬性無部分依賴和傳遞依賴無部分依賴和傳遞依賴6.3.4 BC范式（范式（BCNF）例例3：在關系模式：在關系模式WES(倉庫號倉庫號,設備號設備號,職工號職工號)中。中。說明：說明：一個倉庫可以有多個職工一個倉庫可以有多個職工;一個職工僅在一個倉庫工作一個職工僅在一個倉庫工作;1.每個倉庫一種設備僅由一名職工保管每個倉庫一種設備僅由一名職工保管,但每名職工可以保但每名職工可以保管多種設備管多種設備. 問問:該關系的碼該關系的

28、碼?屬于第幾范式屬于第幾范式?答答:碼碼: (倉庫號倉庫號,設備號設備號) 屬于屬于3NF,但不屬于但不屬于BCNF 非非BCNF的不良特性的不良特性:某位職工剛分配到某位職工剛分配到一個倉庫工作，但一個倉庫工作，但尚未負責具體設備，尚未負責具體設備，這樣的信息就無法這樣的信息就無法插入插入。職工號職工號倉庫號倉庫號 (倉庫號倉庫號,設備號設備號) 職工號職工號練習練習1 1：問：關系模式問：關系模式R中的屬性中的屬性全部是主屬性全部是主屬性,則則R的的必定是必定是_。 3NF練習練習2：如下表所示的關系如下表所示的關系R R，下列選項中關于該關系模，下列選項中關于該關系模式屬于第幾范式判斷正

29、確的是式屬于第幾范式判斷正確的是（ ）。）。A、不是、不是3NF B、是、是3NF但不是但不是2NFC、是、是3NF但不是但不是BCNFD、是、是BCNFD任何一個二元關系必定任何一個二元關系必定屬于基于函數(shù)依賴最高屬于基于函數(shù)依賴最高范式范式BCNFBCNF。6.3.5 多值依賴與第四范式多值依賴與第四范式課課 程程 C教教 員員 T參參 考考 書書 B物理物理 數(shù)學數(shù)學 計算數(shù)計算數(shù)學學李李 勇勇王王 軍軍 李李 勇勇張張 平平 張張 平平周周 峰峰 普通物理學普通物理學光學原理光學原理 物理習題集物理習題集 數(shù)學分析數(shù)學分析微分方程微分方程高等代數(shù)高等代數(shù) 數(shù)學分析數(shù)學分析 例例: 學校

30、中某一門課學校中某一門課程由多個教師講授，程由多個教師講授，他們使用相同的一他們使用相同的一套參考書。套參考書。即：關系模式即：關系模式Teaching(C, T, B) 課程課程C、教師、教師T 和和 參參考書考書B6.3.5 多值依賴與第四范式多值依賴與第四范式普通物理學普通物理學光學原理光學原理物理習題集物理習題集普通物理學普通物理學光學原理光學原理物理習題集物理習題集數(shù)學分析數(shù)學分析微分方程微分方程高等代數(shù)高等代數(shù)數(shù)學分析數(shù)學分析微分方程微分方程高等代數(shù)高等代數(shù)李李 勇勇李李 勇勇李李 勇勇王王 軍軍王王 軍軍王王 軍軍李李 勇勇李李 勇勇李李 勇勇張張 平平張張 平平張張 平平 物物

31、 理理物物 理理物物 理理物物 理理物物 理理物物 理理數(shù)數(shù) 學學數(shù)數(shù) 學學數(shù)數(shù) 學學數(shù)數(shù) 學學數(shù)數(shù) 學學數(shù)數(shù) 學學 參考書參考書B教員教員T課程課程C用二維表表示用二維表表示Teaching6.3.5 多值依賴與第四范式多值依賴與第四范式 Teach具有唯一候選碼具有唯一候選碼(C, T, B)， 即全碼即全碼 TeachingBCNF 存在的問題存在的問題 (1)數(shù)據(jù)冗余數(shù)據(jù)冗余：有多少名任課教師，參考書就要存儲多少次：有多少名任課教師，參考書就要存儲多少次 ； (2)插入異常插入異常：當某一課程增加一名任課教師時，該課程有：當某一課程增加一名任課教師時，該課程有多少本參照書，就必須插入多

32、少個元組；多少本參照書，就必須插入多少個元組； (3) 刪除異常：刪除異常：某一門課要去掉一本參考書，該課程有多少某一門課要去掉一本參考書，該課程有多少名教師，就必須刪除多少個元組；名教師，就必須刪除多少個元組； (4) 修改異常：修改異常：某一門課要修改一本參考書，該課程有多少某一門課要修改一本參考書，該課程有多少名教師，就必須修改多少個元組。名教師，就必須修改多少個元組。 產(chǎn)生原因：存在產(chǎn)生原因：存在多值依賴多值依賴6.3.5 多值依賴與第四范式多值依賴與第四范式定義定義6.11 設設R(U)是屬性集是屬性集U上的一個關系模式。上的一個關系模式。X、 Y、Z是是U的子集，并且的子集，并且Z

33、UXY，多值依，多值依賴賴 XY成立當且僅當對成立當且僅當對R的任一關系的任一關系r，給定一給定一對（對（x，z）值，則對應一組）值，則對應一組Y值，且這組值僅僅決值，且這組值僅僅決定于定于X值而與值而與Z值無關值無關。例：例： Teaching（C, T, B） 對于對于C的每一個值，的每一個值，T總有一組值與之對應，而總有一組值與之對應，而與與B的取值無關，則的取值無關，則T多值依賴于多值依賴于C即：即：CT，且，且B也多值依賴于也多值依賴于C即：即：CB。6.3.5 多值依賴與第四范式多值依賴與第四范式 平凡多值依賴和非平凡的多值依賴平凡多值依賴和非平凡的多值依賴 若若XY，而，而Z，則

34、稱，則稱XY為平凡為平凡的多值依賴；的多值依賴； 否則稱否則稱XY為非平凡的多值依賴。為非平凡的多值依賴。如非平凡的多值依賴：如非平凡的多值依賴：CT，CB6.3.5 多值依賴與第四范式多值依賴與第四范式 多值依賴的性質(zhì)：多值依賴的性質(zhì)：（1）對稱性對稱性： 即：若即：若XY，則，則XZ，其中，其中ZUXY 多值依賴的對稱性可以用多值依賴的對稱性可以用完全二分圖完全二分圖直觀地直觀地表示出來。表示出來。（2）傳遞性傳遞性：即：若即：若XY，YZ， 則則XZ Y6.3.5 多值依賴與第四范式多值依賴與第四范式 物物 理理普通物理學普通物理學 光學原理光學原理 物理習題集物理習題集李勇李勇 王軍王

35、軍完全二分圖描述多值依賴對稱性完全二分圖描述多值依賴對稱性6.3.5 多值依賴與第四范式多值依賴與第四范式（5）函數(shù)依賴是多值依賴的特殊情況：）函數(shù)依賴是多值依賴的特殊情況： 即：若即：若XY，則，則XY。（3）合并性合并性: 若若XY，XZ，則，則 XY Z。（4）分解性分解性: 若若XY，XZ，則，則 XYZ, XYZ， XZY。6.3.5 多值依賴與第四范式多值依賴與第四范式定義定義6.12 關系模式關系模式R1NF，如果對于，如果對于R的每個非平的每個非平凡多值依賴凡多值依賴XY（Y X），），X都含有候選碼，都含有候選碼，則則R4NF。即：即：消除各屬性間非平凡且非函數(shù)依賴的多值依賴

36、。消除各屬性間非平凡且非函數(shù)依賴的多值依賴。 允許出現(xiàn)函數(shù)依賴（非平凡多值依賴）允許出現(xiàn)函數(shù)依賴（非平凡多值依賴） 允許出現(xiàn)平凡多值依賴允許出現(xiàn)平凡多值依賴 如果如果R 4NF， 則則R BCNF6.3.5 多值依賴與第四范式多值依賴與第四范式證明：證明：4NF BCNF反證：若反證：若R 4NF， 但但R BCNF，則按，則按BCNF定定義，一定有一個決定因素不包含碼。義，一定有一個決定因素不包含碼。 于是存在：于是存在：XY， Y X，且，且X中不含有碼。中不含有碼。 由于函數(shù)依賴是多值依賴的特殊情況，即：由于函數(shù)依賴是多值依賴的特殊情況，即：XY ，可得，可得XY （Y X） ，按按4N

37、F定義，定義，X一定含有碼，則與一定含有碼，則與X中不含有碼矛盾。中不含有碼矛盾。 所以：所以：R BCNF。6.3.5 多值依賴與第四范式多值依賴與第四范式 存在非平凡的多值依賴存在非平凡的多值依賴CT，且，且C不是候選不是候選碼，該關系模式的碼是碼，該關系模式的碼是(C,T,B) ，即全碼。，即全碼。 存在問題存在問題：數(shù)據(jù)冗余大，插入、刪除、更新異常：數(shù)據(jù)冗余大，插入、刪除、更新異常 解決方法解決方法：用投影分解法把：用投影分解法把Teach分解為如下兩個分解為如下兩個關系模式關系模式： CT(C, T) 4NF CB(C, B) 4NF 其中：其中：CT， CB是平凡多值依賴是平凡多值

38、依賴 例：例： Teach(C,T,B) 4NF6.3.5 多值依賴與第四范式多值依賴與第四范式 函數(shù)依賴和多值依賴是兩種非常重要的數(shù)據(jù)依賴函數(shù)依賴和多值依賴是兩種非常重要的數(shù)據(jù)依賴 若只考慮若只考慮函數(shù)依賴函數(shù)依賴，則，則BCNF為最高范式（但為最高范式（但不是數(shù)據(jù)庫模式設計的最高范式）；不是數(shù)據(jù)庫模式設計的最高范式）； 若考慮若考慮多值依賴多值依賴，則，則4NF為最高范式；為最高范式； 若消除了若消除了4NF中的中的連接依賴連接依賴，可以得到更為規(guī)，可以得到更為規(guī)范化的范化的5NF。6.3.6 關系模式規(guī)范化關系模式規(guī)范化 一個關系只要其分量都是不可分的數(shù)據(jù)項，它就是一個關系只要其分量都是

39、不可分的數(shù)據(jù)項，它就是規(guī)范化的關系，但這只是最基本的規(guī)范化規(guī)范化的關系，但這只是最基本的規(guī)范化1NF。 規(guī)范化程度過低的關系不一定能夠很好地描述現(xiàn)實規(guī)范化程度過低的關系不一定能夠很好地描述現(xiàn)實世界，可能會存在插入異常、刪除異常、修改復雜、世界，可能會存在插入異常、刪除異常、修改復雜、數(shù)據(jù)冗余等問題。數(shù)據(jù)冗余等問題。 一個低一級范式的關系模式，通過一個低一級范式的關系模式，通過模式分解模式分解可以轉(zhuǎn)可以轉(zhuǎn)換為若干個高一級范式的關系模式集合，這種過程換為若干個高一級范式的關系模式集合，這種過程就叫就叫關系模式的規(guī)范化關系模式的規(guī)范化。6.3.6 關系模式規(guī)范化關系模式規(guī)范化 消除不合適的數(shù)據(jù)依賴消

40、除不合適的數(shù)據(jù)依賴; 采用采用“一事一地一事一地”的模式設計原則，使各關系模的模式設計原則，使各關系模式達到某種程度的式達到某種程度的“分離分離”； 讓一個關系描述一個概念、一個實體或者實體間讓一個關系描述一個概念、一個實體或者實體間的一種聯(lián)系的一種聯(lián)系; 若多于一個概念就把它若多于一個概念就把它“分離分離”出去；出去； 所謂規(guī)范化實質(zhì)上是所謂規(guī)范化實質(zhì)上是概念的單一化概念的單一化。 規(guī)范化的基本思想規(guī)范化的基本思想6.3.6 關系模式規(guī)范化關系模式規(guī)范化 關系模式規(guī)范化的基本步驟關系模式規(guī)范化的基本步驟 1NF 消除決定因素消除決定因素 2NF非碼的非平凡非碼的非平凡 函數(shù)依賴函數(shù)依賴 3N

41、F BCNF 4NF消除非主屬性對碼的部分函數(shù)依賴消除非主屬性對碼的部分函數(shù)依賴消除非主屬性對碼的傳遞函數(shù)依賴消除非主屬性對碼的傳遞函數(shù)依賴消除主屬性對碼的部分和傳遞函數(shù)依賴消除主屬性對碼的部分和傳遞函數(shù)依賴消除非平凡且非函數(shù)依賴的多值依賴消除非平凡且非函數(shù)依賴的多值依賴不能說規(guī)范化程度越高的關系模式就越好；不能說規(guī)范化程度越高的關系模式就越好；在設計數(shù)據(jù)庫模式結構時，必須對現(xiàn)實世界的實際情況和用戶應用需求作在設計數(shù)據(jù)庫模式結構時，必須對現(xiàn)實世界的實際情況和用戶應用需求作進一步分析，確定一個合適的、能夠反映現(xiàn)實世界的模式；進一步分析，確定一個合適的、能夠反映現(xiàn)實世界的模式；上面的規(guī)范化步驟可以

42、在其中任何一步終止。上面的規(guī)范化步驟可以在其中任何一步終止。注意：注意：練習練習 給定關系模式和函數(shù)依賴集合，要求判斷達給定關系模式和函數(shù)依賴集合，要求判斷達到的最高范式。到的最高范式。步驟如下步驟如下：1.1.求出給定關系的候選碼（可能不止一個）求出給定關系的候選碼（可能不止一個）2.2.根據(jù)碼，寫出主屬性和非主屬性。根據(jù)碼，寫出主屬性和非主屬性。3.3.判斷是否滿足第一范式判斷是否滿足第一范式( (屬性的值域是否可以分解）屬性的值域是否可以分解）4.4.判斷是否滿足第二范式判斷是否滿足第二范式( (非主屬性對碼的部分函數(shù)非主屬性對碼的部分函數(shù)依賴依賴) ) 5.5.判斷是否滿足第三范式判斷

43、是否滿足第三范式( (非主屬性對碼的傳遞函數(shù)非主屬性對碼的傳遞函數(shù)依賴依賴) ) 6.6.判斷是否滿足判斷是否滿足BCNFBCNF范式范式( (主屬性對碼的傳遞和部分主屬性對碼的傳遞和部分函數(shù)依賴函數(shù)依賴) )解：解：1. 關系關系r的候選碼為：的候選碼為：AB和和AC 練習練習1. 已知關系模式已知關系模式R U=A,B,C,D F=ABD, AC BD, BC在函數(shù)依賴范圍內(nèi)在函數(shù)依賴范圍內(nèi)該關系屬于的最高范式是什么？該關系屬于的最高范式是什么？2. 主屬性為：主屬性為：A、B、C 非主屬性為：非主屬性為：D3. 判斷是否滿足各個范式的要求判斷是否滿足各個范式的要求： 1) R的的所有的屬

44、性值域都不可再分，則所有的屬性值域都不可再分，則r 1NF。 2) 非主屬性非主屬性D不存在對任何碼的部分函數(shù)依賴，則不存在對任何碼的部分函數(shù)依賴，則r 2NF。 3) 非主屬性非主屬性D不存在對任何碼的傳遞函數(shù)依賴不存在對任何碼的傳遞函數(shù)依賴，則，則r 3NF。 4) 因為有函數(shù)依賴因為有函數(shù)依賴BC，而，而B不是關系不是關系R的碼，則的碼，則r不屬于不屬于BCNF。則：則： r 3NF 解：解：1. 關系關系r的候選碼為：的候選碼為：AC練習練習2. 已知關系模式已知關系模式R U=A,B,C,D,E,F F=AB, C DF, ACE, DF在函數(shù)依賴范圍內(nèi)在函數(shù)依賴范圍內(nèi)該關系屬于的最

45、高范式是什么？該關系屬于的最高范式是什么？2. 主屬性為：主屬性為：A、C 非主屬性為：非主屬性為：B、D、E、F3. 判斷是否滿足各個范式的要求：判斷是否滿足各個范式的要求： 1) R的的所有的屬性值域都不可再分，則所有的屬性值域都不可再分，則r 1NF。 2) 由于存在函數(shù)依賴由于存在函數(shù)依賴AB, C DF，而，而A A和和C C均不是關系的均不是關系的碼，存在碼，存在非主屬性非主屬性B、D、F對碼的部分函數(shù)依賴，則對碼的部分函數(shù)依賴，則r不屬于不屬于2NF。則：則： r 1NF 練習練習練習練習3.假設假設：某商業(yè)集團數(shù)據(jù)庫中有一關系模式：某商業(yè)集團數(shù)據(jù)庫中有一關系模式R R如下：如下

46、：R (R (商店編號，商品編號，數(shù)量，部門編號，負責人商店編號，商品編號，數(shù)量，部門編號，負責人) )如果規(guī)定如果規(guī)定： (1) (1) 每個商店的每種商品只在一個部門銷售；每個商店的每種商品只在一個部門銷售；(2) (2) 每個商店的每個部門只有一個負責人；每個商店的每個部門只有一個負責人；(3) (3) 每個商店的每種商品只有一個庫存數(shù)量。每個商店的每種商品只有一個庫存數(shù)量。試回答下列問題試回答下列問題：(1) (1) 根據(jù)上述規(guī)定，寫出關系模式根據(jù)上述規(guī)定，寫出關系模式R R的基本函數(shù)依賴；的基本函數(shù)依賴；(2) (2) 找出關系模式找出關系模式R R的候選碼；的候選碼；(3) (3)

47、 試問關系模式試問關系模式R R最高已經(jīng)達到第幾范式？為什么？最高已經(jīng)達到第幾范式？為什么？(4) (4) 如果如果R R不屬于不屬于3NF3NF，請將，請將R R分解成分解成3NF3NF模式集模式集 練習練習(1)(1)有三個函數(shù)依賴有三個函數(shù)依賴： ( (商店編號，商品編號商店編號，商品編號) ) 部門編號部門編號 ( (商店編號，部門編號商店編號，部門編號) ) 負責人負責人 ( (商店編號，商品編號商店編號，商品編號) ) 數(shù)量數(shù)量(2) R(2) R的的候選鍵候選鍵: (: (商店編號，商品編號商店編號，商品編號) )(3)(3)因為因為R R中存在著非主屬性中存在著非主屬性“負責人

48、負責人”對候選碼對候選碼 ( (商店編號、商品編號商店編號、商品編號) )的傳遞函數(shù)依賴，但無部的傳遞函數(shù)依賴，但無部分函數(shù)依賴，所以分函數(shù)依賴，所以R R屬于屬于2NF2NF，R R不屬于不屬于3NF3NF。(4) (4) 將將R R分解成：分解成： R1 (R1 (商店編號，商品編號，數(shù)量，部門編號商店編號，商品編號，數(shù)量，部門編號) ) R2 ( R2 (商店編號，部門編號，負責人商店編號，部門編號，負責人) ) 6.4Armstrong公理系統(tǒng)公理系統(tǒng) 函數(shù)依賴公理函數(shù)依賴公理 一套推理規(guī)則，是模式分解算法的理論基礎。一套推理規(guī)則，是模式分解算法的理論基礎。 用途：用途：（1 1）求函

49、數(shù)依賴集閉包、屬性集閉包。）求函數(shù)依賴集閉包、屬性集閉包。（2 2）求最小函數(shù)依賴集。）求最小函數(shù)依賴集。（3 3）求給定關系模式的候選碼。）求給定關系模式的候選碼。（4 4）模式分解。）模式分解。一、邏輯蘊含的定義一、邏輯蘊含的定義定義定義1: 設設F是關系模式是關系模式R 的一個函數(shù)依賴的一個函數(shù)依賴集，集，X,Y U,對對 r，XY都成立都成立, 則稱則稱F邏輯蘊邏輯蘊含含X Y。另一等價定義：設另一等價定義：設F是關系模式是關系模式R 的一個的一個函數(shù)依賴集，函數(shù)依賴集，X,Y U,若從若從F中的函數(shù)依賴可推中的函數(shù)依賴可推出出X Y, 則稱則稱F邏輯蘊含邏輯蘊含X Y。二、推理規(guī)則二

50、、推理規(guī)則設關系模式為設關系模式為R （1）A1自反律（自反律（Reflexivity）：）： 若若Y X U，則，則X Y為為F所蘊含。所蘊含。證明證明: 設設Y X U （僅需了解！（僅需了解！ ）R 的的 r中，對中，對 元組元組t，s：若若tX=sX，(1)Y X，則，則tY=sY，(2)由由(1),(2)可得可得XY成立，自反律得證。成立，自反律得證。注意注意：由自反律所得到的：由自反律所得到的函數(shù)依賴均是函數(shù)依賴均是平凡的函數(shù)平凡的函數(shù)依賴依賴，自反律的使用并不，自反律的使用并不依賴于依賴于F。如：如：(sno,sname)-sname（2）A2.增廣律（增廣律（Augmentat

51、ion）：）： 若若XY為為F所蘊含，且所蘊含，且Z U，則，則XZYZ為為F所蘊含。所蘊含。證明：證明： （僅需了解?。▋H需了解！ ）設設R 的的 r中，中， 元組元組t，s；若若tXZ=sXZ （1），），則有則有tX=sX和和tZ=sZ；（；（2）XY，則有，則有tY=sY，（，（3）由由(2),(3)可得：可得：tYZ=sYZ （4） 由由(1)，(4)可得，則可得，則XZYZ為為F所蘊含，所蘊含，增廣律得證。增廣律得證。如：如：sno-sname，sdeptU, U, 則則(sno,sdept)-(sname,sdept)(sno,sdept)-(sname,sdept)（3）A3.

52、傳遞律（傳遞律（Transitivity）：）： 若若XY及及YZ為為F所蘊含，則所蘊含，則XZ為為F所所蘊含。蘊含。證明：設證明：設XY及及YZ為為F所蘊含。所蘊含。對對R 的的 r， 元組元組 t，s。若若tX=sX （1），），XY，則，則 tY=sY；又又YZ，則有，則有tZ=sZ （2），），由由(1),(2)可得：可得：XZ為為F所蘊含，傳遞律得所蘊含，傳遞律得證。證。如：如：sno-sdept，sdept-dname-dname可得：可得：sno-dnamesno-dname（4）由由Armstrong公理得到以下推論公理得到以下推論:1）、合并律：如果）、合并律：如果XY和和X

53、Z成立，則成立，則XYZ成立。成立。2）、偽傳遞律：如果）、偽傳遞律：如果XY和和WYZ成立，則成立，則WXZ成立。成立。3）、分解律：如果）、分解律：如果XY和和ZY成立，則成立，則XZ成立。成立。（5）根據(jù)合并規(guī)則和分解規(guī)則，可得的引理：）根據(jù)合并規(guī)則和分解規(guī)則，可得的引理： 引理引理1： XA1 A2Ak成立的充分必要條件是成立的充分必要條件是XAi （i=l，2，k）成立。）成立。若已知：若已知：sno-sname,sdept可得：可得：sno-sname, sno-sdeptsno-sname, sno-sdept若已知若已知sno-sname, sno-sdeptsno-sname

54、, sno-sdept可得：可得： sno-sname,sdept三、函數(shù)依賴閉包定義三、函數(shù)依賴閉包定義定義定義2：由被：由被F邏輯蘊涵的函數(shù)依賴的全體構成邏輯蘊涵的函數(shù)依賴的全體構成的集合，稱為的集合，稱為F的閉包的閉包，記作，記作F+。四、四、 Armstrong公理系統(tǒng)的有效性、完備性公理系統(tǒng)的有效性、完備性1、有效性：由、有效性：由F出發(fā)可由出發(fā)可由Armstrong公理推導公理推導出來的每一個函數(shù)依賴一定在出來的每一個函數(shù)依賴一定在F+中；中；2、完備性是指：、完備性是指：F+中的每一個函數(shù)依賴，必中的每一個函數(shù)依賴，必定可由定可由F根據(jù)根據(jù)Armstrong公理推導出來。公理推導

55、出來。6.4 函數(shù)依賴的公理系統(tǒng)函數(shù)依賴的公理系統(tǒng) 邏輯蘊含邏輯蘊含 定義定義6.13 對于滿足一組函數(shù)依賴對于滿足一組函數(shù)依賴 F 的關系模式的關系模式R ，其任何一個關系，其任何一個關系r，若函數(shù)依賴，若函數(shù)依賴XY都都成立，成立， 則稱則稱F邏輯蘊含邏輯蘊含X Y ，或稱，或稱X Y 為為F所所蘊含蘊含。即：對于即：對于r中任意兩個元組中任意兩個元組t和和s，有：若有：若 tX=sX 則則 tY=sY 必成立。必成立。 6.4.1 Armstong公理系統(tǒng)公理系統(tǒng) Armstrong公理系統(tǒng)公理系統(tǒng)函數(shù)依賴的推理規(guī)則函數(shù)依賴的推理規(guī)則 關系模式關系模式R 有以下推理規(guī)則：有以下推理規(guī)則：

56、Al 自反律自反律：若：若Y X U，則，則X Y為為F所蘊含。所蘊含。A2 增廣律增廣律：若：若XY為為F所蘊含，且所蘊含，且Z U，則，則XZYZ為為F所蘊含。所蘊含。A3 傳遞律傳遞律：若：若XY及及YZ為為F所蘊含，則所蘊含，則XZ為為F所蘊含。所蘊含。注：由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴，自反律注：由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴，自反律的使用并不依賴于的使用并不依賴于F。6.4.1 Armstong公理系統(tǒng)公理系統(tǒng)偽傳遞規(guī)則：偽傳遞規(guī)則：若若X Y，WY Z，則，則XW Z 。分解規(guī)則：分解規(guī)則：若若X Y及及 Z Y，則則X Z 。X Y增廣律增廣律X XYX

57、 Z增廣律增廣律XY YZ傳遞律傳遞律X YZ證明合并規(guī)則：證明合并規(guī)則： 由由Armstrong公理導出的推理規(guī)則公理導出的推理規(guī)則:合并規(guī)則：合并規(guī)則：若若X Y，X Z，則，則X YZ。6.4.2 閉包閉包 引理引理6.l 若若A1A2An是關系模式是關系模式R的屬性集的屬性集, 則：則：XA1 A2Ak XAi成立成立(i=l,2,k)。證明：充分性：由合并律證明：充分性：由合并律 必要性：由分解律必要性：由分解律 根據(jù)合并規(guī)則和分解規(guī)則，可得：根據(jù)合并規(guī)則和分解規(guī)則，可得：6.4.2 閉包閉包定義定義6.14 在關系模式在關系模式R中為中為F所邏輯蘊含的函數(shù)依賴所邏輯蘊含的函數(shù)依賴的

58、全體叫作的全體叫作 F的閉包的閉包，記為，記為F+。定義定義6.15 設設F為屬性集為屬性集U上的一組函數(shù)依賴，上的一組函數(shù)依賴，X U， XF+ = A|XA能由能由F 根據(jù)根據(jù)Armstrong公理導出公理導出，XF+稱為稱為屬性集屬性集X關于函數(shù)依賴集關于函數(shù)依賴集F 的閉包。的閉包。引理引理6.2 設設F為屬性集為屬性集U上的一組函數(shù)依賴，上的一組函數(shù)依賴，X，Y U，XY能由能由F 根據(jù)根據(jù)Armstrong公理導出的充分必要條件是公理導出的充分必要條件是Y XF+用途：將判定用途：將判定XY是否能由是否能由F根據(jù)根據(jù)Armstrong公理導出的問公理導出的問題，轉(zhuǎn)化為求出題，轉(zhuǎn)化為

59、求出XF+ ，判定，判定Y是否為是否為XF+的子集的問題。的子集的問題。6.4.2 閉包閉包算法算法6.l 求屬性集求屬性集X（X U）關于）關于U上的函數(shù)依賴集上的函數(shù)依賴集F 的閉包的閉包XF+ 輸入：輸入：X，F(xiàn)輸出：輸出：XF+步驟：步驟：（1）令）令X（0）=X，i=0（2）求）求B：B = A |( V)( W)(VW F V X（i）A W)；（3）X（i+1）=BX（i） （4）判斷）判斷X（i+1）= X （i）嗎嗎?（5）若相等或）若相等或X（i）=U , 則則X（i）就是就是XF+ , 算法終止。算法終止。（6）若不相等）若不相等, 則則 i=i+l，返回第（，返回第（2

60、）步。）步。例：例： 已知關系模式已知關系模式R，其中，其中U=A，B，C，D，EF=ABC，BD，CE，ECB，ACB求（求（AB）F+ 。解：解： (1) 設設X（0）=AB； (2) 計算計算X（1）: 逐一掃描逐一掃描F集合中各個函數(shù)依賴，找左部為集合中各個函數(shù)依賴，找左部為A，B或或AB的函數(shù)依賴。的函數(shù)依賴。 得到兩個：得到兩個：ABC，BD。 (3) X（1）=ABCD=ABCD。 (4) X（0） X（1） 則需再找出左部為則需再找出左部為ABCD子集的那些函數(shù)依賴，又得到子集的那些函數(shù)依賴，又得到ABC，BD， CE，ACB 于是：于是：X（2）=X（1）BCDE=ABCDE