1、目錄*,4.1 模式設(shè)計(jì)與數(shù)據(jù)冗余 4.2 函數(shù)依賴(lài) 4.4 范式 4.4.1 函數(shù)依賴(lài)與范式 4.1.2 多值依賴(lài)與4NF,為什么使用范式？,如何得到“好”的數(shù)據(jù)庫(kù)設(shè)計(jì)？ 判斷一個(gè)關(guān)系是否“好”，是否有“壞”的數(shù)據(jù)依賴(lài) 屬于哪一級(jí)別的范式？ 高級(jí)范式與低級(jí)范式相比，是“更好”的關(guān)系，因?yàn)椤皦摹睌?shù)據(jù)依賴(lài)更少,范式,范式 滿(mǎn)足一定要求的所有關(guān)系模式的全集 范式級(jí)別(從低級(jí)到高級(jí)) 第一范式 (1NF) 第二范式 (2NF) 第三范式 (3NF) BC范式 (BCNF) 第四范式 (4NF) 范式越高級(jí)，代表的關(guān)系模式就越“好”，要滿(mǎn)足的要求也就越高,范式,不同范式之間的聯(lián)系 4NF BCNF 3

2、NF 2NF 1NF 高級(jí)范式是低級(jí)范式的子集 范式越高，滿(mǎn)足的要求也就越高；滿(mǎn)足高要求的關(guān)系肯定能夠滿(mǎn)足低要求，所以高級(jí)范式中的關(guān)系模式肯定也在低級(jí)范式中,第一范式,要求 關(guān)系模式的每個(gè)屬性都是原子的 原子屬性 屬性值不可再分 例如. age, sex 非原子屬性 屬性值可以再分，包括 復(fù)合屬性，值是一個(gè)結(jié)構(gòu)體。例如parents， 多值屬性，值是一個(gè)集合。例如phone-numbers。,第一范式,例子 下面關(guān)系中，哪些在1NF中，哪些不在？,Student,Student,Student,一些術(shù)語(yǔ)和解釋,例子關(guān)系 R(ABCDE)。主鍵ABC，也是唯一候選鍵。 主屬性（鍵屬性） 一個(gè)屬性

3、，出現(xiàn)在某個(gè)候選鍵中 例如：A, B, C 非鍵屬性（非鍵屬性） 一個(gè)屬性，不出現(xiàn)在任何一個(gè)候選鍵中 例如：D, E 鍵的一部分 就是候選鍵的真子集。 例如，AB, BC, AC, A, B, C等等,一些術(shù)語(yǔ)和解釋,超鍵（含鍵） 具有唯一性的屬性集。 從超鍵去掉多余屬性，即得到候選鍵。所以直觀上看，超鍵必然包含一個(gè)候選鍵。 例如：ABC, ABCD, ABCE, ABCDE都是超鍵,第二范式,要求 關(guān)系模式在1NF中 每一個(gè)非鍵屬性完全函數(shù)依賴(lài)于鍵 判斷方法：檢查每個(gè)非鍵屬性A所依賴(lài)的X（即XA），若X是候選鍵的一部分，違反2NF。,第二范式,例子 以下關(guān)系在1NF中？在2NF中？為什么？

4、它們有我們以前討論過(guò)的四個(gè)問(wèn)題嗎？,SC,SC,第三范式,要求 關(guān)系在1NF中 每個(gè)非鍵屬性都非傳遞依賴(lài)于鍵 判斷方法：檢查鍵外每個(gè)屬性A所依賴(lài)的X（即XA），若X不含鍵，違反3NF。 因?yàn)樵O(shè)鍵是K ，則KX（KU，而X必是U的子集 ），所以當(dāng)XA成立時(shí)，A對(duì)鍵K是傳遞依賴(lài),第三范式,例子 以下關(guān)系在3NF中？在2NF中？ 它們有我們以前討論過(guò)的四個(gè)問(wèn)題嗎？,Student,Student,第三范式,思考 如何證明3NF是2NF的子集?（或者，如何證明滿(mǎn)足3NF的條件也就一定滿(mǎn)足2NF的條件?） 要點(diǎn)：函數(shù)依賴(lài) X Y 是非傳遞的 X Y是完全的 反證：如果 X Y 是部分的 X X Y X

5、Y是傳遞的，與前提矛盾,BC范式,要求 關(guān)系在1NF中 每個(gè)屬性都非傳遞依賴(lài)鍵 充要條件：每一個(gè)(非平凡的)函數(shù)依賴(lài)XY，X含鍵 可以證明：BCNF是3NF的真子集,BC范式,例子 考慮以下關(guān)系 R(S, T, C) S: 學(xué)生; T: 教師; C: 課程,R,BC范式,假設(shè)一個(gè)教師只教一門(mén)課程，但是一門(mén)課程有多個(gè)教師。也就是TC 假設(shè)給定一個(gè)學(xué)生和一門(mén)課程，只有一個(gè)老師給他上這門(mén)課程。也就是SCT 所以函數(shù)依賴(lài)集為: F= TC, SCT ,R,BC范式,R(S, T, C), F= TC, SCT 問(wèn)題1: R的候選鍵是什么？ 候選鍵: ST, SC 證明: (ST)+=(STC), (S

6、C)+=(STC),所以ST, TC是超鍵. 而(S)+=(S), (T)+=(TC), (C)+=(C), 所以ST, SC的真子集都不是超鍵,R,BC范式,R(S, T, C), F= TC, SCT , 候選鍵: ST, SC 問(wèn)題2: R在3NF中么？在BCNF中么？ R在3NF中，因?yàn)镽中沒(méi)有非鍵屬性 R不在BCNF中，因?yàn)門(mén)C的左邊T不含鍵。,R,BC范式,R(S, T, C), F= TC, SCT , 候選鍵: ST, SC 問(wèn)題3: 它們有我們以前討論過(guò)的四個(gè)問(wèn)題嗎？ 是的，因?yàn)榻M合(T, C)的值重復(fù),R,三種范式的比較,結(jié)論 2NF保證了這樣的函數(shù)依賴(lài)：右邊非鍵屬性的情況

7、下，左邊!=鍵（含鍵） BCNF在3NF的基礎(chǔ)上，進(jìn)一步保證：右邊不管是還是非鍵屬性，左邊=鍵。 到BCNF為止，任何有意義（非平凡）的函數(shù)依賴(lài)都是好的，即右邊不管是什么，左邊都具有唯一性（含鍵）。,三種范式的判斷,在學(xué)習(xí)這么多的范式以后,認(rèn)識(shí) 高級(jí)范式的問(wèn)題比低級(jí)范式要少 但即使是非常高級(jí)的范式，仍然可能還是有問(wèn)題 所以我們不能期望沒(méi)有任何問(wèn)題的“完美”關(guān)系。只能盡量讓關(guān)系達(dá)到盡可能高的范式，使問(wèn)題盡可能的少,如何讓關(guān)系達(dá)到更高的范式?,分解 把一個(gè)屬于低級(jí)范式的“壞”關(guān)系，分解為幾個(gè)屬于高級(jí)范式的 “好”關(guān)系（更小的關(guān)系） 但是某些情況下分解會(huì)帶來(lái)新的問(wèn)題，比如信息丟失，這樣的分解是不正確

8、的。 兩個(gè)要點(diǎn) 1. 什么樣的分解方案才是正確的（不丟失信息的）? 無(wú)損連接分解 2. 怎么找到正確的分解方案? 規(guī)范化,無(wú)損連接分解,無(wú)損連接分解 不會(huì)丟失信息的分解 判定“一分二”是否無(wú)損連接分解的充分必要條件 將關(guān)系R分解為R1和R2 。則當(dāng)以下兩個(gè)函數(shù)依賴(lài)之一能夠成立時(shí)，這種是無(wú)損的 R1 R2 R1R2 R1 R2 R2R1,無(wú)損連接分解,R(C, T, H, R, S) F = CT, HRC, HTR, HSR 問(wèn)題1: R R1(C, H, S), R2(C, T, H, R). 這一分解是無(wú)損的么? 是的，因?yàn)?CH+ (CTHR) CH TR R1 R2 R2R1 R 分解

9、為 R1, R2 是無(wú)損的 思考: R R1(C, H, S), R2(C, T), R3(C, H, R). 這一分解是無(wú)損的么,規(guī)范化,規(guī)范化 將一個(gè)屬于低級(jí)范式的“壞”關(guān)系，分解為多個(gè)屬于高級(jí)范式的“好”關(guān)系，且無(wú)信息丟失的過(guò)程 根據(jù)目標(biāo)范式的級(jí)別，又有 規(guī)范化到1NF 規(guī)范化到3NF 規(guī)范化到BCNF,規(guī)范化到1NF,非1NF的關(guān)系變?yōu)?NF的關(guān)系 方法：將關(guān)系中每個(gè)非原子的屬性轉(zhuǎn)化成原子的 復(fù)合屬性的處理：轉(zhuǎn)化成相應(yīng)的多個(gè)原子屬性,Student,Student,規(guī)范化到1NF,多值屬性的處理：移出去生成一個(gè)新關(guān)系，同時(shí)還包含原來(lái)的主鍵（新關(guān)系的主鍵為這兩者的和）,Student,S

10、tudent,SC,規(guī)范化到3NF,1NF關(guān)系分解為3NF關(guān)系的算法 輸入 : R（屬于1NF）, F（R滿(mǎn)足的函數(shù)依賴(lài)集合） 輸出 : R1, R2, R3Rn（都屬于3NF）,規(guī)范化到3NF,1- n=0; (n是輸出關(guān)系個(gè)數(shù)) for F 中每一個(gè)X Y doif XY已經(jīng)在某個(gè)輸出關(guān)系Ri (1 i n)中 then 什么也不做 else if X是某一個(gè)輸出關(guān)系Ri (1 i n) 的主鍵 then Ri := Ri + Y; else n := n+1; Rn := XY ; (增加一個(gè)新關(guān)系，X 作為主鍵) end if 2- if R每個(gè)候選鍵都不出現(xiàn)在輸出關(guān)系Ri (1i n

11、) 中 then n := n+1; Rn := R的任何一個(gè)候選鍵 end if,步驟,步驟,規(guī)范化到3NF,例1 輸入: R(A, B, C, D, E), F = (AB, CD, D E) 候選鍵: AC 1. R1(AB) 2. R1(AB), R2(CD) 3. R1(AB), R2(CD), R3(DE) 4. R1(AB), R2(CD), R3(DE), R4(AC) Output: R1(AB), R2(CD), R3(DE), R4(AC),規(guī)范化到3NF,例2 輸入: R(A, B, C, D, E, F), F = (ABD, CE, AB C, CF) 候選鍵: A

12、B 1. R1(ABD) 2. R1(ABD), R2(CE) 3. R1(ABCD), R2(CE) 4. R1(ABCD), R2(CEF) Output: R1(ABCD), R2(CEF),規(guī)范化到BCNF,1NF關(guān)系分解為BCNF關(guān)系的算法 輸入 : R（屬于1NF）, F（R1滿(mǎn)足的函數(shù)依賴(lài)集合） 輸出 : R, R1, R2, R3Rn（都屬于BCNF）,規(guī)范化到BCNF,n=0; (除自己外沒(méi)有輸出關(guān)系) for F 中每個(gè)XY do for 每個(gè)輸出關(guān)系R/Ri do if XY 在Ri中，且X不是Ri的超鍵 then Ri = Ri Y if X是另一個(gè)輸出關(guān)系Rj (1

13、i n) 的主鍵 then Rj := Rj + Y; else n := n+1; Rn := XY ; (增加一個(gè)新關(guān)系，X 作為主鍵) end if end if,規(guī)范化到BCNF,例1 輸入: R (A, B, C, D, E, F), F = (ABD, CE, AB C, CF) 候選鍵: AB 1. R(ABCDF), R1(CE) 處理CE 2. R(ABCD), R1(CEF) 處理CF Output: R(ABCD), R1(CEF),規(guī)范化到BCNF,例2 輸入: R (A, B, C, D), F = (ABC, CA, C D) 候選鍵: AB, BC 1. R(BC

14、D), R1(CA) 處理CA 2. R(BC), R1(CAD) 處理CD Output: R (BC), R1(CAD) 思考 把上面的關(guān)系規(guī)范化到3NF，結(jié)果如何？試與BCNF的結(jié)果作比較 此時(shí)原來(lái)的函數(shù)依賴(lài)ABC, CA, C D在規(guī)范化的結(jié)果關(guān)系上是否還成立？,規(guī)范化到BCNF與規(guī)范化到3NF的對(duì)比 規(guī)范化到BCNF得到的關(guān)系問(wèn)題更少，但是可能丟失某些函數(shù)依賴(lài)（在原來(lái)的關(guān)系上成立，但在分解后的關(guān)系上不成立） 規(guī)范化到3NF得到的關(guān)系可能不是很好，但往往已經(jīng)足夠好了。而且不會(huì)丟失任何函數(shù)依賴(lài),練習(xí),R (C, T, H, R, S) F = CT, HRC, HTR, HSR 問(wèn)題：

15、1. HT是否R的候選鍵? HS呢? 2. R最高屬于第幾范式? 試證明之 3. 把R規(guī)范到BCNF級(jí)別 4. 證明你在3中使用的分解是無(wú)損分解,答案,R (C, T, H, R, S) F = CT, HRC, HTR, HSR 問(wèn)題： 1. HT是否R的候選鍵? HS呢? 答:HT不是R的候選鍵，推理如下： (HT)+=(HTRC) U (HT)+ HT U HT不是超鍵 HT不是候選鍵 HS是R的候選鍵，推理如下： (HS)+=(HSRTC) U (HS)+ HS U HS是超鍵 (H)+=(H) U (H)+ H U H不是超鍵 (S)+=(S) U (S)+ S U S不是超鍵 綜合

16、 HS是最小的超鍵即候選鍵,答案,R (C, T, H, R, S) F = CT, HRC, HTR, HSR 問(wèn)題： 2. R最高屬于第幾范式? 試證明之 答: R最高屬于第二范式，推理如下： R屬于第二范式（思路：證明全部非鍵屬性: C、T、R，對(duì)候選鍵HS的依賴(lài)都是完全的，即不會(huì)函數(shù)依賴(lài)于HS的一部分：H或S，也就是不在H+或者S+中） (H)+=(H), (S)+=(S) 所有非鍵屬性: T, C, R都不函數(shù)依賴(lài)于主鍵HS的一部分 R屬于第二范式 R不屬于第三范式，推理如下：由CT可知，非鍵屬性C函數(shù)依賴(lài)T，而T又函數(shù)依賴(lài)于候選鍵HS HSC, CT 非鍵屬性T對(duì)候選鍵HS的函數(shù)依

17、賴(lài)是傳遞的 R不屬于第三范式 綜上可知，R最高屬于第二范式,答案,R (C, T, H, R, S) F = CT, HRC, HTR, HSR 問(wèn)題： 3. 把R規(guī)范到BCNF級(jí)別 規(guī)范化的分解過(guò)程如下 1. R(HSRC), R1(CT) 2. R(HSR), R1(CT), R2(HRC) 所以規(guī)范化的輸出為： R(HSR), R1(CT), R2(HRC),答案,R (C, T, H, R, S) F = CT, HRC, HTR, HSR 問(wèn)題： 4. 證明你在3中使用的分解是無(wú)損分解 首先證明R分解為R(HSRC), R1(CT)是無(wú)損分解: C T R R1R1R R分解為R,

18、R1是無(wú)損的 再證明R分解為R(HSR), R2(HRC)是無(wú)損的: HR CRR2R2RR分解為R,R2無(wú)損 所以R分解為R(HSR), R1(CT), R2(HRC)是無(wú)損的,目錄*,4.1 模式設(shè)計(jì)與數(shù)據(jù)冗余 4.2 函數(shù)依賴(lài) 4.4 范式 4.4.1 函數(shù)依賴(lài)與范式 4.1.2 多值依賴(lài)與4NF,多值依賴(lài)：例子,例子問(wèn)題 學(xué)校中某一門(mén)課程由多個(gè)教師講授，他們使用相同的一套參考書(shū)。每個(gè)教員可以講授多門(mén)課程，每種參考書(shū)可以供多門(mén)課程使用。 所以這里，課程教師，參考書(shū)課程等任何函數(shù)依賴(lài)統(tǒng)統(tǒng)不成立,多值依賴(lài)：例子,非規(guī)范關(guān)系,Teaching,多值依賴(lài)：例子,規(guī)范化關(guān)系,Teaching,多值依賴(lài)：例子,Teaching具有唯一候選鍵(C，T，B)， 也是全鍵。 TeachingBCNF（不存在函數(shù)依賴(lài)）。 Teaching模式中存在的問(wèn)題 (1) 數(shù)據(jù)冗余度大 (2) 插入操作復(fù)雜 (3) 刪除操作復(fù)雜 (4) 修改操作復(fù)雜,多值依賴(lài)：定義,多值依賴(lài)的定義(1) 設(shè)有關(guān)系模式設(shè)R(U)， X, Y是U的子集。多值依賴(lài) XY成立，當(dāng)且僅當(dāng)對(duì)R(U)上的任一關(guān)系r，以下條件成立 (r在)X上的一個(gè)確定值，都對(duì)應(yīng)在Y上的一組值 Y上的這組對(duì)應(yīng)值，與(r在)Z上的值無(wú)關(guān)，其中Z=UXY,多值依賴(lài)：定義,課程參考書(shū)。無(wú)論教師取何值，一門(mén)課程總是