求候選碼的方法幻燈片

1、候選碼的確定方法,第五章 關(guān)系數(shù)據(jù)理論 數(shù)據(jù)庫(kù)系統(tǒng)概論,1,C,2,6.2.2 碼(參見(jiàn)P173.),定義5.4 設(shè)K為關(guān)系模式R的屬性(組)， 若K U，則稱K為R的候選碼。,主碼：若R有多個(gè)候選碼，則可以從中選定一個(gè)作為R的主碼。 主屬性：包含在任一個(gè)候選碼中的屬性，稱作主屬性。 非主屬性：不包含在任一個(gè)候選碼中的屬性，稱作非主屬性(或非碼屬性)。 全碼：關(guān)系模式的碼由全部屬性構(gòu)成。,2,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,碼: 例,關(guān)系模式 S(S# , SN , SD , DEAN , C# , G),碼的確定 (1) 首先根據(jù)實(shí)際背景數(shù)據(jù)約束的語(yǔ)義確定關(guān)系模式R。 (2)

2、然后應(yīng)用函數(shù)依賴的公理系統(tǒng)，驗(yàn)證F中每一個(gè)函數(shù)依賴的決定因素或其組合K，是否有: K U。,主碼(S#，C#)，因?yàn)?S#，C#) 所有屬性,3,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,碼的確定: 例,求出關(guān)系模式R的所有候選碼： U= A , B , C , D , E F=ABC, BD, CE, ECB, ACB 注: 碼或者是某一函數(shù)依賴的左部, 或是一個(gè)屬性組。,驗(yàn)證AB是否碼, 須證明 AB ABCDE是否成立? ABC(已知), 而ABAB(自反), AB ABC(合并) BD(已知), ABAD(增廣), AB ABCD(合并) CE(已知), ABC(已知), AB E

3、(傳遞) 于是 AB ABCDE(合并),4,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,碼的確定: 例(續(xù)),驗(yàn)證AB是否碼? 前面已得到 AB ABCDE， 又, 顯然 AABCDE, BABCDE, 故所以AB ABCDE。得證AB是一個(gè)候選碼。 同理可證：AC也是一個(gè)候選碼。 說(shuō)明：如果每一個(gè)FD的決定因素都不是碼，則要考慮這些決定因素的組合是否構(gòu)成碼；除了碼的定義外，有候選碼的求解理論和算法，在后面可以補(bǔ)充介紹更好的求碼方法。,5,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,碼的確定: 練習(xí),根據(jù)碼的定義，求關(guān)系模式R的所有候選碼。 U= A , B , C , D ， F=A

4、B, CB ,答：ACD,6,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,關(guān)于2NF的結(jié)論,1. 不存在非主屬性的關(guān)系模式屬于2NF。 沒(méi)有非主屬性 2. 全碼關(guān)系模式屬于2NF。 沒(méi)有非主屬性 3. 碼只由一個(gè)屬性組成的關(guān)系模式屬于2NF。 不會(huì)有部分依賴 4. 二目關(guān)系模式屬于2NF。 碼或是一個(gè)屬性，或是全碼 5. 若R屬于1NF，但R不一定屬于2NF。 例如, 關(guān)系模式 S(S#, SN, SD, DEAN, C#, G),7,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,關(guān)于3NF的結(jié)論,1. 不存在非主屬性的關(guān)系模式屬于3NF。 沒(méi)有非主屬性 2. 全碼關(guān)系模式屬于3NF。 沒(méi)有

5、非主屬性 3. 二目關(guān)系模式屬于3NF。 不會(huì)存在傳遞依賴 4. 若R屬于3NF，那么R也屬于2NF。 可證明，反證 5. 若R屬于2NF，但R不一定屬于3NF。 例如，關(guān)系模式 S_SD(S#, SN, SD, DEAN),8,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,BCNF: 定義,定義5.8 關(guān)系模式R 1NF，對(duì)于屬性組X和Y，若XY且Y X時(shí)X必含有碼，則R BCNF。 注意到：BCNF的定義更簡(jiǎn)單，不需要從1NF到2NF再到3NF再到BCNF一步步檢查，也不涉及完全、部分和傳遞函數(shù)依賴等概念，可以直接判斷一個(gè)1NF的關(guān)系是否屬于BCNF。 BCNF的定義排除了任何屬性(不管是

6、主屬性還是非主屬性)對(duì)碼的傳遞和部分依賴。,9,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,由BCNF的定義得到的結(jié)論,由BCNF的定義，非平凡的FD: X Y,可以證明下述結(jié)論, 一個(gè)滿足BCNF的關(guān)系模式有: 1. 所有非主屬性對(duì)每一個(gè)碼都是完全函數(shù)依賴， 即, 若RBCNF, 則R2NF。 2. 所有的主屬性對(duì)每一個(gè)不包含它的碼也是完全函數(shù)依賴。 3. 沒(méi)有任何屬性完全函數(shù)依賴于非碼的任何一組屬性。 4. 若RBCNF, 則必有R3NF; 反之不一定成立。,10,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,BCNF：例1,關(guān)系模式SCO(S#, C#, ORDER)，表示學(xué)生(S#)

7、選修課程(C#)的名次(ORDER)。 每一個(gè)學(xué)生選修每門課程的成績(jī)有一定的名次，每門課程中每一名次只有一個(gè)學(xué)生，于是有函數(shù)依賴： (S#，C#) ORDER (C#，ORDER) S# 思考: 關(guān)系模式SCO的碼是? 屬于BCNF嗎？屬于3NF嗎? 為什么?,11,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,關(guān)于BCNF的結(jié)論,1. 全碼關(guān)系模式屬于BCNF。 沒(méi)有以非碼屬性作為決定因素的函數(shù)依賴 2. 二目關(guān)系模式屬于BCNF。 如果有函數(shù)依賴, 則其左部一定含碼 3. 不存在函數(shù)依賴的關(guān)系模式屬于BCNF。 沒(méi)有函數(shù)依賴 4. 若R屬于BCNF，那么R也屬于3NF。 5. 若R屬于3N

8、F，但R不一定屬于BCNF。,12,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,范式：綜合例,設(shè)有關(guān)系模式 R U= A , B , C , D , E F=ABC, BD, CE, ECB, ACB 要討論范式，首先確定碼。R的候選碼: AB, AC; 主屬性: A, B, C; 非主屬性: D, E。 R BCNF EC B的決定因素EC不包含碼。 R 3NF 存在非主屬性E對(duì)碼AB的傳遞依賴： ABC , CAB , CE, E C R 2NF 存在非主屬性D對(duì)碼AB的部分依賴 AB D。 R 1NF,P,13,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,范式：綜合例(續(xù)),關(guān)系模式

9、 R U= A , B , C , D , E F=ABC, BD, CE, ECB, ACB R的候選碼: AB, AC。 R 1NF。,將 R規(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) BCNF,14,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,5.2.8 4NF,定義5.10 關(guān)系模式R 1NF，如果對(duì)于R的每個(gè)非平凡多值依賴XY(YX)，X都含有碼，則稱R4NF。 說(shuō)明： 1. 定義中的F是數(shù)據(jù)依賴集, 包括FD和MVD; 當(dāng)F只包含F(xiàn)D時(shí), 4NF

10、的定義就是BCNF的定義。 2. 4NF是BCNF的推廣, 適用于具有多值依賴的關(guān)系模式。 3. 4NF的定義就是限制關(guān)系模式的屬性之間不允許有非平凡且非函數(shù)依賴的多值依賴的存在。,15,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,4NF定義的說(shuō)明,4. 由定義可知, 若XY 是平凡的多值依賴, 則不要求X包含碼。 5. 由定義可知, 若R 4NF, 則必有R BCNF; 反之不成立(因?yàn)楹瘮?shù)依賴是多值依賴的特例)。 思考: 1. 任何一個(gè)二目關(guān)系模式R(A, B)屬于4NF嗎？ 2. 全碼關(guān)系模式屬于4NF嗎？,是,否，如 WSC關(guān)系,16,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,非

11、4NF轉(zhuǎn)為4NF,例2的關(guān)系模式 WSC，有WS，WC，碼為(W, S, C), 所以 WSC4NF, 但 WSC BCNF。 如果倉(cāng)庫(kù)Wi有n個(gè)保管員，存放m件商品，則關(guān)系中分量為Wi的元組共有mn個(gè)，每個(gè)保管員重復(fù)存儲(chǔ)m次,每種商品重復(fù)存儲(chǔ)n次, 數(shù)據(jù)冗余非常大。 增刪也不便, 增加商品, 取消保管員都必須增刪若干元組。 分解改造: 將WSC分解為WS(W，S)和WC(W，C) 分解后的關(guān)系模式都屬于4NF，因?yàn)橹挥衅椒驳亩嘀狄蕾嘩S和WC，滿足4NF的定義。,17,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,范式盤點(diǎn),1. 一個(gè)全是主屬性的關(guān)系模式一定可以達(dá)到3NF。 2. 一個(gè)全碼的

12、關(guān)系模式一定可以達(dá)到BCNF。 3. 一個(gè)二目關(guān)系模式一定可以達(dá)到4NF。 4. 函數(shù)依賴和多值依賴是兩種重要的數(shù)據(jù)依賴。在函數(shù)依賴的范疇內(nèi), BCNF是最高級(jí)別的范式。如果考慮多值依賴, 則4NF是最高的范式級(jí)別。 5. 除FD和MVD外，還有其他數(shù)據(jù)依賴，如連接依賴，在連接依賴的概念上還可以定義5NF的范式級(jí)別。,18,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,范式之間的關(guān)系,1NF,19,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,5.2.9 規(guī)范化小結(jié),1. 規(guī)范化的目的 有些關(guān)系模式存在“插入異常, 更新異常, 刪除異常, 數(shù)據(jù)冗余大”的問(wèn)題 - 不好的模式 尋求解決這些問(wèn)題的

13、方法 - 規(guī)范化的目的 2. 規(guī)范化的基本思想 概念的單一化 逐步消除數(shù)據(jù)依賴中不合適的部分, 使關(guān)系模式達(dá)到某種程度的分離, 即“一事一地”的模式設(shè)計(jì)原則 3. 各種范式及規(guī)范化的過(guò)程 1NF 2NF 3NF BCNF 4NF,20,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,規(guī)范化小結(jié)(續(xù)),4. 關(guān)系模式的規(guī)范化過(guò)程是通過(guò)對(duì)關(guān)系模式的投影分解來(lái)實(shí)現(xiàn)的, 把低一級(jí)的關(guān)系模式分解為若干高一級(jí)的關(guān)系模式, 分解不是唯一的。后面還介紹分解算法。 5. 規(guī)范化理論為數(shù)據(jù)庫(kù)模式設(shè)計(jì)提供了理論指南和工具, 但僅僅是指南和工具。并不是規(guī)范化程度越高越好。 規(guī)范化程度高, 可解決更新異常和冗余大的問(wèn)題,

14、 但會(huì)失去檢索查詢方便快速的優(yōu)點(diǎn), 增加(自然)連接運(yùn)算的開(kāi)銷。 必須結(jié)合應(yīng)用環(huán)境和具體情況合理選擇DB模式, 經(jīng)常用于檢索查詢的系統(tǒng), 寧肯規(guī)范化程度低些。,21,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,補(bǔ)充：候選碼的求解算法,設(shè)關(guān)系模式R (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);,22,CH5. 關(guān)系數(shù)據(jù)理論,20

15、20/10/20,候選碼的求解算法(續(xù)),(3) 否則, 在Y中取一屬性A，求屬性集閉包(XA)+，若(XA)+包含了R的全部屬性，則轉(zhuǎn)(4)；否則，調(diào)換一屬性反復(fù)進(jìn)行這一過(guò)程，直到試完所有Y中的屬性。 (4) 如果已找出了所有的候選碼，則轉(zhuǎn)(5)；否則在Y中依次取2個(gè)、3個(gè)、屬性，求X與它們的屬性集閉包，直到其閉包包含R的全部屬性。 (5) 停止，輸出結(jié)果。,23,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,候選碼的求解：例1,設(shè)關(guān)系模式R(A, B, C, D), 其函數(shù)依賴集： F=DB, BD, ADB, ACD 求R的所有候選碼。 解: L類: A, C R類: N類: LR類:

16、B, D 因?yàn)?AC)F+=ACDB，所以AC是R的唯一候選碼。,24,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,候選碼的求解：例2,設(shè)關(guān)系模式R(A, B, C, D, E, P), 其函數(shù)依賴集： F=AD, ED, DB, BCD, DCA 求R的所有候選碼。 解: L類: C, E R類: N類: P LR類: A, B, D 因?yàn)?CEP)F+=CEPDBA，所以CEP是R的唯一候選碼。,25,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,候選碼的求解：例3,設(shè)關(guān)系模式R(S, D, I, B, O, Q), 其函數(shù)依賴集: F = SD, IB, BO, OQ, QI 求R的所有候選碼。 解: L類(S); R類(D) ; N類(無(wú)) ; LR類(I, B, O, Q) 因?yàn)镾+=SD, 所以S不是R的候選碼； 因?yàn)?SI)+=SIDBOQ，所以SI是一個(gè)候選碼； 因?yàn)?SB)+=SBDOQI，所以SB也是一個(gè)候選碼； 因?yàn)?SO)+=SODQIB，所以SO也是一個(gè)候選碼； 因?yàn)?SQ)+=SQDIBO，所以SQ也是一個(gè)候選碼。,26,CH5. 關(guān)系數(shù)據(jù)理論,2020/10/20,第5章 補(bǔ)充作業(yè)題,1. 設(shè)關(guān)系模式 R, U=A, B, C