1、第6章 關(guān)系數(shù)據(jù)理論,問題的提出 規(guī)范化 數(shù)據(jù)依賴的公理系統(tǒng) 模式的分解,6.1 問題的提出,關(guān)系數(shù)據(jù)庫邏輯設(shè)計 針對具體問題，如何構(gòu)造一個適合于它的數(shù)據(jù)模式 數(shù)據(jù)庫邏輯設(shè)計的工具關(guān)系數(shù)據(jù)庫的規(guī)范化理論,一、概念回顧 二、關(guān)系模式的形式化定義 三、什么是數(shù)據(jù)依賴 四、關(guān)系模式的簡化定義 五、數(shù)據(jù)依賴對關(guān)系模式影響,6.1 問題的提出,一、概念回顧,關(guān)系 關(guān)系模式 關(guān)系數(shù)據(jù)庫 關(guān)系數(shù)據(jù)庫的模式,6.1 問題的提出,二、關(guān)系模式的形式化定義,關(guān)系模式由五部分組成，即它是一個五元組： R(U, D, DOM, F) R： 關(guān)系名 U： 組成該關(guān)系的屬性名集合 D： 屬性組U中屬性所來自的域 DOM：

2、性向域的映象集合 F： 屬性間數(shù)據(jù)的依賴關(guān)系集合,6.1 問題的提出,三、什么是數(shù)據(jù)依賴,1. 完整性約束的表現(xiàn)形式 限定屬性取值范圍：例如學(xué)生成績必須在0-100之間 定義屬性值間的相互關(guān)連（主要體現(xiàn)于值的相等與否），這就是數(shù)據(jù)依賴，它是數(shù)據(jù)庫模式設(shè)計的關(guān)鍵,6.1 問題的提出,2. 數(shù)據(jù)依賴 一個關(guān)系內(nèi)部屬性與屬性之間的約束關(guān)系 現(xiàn)實世界屬性間相互聯(lián)系的抽象 數(shù)據(jù)內(nèi)在的性質(zhì) 語義的體現(xiàn),6.1 問題的提出,3. 數(shù)據(jù)依賴的類型 函數(shù)依賴（Functional Dependency，簡記為FD） 多值依賴（Multivalued Dependency，簡記為MVD） 其他,6.1 問題的提出

3、,四、關(guān)系模式的簡化表示,關(guān)系模式R（U, D, DOM, F） 簡化為一個三元組： R（U, F） 當(dāng)且僅當(dāng)U上的一個關(guān)系r滿足F時，r稱為關(guān)系模式 R（U, F）的一個關(guān)系,6.1 問題的提出,五、數(shù)據(jù)依賴對關(guān)系模式的影響,例1 建立一個描述學(xué)校教務(wù)的數(shù)據(jù)庫： 學(xué)生的學(xué)號（Sno）、所在系（Sdept） 系主任姓名（Mname）、課程名（Cname） 成績（Grade） 單一的關(guān)系模式 ： Student U Sno, Sdept, Mname, Cname, Grade ,6.1 問題的提出,屬性組U上的一組函數(shù)依賴F： F Sno Sdept, Sdept Mname, (Sno, C

4、name) Grade ,6.1 問題的提出,關(guān)系模式Student中存在的問題,1. 數(shù)據(jù)冗余太大 2. 更新異常（Update Anomalies） 3. 插入異常（Insertion Anomalies） 4. 刪除異常（Deletion Anomalies）,6.1 問題的提出,結(jié)論： Student關(guān)系模式不是一個好的模式。 “好”的模式： 不會發(fā)生插入異常、刪除異常、更新異常， 數(shù)據(jù)冗余應(yīng)盡可能少 原因：由存在于模式中的某些數(shù)據(jù)依賴引起的 解決方法：通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴,6.1 問題的提出,分解關(guān)系模式,把這個單一模式分成3個關(guān)系模式： S（Sno，Sdept

5、，Sno Sdept）; SC（Sno，Cno，Grade，（Sno，Cno） Grade）; DEPT（Sdept，Mname，Sdept Mname）,6.1 問題的提出,6.2 規(guī)范化,規(guī)范化理論正是用來改造關(guān)系模式，通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問題。,6.2.1 函數(shù)依賴,函數(shù)依賴 平凡函數(shù)依賴與非平凡函數(shù)依賴 完全函數(shù)依賴與部分函數(shù)依賴 傳遞函數(shù)依賴,一、函數(shù)依賴,6.2.1 函數(shù)依賴,定義6.1 設(shè)R(U)是一個屬性集U上的關(guān)系模式，X和Y是U的子集。 若對于R(U)的任意一個可能的關(guān)系r，r中不可能存在兩個元組在X上的屬

6、性值相等， 而在Y上的屬性值不等， 則稱 “X函數(shù)確定Y” 或 “Y函數(shù)依賴于X”，記作XY。,說明,1. 所有關(guān)系實例均要滿足 2. 語義范疇的概念 3. 數(shù)據(jù)庫設(shè)計者可以對現(xiàn)實世界作強制的規(guī)定,6.2.1 函數(shù)依賴,二、平凡函數(shù)依賴與非平凡函數(shù)依賴,6.2.1 函數(shù)依賴,在關(guān)系模式R(U)中，對于U的子集X和Y， 如果XY，但Y X，則稱XY是非平凡的函數(shù)依賴 若XY，但Y X, 則稱XY是平凡的函數(shù)依賴 例：在關(guān)系SC(Sno, Cno, Grade)中， 非平凡函數(shù)依賴： (Sno, Cno) Grade 平凡函數(shù)依賴： (Sno, Cno) Sno (Sno, Cno) Cno,若X

7、Y，則X稱為這個函數(shù)依賴的決定屬性組，也稱為決定因素（Determinant）。 若XY，YX，則記作XY。 若Y不函數(shù)依賴于X，則記作XY。,6.2.1 函數(shù)依賴,三、完全函數(shù)依賴與部分函數(shù)依賴,6.2.1 函數(shù)依賴,定義6.2 在R(U)中，如果XY，并且對于X的任何一個真子集X，都有X Y, 則稱Y對X完全函數(shù)依賴，記作X F Y。 若XY，但Y不完全函數(shù)依賴于X，則稱Y對X部分函數(shù)依賴，記作X P Y。,6.2.1 函數(shù)依賴,例1 中(Sno,Cno)Grade是完全函數(shù)依賴， (Sno,Cno)Sdept是部分函數(shù)依賴 因為Sno Sdept成立，且Sno是（Sno，Cno）的真子集

8、,F,P,四、傳遞函數(shù)依賴,定義6.3 在R(U)中，如果XY，(YX) ,YX YZ， 則稱Z對X傳遞函數(shù)依賴。 記為：X Z 注: 如果YX， 即XY，則Z直接依賴于X。 例: 在關(guān)系Std(Sno, Sdept, Mname)中，有： Sno Sdept，Sdept Mname Mname傳遞函數(shù)依賴于Sno,傳遞,6.2.1 函數(shù)依賴,6.2.2 碼,定義6.4 設(shè)K為R中的屬性或?qū)傩越M合。若 K U，則K稱為R的侯選碼（Candidate Key）。 若候選碼多于一個，則選定其中的一個做為主碼（Primary Key）。,F,主屬性與非主屬性 包含在任何一個候選碼中的屬性 ，稱為主屬

9、性（Prime attribute） 不包含在任何碼中的屬性稱為非主屬性（Nonprime attribute）或非碼屬性（Non-key attribute） 全碼 整個屬性組是碼，稱為全碼（All-key）,6.2.2 碼,例2 關(guān)系模式S(Sno,Sdept,Sage)，單個屬性Sno是碼，SC（Sno，Cno，Grade）中，（Sno，Cno）是碼 例3 關(guān)系模式R（P，W，A） P：演奏者 W：作品 A：聽眾 一個演奏者可以演奏多個作品 某一作品可被多個演奏者演奏 聽眾可以欣賞不同演奏者的不同作品 碼為(P，W，A)，即All-Key,6.2.2 碼,6.2.2 碼,定義6.5 關(guān)系

10、模式 R 中屬性或?qū)傩越MX 并非 R的碼，但 X 是另一個關(guān)系模式的碼，則稱 X 是R 的外部碼（Foreign key）也稱外碼 如在SC（Sno，Cno，Grade）中，Sno不是碼，但Sno是關(guān)系模式S（Sno，Sdept，Sage）的碼，則Sno是關(guān)系模式SC的外部碼 主碼與外部碼一起提供了表示關(guān)系間聯(lián)系的手段,外部碼,6.2.3 范式,范式是符合某一種級別的關(guān)系模式的集合 關(guān)系數(shù)據(jù)庫中的關(guān)系必須滿足一定的要求。滿足不同程度要求的為不同范式 范式的種類： 第一范式(1NF) 第二范式(2NF) 第三范式(3NF) BC范式(BCNF) 第四范式(4NF) 第五范式(5NF),6.2.3

11、 范式,各種范式之間存在聯(lián)系： 某一關(guān)系模式R為第n范式，可簡記為RnNF。 一個低一級范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換為若干個高一級范式的關(guān)系模式的集合，這種過程就叫規(guī)范化,6.2.4 2NF,1NF的定義 如果一個關(guān)系模式R的所有屬性都是不可分的基本數(shù)據(jù)項，則R1NF 第一范式是對關(guān)系模式的最起碼的要求。不滿足第一范式的數(shù)據(jù)庫模式不能稱為關(guān)系數(shù)據(jù)庫 但是滿足第一范式的關(guān)系模式并不一定是一個好的關(guān)系模式,例4 關(guān)系模式 S-L-C(Sno, Sdept, Sloc, Cno, Grade)，Sloc為學(xué)生住處，假設(shè)每個系的學(xué)生住在同一個地方 函數(shù)依賴包括： (Sno, Cno) F Gr

12、ade Sno Sdept , (Sno, Cno) P Sdept Sno Sloc , (Sno, Cno) P Sloc Sdept Sloc,6.2.4 2NF,S-L-C的碼為(Sno, Cno) S-L-C滿足第一范式。 非主屬性Sdept和Sloc部分函數(shù)依賴于碼(Sno, Cno),Sno,Cno,Grade,Sdept,Sloc,S-L-C,6.2.4 2NF,S-L-C不是一個好的關(guān)系模式,(1) 插入異常 (2) 刪除異常 (3) 數(shù)據(jù)冗余度大 (4) 修改復(fù)雜,6.2.4 2NF,原因 Sdept、 Sloc部分函數(shù)依賴于碼。 解決方法 S-L-C分解為兩個關(guān)系模式，以

13、消除這些部分函數(shù)依賴 SC（Sno， Cno， Grade） S-L（Sno， Sdept， Sloc）,6.2.4 2NF,函數(shù)依賴圖：,關(guān)系模式SC的碼為（Sno，Cno） 關(guān)系模式S-L的碼為Sno 這樣非主屬性對碼都是完全函數(shù)依賴,6.2.4 2NF,2NF的定義 定義6.6 若R1NF，且每一個非主屬性完全函數(shù)依賴于碼，則R2NF。 例：S-L-C(Sno, Sdept, Sloc, Cno, Grade) 1NF S-L-C(Sno, Sdept, Sloc, Cno, Grade) 2NF SC（Sno， Cno， Grade） 2NF S-L（Sno， Sdept， Sloc）

14、 2NF,6.2.4 2NF,采用投影分解法將一個1NF的關(guān)系分解為多個2NF的關(guān)系，可以在一定程度上減輕原1NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問題。 將一個1NF關(guān)系分解為多個2NF的關(guān)系，并不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。,6.2.4 2NF,6.2.5 3NF,3NF的定義 定義6.7 關(guān)系模式R 中若不存在這樣的碼X、屬性組Y及非主屬性Z（Z Y）, 使得XY，YZ成立， Y X，則稱R 3NF。 若R3NF，則每一個非主屬性既不部分依賴于碼也不傳遞依賴于碼。,例：2NF關(guān)系模式S-L(Sno, Sdept, Sloc)中 函數(shù)依賴： SnoS

15、dept Sdept Sno SdeptSloc 可得： SnoSloc，即S-L中存在非主屬性對碼的傳遞函數(shù)依賴，S-L 3NF,6.2.5 3NF,傳遞,函數(shù)依賴圖：,6.2.5 3NF,解決方法 采用投影分解法，把S-L分解為兩個關(guān)系模式，以消除傳遞函數(shù)依賴： S-D（Sno， Sdept） D-L（Sdept，Sloc） S-D的碼為Sno， D-L的碼為Sdept。 分解后的關(guān)系模式S-D與D-L中不再存在傳遞依賴,6.2.5 3NF,S-D的碼為Sno， D-L的碼為Sdept,S-L(Sno, Sdept, Sloc) 2NF S-L(Sno, Sdept, Sloc) 3NF

16、S-D(Sno，Sdept) 3NF D-L(Sdept， Sloc) 3NF,6.2.5 3NF,采用投影分解法將一個2NF的關(guān)系分解為多個3NF的關(guān)系，可以在一定程度上解決原2NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問題。 將一個2NF關(guān)系分解為多個3NF的關(guān)系后，仍然不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。,6.2.5 3NF,6.2.6 BC范式（BCNF）,定義6.8 關(guān)系模式R1NF，若XY且Y X時X必含有碼，則R BCNF。 等價于：每一個決定屬性因素都包含碼,若RBCNF 所有非主屬性對每一個碼都是完全函數(shù)依賴 所有的主屬性對每一個不包含它的碼，也

17、是完全函數(shù)依賴 沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性 R BCNF R 3NF,6.2.6 BC范式（BCNF）,6.2.6 BC范式（BCNF）,例5 關(guān)系模式C（Cno，Cname，Pcno） C3NF CBCNF 例6 關(guān)系模式S（Sno，Sname，Sdept，Sage） 假定S有兩個碼Sno，Sname S3NF。 S BCNF,例7 關(guān)系模式SJP（S，J，P）中，S是學(xué)生，J表示課程，P表示名次。每一個學(xué)生選修每門課程的成績有一定的名次，每門課程中每一名次只有一個學(xué)生(即沒有并列名次)。由語義可得到下面的函數(shù)依賴: （S，J）P；(J，P）S （S，J）與（J，P）都可以

18、作為候選碼,屬性相交 SJP3NF， SJPBCNF,6.2.6 BC范式（BCNF）,例8 關(guān)系模式STJ(S，T，J)中，S表示學(xué)生，T表示教師，J表示課程，每一教師只教一門課。每門課有若干教師，某一學(xué)生選定某門課，就對應(yīng)一個固定的教師。由語義可得到如下的函數(shù)依賴 函數(shù)依賴： (S，J)T，(S，T)J，TJ (S，J)和(S，T)都是候選碼,6.2.6 BC范式（BCNF）,6.2.6 BC范式（BCNF）,STJ3NF 沒有任何非主屬性對碼傳遞依賴或部分依賴 STJBCNF T是決定因素，T不包含碼,解決方法：將STJ分解為二個關(guān)系模式： ST(S，T) BCNF， TJ(T，J) B

19、CNF 沒有任何屬性對碼的部分函數(shù)依賴和傳遞函數(shù)依賴,6.2.6 BC范式（BCNF）,3NF與BCNF的關(guān)系,R BCNF R 3NF 如果R3NF，且R只有一個候選碼 R BCNF R 3NF,6.2.6 BC范式（BCNF）,6.2.6 BC范式（BCNF）,3NF和BCNF是在函數(shù)依賴的條件下對模式分解所能達到的分離程度的測度。一個模式中的關(guān)系模式如果都屬于BCNF,那么在函數(shù)依賴范疇內(nèi),它己實現(xiàn)了徹底的分離,己消除了插入和刪除的異常。 3NF的“不徹底”性表現(xiàn)在可能存在主屬性對碼的部分依賴和傳遞依賴。 BCNF是基于函數(shù)依賴的最高范式，但不是數(shù)據(jù)庫模式設(shè)計的最高范式,6.2.7 多值

20、依賴,例9 學(xué)校中某一門課程由多個教師講授，他們使用相同的一套參考書。每個教員可以講授多門課程，每種參考書可以供多門課程使用。,非規(guī)范化關(guān)系,6.2.7 多值依賴,用二維表表示Teaching,6.2.7 多值依賴,TeachingBCNF Teaching具有唯一候選碼(C，T，B)， 即全碼,6.2.7 多值依賴,Teaching模式中存在的問題 (1)數(shù)據(jù)冗余度大 (2)插入操作復(fù)雜 (3)刪除操作復(fù)雜 (4)修改操作復(fù)雜,存在 多值依賴,定義6.9 設(shè)R(U)是一個屬性集U上的一個關(guān)系模式， X、 Y和Z是U的子集，并且ZUXY。關(guān)系模式R(U)中多值依賴 XY成立，當(dāng)且僅當(dāng)對R(U)

21、的任一關(guān)系r，給定的一對（x，z）值，有一組Y的值，這組值僅僅決定于x值而與z值無關(guān) 例 Teaching（C, T, B）,6.2.7 多值依賴,平凡多值依賴和非平凡的多值依賴 若XY，而Z，則稱 XY為平凡的多值依賴 否則稱XY為非平凡的多值依賴,6.2.7 多值依賴,6.2.8 4NF,定義6.10 關(guān)系模式R1NF，如果對于R的每個非平凡多值依賴XY（Y X），X都含有碼，則R4NF。 如果R 4NF， 則R BCNF,例： Teaching(C,T,B) 4NF 存在非平凡的多值依賴CT，且C不是碼 用投影分解法把Teaching分解為如下兩個關(guān)系模式： CT(C, T) 4NF C

22、B(C, B) 4NF CT， CB是平凡多值依賴,6.2.8 4NF,6.2.9 規(guī)范化小結(jié),關(guān)系數(shù)據(jù)庫的規(guī)范化理論是數(shù)據(jù)庫邏輯設(shè)計的工具 目的：盡量消除插入、刪除異常，修改復(fù)雜，數(shù)據(jù)冗余 基本思想：逐步消除數(shù)據(jù)依賴中不合適的部分 實質(zhì)：概念的單一化,關(guān)系模式規(guī)范化的基本步驟 1NF 消除非主屬性對碼的部分函數(shù)依賴 消除決定屬性 2NF 集非碼的非平 消除非主屬性對碼的傳遞函數(shù)依賴 凡函數(shù)依賴 3NF 消除主屬性對碼的部分和傳遞函數(shù)依賴 BCNF 消除非平凡且非函數(shù)依賴的多值依賴 4NF,6.2.9 規(guī)范化小結(jié),不能說規(guī)范化程度越高的關(guān)系模式就越好 在設(shè)計數(shù)據(jù)庫模式結(jié)構(gòu)時，必須對現(xiàn)實世界的實

23、際情況和用戶應(yīng)用需求作進一步分析，確定一個合適的、能夠反映現(xiàn)實世界的模式 上面的規(guī)范化步驟可以在其中任何一步終止,6.2.9 規(guī)范化小結(jié),6.3 數(shù)據(jù)依賴的公理系統(tǒng),邏輯蘊含 定義6.11 對于滿足一組函數(shù)依賴 F 的關(guān)系模式R ，其任何一個關(guān)系r，若函數(shù)依賴XY都成立, （即r中任意兩元組t，s，若tX=sX，則tY=sY），則稱F邏輯蘊含X Y,設(shè)F是關(guān)系模式R的一個函數(shù)依賴集，X,Y是R的屬性子集，如果從F中的函數(shù)依賴能夠推出XY，則稱F邏輯蘊涵XY,例：關(guān)系模式 R=(A,B,C),函數(shù)依賴集F=AB,BC, F邏輯蘊涵AC,1. Armstrong公理系統(tǒng),6.3 數(shù)據(jù)依賴的公理系統(tǒng)

24、,關(guān)系模式R 來說有以下的推理規(guī)則： A1.自反律（Reflexivity）：若Y X U，則X Y為F所蘊含。 A2.增廣律（Augmentation）：若XY為F所蘊含，且Z U，則XZYZ為F所蘊含。 A3.傳遞律（Transitivity）：若XY及YZ為F所蘊含，則XZ為F所蘊含。,定理 6.1 Armstrong推理規(guī)則是正確的,6.3 數(shù)據(jù)依賴的公理系統(tǒng),（l）自反律: 若Y X U，則X Y為F所蘊含 證: 設(shè)Y X U 對R 的任一關(guān)系r中的任意兩個元組t，s： 若tX=sX，由于Y X，有ty=sy， 所以XY成立，自反律得證,(2)增廣律: 若XY為F所蘊含，且Z U，則

25、XZYZ 為F所蘊含。 證：設(shè)XY為F所蘊含，且Z U。 設(shè)R 的任一關(guān)系r中任意的兩個元組t，s： 若tXZ=sXZ，則有tX=sX和tZ=sZ； 由XY，于是有tY=sY，所以tYZ=sYZ，所以 XZYZ為F所蘊含，增廣律得證。,6.3 數(shù)據(jù)依賴的公理系統(tǒng),(3) 傳遞律：若XY及YZ為F所蘊含，則 XZ為 F所蘊含。 證：設(shè)XY及YZ為F所蘊含。 對R 的任一關(guān)系 r中的任意兩個元組 t，s： 若tX=sX，由于XY，有 tY=sY； 再由YZ，有tZ=sZ，所以XZ為F所蘊含，傳 遞律得證。,6.3 數(shù)據(jù)依賴的公理系統(tǒng),2. 導(dǎo)出規(guī)則,6.3 數(shù)據(jù)依賴的公理系統(tǒng),1.根據(jù)A1，A2，

26、A3這三條推理規(guī)則可以得到下面三條推理規(guī)則： 合并規(guī)則：由XY，XZ，有XYZ。 偽傳遞規(guī)則：由XY，WYZ，有XWZ。 分解規(guī)則：由XY及 ZY，有XZ。,2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理6.1 引理6.l XA1 A2Ak成立的充分必要條件是XAi成立（i=l，2，k）,6.3 數(shù)據(jù)依賴的公理系統(tǒng),Armstrong公理系統(tǒng)是有效的、完備的 有效性：由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來的每一個函數(shù)依賴一定在F+中； 完備性：F+中的每一個函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來,6.3 數(shù)據(jù)依賴的公理系統(tǒng),6.3 數(shù)據(jù)依賴的公理系統(tǒng),定義6.l2 在關(guān)系模式R

27、中為F所邏輯蘊含的函數(shù)依賴的全體叫作 F的閉包，記為F+。,定義：若F為關(guān)系模式R(U)的函數(shù)依賴集，我們把F以及所有被F邏輯蘊涵的函數(shù)依賴的集合稱為F的閉包，記為F+。即：F+=XY|XYF“應(yīng)用Armstong公理從F中導(dǎo)出的任何XY”一般 情況下，F(xiàn)包含于F+，如果F=F+，則稱F為函數(shù)依賴的一個完備集。 規(guī)定：若X為U的子集，X 屬于F+。,例：R=ABC,F=AB, BC, 求F+ 解： F+ =A,AB,AC,ABC,B,C, AA,ABA,ACA,ABCA,BB,CC, AB,ABB,ACB,ABCB,BC, AC,ABC,ACC,ABCC,BBC, AAB,ABAB,ACAB,

28、ABCAB,BC, AAC,ABAC,ACAC,ABCAC,BCB, ABC,ABBC,ACBC,ABCBC,BCC, AABC,ABABC,ACABC,ABCA,BCBC,6.3 數(shù)據(jù)依賴的公理系統(tǒng),例：已知關(guān)系模式R中,U=A，B，C，D, E, G,F=ABC, CA, BCD, ACDB, DEG, BEC, CGBD, CEAG, 判斷BDAC是否屬于F+,解：由DEG知DE，BDBE 又知BEC，CA 所以BEA, BEAC 由、知，BDAC，所以BDAC被F所蘊涵，即BDAC屬于F+,6.3 數(shù)據(jù)依賴的公理系統(tǒng),6.3 數(shù)據(jù)依賴的公理系統(tǒng),定義6.13 設(shè)F為屬性集U上的一組函數(shù)

29、依賴，X U， XF+ = A|XA能由F 根據(jù)Armstrong公理導(dǎo)出，XF+稱為屬性集X關(guān)于函數(shù)依賴集F 的閉包,定義：若F為關(guān)系模式R(U)的函數(shù)依賴集，X是U的子集，則由Armstrong公理推導(dǎo)出的所有XAi所形成的屬性集Ai|i=1,2,稱為X對于F的閉包，記為X+。,6.3 數(shù)據(jù)依賴的公理系統(tǒng),引理6.2 設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y U，XY能由F 根據(jù)Armstrong公理導(dǎo)出的充分必要條件是Y XF+ 用途 將判定XY是否能由F根據(jù)Armstrong公理導(dǎo)出的問題，轉(zhuǎn)化為求出XF+ 、判定Y是否為XF+的子集的問題,6.3 數(shù)據(jù)依賴的公理系統(tǒng),算法：求屬性集X（

30、 X U ）關(guān)于U上的函數(shù)依賴集F的閉包XF+ 。輸入：U，X，F(xiàn) 輸出： XF+ 步驟： (1)令X (0)=X，i=0； (2)X(i+1)=X(i) A,其中A是這樣的屬性，在F中找尚未用過的Y Z， 其中Y X(i)，在Z中找X(i)中未出現(xiàn)的屬性集合A，若無這種A， 則轉(zhuǎn)(4) (3)判斷X(i+1)=X(i)嗎？若相等轉(zhuǎn)(4)，若否， X(i+1)=U嗎，否轉(zhuǎn)（2） (4)輸出X(i) ，即是XF+ ，算法終止。,算法：a.令X+ = X; b.在F中依次查找每個沒有被標記的函數(shù)依賴， 若“左邊屬性集”包含于X+ ，則令 X+ = X+“右邊屬性集”, 為被訪問過的函數(shù)依賴設(shè)置訪問

31、標記。 c.反復(fù)執(zhí)行b直到X+不改變?yōu)橹埂?6.3 數(shù)據(jù)依賴的公理系統(tǒng),例：設(shè)有關(guān)系模式R（U，F(xiàn)），其中： U= A，B，C，D，E，I F= AD，ABE，BIE ，CDI ，EC 計算（AE）+。,計算過程： X(0)=AE; X(1)=ACDE; X(2)=ACDEI; (AE)+=ACDEI,6.3 數(shù)據(jù)依賴的公理系統(tǒng),例：設(shè)R=ABC,F=AB, BC當(dāng)X分別為A,B,C是求X+。 解: 當(dāng)X=A時，X+=ABC當(dāng)X=B時，X+=BC當(dāng)X=C時，X+=C,6.3 數(shù)據(jù)依賴的公理系統(tǒng),結(jié)論 判定函數(shù)依賴XY是否能由F導(dǎo)出的問題，可轉(zhuǎn)化為求X+并判定Y是否是X+子集的問題。 關(guān)鍵字問題

32、可轉(zhuǎn)化為求屬性集閉包問題，因為XX+,若U=X+,則XU，即X為關(guān)鍵字。,例：驗證AD 是否為關(guān)系模式R=(ABCD,AB,BC)的關(guān)鍵字,驗證：(AD)+=ABCD,6.3 數(shù)據(jù)依賴的公理系統(tǒng),例1 已知關(guān)系模式R，其中 U=A，B，C，D，E； F=ABC，BD，CE，ECB，ACB。 求（AB）F+ 。 解 設(shè)X（0）=AB； (1) X（1）=ABCD=ABCD。 (2) X（0） X（1） X（2）=X（1）BE=ABCDE。 (3) X（2）=U，算法終止 （AB）F+ =ABCDE。,6.3 數(shù)據(jù)依賴的公理系統(tǒng),定理6.2 Armstrong公理系統(tǒng)是有效的、完備的 證明略,6.

33、3 數(shù)據(jù)依賴的公理系統(tǒng),定義6.14 如果G+=F+，就說函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價。 引理6.3 F+ = G+ 的充分必要條件是F G+ ，和G F+,6.3 數(shù)據(jù)依賴的公理系統(tǒng),定義6.15 如果函數(shù)依賴集F滿足下列條件，則稱F為一個極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。 (1) F中任一函數(shù)依賴的右部僅含有一個屬性。 (2) F中不存在這樣的函數(shù)依賴XA，使得F與F-XA等價。 (3) F中不存在這樣的函數(shù)依賴XA， X有真子集Z使得F-XAZA與F等價。,Fm三個條件的含義： Fm的函數(shù)依賴右部是單屬性。 Fm 中沒有多余的函數(shù)依賴。 Fm

34、 中的每個函數(shù)依賴的左部沒有多余屬性。,6.3 數(shù)據(jù)依賴的公理系統(tǒng),冗余覆蓋設(shè)F為函數(shù)依賴集，如果存在F的真子集F,使得FF,則稱F是冗余的，否則F為非冗余的。,例2 關(guān)系模式S，其中： U= Sno，Sdept，Mname，Cno，Grade ， F= SnoSdept，SdeptMname，(Sno，Cno)Grade 設(shè)F=SnoSdept，SnoMname，SdeptMname， (Sno，Cno)Grade，(Sno，Sdept)Sdept F是最小覆蓋，而F不是。 因為：F - SnoMname與F 等價 F - (Sno，Sdept)Sdept也與F 等價,6.3 數(shù)據(jù)依賴的公理

35、系統(tǒng),規(guī)約函數(shù)依賴集(1)多余屬性設(shè)F為函數(shù)依賴集，對于任一XYF，屬性AR,如果下列條件之一成立，則稱A是XY關(guān)于F的多余屬性： X=AZ,XZ,且（F-XYZY)F; Y=AW,YW,且（F-XYXW)F;示例：F1=ABC,BC F2=AB,BC F1F2F3=ABC,BC F4=BC F3F4,6.3 數(shù)據(jù)依賴的公理系統(tǒng),(2)規(guī)約函數(shù)依賴集 給定函數(shù)依賴集F，如果F中任一函數(shù)依賴XYF的左邊都不含多余屬性，則稱F為左規(guī)約的；如果F中任一函數(shù)XYF的右邊都不含多余屬性，則稱F為右規(guī)約的。,6.3 數(shù)據(jù)依賴的公理系統(tǒng),定理6.3 每一個函數(shù)依賴集F均等價于一個極小函數(shù)依賴集Fm。此Fm稱

36、為F的最小依賴集。,6.3 數(shù)據(jù)依賴的公理系統(tǒng),最小函數(shù)依賴集給定函數(shù)依賴集F，如果F中每一函數(shù)依賴XYF滿足：(1) XY的右邊Y為單個屬性（F為右規(guī)約的）；(2) F為左規(guī)約；(3) F為非冗余的；則稱F為最小函數(shù)依賴集，或稱F為正則的。如果F是正則的且FG, 則稱F為G的正則覆蓋。,6.3 數(shù)據(jù)依賴的公理系統(tǒng),(1)逐一檢查F中各函數(shù)依賴FDi：XY，若Y=A1A2 Ak，k 2，則用 XAj |j=1，2， k 來取代XY。 (2)逐一檢查F中各函數(shù)依賴FDi：XA，令G=F-XA， 若AXG+， 則從F中去掉此函數(shù)依賴。 (3)逐一取出F中各函數(shù)依賴FDi：XA，設(shè)X=B1B2Bm，

37、 逐一考查Bi （i=l，2，m），若A （X-Bi ）F+ ， 則以X-Bi 取代X。,6.3 數(shù)據(jù)依賴的公理系統(tǒng),算法：計算最小函數(shù)依賴集。 輸入：F 輸出：Fm 方法： 1）應(yīng)用分解規(guī)則，使F中每一個依賴的右部屬性單一化。 2）去掉各依賴左部多余的屬性。 3）去掉多余的函數(shù)依賴。,6.3 數(shù)據(jù)依賴的公理系統(tǒng),(1) 為滿足條件(1)，根據(jù)分解性把右側(cè)是屬性組的函數(shù)依賴分解為單屬性的多個函數(shù)依賴；例：ABC可分解為AB，AC (2) 為滿足條件(2)，逐一考察最新F中的函數(shù)依賴，消除左側(cè)冗余屬性；例：判斷XYA是否冗余，可在F中求X+,若A X+（表A包含于X+），則XA，Y為冗余屬性。

38、(3) 為滿足條件(3)，逐一考察最新F中的函數(shù)依賴XY，檢查XY是否被F-XY所蘊涵，如果是，則XY是冗余的，可以刪除例：F=AB, BC, AC中AC,6.3 數(shù)據(jù)依賴的公理系統(tǒng),例3 F = AB，BA，BC，AC，CA Fm1、Fm2都是F的最小依賴集： Fm1= AB，BC，CA Fm2= AB，BA，AC，CA F的最小依賴集Fm不唯一,候選碼的求解理論（補充內(nèi)容） 對于關(guān)系模式中的屬性，根據(jù)函數(shù)依賴集F可分為以下4類： L類：僅出現(xiàn)在F的函數(shù)依賴的左邊； R類：僅出現(xiàn)在F的函數(shù)依賴的右邊； N類：在F的函數(shù)依賴中不出現(xiàn)； LR類：在F的函數(shù)依賴中左邊、右邊都出現(xiàn)。 求解侯選碼：

39、定理1：對于R（U，F(xiàn)），若X是L類屬性，則X必為R的一侯選碼的成員； 推論：對于R（U，F(xiàn)），若X是L類屬性，且X+=U，則X必為R的唯一侯選碼； 定理2：對于R（U，F(xiàn)），若X是R類屬性，則X不在R的任一侯選碼中；,定理3：對于R（U，F(xiàn)），若X是N類屬性，則X必為R的任一侯選碼的成員； 推論：對于R（U，F(xiàn)），若X是L類和N類組成的屬性集，且X+=U，則X必為R的唯一侯選碼； 算法：求多屬性依賴集侯選碼的方法。 1）將R中屬性分為L、R、N、LR四類，其中令X代表L，N類，Y代表LR類； 2）求X+，若=U，則X為唯一侯選碼，轉(zhuǎn)5）； 3）否則，在Y中取屬性A，求（XA）+，若其等于U，則轉(zhuǎn)5），否則調(diào)換屬性反復(fù)進行，直到試完Y中所有屬性。 4）若找到所有候選碼，則轉(zhuǎn)5）。否則在Y中依次取2個、3個、，求它們的屬性閉包，直到其閉