求候選碼的方法

1、第五章第五章 關(guān)系關(guān)系數(shù)據(jù)理論數(shù)據(jù)理論 數(shù)據(jù)庫系統(tǒng)概論數(shù)據(jù)庫系統(tǒng)概論26.2.2 碼碼(參見參見P173.P173.)定義定義5.45.4 設設K K為關(guān)系模式為關(guān)系模式RR的屬性的屬性( (組組) )， 若若K UK U，則稱則稱K K為為R R的的候選碼。候選碼。 f主碼主碼：若：若RR有多個候選碼，則可以從中選定一個作為有多個候選碼，則可以從中選定一個作為R R的主碼。的主碼。主屬性主屬性：包含在任一個候選碼中的屬性，稱作主屬性。：包含在任一個候選碼中的屬性，稱作主屬性。非主屬性非主屬性：不包含在任一個候選碼中的屬性，稱作非主屬性：不包含在任一個候選碼中的屬性，稱作非主屬性(或或非碼屬性

2、非碼屬性)。全碼全碼：關(guān)系模式的碼由全部屬性構(gòu)成。：關(guān)系模式的碼由全部屬性構(gòu)成。3碼碼: 例例n關(guān)系模式關(guān)系模式 S(S# , SN , SD , DEAN , C# , G) 碼的確定碼的確定(1) (1) 首先根據(jù)實際背景數(shù)據(jù)約束的語義確定關(guān)首先根據(jù)實際背景數(shù)據(jù)約束的語義確定關(guān)系模式系模式RR。(2) (2) 然后應用然后應用函數(shù)依賴的公理系統(tǒng)，驗證函數(shù)依賴的公理系統(tǒng)，驗證F F中中每一個函數(shù)依賴的決定因素或其組合每一個函數(shù)依賴的決定因素或其組合K K，是是否有否有: : K U K U。 f fn主碼主碼( (S#S#，C#)C#)，因為因為(S#(S#，C#) C#) 所有屬性所有屬性

3、4碼的確定碼的確定: 例例n求出關(guān)系模式求出關(guān)系模式RR的所有候選碼：的所有候選碼：nU= A , B , C , D , E U= A , B , C , D , E nF=ABC, BD, CE, ECB, ACB F=ABC, BD, CE, ECB, ACB n注注: : 碼或者是某一函數(shù)依賴的左部碼或者是某一函數(shù)依賴的左部, , 或是一個屬或是一個屬性組。性組。n驗證驗證AB是否碼是否碼, 須證明須證明 AB ABCDE是否成立是否成立?ABC(已知已知), 而而ABAB(自反自反), AB ABC(合并合并)BD(已知已知), ABAD(增廣增廣), AB ABCD(合并合并)CE

4、(已知已知), ABC(已知已知), AB E(傳遞傳遞) 于是于是 AB ABCDE(合并合并)f5碼的確定碼的確定: 例例(續(xù)續(xù))n驗證驗證ABAB是否碼是否碼? ? 前面已得到前面已得到 AB ABCDE， 又又, 顯然顯然 AABCDE, BABCDE, 故所以故所以AB ABCDE。得證得證AB是一個候選碼。是一個候選碼。n同理可證：同理可證：AC也是一個候選碼。也是一個候選碼。n說明：如果每一個說明：如果每一個FD的決定因素都不是碼，的決定因素都不是碼，則要考慮這些決定因素的組合是否構(gòu)成碼；則要考慮這些決定因素的組合是否構(gòu)成碼；除了碼的定義外，有候選碼的求解理論和算除了碼的定義外，

5、有候選碼的求解理論和算法，在后面可以補充介紹更好的求碼方法。法，在后面可以補充介紹更好的求碼方法。f6碼的確定碼的確定: 練習練習n根據(jù)碼的定義，求關(guān)系模式根據(jù)碼的定義，求關(guān)系模式R的所有候的所有候選碼。選碼。U= A , B , C , D ， F=A B, CB 答：答：ACD7關(guān)于關(guān)于2NF的結(jié)論的結(jié)論n1. 不存在非主屬性的關(guān)系模式屬于不存在非主屬性的關(guān)系模式屬于2NF。 n沒有非主屬性沒有非主屬性n2. 全碼關(guān)系模式屬于全碼關(guān)系模式屬于2NF。 n沒有非主屬性沒有非主屬性n3. 碼只由一個屬性組成的關(guān)系模式屬于碼只由一個屬性組成的關(guān)系模式屬于2NF。n不會有部分依賴不會有部分依賴n4

6、. 二目關(guān)系模式屬于二目關(guān)系模式屬于2NF。 n碼或是一個屬性，或是全碼碼或是一個屬性，或是全碼n5. 若若R屬于屬于1NF，但但R不一定屬于不一定屬于2NF。 n例如例如, 關(guān)系模式關(guān)系模式 S(S#, SN, SD, DEAN, C#, G)8關(guān)于關(guān)于3NF的結(jié)論的結(jié)論n1. 不存在非主屬性的關(guān)系模式屬于不存在非主屬性的關(guān)系模式屬于3NF。 n沒有非主屬性沒有非主屬性n2. 全碼關(guān)系模式屬于全碼關(guān)系模式屬于3NF。 n沒有非主屬性沒有非主屬性n3. 二目關(guān)系模式屬于二目關(guān)系模式屬于3NF。 n不會存在傳遞依賴不會存在傳遞依賴n4. 若若R屬于屬于3NF，那么那么R也屬于也屬于2NF。 n可

7、證明，反證可證明，反證n5. 若若R屬于屬于2NF，但但R不一定屬于不一定屬于3NF。 n例如，關(guān)系模式例如，關(guān)系模式 S_SD(S#, SN, SD, DEAN)9BCNF: 定義定義n定義定義5.85.8 關(guān)系模式關(guān)系模式R R 1NF1NF，對于屬，對于屬性組性組X X和和Y Y，若若X XY Y且且Y Y X X時時X X必含有碼必含有碼，則則R R BCNFBCNF。n注意到注意到：BCNFBCNF的定義更簡單，不需要從的定義更簡單，不需要從1 1NFNF到到2 2NFNF再到再到3 3NFNF再到再到BCNFBCNF一步步檢查，也不一步步檢查，也不涉及完全、部分和傳遞函數(shù)依賴等概念

8、，可涉及完全、部分和傳遞函數(shù)依賴等概念，可以以直接判斷一個直接判斷一個1 1NFNF的關(guān)系是否屬于的關(guān)系是否屬于BCNFBCNF。nBCNF的定義排除了任何屬性的定義排除了任何屬性(不管是主屬性不管是主屬性還是非主屬性還是非主屬性)對碼的傳遞和部分依賴。對碼的傳遞和部分依賴。由由BCNF的定義得到的結(jié)論的定義得到的結(jié)論n由由BCNF的定義，非平凡的的定義，非平凡的FD: X Y非主屬性非主屬性主屬性主屬性含碼含碼K，或或X即碼即碼n可以證明下述結(jié)論可以證明下述結(jié)論, 一個滿足一個滿足BCNF的關(guān)系模式有的關(guān)系模式有:n1. 所有非主屬性對每一個碼都是完全函數(shù)依賴，所有非主屬性對每一個碼都是完全

9、函數(shù)依賴， 即即, 若若R BCNF, 則則R 2NF。n2. 所有的主屬性對每一個不包含它的碼也是完全所有的主屬性對每一個不包含它的碼也是完全函數(shù)依賴。函數(shù)依賴。n3. 沒有任何屬性完全函數(shù)依賴于非碼的任何一組沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性。屬性。n4. 若若R BCNF, 則必有則必有R 3NF; 反之不一定成立。反之不一定成立。11BCNF：例例1n關(guān)系模式關(guān)系模式SCO(S#, C#, ORDER)，表示學生，表示學生(S#)選修課程選修課程(C#)的名次的名次(ORDER)。n每一個學生選修每門課程的成績有一定的名每一個學生選修每門課程的成績有一定的名次，每門課程中每一

10、名次只有一個學生，于次，每門課程中每一名次只有一個學生，于是有函數(shù)依賴：是有函數(shù)依賴： (S#，C#) ORDER (C#，ORDER) S#n思考思考: 關(guān)系模式關(guān)系模式SCO的碼是的碼是? 屬于屬于BCNF嗎？屬于嗎？屬于3NF嗎嗎? 為什么為什么?12關(guān)于關(guān)于BCNF的結(jié)論的結(jié)論n1. 全碼關(guān)系模式屬于全碼關(guān)系模式屬于BCNF。n沒有以非碼屬性作為決定因素的函數(shù)依賴沒有以非碼屬性作為決定因素的函數(shù)依賴n2. 二目關(guān)系模式屬于二目關(guān)系模式屬于BCNF。n如果有函數(shù)依賴如果有函數(shù)依賴, 則其左部一定含碼則其左部一定含碼n3. 不存在函數(shù)依賴的關(guān)系模式屬于不存在函數(shù)依賴的關(guān)系模式屬于BCNF。

11、n沒有函數(shù)依賴沒有函數(shù)依賴n4. 若若R屬于屬于BCNF，那么那么R也屬于也屬于3NF。 n5. 若若R屬于屬于3NF，但但R不一定屬于不一定屬于BCNF。 13范式：綜合例范式：綜合例 設有關(guān)系模式設有關(guān)系模式 R U= A , B , C , D , E F=ABC, BD, CE, ECB, ACB n要討論范式，首先確定碼。要討論范式，首先確定碼。R的候選碼的候選碼: AB, AC; 主屬性主屬性: A, B, C; 非主屬性非主屬性: D, E。nR BCNF EC B的決定因素的決定因素EC不包含碼。不包含碼。nR 3NF 存在非主屬性存在非主屬性E對碼對碼AB的傳遞依賴：的傳遞依

12、賴： ABC , CAB , CE, E C nR 2NF 存在非主屬性存在非主屬性D對碼對碼AB的部分依賴的部分依賴 AB D。nR 1NFP14范式：綜合例范式：綜合例(續(xù)續(xù)) 關(guān)系模式關(guān)系模式 R U= A , B , C , D , E F=ABC, BD, CE, ECB, ACB nR的候選碼的候選碼: AB, AC。nR 1NF。n將將 R規(guī)范化規(guī)范化(分解分解)為為 BCNF 模式集模式集： R1(A, B, C; AB C, AC B) BCNF R2(B, D; B D) BCNF R3(B, C, E; C E, EC B) BCNF155.2.8 4NFn定義定義5.1

13、0 關(guān)系模式關(guān)系模式R 1NF，如如果果 對 于對 于 R 的 每 個 非 平 凡 多 值 依 賴的 每 個 非 平 凡 多 值 依 賴XY(Y X)，X都含有碼都含有碼，則稱，則稱R 4NF。n說明：說明：1. 定義中的定義中的F是數(shù)據(jù)依賴集是數(shù)據(jù)依賴集, 包括包括FD和和MVD; 當當F只只包含包含F(xiàn)D時時, 4NF的定義就是的定義就是BCNF的定義。的定義。2. 4NF是是BCNF的推廣的推廣, 適用于具有多值依賴的關(guān)系適用于具有多值依賴的關(guān)系模式。模式。3. 4NF的定義就是限制關(guān)系模式的屬性之間不允許的定義就是限制關(guān)系模式的屬性之間不允許有非平凡且非函數(shù)依賴的多值依賴的存在。有非平凡

14、且非函數(shù)依賴的多值依賴的存在。164NF定義的說明定義的說明4. 由定義可知由定義可知, 若若XY 是平凡的多值依賴是平凡的多值依賴, 則不則不要求要求X包含碼包含碼。5. 由定義可知由定義可知, 若若R 4NF, 則必有則必有R BCNF; 反之反之不成立不成立(因為函數(shù)依賴是多值依賴的特例因為函數(shù)依賴是多值依賴的特例)。n思考思考: 1. 任何一個二目關(guān)系模式任何一個二目關(guān)系模式R(A, B)屬于屬于4NF嗎？嗎？2. 全碼關(guān)系模式屬于全碼關(guān)系模式屬于4NF嗎？嗎？是是否，如否，如 WSC關(guān)系關(guān)系 17非非4NF轉(zhuǎn)為轉(zhuǎn)為4NFn例例2的關(guān)系模式的關(guān)系模式 WSC，有有WS，WC，碼為碼為(

15、W, S, C), 所以所以 WSC 4NF, 但但 WSC BCNF。n如果倉庫如果倉庫Wi有有n個保管員，存放個保管員，存放m件商品，則關(guān)系件商品，則關(guān)系中分量為中分量為Wi的元組共有的元組共有mn個，每個保管員重復個，每個保管員重復存儲存儲m次次,每種商品重復存儲每種商品重復存儲n次次, 數(shù)據(jù)冗余非常大。數(shù)據(jù)冗余非常大。n增刪也不便增刪也不便, 增加商品增加商品, 取消保管員都必須增刪若干取消保管員都必須增刪若干元組。元組。n分解改造分解改造: 將將WSC分解為分解為WS(W，S)和和WC(W，C)n分解后的分解后的關(guān)系模式都屬于關(guān)系模式都屬于4NF，因為因為只有平凡的多只有平凡的多值依

16、賴值依賴WS和和WC，滿足滿足4NF的定義。的定義。18范式盤點范式盤點 1. 一個全是主屬性的關(guān)系模式一定可以達到一個全是主屬性的關(guān)系模式一定可以達到3NF。 2. 一個全碼的關(guān)系模式一定可以達到一個全碼的關(guān)系模式一定可以達到BCNF。 3. 一個二目關(guān)系模式一定可以達到一個二目關(guān)系模式一定可以達到4NF。 4. 函數(shù)依賴和多值依賴是兩種重要的數(shù)據(jù)依賴。函數(shù)依賴和多值依賴是兩種重要的數(shù)據(jù)依賴。在函在函數(shù)依賴的范疇內(nèi)數(shù)依賴的范疇內(nèi), BCNF是最高級別的范式。是最高級別的范式。如果考如果考慮多值依賴慮多值依賴, 則則4NF是最高的范式級別。是最高的范式級別。 5. 除除FD和和MVD外，還有其

17、他數(shù)據(jù)依賴，如外，還有其他數(shù)據(jù)依賴，如連接依賴連接依賴，在連接依賴的概念上還可以定義在連接依賴的概念上還可以定義5NF的范式級別。的范式級別。19范式之間的關(guān)系范式之間的關(guān)系1 1NFNF2 2NFNF消除非主屬性對碼的消除非主屬性對碼的部分函數(shù)依賴部分函數(shù)依賴4 4NFNF消除非平凡且非函數(shù)消除非平凡且非函數(shù)依賴的多值依賴依賴的多值依賴消除主屬性對碼的部消除主屬性對碼的部分和傳遞函數(shù)依賴分和傳遞函數(shù)依賴BCNFBCNF3 3NFNF消除非主屬性對碼的消除非主屬性對碼的傳遞函數(shù)依賴傳遞函數(shù)依賴消除非消除非平凡且平凡且非非FDFD的的MVDMVD消除決消除決定因素定因素非碼的非碼的非平凡非平凡的

18、的FDFD205.2.9 規(guī)范化小結(jié)規(guī)范化小結(jié)n1. 規(guī)范化的目的規(guī)范化的目的 n有些關(guān)系模式存在有些關(guān)系模式存在“插入異常插入異常, 更新異常更新異常, 刪刪除異常除異常, 數(shù)據(jù)冗余大數(shù)據(jù)冗余大”的問題的問題 - 不好的模式不好的模式n尋求解決這些問題的方法尋求解決這些問題的方法 - 規(guī)范化的目的規(guī)范化的目的n2. 規(guī)范化的基本思想規(guī)范化的基本思想 n概念的單一化概念的單一化n逐步消除數(shù)據(jù)依賴中不合適的部分逐步消除數(shù)據(jù)依賴中不合適的部分, 使關(guān)系模式達使關(guān)系模式達到某種程度的分離到某種程度的分離, 即即“一事一地一事一地”的模式設計原的模式設計原則則n3. 各種范式及規(guī)范化的過程各種范式及規(guī)

19、范化的過程n1NF 2NF 3NF BCNF 4NF21規(guī)范化小結(jié)規(guī)范化小結(jié)(續(xù)續(xù))n4. 關(guān)系模式的規(guī)范化過程是通過對關(guān)系模式的關(guān)系模式的規(guī)范化過程是通過對關(guān)系模式的投影分投影分解解來實現(xiàn)的來實現(xiàn)的, 把低一級的關(guān)系模式分解為若干高一級把低一級的關(guān)系模式分解為若干高一級的關(guān)系模式的關(guān)系模式, 分解不是唯一的。分解不是唯一的。后面還介紹分解算法。后面還介紹分解算法。n5. 規(guī)范化理論為數(shù)據(jù)庫模式設計提供了理論指南和工規(guī)范化理論為數(shù)據(jù)庫模式設計提供了理論指南和工具具, 但僅僅是指南和工具。但僅僅是指南和工具。并不是規(guī)范化程度越高越并不是規(guī)范化程度越高越好。好。n規(guī)范化程度高規(guī)范化程度高, 可解決

20、更新異常和冗余大的問題可解決更新異常和冗余大的問題, 但但會失去檢索查詢方便快速的優(yōu)點會失去檢索查詢方便快速的優(yōu)點, 增加增加(自然自然)連接連接運算的開銷。運算的開銷。n必須結(jié)合應用環(huán)境和具體情況合理選擇必須結(jié)合應用環(huán)境和具體情況合理選擇DB模式模式, 經(jīng)經(jīng)常用于檢索查詢的系統(tǒng)常用于檢索查詢的系統(tǒng), 寧肯規(guī)范化程度低些。寧肯規(guī)范化程度低些。22補充：候選碼的求解算法補充：候選碼的求解算法 設關(guān)系模式設關(guān)系模式RRn(1) (1) 將將R R的所有屬性分為的所有屬性分為 L L、 R R、NN和和 LRLR四類，四類，并令并令X X代表代表L L、NN兩類，兩類，Y Y代表代表LRLR類。類。

21、 L類類: 僅出現(xiàn)在僅出現(xiàn)在F的函數(shù)依賴左部的屬性；的函數(shù)依賴左部的屬性； R類類: .右右； N類類: 在在F的函數(shù)依賴左右兩邊都不出現(xiàn)的屬性；的函數(shù)依賴左右兩邊都不出現(xiàn)的屬性； LR類類: 都出現(xiàn)的屬性都出現(xiàn)的屬性 。 n(2) (2) 求屬性集閉包求屬性集閉包X X+ +，若若 X X+ +包含了包含了R R的全部屬的全部屬性則性則X X即為即為R R的唯一候選碼的唯一候選碼, , 轉(zhuǎn)轉(zhuǎn)(5);(5);23候選碼的求解算法候選碼的求解算法(續(xù)續(xù)) (3) (3) 否則否則, , 在在Y Y中取一屬性中取一屬性A A，求求屬性集閉包屬性集閉包( (XA)XA)+ +，若，若( (XA)XA

22、)+ +包含了包含了R R的全部屬性，則轉(zhuǎn)的全部屬性，則轉(zhuǎn)(4)(4)；否則，調(diào)換一屬性反復進行這一過程，直到否則，調(diào)換一屬性反復進行這一過程，直到試完所有試完所有Y Y中的屬性。中的屬性。 (4) (4) 如果已找出了所有的候選碼，則轉(zhuǎn)如果已找出了所有的候選碼，則轉(zhuǎn)(5)(5)；否；否則在則在Y Y中依次取中依次取2 2個、個、3 3個、個、屬性，求屬性，求X X與它與它們的屬性集閉包，直到其閉包包含們的屬性集閉包，直到其閉包包含R R的全部屬的全部屬性。性。 (5) (5) 停止，輸出結(jié)果。停止，輸出結(jié)果。24候選碼的求解：例候選碼的求解：例1n設關(guān)系模式設關(guān)系模式R(A, B, C, D

23、), R(A, B, C, D), 其函數(shù)依賴集：其函數(shù)依賴集： F=DB, BD, ADB, ACD F=DB, BD, ADB, ACD 求求R R的所有候選碼。的所有候選碼。n解解: : L L類類: : A, CA, C R R類類: : NN類類: : LR LR類類: : B, DB, Dn因為因為( (AC)AC)F F+ +=ACDB=ACDB，所以所以ACAC是是R R的唯一候選的唯一候選碼。碼。25候選碼的求解：例候選碼的求解：例2n設關(guān)系模式設關(guān)系模式R(A, B, C, D, E, P), R(A, B, C, D, E, P), 其函數(shù)依賴集：其函數(shù)依賴集： F=AD, ED, DB, BCD, DCAF=AD, ED, DB, BCD, DCA 求求R R的所有候選碼。的所有候選碼。n解解: : L L類類: : C, E RC, E R類類: : NN類類: : P P LR