1、第五章 關(guān)系數(shù)據(jù)理論 5.2 規(guī)范化十、規(guī)范化舉例例1：設(shè)有關(guān)系模式R（職工編號(hào)，日期，日營(yíng)業(yè)額，部門(mén)名，部門(mén)經(jīng)理），該關(guān)系模式統(tǒng)計(jì)商店里每個(gè)職工的日營(yíng)業(yè)額，以及職工所在的部門(mén)和經(jīng)理信息。 如果規(guī)定：每個(gè)職工每天只有一個(gè)營(yíng)業(yè)額；每個(gè)職工只在一個(gè)部門(mén)工作；每個(gè)部門(mén)只有一個(gè)經(jīng)理。 試回答下列問(wèn)題： （1）根據(jù)上述規(guī)定，寫(xiě)出模式R的基本FD和候選碼； （2）說(shuō)明R不是2NF的理由，并把R分解成2NF模式集； （3）進(jìn)而分解成3NF模式集。 解： （1）基本的FD有3個(gè)：（職工編號(hào)，日期） 日營(yíng)業(yè)額 職工編號(hào) 部門(mén)名 部門(mén)名 部門(mén)經(jīng)理 R的候選碼為（職工編號(hào)，日期）。第五章 關(guān)系數(shù)據(jù)理論 5.2 規(guī)范

2、化 （2）R中存在非主屬性“部門(mén)名”對(duì)碼（職工編號(hào)，日期）的部分依賴(lài)，所以R不是2NF模式。 R應(yīng)分解成R1（職工編號(hào)，日期，日營(yíng)業(yè)額） R2（職工編號(hào)，部門(mén)名，部門(mén)經(jīng)理） 這里，R1和R2都是2NF模式。（3）R1已是3NF模式。 在R2中存在兩個(gè)FD：職工編號(hào) 部門(mén)名， 部門(mén)名 部門(mén)經(jīng)理 因此，R2中存在非主屬性“部門(mén)經(jīng)理”對(duì)碼“職工編號(hào)” 的傳遞依賴(lài)，R2不是3NF模式。 將R2分解成R2l（職工編號(hào)，部門(mén)名） R22（部門(mén)名，部門(mén)經(jīng)理） 這樣= R1, R21, R22 是一個(gè)3NF模式集。第五章 關(guān)系數(shù)據(jù)理論 5.2 規(guī)范化例2：設(shè)有關(guān)系模式STUDENT( S#,SName,Ter

3、m_Address, Faculty, Faculty_Head，UNIT#,Unit_Name,Result )，試將該關(guān)系模式分解到3NF。解：基本FD有4個(gè)： S# SName,Term_Address,Faculty Faculty Faculty_Head UNIT# Unit_Name S#,UNIT# Result 所以碼為(S#,UNIT#) 2NF 消除部分依賴(lài) RESULT(S#,UNIT#,Result) UNIT(UNIT#,Unit_Name) STUDENT(S#,SName,Term_Address,Faculty, Faculty_Head) 3NF 消除傳遞依

4、賴(lài) RESULT關(guān)系和UNIT關(guān)系同上，而STUDENT分解為： STUDENT(S#,SName,Term_Address,Faculty) FACULTY(Faculty, Faculty_Head) 這樣=RESULT, UNIT, STUDENT, FACULTY 是一個(gè)3NF模式集。第五章 關(guān)系數(shù)據(jù)理論 5.3 數(shù)據(jù)依賴(lài)的公理系統(tǒng)三、求關(guān)系模式的候選碼 1、方法：求出關(guān)系模式R(U, F)的屬性集U所有可能的真子集X關(guān)于函數(shù)依賴(lài)集F的屬性集閉包XF+ ，若有U XF+ 且X的任何一個(gè)真子集Y的YF+, 有U YF+, 則X為一候選碼。 2、舉例例1：設(shè)有關(guān)系模式R(U, F)，U=A

5、,B,C,D, F=AB, BC 求R的所有候選碼。解：AF+=ABC, BF+=BC, CF+=C, DF+=D (AB)F+=(AC)F+=ABC, (AD)F+=ABCD, (BC)F+=BC, (BD)F+=BCD, (CD)F+=CD (ABC)F+=ABC, (BCD)F+=BCD, (ACD)F+=(ABD)F+= ABCD , 故R只有一個(gè)候選碼AD第五章 關(guān)系數(shù)據(jù)理論 5.3 數(shù)據(jù)依賴(lài)的公理系統(tǒng)例2：設(shè)有關(guān)系模式W(U, F)，U=C, T, H, R, S, G, 這些屬性 分別表示課程名、任課教師、上課時(shí)間、上課教室、學(xué)生姓名、成績(jī)，F(xiàn)=CT,CSG,HRC,HTR,HS

6、R 求R的所有候選碼。解：CF+=CT,TF+=T,HF+=H,RF+=R,SF+=S,GF+=G (CT)F+=CT, (CH)F+=CTHR, (CR)F+=CTR, (CS)F+=CTSG, (CG)F+=CTG, (TH)F+=THRC, (TR)F+=TR, (TS)F+=TS, (TG)F+=TG, (HR)F+=HRCT, (HS)F+=CTHRSG, (HG)F+=HG, (RS)F+=RS, (RG)F+=RG, (SG)F+=SG, (CTH)F+=(THR)F+=CTHR, (CTR)F+=CTR, (CTS)F+=CTS, (CTG)F+=CTG, (THS)F+=(H

7、RS)F+=CTHRSG,(THG)F+=(HRG)F+=THRCG, (RSG)F+=RSG, (CTHR)F+=CTHR, (CTHS)F+=(THRS)F+=(HRSG)F+=CTHRSG, (CTHG)F+=(THRG)F+=CTHRG, 故R只有一個(gè)候選碼HS第五章 關(guān)系數(shù)據(jù)理論 5.3 數(shù)據(jù)依賴(lài)的公理系統(tǒng)候選碼的求解理論和算法 對(duì)于給定的關(guān)系R(U, F)，可將其屬性分為四類(lèi)： L類(lèi)：僅出現(xiàn)在函數(shù)依賴(lài)集F的左部的屬性。 R類(lèi)：僅出現(xiàn)在函數(shù)依賴(lài)集F的右部的屬性。 LR類(lèi)：在函數(shù)依賴(lài)集F的左右兩邊均出現(xiàn)的屬性。 N類(lèi)：在函數(shù)依賴(lài)集F的左右兩邊均未出現(xiàn)的屬性?？焖偾蠼夂蜻x碼的一個(gè)充分條件

8、： 定理1：對(duì)于給定的關(guān)系模式R(U, F)，若 X(X U)是R的L類(lèi)屬性，則X必為R的任一候選碼中的屬性。 例3：設(shè)有關(guān)系模式R(U, F)，U=A, B, C, D，F(xiàn)=DB, BD, ADB, ACD，求R的所有候選碼。 解：考察F發(fā)現(xiàn)，A、C兩屬性是R的L類(lèi)屬性，由定理1可知，AC必是R的任一候選碼中的屬性，又(AC)關(guān)于F的閉包ABCD，AC是R的唯一候選碼。第五章 關(guān)系數(shù)據(jù)理論 5.3 數(shù)據(jù)依賴(lài)的公理系統(tǒng) 例4：重做例2 W(U, F)，U=C, T, H, R, S, G, 這些屬性分別表示課程名、任課教師、上課時(shí)間、上課教室、學(xué)生姓名、成績(jī)，F(xiàn)=CT,CSG,HRC,HTR,

9、HSR 解：考察F發(fā)現(xiàn)，H、S兩屬性是R的L類(lèi)屬性，由定理1可知，HS必是R的任一候選碼中的屬性，又(HS)關(guān)于F的閉包CTHRSG，HS是R的唯一候選碼。 推論1：對(duì)于給定的關(guān)系模式R(U, F)，若 X(X U)是L類(lèi)屬性，且X包含了R的全部屬性，則X必為R的唯一候選碼。 定理2：對(duì)于給定的關(guān)系模式R(U, F)，若 X(X U)是R的R類(lèi)屬性，則X必不在R的任一候選碼中。第五章 關(guān)系數(shù)據(jù)理論 5.3 數(shù)據(jù)依賴(lài)的公理系統(tǒng)定理3：對(duì)于給定的關(guān)系模式R(U, F)，若 X(X U)是R的N類(lèi)屬性，則X必為R的任一候選碼中的屬性。例5：設(shè)有關(guān)系模式R(U, F)，U=A, B, C, D, E,

10、 P，F(xiàn)=AD，ED，DB，BCD，DCA，求R的所有候選碼。 解：考察F發(fā)現(xiàn)，C、E兩屬性是R的L類(lèi)屬性，故CE必是R的任一候選碼中的屬性，又P是N類(lèi)屬性，故P也必是R的任一候選碼中的屬性。再(CEP)關(guān)于F的閉包=ABCDEP，CEP是R的唯一候選碼。 推論2：對(duì)于給定的關(guān)系模式R(U, F)，如果X是R的N類(lèi)和L類(lèi)組成的屬性集，且X關(guān)于F的閉包包含了R的全部屬性，則X是R的唯一候選碼。第五章 關(guān)系數(shù)據(jù)理論 5.4 模式的分解 模式分解（等價(jià)）的三個(gè)定義 (1) 分解應(yīng)具有“無(wú)損連接性” (2) 分解要“保持函數(shù)依賴(lài)” (3) 分解既要“保持函數(shù)依賴(lài)”，又要具有“無(wú)損連接性”二、分解的無(wú)損

11、連接性 1、記號(hào)和引理 設(shè)=R1(U1, F1), , Rk(Uk, Fk)是關(guān)系模式R(U, F)的一個(gè)分解，r是R(U, F)的一個(gè)關(guān)系，則記m(r) =R1(r) R2(r) , ,Rk(r) , 即m(r) 是r在中各關(guān)系模式上投影的連接。 Ri (r) =t.Ui|tr。 引理：設(shè)=R1(U1, F1), , Rk(Uk, Fk)是關(guān)系模式R(U, F)的一個(gè)分解，r是R的一個(gè)關(guān)系，若記s=m(r) , ri=Ri (r), 則有： （1）r m(r) （2）Ri (s) =ri （3）m(m(r) = m (r)第五章 關(guān)系數(shù)據(jù)理論 5.4 模式的分解2、定義: =R1(U1, F

12、1), , Rk(Uk, Fk)是R(U, F)的一個(gè)分解，若對(duì)R(U, F)上的任何一個(gè)關(guān)系r 均有r =m(r) 成立，則稱(chēng)分解具有無(wú)損連接性。 舉例：（1）設(shè)有關(guān)系模式R(U, F), U=A,B,C, F=AC R的一個(gè)分解為R1(A, B), R2(A, C) r A B C r1 A B r2 A C 1 1 1 1 1 1 1 1 2 1 1 2顯然 r= r1 r2, 分解具有無(wú)損連接性 （2）設(shè)有關(guān)系模式R(U, F), U=A,B,C, F=BC R的一個(gè)分解為R1(A, B), R2(A, C) r A B C r1 A B r2 A C 1 1 4 1 1 1 4 1

13、2 3 1 2 1 3顯然 r r1r2, 分解不具有無(wú)損連接性(多出二個(gè)元組，注意多了反而是丟失了信息)第五章 關(guān)系數(shù)據(jù)理論 5.4 模式的分解 3、評(píng)定算法：（教科書(shū)P.190 通過(guò)舉例說(shuō)明該算法） 例1：已知R(U, F), U=A,B,C,D,E, F=ABC,CD,DE R的一個(gè)分解為R1(A, B, C), R2(C, D), R3(D, E) 。 (1) 首先構(gòu)成初始矩陣 A B C D E R1(A, B, C) a1 a2 a3 b14 a4 b15 a5 R2(C, D) b21 b22 a3 a4 b25 a5 R3(D, E) b31 b32 b33 a4 a5 (2)

14、 按照函數(shù)依賴(lài)對(duì)初始矩陣進(jìn)行變換，由CD可以把 b14改為a4, 再由DE使得b15 ，b25全改為a5.。因?yàn)榈?行 成為全a, 所有分解具有無(wú)損連接性。第五章 關(guān)系數(shù)據(jù)理論 5.4 模式的分解例2：已知R(U, F), U=A,B,C,D,E, F=AC, BC, CD,DEC,CEA R的一個(gè)分解為: R1(A, D), R2(A, B), R3(B, E), R4(C, D, E), R5(A, E) 。 (1) 首先構(gòu)成初始矩陣 A B C D E R1(A, D) a1 b12 b13 a4 b15 R2(A, B) a1 a2 b23 b24 b25 R3(B, E) b31 a

15、2 b33 b34 a5 R4(C, D, E) b41 b42 a3 a4 a5 R5(A, E) a1 b52 b53 b54 a5第五章 關(guān)系數(shù)據(jù)理論 5.4 模式的分解 (2) 根據(jù)函數(shù)依賴(lài)AC和BC對(duì)初始矩陣進(jìn)行變換 A B C D E R1(A, D) a1 b12 b13 a4 b15 R2(A, B) a1 a2 b23 b13 b24 b25 R3(B, E) b31 a2 b33 b13 b34 a5 R4(C, D, E) b41 b42 a3 a4 a5 R5(A, E) a1 b52 b53 b13 b54 a5 (3) 根據(jù)函數(shù)依賴(lài)CD、DEC和CEA繼續(xù)進(jìn)行變換

16、A B C D E R1(A, D) a1 b12 b13 a4 b15 R2(A, B) a1 a2 b13 b24 a4 b25 R3(B, E) b31 a1 a2 b13 a3 b34 a4 a5 R4(C, D, E) b41 a1 b42 a3 a4 a5 R5(A, E) a1 b52 b13 a3 b54 a4 a5 因?yàn)榈?行成為全a, 所有分解具有無(wú)損連接性。第五章 關(guān)系數(shù)據(jù)理論 5.4 模式的分解 4、 R(U, F)的一個(gè)分解=R1(U1, F1), R2(U2, F2)具有 無(wú)損連接性的充要條件是： U1 U2 U1 U2F+ 或 U1 U2 U2 U1F+證明： U

17、1 U2 U1 U2 U2 U1 U1 aaa aaa bbb U2 aaa bbb aaa 證畢 5、對(duì)引理的一點(diǎn)說(shuō)明 如果首先不提 r的存在性，而先說(shuō)存在一個(gè)r的分解=r1, r2, , rk)，則Ri (s)就未必與ri相等了。例如： r1 A B r2 B C r1 r2 A B C 1 1 1 3 1 1 3 2 4 = 懸掛元組 顯然BC(r1 r2)r2 （因?yàn)橛袘覓煸M）, 能存儲(chǔ)懸掛元組是模式分解的一大優(yōu)點(diǎn)（因?yàn)橄瞬迦氘惓＃┑谖逭?關(guān)系數(shù)據(jù)理論 5.4 模式的分解三、分解的保持函數(shù)依賴(lài)性 1、定義：若F+=( Fi)+, 則關(guān)系模式R(U, F)的分解=R1(U1, F1

18、), , Rk(Uk, Fk)保持函數(shù)依賴(lài) 2、令G= Fi, 則F+= G+的充要條件是F G+， G F+ 。 故要判斷一個(gè)分解是否保持函數(shù)依賴(lài)，需逐個(gè)驗(yàn)證F中的每個(gè)FD是否被G所邏輯蘊(yùn)含（多項(xiàng)式級(jí)時(shí)間）。 3、意義 ：如果某個(gè)分解能保持FD集，那么在數(shù)據(jù)輸入 或更新時(shí)，只要每個(gè)關(guān)系模式本身的FD約束被滿(mǎn)足，就可以確保整個(gè)數(shù)據(jù)庫(kù)中數(shù)據(jù)的語(yǔ)義完整性不受破壞。 例1：設(shè)有關(guān)系模式R(WNO, WS, WG), 其中WNO表示工號(hào)、WS表示工資級(jí)別、WG表示工資數(shù)目 FD有: WNOWS, WSWG, 若將R(WNO, WS, WG)分解第五章 關(guān)系數(shù)據(jù)理論 5.4 模式的分解為=R1(WNO,

19、 WS), R2(WNO, WG), 因?yàn)閁1U2 WNO U1U2WS，又WNOWS F+，根據(jù)三中4的充要條件，知道這個(gè)分解具有無(wú)損連接性。但從R1中的函數(shù)依賴(lài) WNOWS和R2中的函數(shù)依賴(lài)WNOWG，推不出R上成立的函數(shù)依賴(lài)WS WG，故該分解不保持函數(shù)依賴(lài)。 r1 WNO WS r2 WNO WG r1 r2 WNO WS WG W1 8級(jí) W1 2000 W1 8級(jí) 2000 W2 6級(jí)2400 W2 6級(jí) 2200 W3 6級(jí) W3 2400 W3 6級(jí) 2400 r1和r2分別滿(mǎn)足R1(F)和R2(F) ，但r1 r2違反了WS WG沒(méi)有保持FD的分解不是一種好的分解，即修改將不

20、獨(dú)立另外數(shù)據(jù)冗余也很大。造成上面的r1和r2，可能是在更新r1中的W2時(shí)，忘記了更新r2中的W2。第五章 關(guān)系數(shù)據(jù)理論 5.4 模式的分解 例2：設(shè)關(guān)系模式R(B#,BNAME,AUTHOR)中的屬性分別表示書(shū)號(hào)、書(shū)名和作者名。假定：(1)每個(gè)書(shū)號(hào)只有一個(gè)書(shū)名，但不同書(shū)號(hào)可以有相同書(shū)名，故B#BNAME ; (2) 每本書(shū)可以有多個(gè)作者合寫(xiě)，但每個(gè)作者參與編寫(xiě)的書(shū)的書(shū)名應(yīng)該互不相同，故(BNAME,AUTHOR)B# 。顯然R的候選碼有 (BNAME,AUTHOR)和 (B#,AUTHOR)，又因?yàn)橛蠪D B#BNAME，所以R不是BCNF。若將它分解為=R1(BNAME, B#), R2(A

21、UTHOR, B#), 盡管它們都是BCNF，且根據(jù)二中4的充要條件，可以證明這個(gè)分解具有無(wú)損連接性，但有可能引起新的問(wèn)題（主要是這個(gè)分解丟失了FD：(AUTHOR, BNAME) B# ）。 r1 BNAME B# r2 AUTHOR B# r1 r2 BNAME AUTHOR B# Maths 7-302 Wen 7-302 Maths Wen 7-302 Maths 8-304 Wen 8-304 Maths Wen 8-304 r1和r2分別滿(mǎn)足R1(F)和R2(F) ，但r1 r2違反了(AUTHOR, BNAME) B# 第五章 關(guān)系數(shù)據(jù)理論 5.4 模式的分解 注意：與例1不同的

22、是, 在例1中可將R分解為=R1(WNO, WS), R2(WS, WG), 做到既有無(wú)損連接性又保持函數(shù)依賴(lài) 但例2做不到既無(wú)損連接又保持函數(shù)依賴(lài)分解到BCNF。 例3：第2節(jié)中的STJ(S,T,J) 不是BCNF，若將它分解為ST(S,T)和TJ(T,J)，盡管它們都是BCNF，且可以證明分解具有無(wú)損連接性，但有可能引起新的問(wèn)題（主要是這個(gè)分解丟失了FD：(S, J) T ） r1 S T r2 T J r1 r2 S T J s1 LU LU DB s1 LU DB s1 LI LI DB s1 LI DBr1和r2分別滿(mǎn)足R1(F)和R2(F) ，但r1 r2違反了(S, J) T第五

23、章 關(guān)系數(shù)據(jù)理論 5.4 模式的分解 4、求函數(shù)依賴(lài)的投影假設(shè)把關(guān)系R分解為關(guān)系S和另一個(gè)關(guān)系，F(xiàn)是R中成立的函數(shù)依賴(lài)集，求S中成立的函數(shù)依賴(lài) 1) 方法：考慮包含于S的屬性集的每個(gè)屬性集X，計(jì)算XF+，于是對(duì)于滿(mǎn)足下列條件的每個(gè)屬性B，函數(shù)依賴(lài)XB在S中成立：1) B是S的一個(gè)屬性2) B屬于XF+，而且3) B不屬于X 2) 舉例例4：已知關(guān)系模式R(U, F), U=A,B,C,D, F=AB, BC S(A,C), 求S(A,C) (F)解：AF+=ABC 得AC，但CF+=C 得不出非平凡的FD (AC)F+=ABC 得不出非平凡的FD, 故S(A,C) (F)=AC第五章 關(guān)系數(shù)據(jù)

24、理論 5.4 模式的分解例5：設(shè)有關(guān)系模式W(U, F)，U=C, T, H, R, S, G, 這些屬性 分別表示課程名、任課教師、上課時(shí)間、上課教室、學(xué)生姓名、成績(jī)，F(xiàn)=CT,CSG,HRC,HTR,HSR將W分解為=S1(C, S, G),S2(C, T),S3(C, H, R),S4(C, H, S), 求F在各關(guān)系模式上的投影解：顯然有 S1(C,S,G) (F)=CSG S2(C,T) (F)=CT 再有 CF+=CT, HF+=H, RF+=R, (CR)F+=CTR, (CH)F+=CTHR 得CHR, (HR)F+=HRCT 得HRC, 故S3(C,H,R) (F)=CHR,

25、 HRC 最后有 CF+=CT, HF+=H, SF+=S, (CH)F+=CTHR, (CS)F+=CTSG, (HS)F+=CTHRSG 得HSC 故S4(C,H,S) (F)=HSC 該分解將HTR丟失了，但HSR沒(méi)有丟失，因?yàn)樗?從HSC和CHR中導(dǎo)出。第五章 關(guān)系數(shù)據(jù)理論 5.4 模式的分解 5、判分解是否保持函數(shù)依賴(lài)的算法 1) 求出函數(shù)依賴(lài)集在各上的投影Ri(F)，且令G= Ri(F) 2) 求出F=F-G 3) 求出F中各函數(shù)依賴(lài)決定因子X(jué)關(guān)于G的屬性集 閉包XG+ 4) 若對(duì)F中的每一個(gè)函數(shù)依賴(lài)XY，均有Y XG+ 則分解是保持FD的舉例：對(duì)前面的例5 G=CSG, CT, CHR, HRC, HSC F=THR, HSR 因?yàn)?R (TH)G+=TH 故這種分解