求候選碼的方法

候選碼的確定方法章關(guān)系數(shù)據(jù)理論《數(shù)據(jù)庫系統(tǒng)概論》2021/6/2716.2.2碼(參見P173.)定義5.4

設(shè)K為關(guān)系模式R<U,F>的屬性(組)，若KU，則稱K為R的候選碼。主碼：若R<U,F>有多個候選碼，則可以從中選定一個作為R的主碼。主屬性：包含在任一個候選碼中的屬性，稱作主屬性。非主屬性：不包含在任一個候選碼中的屬性，稱作非主屬性(或非碼屬性)。全碼：關(guān)系模式的碼由全部屬性構(gòu)成。2021/6/272碼:例關(guān)系模式S(S#,SN,SD,DEAN,C#,G)碼的確定(1)首先根據(jù)實際背景數(shù)據(jù)約束的語義確定關(guān)系模式R<U,F>。(2)然后應(yīng)用函數(shù)依賴的公理系統(tǒng)，驗證F中每一個函數(shù)依賴的決定因素或其組合K，是否有:KU。主碼(S#，C#)，因為(S#，C#)所有屬性2021/6/273碼的確定:例求出關(guān)系模式R<U,F>的所有候選碼：U={A,B,C,D,E}F={AB→C,B→D,C→E,EC→B,AC→B}注:碼或者是某一函數(shù)依賴的左部,或是一個屬性組。驗證AB是否碼,須證明ABABCDE是否成立?∵AB→C(已知),而AB→AB(自反),∴AB→ABC(合并)∵B→D(已知),∴AB→AD(增廣),∴AB→ABCD(合并)∵C→E(已知),AB→C(已知),∴AB→E(傳遞)于是AB→ABCDE(合并)2021/6/274碼的確定:例(續(xù))驗證AB是否碼?前面已得到AB→ABCDE，又,顯然A→ABCDE,B→ABCDE,故所以ABABCDE。得證AB是一個候選碼。同理可證：AC也是一個候選碼。說明：如果每一個FD的決定因素都不是碼，則要考慮這些決定因素的組合是否構(gòu)成碼；除了碼的定義外，有候選碼的求解理論和算法，在后面可以補充介紹更好的求碼方法。2021/6/275碼的確定:練習(xí)根據(jù)碼的定義，求關(guān)系模式R<U,F>的所有候選碼。U={A,B,C,D}，F(xiàn)={A→B,C→B}答：ACD2021/6/276關(guān)于2NF的結(jié)論1.不存在非主屬性的關(guān)系模式屬于2NF。沒有非主屬性2.全碼關(guān)系模式屬于2NF。沒有非主屬性3.碼只由一個屬性組成的關(guān)系模式屬于2NF。不會有部分依賴4.二目關(guān)系模式屬于2NF。碼或是一個屬性，或是全碼5.若R屬于1NF，但R不一定屬于2NF。

例如,關(guān)系模式

S(S#,SN,SD,DEAN,C#,G)2021/6/277關(guān)于3NF的結(jié)論1.不存在非主屬性的關(guān)系模式屬于3NF。沒有非主屬性2.全碼關(guān)系模式屬于3NF。沒有非主屬性3.二目關(guān)系模式屬于3NF。不會存在傳遞依賴4.若R屬于3NF，那么R也屬于2NF。

可證明，反證5.若R屬于2NF，但R不一定屬于3NF。

例如，關(guān)系模式

S_SD(S#,SN,SD,DEAN)2021/6/278BCNF:定義定義5.8關(guān)系模式R<U,F>

1NF，對于屬性組X和Y，若X

Y且Y

X時X必含有碼，則R<U,F>

BCNF。注意到：BCNF的定義更簡單，不需要從1NF到2NF再到3NF再到BCNF一步步檢查，也不涉及完全、部分和傳遞函數(shù)依賴等概念，可以直接判斷一個1NF的關(guān)系是否屬于BCNF。BCNF的定義排除了任何屬性(不管是主屬性還是非主屬性)對碼的傳遞和部分依賴。2021/6/279由BCNF的定義得到的結(jié)論由BCNF的定義，非平凡的FD:X→Y非主屬性主屬性含碼K，或X即碼可以證明下述結(jié)論,一個滿足BCNF的關(guān)系模式有:1.所有非主屬性對每一個碼都是完全函數(shù)依賴，即,若R

BCNF,則R

2NF。2.所有的主屬性對每一個不包含它的碼也是完全函數(shù)依賴。3.沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性。4.若R

BCNF,則必有R

3NF;反之不一定成立。2021/6/2710BCNF：例1關(guān)系模式SCO(S#,C#,ORDER)，表示學(xué)生(S#)選修課程(C#)的名次(ORDER)。每一個學(xué)生選修每門課程的成績有一定的名次，每門課程中每一名次只有一個學(xué)生，于是有函數(shù)依賴：(S#，C#)ORDER(C#，ORDER)S#思考:關(guān)系模式SCO的碼是?

屬于BCNF嗎？屬于3NF嗎?為什么?2021/6/2711關(guān)于BCNF的結(jié)論1.全碼關(guān)系模式屬于BCNF。沒有以非碼屬性作為決定因素的函數(shù)依賴2.二目關(guān)系模式屬于BCNF。如果有函數(shù)依賴,則其左部一定含碼3.不存在函數(shù)依賴的關(guān)系模式屬于BCNF。沒有函數(shù)依賴4.若R屬于BCNF，那么R也屬于3NF。

5.若R屬于3NF，但R不一定屬于BCNF。

2021/6/2712范式：綜合例設(shè)有關(guān)系模式R<U,F>U={A,B,C,D,E}F={AB→C,B→D,C→E,EC→B,AC→B}要討論范式，首先確定碼。R的候選碼:AB,AC;主屬性:A,B,C;非主屬性:D,E。R

BCNF∵EC→B的決定因素EC不包含碼。R

3NF∵存在非主屬性E對碼AB的傳遞依賴：ABC,C

AB,C

E,E

C

R

2NF

∵存在非主屬性D對碼AB的部分依賴AB→D。R

1NFP2021/6/2713范式：綜合例(續(xù))關(guān)系模式R<U,F>U={A,B,C,D,E}F={AB→C,B→D,C→E,EC→B,AC→B}R的候選碼:AB,AC。R

1NF。將R規(guī)范化(分解)為BCNF模式集：R1(A,B,C;AB→C,AC→B)BCNFR2(B,D;B→D)BCNFR3(B,C,E;C→E,EC→B)BCNF2021/6/27145.2.84NF定義5.10

關(guān)系模式R<U,F>1NF，如果對于R的每個非平凡多值依賴X

Y(YX)，X都含有碼，則稱R4NF。說明：1.定義中的F是數(shù)據(jù)依賴集,包括FD和MVD;當(dāng)F只包含F(xiàn)D時,4NF的定義就是BCNF的定義。2.4NF是BCNF的推廣,適用于具有多值依賴的關(guān)系模式。3.4NF的定義就是限制關(guān)系模式的屬性之間不允許有非平凡且非函數(shù)依賴的多值依賴的存在。2021/6/27154NF定義的說明4.由定義可知,若X

Y是平凡的多值依賴,則不要求X包含碼。5.由定義可知,若R4NF,則必有RBCNF;反之不成立(因為函數(shù)依賴是多值依賴的特例)。思考:1.任何一個二目關(guān)系模式R(A,B)屬于4NF嗎？2.全碼關(guān)系模式屬于4NF嗎？是否，如WSC關(guān)系2021/6/2716非4NF轉(zhuǎn)為4NF例2的關(guān)系模式WSC，有WS，WC，碼為(W,S,C),所以WSC4NF,但WSCBCNF。如果倉庫Wi有n個保管員，存放m件商品，則關(guān)系中分量為Wi的元組共有m×n個，每個保管員重復(fù)存儲m次,每種商品重復(fù)存儲n次,數(shù)據(jù)冗余非常大。增刪也不便,增加商品,取消保管員都必須增刪若干元組。分解改造:將WSC分解為WS(W，S)和WC(W，C)分解后的關(guān)系模式都屬于4NF，因為只有平凡的多值依賴WS和WC，滿足4NF的定義。2021/6/2717范式盤點1.一個全是主屬性的關(guān)系模式一定可以達到3NF。2.一個全碼的關(guān)系模式一定可以達到BCNF。3.一個二目關(guān)系模式一定可以達到4NF。4.函數(shù)依賴和多值依賴是兩種重要的數(shù)據(jù)依賴。在函數(shù)依賴的范疇內(nèi),BCNF是最高級別的范式。如果考慮多值依賴,則4NF是最高的范式級別。5.除FD和MVD外，還有其他數(shù)據(jù)依賴，如連接依賴，在連接依賴的概念上還可以定義5NF的范式級別。2021/6/2718范式之間的關(guān)系1NF2NF消除非主屬性對碼的部分函數(shù)依賴4NF消除非平凡且非函數(shù)依賴的多值依賴消除主屬性對碼的部分和傳遞函數(shù)依賴BCNF3NF消除非主屬性對碼的傳遞函數(shù)依賴消除非平凡且非FD的MVD消除決定因素非碼的非平凡的FD2021/6/27195.2.9規(guī)范化小結(jié)1.規(guī)范化的目的

有些關(guān)系模式存在“插入異常,更新異常,刪除異常,數(shù)據(jù)冗余大”的問題---不好的模式尋求解決這些問題的方法---規(guī)范化的目的2.規(guī)范化的基本思想

概念的單一化逐步消除數(shù)據(jù)依賴中不合適的部分,使關(guān)系模式達到某種程度的分離,即“一事一地”的模式設(shè)計原則3.各種范式及規(guī)范化的過程1NF

2NF

3NF

BCNF

4NF2021/6/2720規(guī)范化小結(jié)(續(xù))4.關(guān)系模式的規(guī)范化過程是通過對關(guān)系模式的投影分解來實現(xiàn)的,把低一級的關(guān)系模式分解為若干高一級的關(guān)系模式,分解不是唯一的。后面還介紹分解算法。5.規(guī)范化理論為數(shù)據(jù)庫模式設(shè)計提供了理論指南和工具,但僅僅是指南和工具。并不是規(guī)范化程度越高越好。規(guī)范化程度高,可解決更新異常和冗余大的問題,但會失去檢索查詢方便快速的優(yōu)點,增加(自然)連接運算的開銷。必須結(jié)合應(yīng)用環(huán)境和具體情況合理選擇DB模式,經(jīng)常用于檢索查詢的系統(tǒng),寧肯規(guī)范化程度低些。2021/6/2721補充：候選碼的求解算法設(shè)關(guān)系模式R<U,F>(1)將R的所有屬性分為L、R、N和LR四類，并令X代表L、N兩類，Y代表LR類。

L類:僅出現(xiàn)在F的函數(shù)依賴左部的屬性；R類:………...右…………；N類:在F的函數(shù)依賴左右兩邊都不出現(xiàn)的屬性；LR類:…………都出現(xiàn)的屬性。

(2)求屬性集閉包X+，若X+包含了R的全部屬性則X即為R的唯一候選碼,轉(zhuǎn)(5);2021/6/2722候選碼的求解算法(續(xù))(3)否則,在Y中取一屬性A，求屬性集閉包(XA)+，若(XA)+包含了R的全部屬性，則轉(zhuǎn)(4)；否則，調(diào)換一屬性反復(fù)進行這一過程，直到試完所有Y中的屬性。(4)如果已找出了所有的候選碼，則轉(zhuǎn)(5)；否則在Y中依次取2個、3個、…屬性，求X與它們的屬性集閉包，直到其閉包包含R的全部屬性。(5)停止，輸出結(jié)果。2021/6/2723候選碼的求解：例1設(shè)關(guān)系模式R(A,B,C,D),其函數(shù)依賴集：

F={D→B,B→D,AD→B,AC→D}

求R的所有候選碼。解:L類:A,CR類:

N類:LR類:B,D因為(AC)F+=ACDB，所以AC是R的唯一候選碼。2021/6/2724候選碼的求解：例2設(shè)關(guān)系模式R(A,B,C,D,E,P),其函數(shù)依賴集：

F={A→D,E→D,D→B,BC→D,DC→A}求R的所有候選碼。解:L類:C,ER類:N類:PLR類:A,B,D因為(CEP)F+=CEPDBA，所以CEP是R的唯一候選碼。2021/6/2725候選碼的求解：例3設(shè)關(guān)系模式R(S,D,I,B,O,Q),其函數(shù)依賴集:

F={S→D,I→B,B→O,O→Q,Q→I}求R的所有候選碼。解:L類(S);R