1、4.1 關(guān)系模式的設(shè)計(jì)問題,4.2 關(guān)系模式的規(guī)范化,4.3 數(shù)據(jù)依賴的公理系統(tǒng),4.4 關(guān)系模式的分解,第四章 關(guān)系數(shù)據(jù)理論,本章小結(jié),4.1函數(shù)依賴,一、問題如何構(gòu)造一個(gè)關(guān)系模式 例：假設(shè)有學(xué)生關(guān)系模式,其中，S#學(xué)號(hào)、 SNAME學(xué)生姓名、 CLASS班級(jí)、 C#課程號(hào)、 TNAME教師姓名、 TAGE教師年齡、ADDRESS教師地址、 GRADE成績(jī)。,S(S#,SNAME,CLASS,C#,TNAME,TAGE,ADDRESS,GRADE),關(guān)系S存在以下問題： 1數(shù)據(jù)冗余度高。 SNAME、CLASS、TNAME、TAGE、ADDRESS重復(fù)存儲(chǔ)多次。,4.1函數(shù)依賴,2數(shù)據(jù)修改復(fù)

2、雜。 3插入異常。 插入異常是指應(yīng)該插入到數(shù)據(jù)庫中的數(shù)據(jù)不能執(zhí)行插入操作的情形。,關(guān)系S的主碼：,（S#，C#）,從在S#、C#、和(S#,c#)上出現(xiàn)NULL值去分析。 注意：當(dāng)一個(gè)元組在主碼的屬性上部分或全部為空時(shí)，該元組不能插入到關(guān)系中。,4.1函數(shù)依賴,4刪除異常。 刪除異常是指不應(yīng)該刪去的數(shù)據(jù)被刪去的情形。 例如：選修某門課的所有學(xué)生都退選時(shí)，刪除相關(guān)元組，會(huì)丟失該課程老師的信息。 解決：關(guān)系模式分解（關(guān)系規(guī)范化） 分解為 ST(S#，SNAME，CLASS) CT(C#,TNAME) TA(TNAME,TAGE,ADDRESS) SC(S#,C#,GRADE),4.1函數(shù)依賴,二、

3、函數(shù)依賴functional dependency, abbr. FD,設(shè)：R（A1，A2，An)=R( U ) X，Y，Z 為U的不同子集,定義4.1： 函數(shù)依賴 是完整性約束的一種，它推廣了關(guān)鍵詞的概念。If t1.X=t2.X, then t1.Y=t2.Y 函數(shù)依賴：若R的任意關(guān)系有：對(duì)X中的每個(gè)屬性值，在Y中都有惟一的值與之對(duì)應(yīng)，則稱Y函數(shù)依賴于X，記作 XY 。,屬性全集,4.1函數(shù)依賴,例：指出下列關(guān)系R中的函數(shù)依賴。,FD: AB-C、 AC、CA、ABD？ Insert into R values(a1, b1, c2, d1) FD = key constraint ?,4

4、.1函數(shù)依賴,函數(shù)依賴與屬性間的關(guān)系有： 若X，Y是1 1關(guān)系， 則存在 XY或Y X 。如學(xué)號(hào)與借書證號(hào) 若X，Y是m 1關(guān)系， 則存在 XY但 Y+ X。如學(xué)號(hào)與姓名 若X，Y是m n關(guān)系， 則X，Y間不存在函數(shù)依賴關(guān)系。如姓名與課程 CF: 實(shí)體間的聯(lián)系 NOTE: 函數(shù)依賴的方向性,4.1函數(shù)依賴,例 試指出學(xué)生關(guān)系S(S#，SNAME，CLASS，C#，TNAME，TAGE，ADDRESS，GRADE)中存在的函數(shù)依賴關(guān)系。 S#SNAME（每個(gè)學(xué)號(hào)只能有一個(gè)學(xué)生姓名） S#CLASS（每個(gè)學(xué)號(hào)只能有一個(gè)班級(jí)） C#TNAME（設(shè)每門課程只有一個(gè)教師任教，而一個(gè)教師可教多門課程，見C

5、T表） TNAMETAGE（每個(gè)教師只能有一個(gè)年齡） TNAMEADDRESS（每個(gè)教師只能有一個(gè)地址） (S#，C#)GRADE（每個(gè)學(xué)生學(xué)習(xí)一門課只能有一個(gè)成績(jī)） (S#，C#)SNAME、 (S#，C#)CLASS、 (S#，C#)C#、 (S#，C#)TNAME、 (S#，C#)TAGE、 (S#，C#)ADDRESS,4.1函數(shù)依賴,三、函數(shù)依賴的分類 XY，但Y 不包含于 X則稱X是非平凡的函數(shù)依賴。 XY，但Y X 則稱X是平凡的函數(shù)依賴。 若XY ，則X叫做決定因素。 若XY，Y X，則記作: XY。 定義4.2：在R( U)中，X, Y, Z為U的不同子集。 完全函數(shù)依賴:

6、是指 XY，且對(duì)任何X的真子集X， 都有X+Y，記作：X F Y。 部分函數(shù)依賴: 是指XY，且存在X的真子集X， 有X-Y， 記作：X P Y。,定義4.3：在R( U )中 傳遞函數(shù)依賴：是指若XY (Y 不包含于 X)， Y + X ， 而Y Z。記作： X T Z 。,4.1函數(shù)依賴,左部為單屬性的函數(shù)依賴一定是完全函數(shù)依賴。 左部為多屬性的函數(shù)依賴，如何判斷其是否為完全函數(shù)依賴？ 方法：取真子集，看其能否決定右部屬性。 例：試指出學(xué)生關(guān)系S中存在的完全函數(shù)依賴和部分函數(shù)依賴。 S#SNAME，S#CLASS，TNAMETAGE， TNAMEADDRESS，C#TNAME都是完全函數(shù)依

7、賴。 (S#，C#)GRADE 是一個(gè)完全函數(shù)依賴，因?yàn)镾#+GRADE，C#+GRADE。,4.1函數(shù)依賴,例：試指出學(xué)生關(guān)系S中存在的傳遞函數(shù)依賴。 解：因?yàn)镃#TNAME，TNAME+C#，TNAMETAGE，所以C#TAGE 是一個(gè)傳遞函數(shù)依賴。類似地，C#ADDRESS也是一個(gè)傳遞函數(shù)依賴。,(S#，C#)SNAME，(S#，C#)CLASS， (S#，C#)TNAME，(S#，C#)TAGE， (S#，C#)ADDRESS都是部分函數(shù)依賴，因?yàn)镾#SNAME，S#CLASS，C#TNAME，C#TAGE，C#ADDRESS。,4.1函數(shù)依賴,四、候選碼 用函數(shù)依賴的概念來定義碼。

8、定義4.4 : 設(shè)X為R中的屬性或?qū)傩越M合，若 X F U 則X為R的候選碼。 說明： X F U X - U X能決定整個(gè)元組 X+ U X中無多余的屬性,術(shù)語： 主碼 主屬性: 侯選碼中的屬性 非主屬性 全碼：整個(gè)屬性組為碼 例：R(顧客，商品，日期),4.1函數(shù)依賴,例：試指出下列關(guān)系R中的侯選碼、主屬性和非主屬性。,解：關(guān)系R的侯選碼為：A，(D,E) 關(guān)系R的主屬性為：A，D，E 關(guān)系R的非主屬性：無,函數(shù)依賴判斷：A-D? D-A? AD-E? 候選碼判斷: A-ADE? AD-ADE?,4.1函數(shù)依賴,例1. R(A, B, C, D)，F(xiàn)=A-B, A-C, AB-D 解：由

9、AB-A(自反律) 和 A-C(已知) 得：AB-C(傳遞律) 又因?yàn)?AB-A (自反律) ，AB-B (自反律) 和 AB-D (已知) 得：AB-ABCD。 AB是R的唯一候選碼，同時(shí)也是R的主碼。,4.1函數(shù)依賴,例2. R(A, B, C, D)，F(xiàn)=A-B, A-C, A-D, AB-D 解：由 A-A(自反律) 和 A-B, A-C, A-D(已知) 得：A- ABCD 可知 A是R的候選碼 AB-ABCD，但由于存在A- ABCD，則AB對(duì)ABCD是部分函數(shù)依賴，因此AB不能成為候選碼。 A是R的唯一候選碼，A是主碼。,4.2 關(guān)系模式的規(guī)范化,一、關(guān)系與范式 關(guān)系的規(guī)范化是將

10、一個(gè)低級(jí)范式的關(guān)系模式，通過關(guān)系模式的分解轉(zhuǎn)換為若干個(gè)高級(jí)范式的過程。 關(guān)系模式分解的目的：去冗余、滿足約束。 關(guān)系模式的冗余性問題。例R(A,B,C)，無任何約束可導(dǎo)致冗余，若規(guī)定FD:A-B，則冗余可利用FD預(yù)測(cè)到。 約束條件通過函數(shù)的多值依賴和連接依賴及范式完成。,4.2 關(guān)系模式的規(guī)范化,二、第一范式：1NF 定義4.5: 若R的每個(gè)分量都是不可分的數(shù)據(jù)項(xiàng)，則R1NF。 從型上看：不存在嵌套結(jié)構(gòu) 從值上看，不存在重復(fù)組 1NF是關(guān)系模式的最低要求。 例：學(xué)生關(guān)系S(S#，SNAME，CLASS，C#，TNAME，TAGE，ADDRESS，GRADE)是1NF關(guān)系，但它存在數(shù)據(jù)冗余，插入

11、異常和刪除異常等問題。,4.2 關(guān)系模式的規(guī)范化,三、第二范式： 2NF 定義4.6 若R1NF，且R中的每一個(gè)非主屬性都完全函數(shù)依賴于R的任一候選碼，則R2NF。 例：學(xué)生關(guān)系S(S#，SNAME，CLASS，C#，TNAME，TAGE，ADDRESS，GRADE),判斷R是否為2NF? 侯選碼為(S#，C#)，非主屬性有：SNAME，CLASS，TNAME，TAGE，ADDRESS，GRADE (S#，C#)SNAME， S# SNAME (S#，C#) P SNAME S2NF(每一個(gè)非主屬性!)。,4.2 關(guān)系模式的規(guī)范化,分解為2NF的方法：破壞部分依賴的條件。 將滿足部分函數(shù)依賴和

12、滿足完全函數(shù)依賴的屬性分解到不同的關(guān)系中。 對(duì)上例，考察非主屬性和侯選碼之間的函數(shù)依賴關(guān)系： (S#，C#) P SNAME， (S#，C#) P CLASS， (S#，C#) P TNAME， (S#，C#) P TAGE， (S#，C#) P ADDRESS， (S#，C#) F GRADE 區(qū)分出完全依賴和部分依賴，若是部分依賴，標(biāo)記出其中的主屬性。,4.2 關(guān)系模式的規(guī)范化,關(guān)系S分解為三個(gè)關(guān)系： ST(S#，SNAME，CLASS)（只依賴S#的屬性分解到一個(gè)子模式中） CTA(C#，TNAME，TAGE，ADDRESS) （只依賴C#的屬性分解到另一個(gè)子模式中） SC(S#，C#，

13、GRADE) （完全函數(shù)依賴于候選碼的屬性分解到第三個(gè)子模式中） 分解后，關(guān)系ST、CTA和SC都為2NF。 結(jié)論1：若關(guān)系R的侯選碼是單屬性的，則R必定是2NF。,4.2 關(guān)系模式的規(guī)范化,達(dá)到2NF的關(guān)系仍然可能存在問題。 例如，在關(guān)系CTA中還存在以下問題： （1） 數(shù)據(jù)冗余。一個(gè)教師承擔(dān)多門課程時(shí)，教師的姓名、年齡、地址要重復(fù)存儲(chǔ)。 （2） 修改復(fù)雜。一個(gè)教師更換地址時(shí)，必須修改相關(guān)的多個(gè)元組。 （3） 插入異常。一個(gè)新教師報(bào)到，需將其有關(guān)數(shù)據(jù)插入到CTA關(guān)系中，但該教師暫時(shí)還未承擔(dān)任何教學(xué)任務(wù)，則因缺碼C#值而不能進(jìn)行插入操作。 （4） 刪除異常。刪除某門課程時(shí)，會(huì)丟失該課程任課教師

14、的姓名、年齡和地址信息。,4.2 關(guān)系模式的規(guī)范化,四、第三范式： 3NF 定義4.7 如果關(guān)系R的任意一個(gè)非主屬性都不傳遞函數(shù)依賴于它的任意一個(gè)候選碼，則R3NF。 關(guān)系CTA(C#，TNAME，TAGE，ADDRESS)是2NF，但不是3NF。 候選碼：C#，非主屬性：TNAME、TAGE、ADDRESS。 由于C#TNAME，TNAME+C#，TNAMETAGE，所以 C# T TAGE ，同樣有C# T ADDRESS，即存在非主屬性對(duì)候選碼的傳遞函數(shù)依賴。,關(guān)系模式R（A，B，C，D），碼為AB，給出它的 一個(gè)函數(shù)依賴集，使得R屬于2NF而不屬于3NF,4.2 關(guān)系模式的規(guī)范化,分解

15、為3NF的方法：破壞傳遞依賴的條件。 將涉及傳遞函數(shù)依賴中的兩個(gè)依賴中的屬性分解到不同的關(guān)系中。 例：CTA中，兩個(gè)傳遞依賴C# T TAGE ，C# T ADDRESS C#TNAME，TNAME+C#，TNAMETAGE。 C#TNAME，TNAME+C#，TNAMEADDRESS。 將CTA分解為： CT(C#，TNAME) TA(TNAME，TAGE，ADDRESS) 則關(guān)系CT和TA都是3NF，關(guān)系CTA中存在的問題得到了解決。,4.2 關(guān)系模式的規(guī)范化,定理4.1 一個(gè)3NF的關(guān)系必定是 2NF。 （3NF傳遞函數(shù)依賴，2NF完全函數(shù)依賴。） 證明：用反證法。設(shè)R3NF，但R2NF

16、，則R中必有非 主屬性A、侯選碼X和X的真子集X存在，使得XA。 X是侯選碼X的真子集，有X-X；A是非主屬性，A-X，A-X，這樣A、X、X是U的不同子集。 X是侯選碼X的真子集，則有XX 且 X+X，聯(lián)合反證假設(shè)XA可知存在傳遞依賴（XX，X+X，XA） R不是3NF，與題設(shè)矛盾。,4.2 關(guān)系模式的規(guī)范化,通過轉(zhuǎn)為2NF消除了部分依賴，通過轉(zhuǎn)為3NF消除了傳遞依賴，問題：達(dá)到3NF的關(guān)系是否仍然存在問題？ 例：每一教師只教一門課。每門課由若干教師教，某一學(xué)生選定某門課，就確定了一個(gè)固定的教師。某個(gè)學(xué)生選修某個(gè)教師的課就確定了所選課的名稱 ：,4.2 關(guān)系模式的規(guī)范化,解：關(guān)系SCT的侯選

17、碼：(S#，CNAME)和(S#，TNAME) 非主屬性：無 （SCT至少是一個(gè)3NF關(guān)系) 結(jié)論2：若關(guān)系R的所有屬性都是主屬性，則R必定是3NF。,候選碼判斷: S#-S# CNAME TNAME. 取左部的相同值，判斷右部。,4.2 關(guān)系模式的規(guī)范化,在3NF關(guān)系SCT中存在： 插入異常。例如，一個(gè)新課程和任課教師的數(shù)據(jù)，在沒有學(xué)生選課時(shí)不能插入數(shù)據(jù)庫。 刪除異常。例如，刪除某門課的所有選課記錄，會(huì)丟失課程與教師的數(shù)據(jù)。 達(dá)到3NF的關(guān)系仍然可能存在問題。,4.2 關(guān)系模式的規(guī)范化,五、BCNF 定義4.8 關(guān)系模式R1NF。若函數(shù)依賴集合F中的 所有函數(shù)依賴XY（Y不包含于X）的左部都

18、包含R的任一侯選碼，則RBCNF。 換言之，BCNF中的所有依賴的左部都必須包含候選碼。 例：關(guān)系SCT是否BCNF? 因?yàn)門NAMECNAME，其左部未包含該關(guān)系的任一侯選碼 ，所以它不是BCNF。 解決：BCNF分解。,4.2 關(guān)系模式的規(guī)范化,分解為BCNF的方法： 消除不包含關(guān)系。 1. 假設(shè)R(U)不是BCNF, X是R的屬性子集，A是R的單個(gè)屬性，X-A是導(dǎo)致違反BCNF的函數(shù)依賴，則將R分解為R-A 以及 XA。 2. 若R-A以及 XA 仍然不是BCNF，則在R-A 以及 XA遞歸地執(zhí)行上述分解。 例 SCT：(S#，CNAME，TNAME)，F(xiàn)D: TNAMECNAME。 可

19、分解為SC(S#，TNAME)和CT(CNAME，TNAME)，它們都是BCNF。,4.2 關(guān)系模式的規(guī)范化,定理4.2：一個(gè)BCNF的關(guān)系必定是3NF。 （3NF：任意的非主屬性都不傳遞依賴于任意一個(gè)候選碼。） 證明：用反證法。設(shè)R是一個(gè)BCNF，但不是3NF，則必存在一個(gè)非主屬性A和候選碼X以及屬性集Y，使得A傳遞依賴于X，即XY(Y不包含于X)，Y+X，YA。 這就是說Y不包含R的候選碼，但YA卻成立。 根據(jù)BCNF定義可知，R不是BCNF，與題設(shè)矛盾。 結(jié)論3：任何的二元關(guān)系必定是BCNF。,4.2 關(guān)系模式的規(guī)范化,3NF下仍然存在插入異常和刪除異常， 原因在于可能存在主屬性對(duì)候選碼

20、的部分函數(shù)依賴和傳遞函數(shù)依賴。 一個(gè)模式中的關(guān)系模式如果都屬于BCNF，則在函數(shù)依賴的范疇內(nèi)實(shí)現(xiàn)了徹底的分離，已消除了插入和刪除的異常。 其它問題？,4.2 關(guān)系模式的規(guī)范化,六、第四范式：4NF 定義4.10 若R 1NF，D是R上的依賴集，如果對(duì)于任何一個(gè)多值依賴XY (Y-X,XY沒有包含R的全部屬性)，X都包含了R的一個(gè)候選關(guān)鍵詞，則R4NF。 4NF必定是BCNF，但BCNF不一定是4NF。,5種范式的關(guān)系：,4.2 關(guān)系模式的規(guī)范化,1NF,非規(guī)范化的關(guān)系,2NF,3NF,4NF,BCNF,范式的 轉(zhuǎn)換關(guān)系：,1NF,2NF,3NF,BCNF,4NF,4.2 關(guān)系模式的規(guī)范化,關(guān)系

21、的規(guī)范化是將一個(gè)低級(jí)范式的關(guān)系模式，通過關(guān)系模式的分解轉(zhuǎn)換為若干個(gè)高級(jí)范式的過程。 范式的轉(zhuǎn)換過程是通過分析和消除屬性間的數(shù)據(jù)依賴關(guān)系來實(shí)現(xiàn)的。 屬性可分為碼和非主屬性。 2NF, 3NF考察非主屬性和碼的關(guān)系，BCNF考察主屬性和碼的關(guān)系。 屬性間的依賴關(guān)系包括函數(shù)依賴和多值依賴。 1NF, 2NF, 3NF, BCNF考察了函數(shù)依賴關(guān)系；4NF考察了多值依賴。,4.3 數(shù)據(jù)依賴的公理系統(tǒng),1.阿氏公理 定義4.13 設(shè)F是關(guān)系模式R的函數(shù)依賴集，X、Y是R的屬性子集，如果從F的函數(shù)依賴中能夠推出XY，則稱F邏輯蘊(yùn)涵XY。 在R 中為F所邏輯蘊(yùn)含的函數(shù)依賴全體叫F的閉包，記為：F+。 F+=

22、 F； F中推出的非平凡的函數(shù)依賴； 平凡的函數(shù)依賴：A-、A-A、AB- A. 例：有關(guān)系模式R(A，B，C)，它的函依賴集F=AB，BC，計(jì)算F的閉包。,4.3 數(shù)據(jù)依賴的公理系統(tǒng),Armstrong公理(阿氏公理)： 對(duì)R 有： A1自反律：若YX ，則XY。 A2增廣律：若XY，則XZYZ。 A3傳遞律：若XY、YZ，則XZ。 Note：XY與YX的次序無關(guān)。,4.3 數(shù)據(jù)依賴的公理系統(tǒng),證：設(shè)s，t是r的任意兩個(gè)元組，r是R的任意一個(gè)關(guān)系。 A1自反律：若YX ，則XY。 若sx=tx，則在s和t中的x的任何子集也必相等。 YX， sy=ty XY。 A2增廣律：若XY，則XZYZ。

23、 若sxz=txz，即sxsz=txtz 則 sx=tx 且 sz=tz XY， sy=ty syz=sysz=tytz=tyz XZYZ,4.3 數(shù)據(jù)依賴的公理系統(tǒng),A3傳遞律：若XY、YZ，則XZ。 若sx=tx XY sy=ty 又 YZ sz=tz XZ。,4.3 數(shù)據(jù)依賴的公理系統(tǒng),公理的推論： 合并規(guī)則：若XY 、 XZ，則XYZ。 分解規(guī)則：若XYZ，則XY,XZ。 偽傳遞規(guī)則：若XY 、WYZ，則WXZ。 證明： 合并規(guī)則： XY XXY (A2) 又 XZ XYYZ (A2) XYZ (A3),4.3 數(shù)據(jù)依賴的公理系統(tǒng),分解規(guī)則： YY Z YZY (A1) 又 XYZ(已

24、知） XY (A3) 同理可證XZ。 偽傳遞規(guī)則： XY WXWY (A2) 又 WYZ (已知) WXZ (A3) 定理4.5: XA1A2AK成立的充分必要條件是XAi成立。,由合并律 由分解律 ,4.3 數(shù)據(jù)依賴的公理系統(tǒng),定義4.14: XF+=A|XA能由F用阿氏公理導(dǎo)出 XF+稱為屬性集X關(guān)于F的閉包。 定理4.6： XY能從F中用阿氏公理導(dǎo)出的充要條件是：YXF+,4.3 數(shù)據(jù)依賴的公理系統(tǒng),定理4.6的證明 證明： 充分性（ YXF+ - XY） 假設(shè)YXF+ (其中Y=A1A2An ) 由屬性閉包定義可知， XA1， XA2， XAn能由阿氏公理導(dǎo)出，再由合并規(guī)則得X A1A

25、2An，即XY。,4.3 數(shù)據(jù)依賴的公理系統(tǒng),必要性：（ XY - YXF+ ） 假設(shè)XY能由阿氏公理導(dǎo)出(Y=A1A2An) 則有XA1A2An 由分解規(guī)則得： XA1， XA2， XAn 由XF+的定義可知，Ai XF+ (i=1,2,n) 即YXF+ 。,Armstrong公理系統(tǒng),Armstrong公理完備性的證明 證明：（構(gòu)造性證明）用反證法 假定存在函數(shù)依賴XY被F邏輯蘊(yùn)涵，但XY不能用Armstrong公理從F中導(dǎo)出 由引理二， 構(gòu)造R(U)上的關(guān)系r如下： 下面證明（1）r滿足F，（2）r不滿足XY,Y ，Y ， U ,4.3 數(shù)據(jù)依賴的公理系統(tǒng),2. 屬性閉包的計(jì)算 算法4.

26、1 : 求屬性集X關(guān)于F的閉包XF+(X+)。 算法： 設(shè) R，A為U中屬性(集)。 (1) X(0)=X (2) X(i+1)=X(i)A 其中：對(duì)F中任一個(gè)Y-A ，且YX(i)； 求得X(i+1) 后，對(duì)Y-A 做刪除標(biāo)記。 (3)若X(i+1)=X(i) 或 X(i+1) =U則結(jié)束，否則轉(zhuǎn)(2)。,最多|U-X|步,閉包的計(jì)算,示例1 R, U = (A, B, C, G, H, I), F = AB, AC, CGH, CGI, BH,計(jì)算 所用依賴 ABAGB ACAGBC CGHAGBCH CGIAGBCH I = AGBCH I,閉包的計(jì)算,示例2 R, U = (A, B,

27、 C, D, E), F = ABC, BD, CE, CEB, ACB,計(jì)算 所用依賴 ABCABC BDABCD CEABCDE = ABCDE,閉包的計(jì)算,示例3 R, U = (A, B, C, D, E, G), F = AE, BEAG, CEA, GD,計(jì)算 所用依賴 AEABE BEAGABEG GDABEGD = ABEGD,4.3 數(shù)據(jù)依賴的公理系統(tǒng),3.函數(shù)依賴集的等價(jià)和覆蓋 定義4.15 : 如果F+=G+ ，就說函數(shù)依賴集F覆蓋G或F與G等價(jià)。 定理4.9: F+=G+ 的充分必要條件是FG+，和GF+。 （1）必要性 F和G等價(jià)，F(xiàn)+=G+，又FF+，F(xiàn)G+ 同理，

28、GG+，GF+。 （2）充分性 任取XYF+，則有YXF+ (定理4.6) 又FG+（已知），YXG+ XY(G+)+=G+，F(xiàn)+G+。 同理可證G+F+，F(xiàn)+=G+，即F和G等價(jià)。,4.3 數(shù)據(jù)依賴的公理系統(tǒng),如何判斷函數(shù)依賴集F和G是否等價(jià)？ 根據(jù)定理4.9: 只需FG+和GF+，即證集合的包含關(guān)系。 對(duì)每個(gè)T F,有T G+；對(duì)每個(gè)S G，有S F+，T和S是形如X-Y的屬性依賴。 證 X-Y G+,根據(jù)定理4.6：只需Y XG+ 轉(zhuǎn)為計(jì)算XG+,4.3 數(shù)據(jù)依賴的公理系統(tǒng),例：F=AB，BC，G=ABC，BC，判斷F和G是否等價(jià)。 解：（1）先檢查F中的每一個(gè)函數(shù)依賴是否屬于G+。 A

29、G+=ABC，BAG+，ABG+ (定理4.6) 又BG+=BC，CBG+，BCG+ FG+ （2）然后檢查G中的每一個(gè)函數(shù)依賴是否屬于F+。 AF+=ABC，BCAF+，ABCF+ 又BF+=BC，CBF+，BCF+ GF+ 由（1）和（2）可得F和G等價(jià)。,4.3 數(shù)據(jù)依賴的公理系統(tǒng),4.最小函數(shù)依賴集 定義4.16:若F滿足下列條件，則稱其為一個(gè)最小函數(shù)依賴集Fm。 (1) F中每個(gè)函數(shù)依賴的右部都是單屬性； (2) 對(duì)于F的任一函數(shù)依賴XA，F(xiàn)-XA與F都不等價(jià)； (3) 對(duì)于F中的任一函數(shù)依賴XA和X的真子集Z， (F-(XA)UZA與F都不等價(jià)。,最?。海?）F中每個(gè)函數(shù)依賴的右部

30、沒有多余的屬性； （2）F中不存在多余的函數(shù)依賴； （3）F中每個(gè)函數(shù)依賴的左部沒有多余的屬性。,4.3 數(shù)據(jù)依賴的公理系統(tǒng),定理4.10: 每個(gè)F與Fm等價(jià)。 如何求最小函數(shù)依賴集Fm？ (1)分解：使F中任一函數(shù)依賴的右部?jī)H含有單屬性。 (2)刪除冗余的函數(shù)依賴： 方法：對(duì)F中任一XA，在F-XA中求X+， 若AX+，則XA為多余的。 (3)最小化左邊的多余屬性： 方法：對(duì)F中任一XYA，在F中求X+， 若AX+ ，則Y為多余的。 (4)檢查：用公理或(2) ,4.3 數(shù)據(jù)依賴的公理系統(tǒng),例：設(shè)有F=BC，CAB，BCA，求與F等價(jià)的最小函數(shù)依賴集。 分解CAB，F(xiàn)=BC，CA，CB，BC

31、A 判斷BC是否冗余，F(xiàn)=CA，CB，BCA B+ = B, BC非冗余。 F=BC，CA，CB，BCA 判斷CA是否冗余，F(xiàn)=BC, CB，BCA C+ = ABC, CA冗余。 F=BC，CB，BCA 判斷CB是否冗余，F(xiàn)=BC, BCA C+ = C, CB非冗余。 F=BC，CB，BCA 判斷BCA是否冗余，F(xiàn)=BC，CB BC+ = BC, BCA非冗余。F=BC，CB，BCA 判斷BCA。 B+ = ABC, AB+ ，則C在BCA中是多余的。 Fmin=BC，CB，BA,注意： 對(duì)當(dāng)前F求閉包,4.3 數(shù)據(jù)依賴的公理系統(tǒng),例：設(shè)有函數(shù)依賴集F=AB,ABCDE,EFG,EFH,A

32、CDFEG 求與F等價(jià)的最小函數(shù)依賴集。 注意：一個(gè)函數(shù)依賴集的最小集不是惟一的。 例如，F(xiàn)=AB，BA，BC，AC，CA Fm1=AB，BC，CA， Fm2=AB，BA，AC，CA。 方法1： 無多余屬性；依次判斷B-A, A-C是否冗余； 方法2： 無多余屬性；依次判斷B-C是否冗余。,Fmin = AB,ACDE, EFG,EFH,4.4 關(guān)系模式的分解,對(duì)于存在數(shù)據(jù)冗余、插入異常、刪除異常的關(guān)系模式，可以通過對(duì)關(guān)系模式的分解來解決問題。關(guān)系模式分解后會(huì)帶來兩個(gè)問題： （1）查詢時(shí)的連接操作是否會(huì)丟失某些信息或多出某些信息。這引出了無損連接的概念。 （2）分解后的關(guān)系模式是否保持了原來的

33、函數(shù)依賴。這是保持函數(shù)依賴性的問題。,4.4 關(guān)系模式的分解,1. 等價(jià)模式分解的定義 一個(gè)關(guān)系可以有多種分解方法，如何判斷分解的好與壞呢？ 例：關(guān)系模式R(S#，SD，MN),F=S#SD，SDMN 分解一：1=R1(S#)， R2(SD)， R3(MN) 不好！無法恢復(fù)r. 分解二：2=R1(S#，SD)，R2(S#，MN) 不好！丟失SDMN 分解三：3=R1(S#，SD)，R2(SD，MN) 好！,R(A, B, C),AB(R),BC(R),AB(R),BC(R),R(A, B, C),AB(R),BC(R),AB(R),BC(R),有損分解,無損分解,4.4 關(guān)系模式的分解,2.無

34、損連接性與依賴保持性 對(duì)于R中任何一個(gè)關(guān)系r， R分解=R1, R2.RK 無損連接性： r=R1(r) R2(r) RK(r) 保持函數(shù)依賴： F R1(F)R2(F) RK(F) Ri(F)=X-Y| X-YF+XYRi ,Ri所蘊(yùn)含的F+中的函數(shù)依賴,4.4 關(guān)系模式的分解,例：R(A，B，C) ， F=A-B，A-C ，分解=AB，AC 判斷1： r=AB(r) |X| AC(r) 是無損連接分解。 判斷2: FAB(F)AC(F) = A-B，A-C 具有函數(shù)依賴保持性。,r,?=AB，BC,4.4 關(guān)系模式的分解,算法4.3 無損連接性檢驗(yàn)。 輸入：關(guān)系模式R(A1，A2，An)，

35、它的函數(shù)依賴集F，以及分 解=R1，R2，Rk。 輸出：確定是否具有無損連接性。 方法：(1)構(gòu)造一個(gè)k行n列的表，第i行對(duì)應(yīng)于關(guān)系模式Ri，第j列 對(duì)應(yīng)于屬性Aj。如果AjRi，則在第i行第j列上放符號(hào)aj，否則放 符號(hào)bij。（屬于用a代表，且位置信息用j表示；不屬于用b代表,且位置信息用ij表示。） (2)重復(fù)考察F中的每一個(gè)函數(shù)依賴，并修改表中的元素。其方 法如下：取F中一個(gè)函數(shù)依賴XY，在X的分量中尋找相同的行，然 后將這些行中Y的分量改為相同的符號(hào)，如果其中有aj，則將bij改 為aj；若其中無aj，則全部改為bij（i是這些行的行號(hào)最小值）。,4.4 關(guān)系模式的分解,(3)如果發(fā)

36、現(xiàn)表中某一行變成了al，a2，an，則分解 具有無損連接性；如果F中所有函數(shù)依賴都不能再修改 表中的內(nèi)容，且沒有發(fā)現(xiàn)這樣的行，則分解不具有無 損連接性。,無損連接分解,示例一：U=A,B,C,D,E, F=ABC, CD,DE =(A, B, C), (C, D), (D, E),ABC,CD,DE,4.4 關(guān)系模式的分解,示例二：U=A,B,C,D,E, F=AC, BC, CD,DEC ,CEA =(A, D), (A, B), (B, E), (C, D, E), (A, E),AC,4.4 關(guān)系模式的分解,BC,CD,4.4 關(guān)系模式的分解,DEC,CEA,4.4 關(guān)系模式的分解,定理

37、4.12 設(shè)=(R1，R2)是R的一個(gè)分解，F(xiàn)是R上的函數(shù) 依賴集，分解具有無損連接性的充分必要條件是： R1R2(R1-R2)F+ 或 R1R2(R2-R1)F+ 證明： （1）充分性：設(shè)R1R2(R1-R2)，按算法5.2可構(gòu)造出下表。表中省略了a和b的下標(biāo)，這無關(guān)緊要。,只能用于判斷分解為2個(gè)子模式的情況。,4.4 關(guān)系模式的分解,如果R1R2(R1-R2)在F中，則可將表中第2行位于(R1-R2)列 中的所有符號(hào)都改為a，這樣該表中第2行就全是a了，則具有無 損連接性。同理可證R1R2(R2-R1)的情況。 如果R1R2(R1-R2)不在F中，但在F+中，即它可以用公理從 F中推出來，

38、從而也能推出R1R2Ax, 其中AxR1-R2，所以可 以將Ax列的第2行改為全a，同樣可以將R1-R2中的其他屬性的第2 行也改為a，這樣第2行就變成全a行。所以分解=R1，R2具有 無損連接性。 同樣可以證明R1R2(R2-R1)的情況。 （2）必要性：設(shè)構(gòu)造的表中有一行全為a，例如第1行全為a，則 由函數(shù)依賴定義可知R1R2(R2-R1)；如果是第2行全為a，則 R1R2(R1-R2)。定理證畢。,4.4 關(guān)系模式的分解,例:下列分解是否具有無損連接性和函數(shù)依賴保持性。 已知：R(A,B,C) F=AB，CB (1）1=AB，BC （2）2=AC，BC,4.4 關(guān)系模式的分解,（1）對(duì)1

39、和F構(gòu)造表：,（2）檢查F=AB，CB 對(duì)AB，A列中無相同的行； 對(duì)CB, C列中無相同的行。 1不具有無損連接性。,1=AB，BC F=AB，CB,4.4 關(guān)系模式的分解,1=AB，BC F=AB，CB 利用定理4.12解。 R1R2 = B (R1-R2) = A R1R2 + (R1-R2) 1不是無損連接分解。,4.4 關(guān)系模式的分解,2=AC，BC F=AB，CB,對(duì)2和F構(gòu)造表：,檢查F=AB，CB 對(duì)CB, C列有相同的行，改寫B(tài)列的相異符號(hào)為a，下標(biāo)為列號(hào)2。第一行變?yōu)閍1a2a3,2具有無損連接性。,4.4 關(guān)系模式的分解,2=AC，BC F=AB，CB 利用定理4.12解

40、。 R1R2 = C (R1-R2) = A；(R2-R1) = B； R1R2 + (R2-R1) 2是無損連接分解。,4.4 關(guān)系模式的分解,3. 模式分解的方法 3NF的保持無損連接及函數(shù)依賴的分解： 設(shè)： R 1)對(duì)Fm中任一X-A，若XA=U則不分解，結(jié)束。 2)若R中Z屬性在Fm中未出現(xiàn)，則所有Z為一個(gè)子模式， 令U=U-Z。 3)對(duì)Fm中 X-A1，. X-An，用合成規(guī)則合成一個(gè)， 再對(duì)Fm中每個(gè)X-A，令Ri=XA。 4) R的分解為R1，R2，.RK，碼,依賴保持不需要； 原包含有不需要。,4.4 關(guān)系模式的分解,BCNF的保持無損連接的分解： （1）令=R； （2）如果中

41、所有關(guān)系模式都是BCNF，則轉(zhuǎn)（4）； （3）如果中有一個(gè)關(guān)系模式Ri不是BCNF，則Ri中必有XAFi+(AX)，且X不是Ri的碼。設(shè)S1=XA，S2=Ui-A，用分解S1，S2代替Ri，轉(zhuǎn)（2）； （4）分解結(jié)束，輸出。 例：設(shè)R=A,B,C,D,F=AC，CA，BAC，DAC，BDA （1）將R 分解為3NF且具有無損連接性和依賴保持性。 （2）將R 分解為BCNF且具有無損連接性。,關(guān)系模式的分解算法,示例：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

42、#,C#)G U1 = S#, SD, F1=S#SD U2 = S#, MN, F2=S#MN U3 = S#, C#, G, F3 = (S#,C#)G,4.4 關(guān)系模式的分解,關(guān)系模式CTHRSG，其中C表示課程，T表示教師，H表示時(shí) 間，R表示教室，S表示學(xué)生，G表示成績(jī)。函數(shù)依賴集F及 其所反映的語義分別為： CT 每門課程僅有一位教師擔(dān)任。 HTR 在任一時(shí)間，一個(gè)教師只能在一個(gè)教室上課。 HRC 在任一時(shí)間，每個(gè)教室只能上一門課。 HSR 在任一時(shí)間，每個(gè)學(xué)生只能在一個(gè)教室聽課。 CSG 每個(gè)學(xué)生學(xué)習(xí)一門課程只有一個(gè)成績(jī)。,4.4 關(guān)系模式的分解,解：HSCTHRSG，HS是關(guān)系

43、模式的關(guān)鍵字。, 面向3NF且保持函數(shù)依賴的分解。 最小函數(shù)依賴集為 F=CT,CSG,HRC,HSR,THR 分解為：CT，CSG，HRC，HSR，THR, 面向3NF既有無損連接性又保持函數(shù)依賴的分解。 HS是關(guān)鍵字， HS ，HS是HSR的一個(gè)子集 分解仍為：CT，CSG，HRC，HSR，THR,4.4 關(guān)系模式的分解, 面向BCNF且具有無損連接性的分解。,CTHRSG Key=HS,CSG Key=CS CSG,CTHRS Key=HS CT，THR HRC，HSR,CT Key=C CT,CHRS Key=HS CHR，HRC HSR,CHR Key=CH，HR CHR， HRC,

44、CHS Key=HS HSC,4.5. 多值依賴與第四范式4NF）,例: 學(xué)校中某一門課程由多個(gè)教師講授，他們使用相同的一套參考書。 關(guān)系模式Teaching(C, T, B) 課程C、教師T 和 參考書B,例: 學(xué)校中某一門課程由多個(gè)教師講授，他們使用相同的一套參考書。 關(guān)系模式Teaching(C, T, B) 課程C、教師T 和 參考書B,4.5. 多值依賴與第四范式4NF）,4.5. 多值依賴與第四范式4NF）,TeachingBCNF: Teach具有唯一候選碼(C，T，B)， 即全碼 Teaching模式中存在的問題 (1)數(shù)據(jù)冗余度大：有多少名任課教師，參考書就要存儲(chǔ)多少次 (2

45、)插入操作復(fù)雜：當(dāng)某一課程增加一名任課教師時(shí)，該課程有多少本參照書，就必須插入多少個(gè)元組 例如物理課增加一名教師劉關(guān)，需要插入兩個(gè)元組： （物理，劉關(guān)，普通物理學(xué)） （物理，劉關(guān)，光學(xué)原理）,4.5. 多值依賴與第四范式4NF）,(3) 刪除操作復(fù)雜：某一門課要去掉一本參考書，該課程有多少名教師，就必須刪除多少個(gè)元組 (4) 修改操作復(fù)雜：某一門課要修改一本參考書，該課程有多少名教師，就必須修改多少個(gè)元組 產(chǎn)生原因 存在多值依賴,4.5. 多值依賴與第四范式4NF,第四范式：4NF 定義4.10 若R 1NF，D是R上的依賴集，如果對(duì)于任何一個(gè)多值依賴XY (Y-X,XY沒有包含R的全部屬性)

46、，X都包含了R的一個(gè)候選關(guān)鍵詞，則R4NF。 4NF必定是BCNF，但BCNF不一定是4NF。,4.5. 多值依賴與第四范式4NF,在R（U）的任一關(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值所得的兩個(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,4.5. 多值依賴與第四范式4NF,平凡多值依賴和非平凡的多值依賴 若XY，而Z，則稱 XY為平凡的多值依賴 否則稱XY為非平凡的多值依賴,4.5. 多值依賴與第四范式4NF多值依賴的性質(zhì),（1）多值依賴具有對(duì)稱性 若XY，則XZ，其中