關(guān)系模式分解

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—成績。,S(S#,SNAME,CLASS,C#,T

2、NAME,TAGE,ADDRESS,GRADE),關(guān)系S存在以下問題：1．?dāng)?shù)據(jù)冗余度高。SNAME、CLASS、TNAME、TAGE、ADDRESS重復(fù)存儲(chǔ)多次。,4.1函數(shù)依賴,2．?dāng)?shù)據(jù)修改復(fù)雜。 3．插入異常。 插入異常是指應(yīng)該插入到數(shù)據(jù)庫中的數(shù)據(jù)不能執(zhí)行插入操作的情形。,關(guān)系S的主碼：,（S#，C#）,從在S#、C#、和(S#,c#)上出現(xiàn)NULL值去分析。注意：當(dāng)一個(gè)元組在主碼的屬性上部分或全部為空時(shí)，該元組不能

3、插入到關(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ù)依賴,

4、二、函數(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，記作 X?Y 。,屬性全集,4.1函數(shù)依賴,例：指出

5、下列關(guān)系R中的函數(shù)依賴。,FD: AB->C、 A→C、C→A、AB→D？Insert into R values(a1, b1, c2, d1)FD = key constraint ?,4.1函數(shù)依賴,函數(shù)依賴與屬性間的關(guān)系有：若X，Y是1 — 1關(guān)系， 則存在 X?Y或Y ?X 。如學(xué)號(hào)與借書證號(hào)若X，Y是m — 1關(guān)系， 則存在 X?Y但 Y+> X。如學(xué)號(hào)與姓名 若X，Y是m — n關(guān)系，

6、 則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è)教師可教多門課程，見CT表）TNA

7、ME→TAGE（每個(gè)教師只能有一個(gè)年齡）TNAME→ADDRESS（每個(gè)教師只能有一個(gè)地址）(S#，C#)→GRADE（每個(gè)學(xué)生學(xué)習(xí)一門課只能有一個(gè)成績）(S#，C#)→SNAME、 (S#，C#)→CLASS、 (S#，C#)→C#、(S#，C#)→TNAME、 (S#，C#)→TAGE、 (S#，C#)→ADDRESS,4.1函數(shù)依賴,三、函數(shù)依賴的分類X?Y，但Y 不包含于 X則稱X是非平凡的函數(shù)依賴。X?Y，但Y

8、? X 則稱X是平凡的函數(shù)依賴。 若X?Y ，則X叫做決定因素。若X?Y，Y ?X，則記作: XY。 定義4.2：在R( U)中，X, Y, Z為U的不同子集。完全函數(shù)依賴: 是指 X?Y，且對(duì)任何X的真子集X’， 都有X’+>Y，記作：X F > Y。部分函數(shù)依賴: 是指X?Y，且存在X的真子集X’，

9、 有X’->Y， 記作：X P > Y。,定義4.3：在R( U )中傳遞函數(shù)依賴：是指若X?Y (Y 不包含于 X)， Y +> X ， 而Y ? Z。記作： X T > Z 。,4.1函數(shù)依賴,左部為單屬性的函數(shù)依賴一定是完全函數(shù)依賴。左部為多屬性的函數(shù)依賴，如何判斷其是否為完全函數(shù)依賴？ 方法：取真子集，看其能否決定右部屬性。

10、例：試指出學(xué)生關(guān)系S中存在的完全函數(shù)依賴和部分函數(shù)依賴。S#→SNAME，S#→CLASS，TNAME→TAGE， TNAME→ADDRESS，C#→TNAME都是完全函數(shù)依賴。(S#，C#)→GRADE 是一個(gè)完全函數(shù)依賴，因?yàn)镾#+>GRADE，C#+>GRADE。,4.1函數(shù)依賴,例：試指出學(xué)生關(guān)系S中存在的傳遞函數(shù)依賴。解：因?yàn)镃#→TNAME，TNAME+>C#，TNAME→TAGE，所以C#→

11、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ù)依賴的概念來定義碼。定義4.4 : 設(shè)X為R中

12、的屬性或?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的主屬性

13、為：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}解：由 AB->A(自反律) 和 A->C(已知) 得：AB->C(傳遞律) 又因?yàn)?AB-

14、>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-> AB

15、CD 可知 A是R的候選碼 AB->ABCD，但由于存在A-> ABCD，則AB對(duì)ABCD是部分函數(shù)依賴，因此AB不能成為候選碼。 A是R的唯一候選碼，A是主碼。,4.2 關(guān)系模式的規(guī)范化,一、關(guān)系與范式關(guān)系的規(guī)范化是將一個(gè)低級(jí)范式的關(guān)系模式，通過關(guān)系模式的分解轉(zhuǎn)換為若干個(gè)高級(jí)范式的過程。關(guān)系模式分解的目的：去冗余、滿足約束。關(guān)系模式的冗余性問題。例R(A,B,C)，無任何約束可導(dǎo)致冗余，

16、若規(guī)定FD:A->B，則冗余可利用FD預(yù)測(cè)到。約束條件通過函數(shù)的多值依賴和連接依賴及范式完成。,4.2 關(guān)系模式的規(guī)范化,二、第一范式：1NF定義4.5: 若R的每個(gè)分量都是不可分的數(shù)據(jù)項(xiàng)，則R∈1NF。 從型上看：不存在嵌套結(jié)構(gòu) 從值上看，不存在重復(fù)組 1NF是關(guān)系模式的最低要求。例：學(xué)生關(guān)系S(S#，SNAME，CLASS，C#，TNAME，TAGE，ADDRESS，GRADE)是1NF關(guān)系，

17、但它存在數(shù)據(jù)冗余，插入異常和刪除異常等問題。,4.2 關(guān)系模式的規(guī)范化,三、第二范式： 2NF 定義4.6 若R∈1NF，且R中的每一個(gè)非主屬性都完全函數(shù)依賴于R的任一候選碼，則R∈2NF。例：學(xué)生關(guān)系S(S#，SNAME，CLASS，C#，TNAME，TAGE，ADDRESS，GRADE),判斷R是否為2NF?侯選碼為(S#，C#)，非主屬性有：SNAME，CLASS，TNAME，TAGE，ADDRESS，GRADE

18、(S#，C#)－>SNAME， S# －> SNAME (S#，C#) P >SNAME S?2NF(每一個(gè)非主屬性!)。,4.2 關(guān)系模式的規(guī)范化,分解為2NF的方法：破壞部分依賴的條件。 將滿足部分函數(shù)依賴和滿足完全函數(shù)依賴的屬性分解到不同的關(guān)系中。對(duì)上例，考察非主屬性和侯選碼之間的函數(shù)依賴關(guān)系：(S#，C#) P >SNAME， (S#，C#) P &

19、gt;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#，

20、TNAME，TAGE，ADDRESS) （只依賴C#的屬性分解到另一個(gè)子模式中）SC(S#，C#，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ù)存

21、儲(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ì)丟失該課程任課教師的姓名、年齡和地址信息。,4.2 關(guān)系模式的規(guī)范化,四、第三范式： 3NF定義4.7 如果關(guān)系R的任意一個(gè)非主屬性都不傳遞函數(shù)依賴于它的任意一個(gè)候選碼，則R∈3NF。關(guān)系C

22、TA(C#，TNAME，TAGE，ADDRESS)是2NF，但不是3NF。候選碼：C#，非主屬性：TNAME、TAGE、ADDRESS。 由于C#→TNAME，TNAME+>C#，TNAME→TAGE，所以 C# T >TAGE ，同樣有C# T >ADDRESS，即存在非主屬性對(duì)候選碼的傳遞函數(shù)依賴。,關(guān)系模式R（A，B，C，D），碼為AB，給出它的一個(gè)函數(shù)依賴集，使得R屬于2NF而不屬于

23、3NF,4.2 關(guān)系模式的規(guī)范化,分解為3NF的方法：破壞傳遞依賴的條件。 將涉及傳遞函數(shù)依賴中的兩個(gè)依賴中的屬性分解到不同的關(guān)系中。例：CTA中，兩個(gè)傳遞依賴C# T >TAGE ，C# T >ADDRESS C#→TNAME，TNAME+>C#，TNAME→TAGE。 C#→TNAME，TNAME+>C#，TNAME→ADDRESS。 將CTA分解為： CT(C#，T

24、NAME) 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è)R∈3NF，但R?2NF，則R中必有非主屬性A、侯選碼X和X的真子集X‘存在，使得X’→A。X’是侯選碼X的真子集，有X-X‘≠ф；A是非主屬性，A-X≠ф，A

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

26、生選修某個(gè)教師的課就確定了所選課的名稱 ：,4.2 關(guān)系模式的規(guī)范化,解：關(guān)系SCT的侯選碼：(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è)新課程和任課教師

27、的數(shù)據(jù)，在沒有學(xué)生選課時(shí)不能插入數(shù)據(jù)庫。刪除異常。例如，刪除某門課的所有選課記錄，會(huì)丟失課程與教師的數(shù)據(jù)。達(dá)到3NF的關(guān)系仍然可能存在問題。,4.2 關(guān)系模式的規(guī)范化,五、BCNF 定義4.8 關(guān)系模式R∈1NF。若函數(shù)依賴集合F中的所有函數(shù)依賴X→Y（Y不包含于X）的左部都包含R的任一侯選碼，則R∈BCNF。 換言之，BCNF中的所有依賴的左部都必須包含候選碼。 例：關(guān)系SCT是否BCNF? 因?yàn)門NAME→CNA

28、ME，其左部未包含該關(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#，C

29、NAME，TNAME)，F(xiàn)D: TNAME→CNAME。 可分解為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，即X→Y(Y不包含于X)，Y+>X，Y

30、→A。 這就是說Y不包含R的候選碼，但Y→A卻成立。 根據(jù)BCNF定義可知，R不是BCNF，與題設(shè)矛盾。結(jié)論3：任何的二元關(guān)系必定是BCNF。,4.2 關(guān)系模式的規(guī)范化,3NF下仍然存在插入異常和刪除異常， 原因在于可能存在主屬性對(duì)候選碼的部分函數(shù)依賴和傳遞函數(shù)依賴。一個(gè)模式中的關(guān)系模式如果都屬于BCNF，則在函數(shù)依賴的范疇內(nèi)實(shí)現(xiàn)了徹底的分離，已消除了插入和刪除的異常。其它問題？,4.2 關(guān)系模式的規(guī)范化,六、第

31、四范式：4NF定義4.10 若R∈ 1NF，D是R上的依賴集，如果對(duì)于任何一個(gè)多值依賴X??Y (Y-X≠ф,XY沒有包含R的全部屬性)，X都包含了R的一個(gè)候選關(guān)鍵詞，則R∈4NF。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ī)范化,

32、關(guān)系的規(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

33、是關(guān)系模式R的函數(shù)依賴集，X、Y是R的屬性子集，如果從F的函數(shù)依賴中能夠推出X?Y，則稱F邏輯蘊(yùn)涵X?Y。在R 中為F所邏輯蘊(yùn)含的函數(shù)依賴全體叫F的閉包，記為：F+。 F+={ ① F； ② F中推出的非平凡的函數(shù)依賴； ③平凡的函數(shù)依賴：A->φ、A->A、AB-> A….. } 例：有關(guān)系模式R(A，B，C)，它的函依賴集F={A→B，B→C}，計(jì)算F的閉包

34、。,4.3 數(shù)據(jù)依賴的公理系統(tǒng),Armstrong公理(阿氏公理)： 對(duì)R 有：A1自反律：若Y?X ，則X?Y。A2增廣律：若X?Y，則XZ?YZ。A3傳遞律：若X?Y、Y?Z，則X?Z。Note：XY與YX的次序無關(guān)。,4.3 數(shù)據(jù)依賴的公理系統(tǒng),證：設(shè)s，t是r的任意兩個(gè)元組，r是R的任意一個(gè)關(guān)系。A1自反律：若Y?X ，則X?Y。 若s[x]=t[x]，則在s和t中的x的任何子集也必相等。 ∵ Y

35、?X，∴ s[y]=t[y] ∴ X?Y。A2增廣律：若X?Y，則XZ?YZ。 若s[xz]=t[xz]，即s[x]s[z]=t[x]t[z] 則 s[x]=t[x] 且 s[z]=t[z] ∵ X?Y， ∴ s[y]=t[y] ∴ s[yz]=s[y]s[z]=t[y]t[z]=t[yz] ∴ XZ?YZ,4.3 數(shù)據(jù)依賴的公理系統(tǒng),A3傳遞律：若X?Y、Y?Z，則X?Z。 若s[x]=t[x]

36、 ∵ X?Y ∴ s[y]=t[y] 又∵ Y?Z ∴ s[z]=t[z] ∴ X?Z。,4.3 數(shù)據(jù)依賴的公理系統(tǒng),公理的推論： 合并規(guī)則：若X?Y 、 X?Z，則X?YZ。 分解規(guī)則：若X?YZ，則X?Y,X?Z。 偽傳遞規(guī)則：若X?Y 、WY?Z，則WX?Z。 證明：合并規(guī)則：∵ X?Y ∴ X?XY (A2)

37、又∵ X?Z ∴ XY?YZ (A2) ∴ X?YZ (A3),4.3 數(shù)據(jù)依賴的公理系統(tǒng),分解規(guī)則： ∵ Y?Y Z ∴ YZ?Y (A1) 又∵ X?YZ(已知） ∴ X?Y (A3) 同理可證X?Z。偽傳遞規(guī)則：∵ X?Y ∴ WX?WY (A2)

38、 又∵ WY?Z (已知) ∴ WX?Z (A3)定理4.5: X?A1A2…AK成立的充分必要條件是X?Ai成立。,由合并律 ?由分解律 ?,4.3 數(shù)據(jù)依賴的公理系統(tǒng),定義4.14: XF+={A|X?A能由F用阿氏公理導(dǎo)出} XF+稱為屬性集X關(guān)于F的閉包。定理4.6： X?Y能從F中用阿氏公理導(dǎo)出的充要條件是：Y?XF+,4.3

39、 數(shù)據(jù)依賴的公理系統(tǒng),定理4.6的證明證明： 充分性（ Y?XF+ -> X?Y） 假設(shè)Y?XF+ (其中Y=A1A2…An ) 由屬性閉包定義可知， X?A1， X?A2…， X?An能由阿氏公理導(dǎo)出，再由合并規(guī)則得X? A1A2…An，即X?Y。,4.3 數(shù)據(jù)依賴的公理系統(tǒng),必要性：（ X?Y -> Y?XF+ ） 假設(shè)X?Y能由阿氏公理導(dǎo)出(Y=A1A2…An)

40、 則有X?A1A2…An 由分解規(guī)則得： X?A1， X?A2…， X?An 由XF+的定義可知，Ai? XF+ (i=1,2,…,n) 即Y?XF+ 。,Armstrong公理系統(tǒng),Armstrong公理完備性的證明證明：（構(gòu)造性證明）用反證法假定存在函數(shù)依賴X?Y被F邏輯蘊(yùn)涵，但X?Y不能用Armstrong公理從F中導(dǎo)出由引理二，構(gòu)造R(U)上的關(guān)系r如下：下面證明

41、（1）r滿足F，（2）r不滿足X?Y,Y ? ，?Y? ≠ ?， U ? ≠ ?,4.3 數(shù)據(jù)依賴的公理系統(tǒng),2. 屬性閉包的計(jì)算算法4.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 ，且Y?X(i)； 求得X(i+1)

42、 后，對(duì)Y->A 做刪除標(biāo)記。 (3)若X(i+1)=X(i) 或 X(i+1) =U則結(jié)束，否則轉(zhuǎn)(2)。,最多|U-X|步,閉包的計(jì)算,示例1R, U = (A, B, C, G, H, I), F = {A?B, A?C, CG?H, CG?I, B?H},計(jì)算 所用依賴 A?BAGB A?CAGBC CG?HAGBCH

43、 CG?IAGBCH I= AGBCH I,,閉包的計(jì)算,示例2R, U = (A, B, C, D, E), F = {AB?C, B?D, C?E, CE?B, AC?B},計(jì)算所用依賴 AB?CABC B?DABCD C?EABCDE= ABCDE,,閉包的計(jì)算,示例3R, U = (A, B, C, D, E,

44、G), F = {A?E, BE?AG, CE?A, G?D},計(jì)算所用依賴 A?EABE BE?AGABEG G?DABEGD= ABEGD,,4.3 數(shù)據(jù)依賴的公理系統(tǒng),3.函數(shù)依賴集的等價(jià)和覆蓋定義4.15 : 如果F+=G+ ，就說函數(shù)依賴集F覆蓋G或F與G等價(jià)。定理4.9: F+=G+ 的充分必要條件是F?G+，和G?F+。（1）必

45、要性∵F和G等價(jià)，∴F+=G+，又∵F?F+，∴F?G+同理，∵G?G+，∴G?F+。（2）充分性任取X→Y∈F+，則有Y?XF+ (定理4.6)又∵F?G+（已知），∴Y?XG++∴X→Y∈(G+)+=G+，∴F+?G+。同理可證G+?F+，∴F+=G+，即F和G等價(jià)。,4.3 數(shù)據(jù)依賴的公理系統(tǒng),如何判斷函數(shù)依賴集F和G是否等價(jià)？根據(jù)定理4.9: 只需F?G+和G?F+，即證集合的包含關(guān)系。 對(duì)每個(gè)T ∈

46、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={A→B，B→C}，G={A→BC，B→C}，判斷F和G是否等價(jià)。解：（1）先檢查F中的每一個(gè)函數(shù)依賴是否屬于G+。 ∵AG+=ABC，∴B?AG+，∴A→B∈G+ (定理4.6) 又∵BG+=BC，∴

47、C?BG+，∴B→C∈G+ ∴F?G+ （2）然后檢查G中的每一個(gè)函數(shù)依賴是否屬于F+。 ∵AF+=ABC，∴BC?AF+，∴A→BC∈F+ 又∵BF+=BC，∴C?BF+，∴B→C∈F+ ∴G?F+ 由（1）和（2）可得F和G等價(jià)。,4.3 數(shù)據(jù)依賴的公理系統(tǒng),4.最小函數(shù)依賴集定義4.16:若F滿足下列條件，則稱其為一個(gè)最小函數(shù)依賴集Fm。

48、 (1) F中每個(gè)函數(shù)依賴的右部都是單屬性； (2) 對(duì)于F的任一函數(shù)依賴X→A，F(xiàn)-{X→A}與F都不等價(jià)； (3) 對(duì)于F中的任一函數(shù)依賴X→A和X的真子集Z， (F-(X→A))U{Z→A}與F都不等價(jià)。,最?。海?）F中每個(gè)函數(shù)依賴的右部沒有多余的屬性； （2）F中不存在多余的函數(shù)依賴； （3）F中每個(gè)函數(shù)依賴的左部沒有多余的屬性。,4.3 數(shù)據(jù)依賴的公理系統(tǒng),定理4.10: 每

49、個(gè)F與Fm等價(jià)。如何求最小函數(shù)依賴集Fm？ (1)分解：使F中任一函數(shù)依賴的右部僅含有單屬性。 (2)刪除冗余的函數(shù)依賴： 方法：對(duì)F中任一X?A，在F-{X?A}中求X+， 若A?X+，則X?A為多余的。 (3)最小化左邊的多余屬性： 方法：對(duì)F中任一XY?A，在F中求X+， 若A?X+ ，則Y為多余的。 [ (4)

50、檢查：用公理或(2) ],4.3 數(shù)據(jù)依賴的公理系統(tǒng),例：設(shè)有F={B→C，C→AB，BC→A}，求與F等價(jià)的最小函數(shù)依賴集。分解C→AB，F(xiàn)={B→C，C→A，C→B，BC→A}判斷B→C是否冗余，F(xiàn)’={C→A，C→B，BC→A} B+ = B, B→C非冗余。 F={B→C，C→A，C→B，BC→A} 判斷C→A是否冗余，F(xiàn)’={B→C, C→B，BC→A} C+ = ABC, C→A冗余。 F={B→C，

51、C→B，BC→A} 判斷C→B是否冗余，F(xiàn)’={B→C, BC→A} C+ = C, C→B非冗余。 F={B→C，C→B，BC→A} 判斷BC→A是否冗余，F(xiàn)’={B→C，C→B} BC+ = BC, BC→A非冗余。F={B→C，C→B，BC→A}判斷BC→A。 B+ = ABC, A?B+ ，則C在BC→A中是多余的。 Fmin={B→C，C→B，B→A},注意：對(duì)當(dāng)前F求閉包,4.3 數(shù)據(jù)依賴的公

52、理系統(tǒng),例：設(shè)有函數(shù)依賴集F={A→B,ABCD→E,EF→G,EF→H,ACDF→EG} 求與F等價(jià)的最小函數(shù)依賴集。注意：一個(gè)函數(shù)依賴集的最小集不是惟一的。例如，F(xiàn)={A→B，B→A，B→C，A→C，C→A} Fm1={A→B，B→C，C→A}， Fm2={A→B，B→A，A→C，C→A}。方法1： 無多余屬性；依次判斷B->A, A->C是否冗余；方法2： 無多余屬性

53、；依次判斷B->C是否冗余。,Fmin = {A→B,ACD→E, EF→G,EF→H},4.4 關(guān)系模式的分解,對(duì)于存在數(shù)據(jù)冗余、插入異常、刪除異常的關(guān)系模式，可以通過對(duì)關(guān)系模式的分解來解決問題。關(guān)系模式分解后會(huì)帶來兩個(gè)問題：（1）查詢時(shí)的連接操作是否會(huì)丟失某些信息或多出某些信息。這引出了無損連接的概念。（2）分解后的關(guān)系模式是否保持了原來的函數(shù)依賴。這是保持函數(shù)依賴性的問題。,4.4 關(guān)系模式的分解,1. 等價(jià)模式分解

54、的定義 一個(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

55、, 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.無損連接性與依賴保持性 對(duì)于R中任何一個(gè)關(guān)系r，R分解ρ={R1, R2….RK}無損連接性： r=ΠR1(r) ? ΠR2(r) ? … ? ΠRK(r)保持函數(shù)依賴： F ≡ ΠR1(F)∪ΠR2(F)∪… Π

56、RK(F) ΠRi(F)={X->Y| X->Y∈F+∧XY?Ri },,,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: F≡ΠAB(F)∪ΠAC(F)

57、 = {A->B，A->C} 具有函數(shù)依賴保持性。,r,?ρ={AB，BC},4.4 關(guān)系模式的分解,算法4.3 無損連接性檢驗(yàn)。 輸入：關(guān)系模式R(A1，A2，…，An)，它的函數(shù)依賴集F，以及分解ρ={R1，R2，…，Rk}。 輸出：確定ρ是否具有無損連接性。方法：(1)構(gòu)造一個(gè)k行n列的表，第i行對(duì)應(yīng)于關(guān)系模式Ri，第j列對(duì)應(yīng)于屬性Aj。如果Aj∈Ri，則在第i行第

58、j列上放符號(hào)aj，否則放符號(hào)bij。（屬于用a代表，且位置信息用j表示；不屬于用b代表,且位置信息用ij表示。） (2)重復(fù)考察F中的每一個(gè)函數(shù)依賴，并修改表中的元素。其方法如下：取F中一個(gè)函數(shù)依賴X→Y，在X的分量中尋找相同的行，然后將這些行中Y的分量改為相同的符號(hào)，如果其中有aj，則將bij改為aj；若其中無aj，則全部改為bij（i是這些行的行號(hào)最小值）。,4.4 關(guān)系模式的分解,(3)如果發(fā)現(xiàn)表中某一行變成了al

59、，a2，…，an，則分解ρ 具有無損連接性；如果F中所有函數(shù)依賴都不能再修改 表中的內(nèi)容，且沒有發(fā)現(xiàn)這樣的行，則分解ρ不具有無 損連接性。,無損連接分解,示例一：U={A,B,C,D,E}, F={AB?C, C?D,D?E}? ={(A, B, C), (C, D), (D, E)},AB?C,C?D,D?E,,,4.4 關(guān)系模式的分解,示例二：U={A,B,C,D,E}, F={A?C, B?C, C?D,DE

60、?C ,CE?A}? ={(A, D), (A, B), (B, E), (C, D, E), (A, E)},A?C,,,4.4 關(guān)系模式的分解,B?C,,C?D,,,,4.4 關(guān)系模式的分解,DE?C,,,CE?A,,,4.4 關(guān)系模式的分解,定理4.12 設(shè)ρ=(R1，R2)是R的一個(gè)分解，F(xiàn)是R上的函數(shù) 依賴集，分解ρ具有無損連接性的充分必要條件是： R1∩R2→(R1-R2)∈F+

61、 或 R1∩R2→(R2-R1)∈F+證明： （1）充分性：設(shè)R1∩R2→(R1-R2)，按算法5.2可構(gòu)造出下表。表中省略了a和b的下標(biāo)，這無關(guān)緊要。,只能用于判斷分解為2個(gè)子模式的情況。,4.4 關(guān)系模式的分解,如果R1∩R2→(R1-R2)在F中，則可將表中第2行位于(R1-R2)列 中的所有符號(hào)都改為a，這樣該表中第2行就全是a了，則ρ具有無 損連接性。同理可證R1∩R2→(R2-R1)的情況。 如果R

62、1∩R2→(R1-R2)不在F中，但在F+中，即它可以用公理從 F中推出來，從而也能推出R1∩R2→Ax, 其中Ax?R1-R2，所以可 以將Ax列的第2行改為全a，同樣可以將R1-R2中的其他屬性的第2 行也改為a，這樣第2行就變成全a行。所以分解ρ={R1，R2}具有 無損連接性。 同樣可以證明R1∩R2→(R2-R1)的情況。 （2）必要性：設(shè)構(gòu)造的表中有一行全為a，例如第1行全為a，則 由函數(shù)依賴定

63、義可知R1∩R2→(R2-R1)；如果是第2行全為a，則 R1∩R2→(R1-R2)。定理證畢。,4.4 關(guān)系模式的分解,例:下列分解是否具有無損連接性和函數(shù)依賴保持性。 已知：R(A,B,C) F={A→B，C→B} (1）ρ1={AB，BC}（2）ρ2={AC，BC},4.4 關(guān)系模式的分解,（1）對(duì)ρ1和F構(gòu)造表：,（2）檢查F={A→B，C→B} 對(duì)A→B，A列中無相同的行； 對(duì)C→B, C列中無相同

64、的行。 ρ1不具有無損連接性。,ρ1={AB，BC} F={A→B，C→B},4.4 關(guān)系模式的分解,ρ1={AB，BC} F={A→B，C→B} 利用定理4.12解。 R1∩R2 = B (R1-R2) = A R1∩R2 +> (R1-R2) ρ1不是無損連接分解。,4.4 關(guān)系模式的分解,ρ2={AC，BC} F={A→B，C→B},對(duì)ρ2和F構(gòu)造表：,檢查F={A→B，C

65、→B} 對(duì)C→B, C列有相同的行，改寫B(tài)列的相異符號(hào)為a，下標(biāo)為列號(hào)2。第一行變?yōu)閍1a2a3,ρ2具有無損連接性。,4.4 關(guān)系模式的分解,ρ2={AC，BC} F={A→B，C→B}利用定理4.12解。 R1∩R2 = C (R1-R2) = A；(R2-R1) = B； R1∩R2 +> (R2-R1) ρ2是無損連接分解。,4.4 關(guān)系模式的分解,3. 模式分解的方法3NF的保持無損

66、連接及函數(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)系模式的

67、分解,BCNF的保持無損連接的分解：（1）令ρ={R}；（2）如果ρ中所有關(guān)系模式都是BCNF，則轉(zhuǎn)（4）；（3）如果ρ中有一個(gè)關(guān)系模式Ri不是BCNF，則Ri中必有X→A∈Fi+(A?X)，且X不是Ri的碼。設(shè)S1=XA，S2=Ui-A，用分解{S1，S2}代替Ri，轉(zhuǎn)（2）；（4）分解結(jié)束，輸出ρ。例：設(shè)R={A,B,C,D},F={A→C，C→A，B→AC，D→AC，BD→A} （1）將R 分解為3NF且具有無損連接

68、性和依賴保持性。 （2）將R 分解為BCNF且具有無損連接性。,關(guān)系模式的分解算法,示例：U={S#，SD，MN，C#，G}F={S#?SD，S#?MN，SD?MN，(S#,C#)?G}⒈U1={S#，SD} , F1={S#?SD} U2={S#, MN, C#, G}, F2={S#?MN, (S#,C#)?G}⒉U1 = {S#, SD}, F1={S#?SD} U2 = {S#, MN}, F2={S#

69、?MN} U3 = {S#, C#, G}, F3 = {(S#,C#)?G},4.4 關(guān)系模式的分解,關(guān)系模式CTHRSG，其中C表示課程，T表示教師，H表示時(shí)間，R表示教室，S表示學(xué)生，G表示成績。函數(shù)依賴集F及其所反映的語義分別為： C?T 每門課程僅有一位教師擔(dān)任。 HT?R 在任一時(shí)間，一個(gè)教師只能在一個(gè)教室上課。 HR?C 在任一時(shí)間，每個(gè)教室只能上一門課。 HS?R 在任一時(shí)間