數(shù)據(jù)庫原理及應(yīng)用 第4章 關(guān)系數(shù)據(jù)庫規(guī)范化理論

4章 關(guān)系數(shù)據(jù)庫規(guī)范化理論 關(guān)系數(shù)據(jù)理論是關(guān)系數(shù)據(jù)庫的理論基礎(chǔ)，也是設(shè)計(jì)關(guān)系數(shù)據(jù)庫的指南。本章計(jì)論關(guān)系數(shù)據(jù)理論的基本概念、方法和題解。 如何設(shè)計(jì)數(shù)據(jù)庫模式 1) 設(shè)計(jì)一個(gè)好的關(guān)系數(shù)據(jù)庫模式（概念模式） 邏輯設(shè)計(jì) 2) 憑經(jīng)驗(yàn)設(shè)計(jì)？ 3) 什么是好的關(guān)系數(shù)據(jù)庫模式？ 4) 好的關(guān)系數(shù)據(jù)庫模式應(yīng)該包括多少關(guān)系模式？ 5) 每個(gè)關(guān)系模式應(yīng)該包含哪些屬性？ 6) 借助數(shù)學(xué)工具規(guī)定設(shè)計(jì)的理論和方法 規(guī)范化 假設(shè)有如下關(guān)系 示 學(xué)號(hào) ,姓名 ,性別 ,課程 ,成績 其中 這個(gè)關(guān)系模式存在如下問題 : 數(shù)據(jù)冗余 一個(gè)學(xué)生選修多門課程 ,導(dǎo)致 不一致性 由于數(shù)據(jù)存儲(chǔ)冗余 ,當(dāng)更新某些數(shù)據(jù)項(xiàng)時(shí) ,就有可能一部分修改了 ,而另一部分未修改 ,造成數(shù)據(jù)不一致性 插入異常 如果某個(gè)學(xué)生未選課 ,他的信息 (無法插入 刪除異常 當(dāng)要?jiǎng)h除所有學(xué)生成績時(shí) ,將所有(都刪除了 ,這便是刪除異常 為了克服上述這些異常 ,將 O,O,這是因?yàn)?數(shù)據(jù)依賴是現(xiàn)實(shí)世界事物之間的相互關(guān)聯(lián)性的一種表達(dá) ,是屬性固有語義的體現(xiàn) 才能歸納與客觀事實(shí)相符合的數(shù)據(jù)依賴 數(shù)依賴 數(shù)依賴 (定義 函數(shù)依賴 定義 4設(shè) R(U)是一個(gè)關(guān)系模式 ,X,的兩個(gè)屬性集合 ,X,YR,RX,Y是關(guān)系 當(dāng)任何時(shí)刻 RX,Y中的任意兩個(gè)元組中的 則它的 則稱 ,或稱為 ,記作 XY 例子 (1) S(N,(2) (3) 函數(shù) (賴于 (4) 函數(shù)依賴的推導(dǎo)公理 姆斯特朗公理） 設(shè)有關(guān)系模式 R（ U）， X， Y， Z， WU，則： 反性）：若 YX，則 XY 廣性）：若 XY ，則 遞性）：若 XY ， YZ ，則 XZ 由 合成規(guī)則：若 XY ， XZ ，則 X 分解規(guī)則：若 X則 XY ， XZ ； 偽傳遞規(guī)則：若 XY ， Z ，則 Z 數(shù)依賴的分類 1) 平凡函數(shù)依賴與非平凡函數(shù)依賴 定義 2 在關(guān)系 R(U)中 ,對(duì)于 和 Y,如果 XY , 但 則 XY 是非平凡函數(shù)依賴 是 則稱XY 為平凡函數(shù)依賴 2)完全函數(shù)依賴與部分函數(shù)依賴 設(shè) XY 是一個(gè) 且對(duì)于任何一個(gè) XX,X Y 不成立 ,則稱 XY 是一個(gè)完全函數(shù)依賴 ,記作 X Y 設(shè) XY 是一個(gè) 且存在一個(gè) XX,使 X Y 成立 ,則稱XY 是一個(gè)部分函數(shù)依賴 ,記作 X Y 示例 1) ) (G 是完全函數(shù)依賴 (2) (G 所以存在部分函數(shù)依賴 3)傳遞函數(shù)依賴 設(shè) X,Y,互不相同的屬性集合 X Y， Y X,且 Y Z 則稱屬性集合 數(shù)依賴于 X ,記作 X Z (1) N,G,M) (學(xué)號(hào) ,課程名 ,成績 ,系名 ,系主任 ) (2) (3) (4) 引理： XA 1 A A I=1,2,3 如果 之間是 1系，則存在 XY ， YX 如果 之間是“多對(duì) 1”關(guān)系，則存在 XY 如果 之間是“多對(duì)多”，則 不存在函數(shù)依賴 結(jié) 1) 函數(shù)依賴是完整性約束的一種特殊形式 2) 函數(shù)依賴分為 (1) 完全函數(shù)依賴 (2) 部分函數(shù)依賴 (3) 傳遞函數(shù)依賴 3) 函數(shù)依賴是規(guī)范化理論的依據(jù) 4) 函數(shù)依賴是規(guī)范化程度的準(zhǔn)則 函數(shù)依賴的閉包 F+ 屬性閉包及其計(jì)算 函數(shù)依賴的閉包 F+ 定義 4關(guān)系模式 R(U,F)中為 的閉包 ,記為 :F+ 例 :關(guān)系模式 S(U,F),其中 U=F= 義 4關(guān)系模式 R(U),則稱所有用 推出的函數(shù)依賴XA 的屬性閉包 ,記作X+ 例 : 有關(guān)系模式 S(N,有 有N,理 設(shè)關(guān)系模式 R(U),X,YU,則從 Y 的充分必要條件是 Y X+ 法 4屬性集 的屬性閉包 X+ 算法 求屬性的閉包 X+ 輸入 X,F 輸出 X+ 步驟 (1)令 X(0)=X,I=0 (2)求 B,B=A|(E)(W)(V W F V X(I) A W (在 (I)的子集的函數(shù)依賴 ) (3)X(I+1)=B X(I) (4)判斷 X(I+1)=X(I)嗎 ? (5)若相等 ,或 X(I)=U,則 X(I)為屬性集 且算法終止 (6)若不相等 ,則 I=I+1,返回第 2步 . 性閉包計(jì)算示例 例 1 已知關(guān)系模式 R(U,F),U=A,B,C,D,E; F=AB, DC,E,B 求 ( ,( 解 求 ( 設(shè) X(0)=計(jì)算 X(1) : 逐一掃描 找出左部為 A,得到一個(gè) : AB. 故有 X(1)=B=計(jì)算 X(2): 逐一掃描 找到左部為 A,B,B,E,示發(fā)現(xiàn)有新的函數(shù)依賴 X(2)=X(1) =有 X(1)=X(2),算法終止 , ( = (注 :因?yàn)檎也坏叫碌暮瘮?shù)依賴 ,即 (1)的子集 ,所以 ,不必再計(jì)算下去 ,算法終止 ) 練習(xí) 求 ( 解 求 ( X(0)=求 X(1):逐一掃描 找出左部為 A,得到 : AB,D C, 故有 X(1)=求 X(2):逐一掃描 找出左部為 得到 : ,B, 故有X(2)=因?yàn)?X(2)=U,故算法終止 , (= 2 設(shè)有關(guān)系模式 R(U,F),其中 U=A,B,C,D,E,I; F=AD,E, ,I,E C 計(jì)算 ( 解 : 設(shè) X(0)=求 X(1) 在 有 AD,E C 所以 X(1)=求 X(2) 在 新的依賴有 所以 X(2)=求 X(3) 因?yàn)樵?(2)的子集 ,所以不必再計(jì)算 ,即 X(3)=X(2),算法終止 (=習(xí) 設(shè)有函數(shù)依賴集 F=DG,C A,E,A B 計(jì)算閉包 D+ ,C+, A+ ,( ,(, (, ( 最小函數(shù)依賴集及其算法 1. 等價(jià)與覆蓋 定義 : 一個(gè)關(guān)系模式 R(U)上的兩個(gè)依賴集 ,如果 F+=G+,則稱 是等價(jià)的 ,記作 F G. 如果函數(shù)依賴集 F是 反之亦然 兩個(gè)等價(jià)的依賴集在表示能力上是完全相同的 . 最小函數(shù)依賴集及其算法 定義 :對(duì)于給定的函數(shù)依賴 F,當(dāng)滿足下列條件時(shí) ,稱為 記作 F: 1) F的每個(gè)依賴的右部都是單個(gè)屬性 2) 對(duì)于 F中的任何一個(gè)函數(shù)依賴 XA, F -XA 與 F都不等價(jià) 3) 對(duì)于 F中的任何一個(gè) XA 和 ,(F-XA) ZA 與 F都不等價(jià) 說明 :條件 (2)保證了在 條件 (3)保證了 最小函數(shù)依賴集及其算法 算法 4 輸入 :一個(gè)函數(shù)依賴集 F 輸出 : 方法 : (1)應(yīng)用分解規(guī)則 ,使 (2)去掉各依賴左部多余的屬性 一個(gè)一個(gè)地檢查 例如 , 現(xiàn)在要判斷 則以 XA 代替 是否等價(jià) ?只要在 若 X+包含 A,則 否則 依次判斷其他屬性即可消除各依賴左邊的多余屬性 . (3)去掉多余的依賴 從第一個(gè)依賴開始 ,從 假設(shè)該依賴為 XY), 然后在剩下的依賴中求 X+,看X+是否包含 Y,若是 ,則去掉 XY; 若不包含 Y,則不能去掉XY. (4)這樣依次做下去 . 例 設(shè)有依賴集 : F=,C A,D,B,D E C,E 計(jì)算其等價(jià)的最小依賴集 . 解 : (1)將依賴右邊屬性單一化 ,結(jié)果為 C C C A B D D B A D E G D G (2)在 因?yàn)橛?C A, 則對(duì) A,E 是多余的 ,對(duì)于 B, 若去掉 A,由于 (= 刪除依賴左部多余的依賴后 : C C C A B D D B C A D E G D G (3)在 對(duì)于 B, 去掉他 ,仍有(=是多余的 ,刪除多余的依賴后 : C D G C A C D D B G D E C C C A B D D B C A D E G D G 注意： 與對(duì)各函數(shù)依賴 A 中 候選關(guān)鍵字的求解理論與算法 候選關(guān)鍵字 : 屬性或?qū)傩缘淖钚〗M合 ,其值能夠惟一地標(biāo)識(shí)一個(gè)元組 . 對(duì)于給定的關(guān)系 R(2,和函數(shù)依賴集 F,可將其屬性分為四類 : 僅出現(xiàn)在 僅出現(xiàn)在 在 在 例 :有關(guān)系模式 R(A,B,C,D,E,F,P) R 的函數(shù)依賴集為 F=AD,E D,D B,D,A,D F 則 C E F P 1. 快速求解候選關(guān)鍵字的充分條件 定理 對(duì)于給定的關(guān)系模式 ,若 X(X R)是 則 的任一候選關(guān)鍵字的成員 ,若 Y(Y R)是 則 若 Z (Z R)是 則的任一候選關(guān)鍵字中 . 推論 1 對(duì)于給定的關(guān)系模式 ，如果 類屬性，且 的全部屬性；則 的惟一候選關(guān)鍵字 推論 2 對(duì)于給定的關(guān)系模式及其函數(shù)依賴集 F，如果 的 類組成的屬性集，且 X+包含了 的惟一候選關(guān)鍵字 例 1 設(shè)有關(guān)系模式 R（ A,B,C,D),其函數(shù)依賴集 F=DB,BD, ,D, 求 解 :在 L 類屬性有 A,則 又 (=以 例 2 設(shè)有關(guān)系模式 R(A,B,C,D,E,P)及其函數(shù)依賴集 F=A D,E D,D B,D,A, 求 解 :考察 L 類屬性有 C,E ,則 又 (=以 的惟一候選關(guān)鍵字 定義 :在一個(gè)函數(shù)依賴圖中有下列術(shù)語 (1)引出線 /引入線 :若 A B, 則 是連接的 ,則 (A,B)是引出線 ,對(duì) (2)原始點(diǎn) :只有引出線而無引入線的結(jié)點(diǎn) ,它表示 (3)終結(jié)點(diǎn) :只有引入線而無引出線的結(jié)點(diǎn) ,它表示 (4)途中點(diǎn) :即有引入線又有引出線的結(jié)點(diǎn) ,對(duì)應(yīng) (5)孤立點(diǎn) :既無引入線又無引出線的結(jié)點(diǎn) ,對(duì)應(yīng) (6)關(guān)鍵點(diǎn) :原始點(diǎn)和孤立點(diǎn)統(tǒng)稱為關(guān)鍵點(diǎn) (7)關(guān)鍵屬性 :關(guān)鍵點(diǎn)對(duì)應(yīng)的屬性稱為關(guān)鍵屬性 (8)獨(dú)立回路 :不能被其他結(jié)點(diǎn)到達(dá)回路 數(shù)依賴圖示例 A B C D E F 原始點(diǎn) 途中點(diǎn) 終結(jié)點(diǎn) 孤立點(diǎn) 獨(dú)立回路 算法 單屬性依賴集圖論求解法 輸入 :關(guān)系模式 R, 輸出 : 方法 (1)求 (2)構(gòu)造函數(shù)依賴圖 (3)從圖中找出關(guān)鍵屬性集 X( (4)查看圖中有無獨(dú)立回路 ,若無則輸出 的惟一候選關(guān)鍵字 ,轉(zhuǎn) (6);若有 ,則轉(zhuǎn) (5) (5)從各獨(dú)立回路中各取一結(jié)點(diǎn)對(duì)應(yīng)的屬性與 并重復(fù)這一過程取盡所有可能的組合 ,即為 (6)結(jié)束 . 例 3 設(shè) R=O,B,I,S,Q,DF=SD,D S,I B,B I,B O,O B 求 解 : (1)F=F= SD,D S,I B,B I,B O,O B (2)構(gòu)造函數(shù)依賴圖如圖所示 S D O I B Q (3)關(guān)鍵屬性 Q (4)共有兩個(gè)獨(dú)立回路 ,以共有 2*3=6個(gè)候選關(guān)鍵字 (5) 3. 多屬性依賴集候選關(guān)鍵字求解法 算法 多屬性依賴集候選關(guān)鍵字求解法 輸入 :關(guān)系模式 輸出 : 方法 : (1)將 ,R,并令 ,(2)求 X+,若 X+包含了 則 的惟一候選關(guān)鍵字 ,轉(zhuǎn) (4),否則轉(zhuǎn) (3) (3)在 ,求 (,若它包含了 則為一個(gè)候選關(guān)鍵字 ,否則依次取兩個(gè) ,三個(gè) .的全部屬性 (4)結(jié)束 ,輸出結(jié)果 例 4 有一關(guān)系模式 R(求其全部候選關(guān)鍵字 解 :由生活常識(shí)可知 F=( (1) X= Y=(2)X+= (3)從 =從 =(4)所有 ( 述 關(guān)系數(shù)據(jù)庫中的關(guān)系必須滿足一定的規(guī)范化要求，對(duì)于不同的規(guī)范化程度可用范式（ 衡量。范式是符合某一種級(jí)別的關(guān)系模式的集合，是衡量關(guān)系模式規(guī)范化程度的標(biāo)準(zhǔn)，達(dá)到的關(guān)系才是規(guī)范化的。函數(shù)依賴的范圍主要有 4種范式：第一范式、第二范式、第三范式、足最低要求的叫第一范式，簡稱為 1第一范式基礎(chǔ)上進(jìn)一步滿足一些要求的為第二范式，簡稱為 2余以此類推。顯然各種范式之間存在聯(lián)系。 1 通常把某一關(guān)系模式 關(guān)系模式的級(jí)別 1) 全鍵 (1) 整個(gè)屬性組合是關(guān)系鍵 2) 主屬性 (鍵屬性 ) (1) 包含在任何一個(gè)候選鍵中的屬性 3) 非主屬性 (非鍵屬性 ) (1) 不包含在任何候選鍵中的屬性 例子 1) S(N,(1) 2) 2) ) (1) (2) 3) 奏者 P,作品 W,聽眾 A) (1) 之間為多對(duì)多關(guān)系，無函數(shù)依賴 (2) 全屬性集 (P,W,A)是鍵、主鍵、全鍵 (3) P,W,范式 1. 范式 ( 1) 定義 (1) 符合某種級(jí)別的關(guān)系模式的集合 (2) 如果一個(gè)關(guān)系滿足某個(gè)特定的約束值，則稱它屬于某種特定的范式 2) 各級(jí)范式的要求 (1) 第一范式：關(guān)系滿足只包含原子值的約束 (2) 第二范式：每個(gè)非主屬性都完全函數(shù)依賴于 (3) 第三范式：每個(gè)非主屬性都不傳遞依賴于 (4) (5) 第四范式：對(duì)于 Y ， (6) 第五范式：投影 連接范式 3) 各級(jí)范式的關(guān)系 (1) 5(2) 如果關(guān)系滿足某個(gè)范式要求，也會(huì)滿足級(jí)別較低的所有范式的要求 (3) 較高層次的范式比較低層次的范式具有更合乎要求 4) 模式分解（也叫規(guī)范化） 將一個(gè)低一級(jí)范式的關(guān)系模式通過投影運(yùn)算轉(zhuǎn)化為若干個(gè)高一級(jí)范式的關(guān)系模式的集合的過程 一范式 (1 1) 定義 (1) 若關(guān)系模式 (2) 則 R1 2) 說明 (1) 1 (2) 若 R1 3) 例子 (1) n,m,G) (2) (n)為關(guān)系鍵、候選鍵、主鍵 (3) 函數(shù)依賴關(guān)系 1. (N) G 2. n 3. m 4. m (4) 存在的問題 1. 插入異常 2. 刪除異常 3. 冗余太大 4. 修改異常 二范式 (2 1) 定義 (1) 在關(guān)系模式 R1(2) 且每個(gè)非主屬性都完全依賴于 (3) 則 R2 2) 例子 (1) S(N,1(2) (3) (4) (5) (6) (7) S2 3) 注意 (1) 如果關(guān)系 的主屬性，或者 么 R2 (2) 從 1可獲得2 4) 三個(gè)問題的解決 1. 插入異常有所改善 2. 刪除異常仍然存在 3. 冗余得到改善 示例 :現(xiàn)有關(guān)系模式其屬于第幾 學(xué)號(hào) ,課程號(hào) ,課程名 ,教師名 ,教師住址 ,成績 范式 ,為什么 ? 三范式 (3 11) 定義 若關(guān)系模式 R(U,F)中若不存在這樣的碼 X,屬性組 (ZY),使得 X Y,Y Z 且 ,則 R3即 (1) 若 R2(2) 且每個(gè)非主屬性都不傳遞依賴于 (3) 則 R3 2) 說明 (1) 每個(gè)非主屬性既不部分依賴，也不傳遞依賴于 (2) 從 1消除非主屬性對(duì)鍵的部分函數(shù)依賴 (3) 從 2消除非主屬性對(duì)鍵的傳遞函數(shù)依賴 3) 3設(shè)有關(guān)系 R(課程名 ,教師名 ,教師地址 )(注 :每門課程只由一名教師講解 ) 問 :它為第幾范式 ,為什么 ? 稱 1) 3(1) 3(2) 把能夠分離的屬性盡可能地分解為單獨(dú)的關(guān)系 (3) 但 3 2) (1) 若 R1(2) 如果對(duì)于 Y ， (3) 決定因素 )決定屬性集 (4) 則 R 3) 說明 (1) 在滿足 候選鍵之外沒有其他的決定因素 (決定屬性集 ) (2) 滿足 主屬性或非主屬性 )對(duì)鍵的部分依賴或傳遞依賴 (3)屬于 屬于 3例 有一關(guān)系模式 R(問其最高屬于第幾范式 解 :1）求候選關(guān)鍵字 F=( (1) X= Y=(2)X+= (3)從 =從 =(4)所有 (2）因有 而 在主屬性對(duì)碼的部分函數(shù)依賴，所以 R 3 關(guān)系模式的分解 無損連接性 無損連接性指的是對(duì)關(guān)系模式分解時(shí) ,原關(guān)系模式下的任一合法的關(guān)系實(shí)例在分解之后應(yīng)能通過自然連接運(yùn)算恢復(fù)起來 . 函數(shù)依賴保持性 函數(shù)依賴的保持性是指關(guān)系模式 注 :一個(gè)無損連接分解不一定具有依賴保持性 ;同樣 ,一個(gè)依賴保持性分解不一定具有無損連接性 、 分解到 2采用投影分解運(yùn)算 ,將部分依賴分解出去 示例 學(xué)號(hào) ,課程號(hào) ,課程名 ,教師名 ,教師住址 ,成績 要求將其分解成