2.1-第章 關(guān)系數(shù)據(jù)庫設(shè)計理論ppt課件

1、- 1-第5章 關(guān)系數(shù)據(jù)庫設(shè)計理論- 2-本章主要講解內(nèi)容本章主要講解內(nèi)容n 關(guān)系數(shù)據(jù)理論是關(guān)系數(shù)據(jù)庫的理論基礎(chǔ)，也是設(shè)計關(guān)系數(shù)據(jù)庫的指南。本章計論關(guān)系數(shù)據(jù)理論的基本概念、方法和題解。n 如何設(shè)計數(shù)據(jù)庫模式n 1) 設(shè)計一個好的關(guān)系數(shù)據(jù)庫模式概念模式）邏輯設(shè)計n 2) 憑經(jīng)驗設(shè)計？n 3) 什么是好的關(guān)系數(shù)據(jù)庫模式？n 4) 好的關(guān)系數(shù)據(jù)庫模式應(yīng)該包括多少關(guān)系模式？n 5) 每個關(guān)系模式應(yīng)該包含哪些屬性？n 6) 借助數(shù)學(xué)工具規(guī)定設(shè)計的理論和方法規(guī)范化- 3-5、1 數(shù)據(jù)存儲異常數(shù)據(jù)存儲異常n 假設(shè)有如下關(guān)系STUDENT：n STUDENTSNO,SNAME,SEX,CNO,SCORE表示學(xué)

2、號,姓名,性別,課程,成果 其中SNO,CNO是主關(guān)鍵字n 這個關(guān)系模式存在如下問題:n 數(shù)據(jù)冗余 一個學(xué)生選修多門課程,導(dǎo)致SNAME和SEX多次重復(fù)存儲.n 不一致性 由于數(shù)據(jù)存儲冗余,當更新某些數(shù)據(jù)項時,就有可能一部分修改了,而另一部分未修改,造成數(shù)據(jù)不一致性n 插入異常 如果某個學(xué)生未選課,他的信息(SNO,SNAME,SEX)就無法插入n 刪除異常 當要刪除所有學(xué)生成績時,將所有(SNO,SNAME,SEX)也都刪除了,這便是刪除異常- 4-n 為了克服上述這些異常,將STUDENT分解為如下兩個關(guān)系n STUDENT(SNO,SNAME,SEX)n SC(SNO,CNO,SCORE

3、)n 這是因為STUDENT關(guān)系中的某些屬性間存在數(shù)據(jù)依賴,數(shù)據(jù)依賴是現(xiàn)實世界事物之間的相互關(guān)聯(lián)性的一種表達,是屬性固有語義的體現(xiàn).人們只有對一個數(shù)據(jù)庫所要表達的現(xiàn)實世界進行認真的調(diào)查與分析,才能歸納與客觀事實相符合的數(shù)據(jù)依賴- 5-5.2 函數(shù)依賴函數(shù)依賴n 5.2.1 函數(shù)依賴(FD)的定義n 1) 函數(shù)依賴n 定義1 設(shè)R(U)是一個關(guān)系模式,X,Y是R的兩個屬性集合,X,YR,RX,Y是關(guān)系R在屬性XY上的投影,當任何時刻RX,Y中的任意兩個元組中的X屬性值相同時,則它的Y屬性值也相同,則稱X函數(shù)決定Y,或稱為Y函數(shù)依賴于X,記作XYn 例子n (1) S(SNO,SN,AGE,SEX

4、,DEPT)n (2) SNO函數(shù)決定 (SN,AGE,SEX,DEPT)n (3) (SN,AGE,SEX,DEPT)函數(shù)依賴于SNOn (4)SNO(SN,AGE,SEX,DEPT) n 2) 平凡函數(shù)依賴與非平凡函數(shù)依賴定義2 在關(guān)系R(U)中,對于U的子集X和Y,如果XY ,但Y不是X的了集,則XY是非平凡函數(shù)依賴.若Y 是X的子集,則稱XY為平凡函數(shù)依賴- 6-n 3)完全函數(shù)依賴與部分函數(shù)依賴n 設(shè)XY是一個FD,并且對于任何一個XX,X Y不成立,則稱XY是一個完全函數(shù)依賴,記作X Yn 設(shè)XY是一個FD,并且存在一個XX,使X Y成立,則稱XY是一個部分函數(shù)依賴,記作X Yn

5、例如n 1) SC(SNO,CNO,G) (SNO,CNO) G是完全函數(shù)依賴n (2)SC(SNO,CNO,SNAME,CNAME,G)n SNO,CNO是主鍵 (SNO,CNO) G n SNO SNAMEn CNO CNAMEn 所以存在部分函數(shù)依賴- 7-n 4)傳遞函數(shù)依賴n 設(shè) X,Y,Z是R互不相同的屬性集合 XY，Y X,且 YZ 則稱屬性集合Z傳遞(transfer)函數(shù)依賴于X ,記作 X Zn (1) UN(SNO,CN,G,DN,DM) (學(xué)號,課程名,成果,系名,系主任)n (2) SNODNn (3) DN SNOn (4) DNDM則DM傳遞函數(shù)依敕于SNO -

6、8-n 5.2.2函數(shù)依賴公理n 函數(shù)依賴的推導(dǎo)公理-Armstrong公理阿姆斯特朗公理）設(shè)有關(guān)系模式 RU），X，Y，Z，WU，那么：n A1自反性）：若YX，則XYn A2增廣性）：若XY，則XZ YZn A3傳遞性）：若XY， YZ，則XZn 由Armstrong公理可以得到以下推論n 合成規(guī)則：若XY， XZ，則XYZ；n 分解規(guī)則：若XYZ，則XY， XZ；n 偽傳遞規(guī)則：若XY，YW Z，則XW Z- 9-n 引理：XA1 A2 AN成立的充分必要條件是X AI成立(I=1,2,3.N)n 5、2、3函數(shù)依賴與屬性關(guān)系n 如果X和Y之間是1-1關(guān)系，則存在XY， YXn 如果X和

7、Y之間是“多對1關(guān)系，則存在XYn 如果X和Y之間是“多對多”，則X和Y 不存在函數(shù)依賴- 10-小結(jié)小結(jié)n 1) 函數(shù)依賴是完整性約束的一種特殊形式n 2) 函數(shù)依賴分為n (1) 完全函數(shù)依賴n (2) 部分函數(shù)依賴n (3) 傳遞函數(shù)依賴n 3) 函數(shù)依賴是規(guī)范化理論的依據(jù)n 4) 函數(shù)依賴是規(guī)范化程度的準則- 11-n 設(shè)有如下關(guān)系R：請僅在R中已給出數(shù)據(jù)的范圍內(nèi)分析其函數(shù)依賴關(guān)系 - 12-5.3 函數(shù)依賴的閉包函數(shù)依賴的閉包F+ 屬性閉包及其計算屬性閉包及其計算n 5.3.1函數(shù)依賴的閉包F+n 定義 關(guān)系模式R(U,F)中為F所邏輯蘊含的函數(shù)依賴的全體稱為F的閉包,記為:F+n

8、例:關(guān)系模式S(U,F),其中U=SNO,SNAME,SEX,AGEF=SNOSNAME,SNOSEX,SNOAGE- 13-5.3.2 屬性閉包及其計算屬性閉包及其計算n定義 設(shè)關(guān)系模式R(U),F為其函數(shù)依賴集,則稱所有用Armstrong公理從F推出的函數(shù)依賴XAi中的Ai的屬性集合為X的屬性閉包,記作X+n例: 有關(guān)系模式 S(SNO,SN,SEX,AGE)有 SNO SN,SNO SEX,SNO AGE則有SNO+=SNO,SN,SEX,AGEn定理 設(shè)關(guān)系模式R(U),F為其函數(shù)依賴集,X,YU,則從F推出X Y的充分必要條件是Y X+- 14-算法算法5.1 求屬性集求屬性集X關(guān)

9、于函數(shù)依賴關(guān)于函數(shù)依賴F的屬性閉包的屬性閉包X+n 算法 求屬性的閉包X+n輸入 X,F n輸出 X+n步驟 n(1)令X(0)=X,I=0n(2)求B,B=A|(V)(W)(V W FV X(I)AW(A是這樣的屬性:在F中尋找尚未用過的左邊是X(I)的子集的函數(shù)依賴)n(3)X(I+1)=BX(I)n(4)判斷X(I+1)=X(I)嗎?n(5)若相等,或X(I)=U,則X(I)為屬性集X的屬性閉包.且算法終止n(6)若不相等,則I=I+1,返回第2步.- 15-屬性閉包計算示例屬性閉包計算示例n 例1 已知關(guān)系模式R(U,F),U=A,B,C,D,E;F=AB, DC,BC E,AC B求

10、(AE)+ ,(AD)+n 解 求(AE)+ n 設(shè)X(0)=AEn 計算X(1) : 逐一掃描F中的各個函數(shù)依賴,找出左部為A,E或AE的函數(shù)依賴,得到一個: AB.故有X(1)=AEB=ABEn 計算X(2):逐一掃描F中的各個函數(shù)依賴,找到左部為A,B,E或AB,AE,BE,ABE的函數(shù)依賴,示發(fā)現(xiàn)有新的函數(shù)依賴X(2)=X(1)=ABE 有 X(1)=X(2),算法終止, (AE)+ =ABEn (注:因為找不到新的函數(shù)依賴,即F中未用過的函數(shù)依賴的左邊屬性已沒有X(1)的子集,所以,不必再計算下去,算法終止)n 練習(xí) 求(AD)+- 16-n 解 求(AD)+n X(0)=ADn 求

11、X(1):逐一掃描F中的各個函數(shù)依賴,找出左部為A,D或AD的函數(shù)依賴,得到: AB,D C,故有X(1)=ABCDn 求X(2):逐一掃描F中的各個函數(shù)依賴,找出左部為ABCD或其子集的函數(shù)依賴,得到: BCE,AC B,故有X(2)=ABCDEn 因為X(2)=U,故算法終止, (AD)+=ABCDE- 17-例例2n 設(shè)有關(guān)系模式R(U,F),其中U=A,B,C,D,E,I;F=AD,AB E, BIE,CD I,E C計算(AE)+n 解:n 設(shè)X(0)=AEn 求X(1) 在F的左部找出AE及其子集的函數(shù)依賴,有AD,E C 所以X(1)=ACDEn 求X(2) 在F的左部找出ACD

12、E及其子集的函數(shù)依賴,新的依賴有CDI 所以X(2)=ACDEI n 求X(3) 因為在F中未用過的函數(shù)依賴左邊屬性已沒有X(2)的子集,所以不必再計算,即X(3)=X(2),算法終止n (AE)+=ACDEI- 18-n練習(xí) 設(shè)有函數(shù)依賴集F=DG,C A,CD E,A B計算閉包D+ ,C+, A+ ,(CD)+ ,(AD)+, (AC)+, (ACD)+- 19-5.4 函數(shù)依賴的等價與覆蓋函數(shù)依賴的等價與覆蓋 n 5.4.1 等價與覆蓋n 定義: 一個關(guān)系模式R(U)上的兩個依賴集F和G,如果F+=G+,則稱F和G是等價的,記作F G.n 如果函數(shù)依賴集FG.則稱G是F的一個覆蓋,反之

13、亦然n 兩個等價的依賴集在表示能力上是完全相同的.- 20-5.4.2 函數(shù)依賴集的最小集函數(shù)依賴集的最小集n 簡稱為最小函數(shù)依賴集n 定義 :對于給定的函數(shù)依賴F,當滿足下列條件時,稱為F的最小集,記作F:n F的每個依賴的右部都是單個屬性n 對于F中的任何一個函數(shù)依賴XA, F-XA與F都不等價n 對于F中的任何一個XA和X的真子集Z,(F-XA) ZA與F都不等價n 說明:條件(2)保證了在F中不存在多余的函數(shù)依賴;條件(3)保證了F中每個函數(shù)依賴的左邊沒有多余的屬性- 21-5.4.3 最小依賴集的求解算法最小依賴集的求解算法n算法4.2 計算最小依賴集n輸入:一個函數(shù)依賴集Fn輸出:

14、F的一個等價最小依賴集Fn方法:n(1)應(yīng)用分解規(guī)則,使F中每一個依賴的右部屬性單一化n(2)去掉各依賴左部多余的屬性.具體做法是:一個一個地檢查F中左邊是非單屬性的依賴,例如XYA,現(xiàn)在要判斷Y是否為多余的,則以XA代替XYA是否等價?只要在F中求X+,若X+包含A,則Y是多余的屬性;否則Y不是多余的屬性.依次判斷其他屬性即可消除各依賴左邊的多余屬性.n(3)去掉多余的依賴.具體做法是:從第一個依賴開始,從F中去掉它(假設(shè)該依賴為XY),然后在剩下的依賴中求X+,看X+是否包含Y,若是,則去掉XY;若不包含Y,則不能去掉XY.n(4)這樣依次做下去.- 22-n 例 設(shè)有依賴集:F=ABC,

15、C A,BC D,ACD B,D EG,BE C,CG BD,CE AG計算其等價的最小依賴集.n 解:n (1)將依賴右邊屬性單一化,結(jié)果為n F1=AB C BE CC A CG BBC D CG DACD B CE AD E CE GD G- 23-n (2)在F1中去掉依賴左部多余的屬性,因為有C A,則對CE A,E是多余的,對于ACD B,若去掉A,由于(CD)+=ABCDEG,則A是多余的,刪除依賴左部多余的依賴后:n F2=AB C BE CC A CG BBC D CG DCD B C AD E CE GD G- 24- n (3)在F2中去掉多余的依賴.對于CG B,去掉他

16、,仍有(CG)+=ABCDEG,則是多余的,刪除多余的依賴后: n F3=AB C D GC A BE CBC D CG DCD B CE GD EAB C BE CC A CG BBC D CG DCD B C AD E CE GD G注意：F的最小依賴集不一定是惟一的，它與對各函數(shù)依賴FD及XA中X各屬性的處理順序有關(guān)。F3即是求得的最小函數(shù)依賴集F- 25-5.5 候選關(guān)鍵字的求解理論與算法候選關(guān)鍵字的求解理論與算法n 候選關(guān)鍵字: 屬性或?qū)傩缘淖钚〗M合,其值能夠惟一地標識一個元組.n 對于給定的關(guān)系R(A1,A2,An)和函數(shù)依賴集F,可將其屬性分為四類:n L類:僅出現(xiàn)在F的函數(shù)依賴

17、左部的屬性n R類:僅出現(xiàn)在F的函數(shù)依賴右部的屬性n N類:在F的函數(shù)依賴左右兩邊均未出現(xiàn)的屬性n LR類:在F的函數(shù)依賴左右兩邊均出現(xiàn)的屬性n 例:有關(guān)系模式R(A,B,C,D,E,F,P) R 的函數(shù)依賴集為F=AD,E D,D B,BC D,DC A,D F那么n L類屬性有:C En R類屬性有:Fn LR類屬性有:ABDn N類屬性:P- 26-n5.5.1 快速求解候選關(guān)鍵字的充分條件快速求解候選關(guān)鍵字的充分條件n定理定理 對于給定的關(guān)系模式對于給定的關(guān)系模式R及其函數(shù)依賴及其函數(shù)依賴F,若若X(XR)是是L類屬性類屬性,則則X必為必為R的任一候選的任一候選關(guān)鍵字的成員關(guān)鍵字的成員

18、,若若Y(Y R)是是R類屬性類屬性,則則Y不不在任何候選關(guān)鍵字中在任何候選關(guān)鍵字中,若若Z (Z R)是是N類屬性類屬性,則則Z必包含在必包含在R的任一候選關(guān)鍵字中的任一候選關(guān)鍵字中.n推論推論1 對于給定的關(guān)系模式對于給定的關(guān)系模式R及其函數(shù)依賴集及其函數(shù)依賴集F，如果，如果X是是L類屬性，且類屬性，且X+包含了包含了R的全部的全部屬性；則屬性；則X必為必為R的惟一候選關(guān)鍵字的惟一候選關(guān)鍵字n推論推論2 對于給定的關(guān)系模式及其函數(shù)依賴集對于給定的關(guān)系模式及其函數(shù)依賴集F，如果如果X是是R的的N類和類和L類組成的屬性集，且類組成的屬性集，且X+包含了包含了R的全部屬性，則的全部屬性，則X是是

19、R的惟一候選關(guān)的惟一候選關(guān)鍵字鍵字- 27- 28-n 5.5.2 左邊為單屬性的函數(shù)依賴集的候選關(guān)鍵字成員的圖論判定方法n 定義:在一個函數(shù)依賴圖中有下列術(shù)語n (1)引出線/引入線:若A B,則A與B是連接的,那么(A,B)是引出線,對B而言是引入線n (2)原始點:只有引出線而無引入線的結(jié)點,它表示L類屬性n (3)終結(jié)點:只有引入線而無引出線的結(jié)點,它表示R類屬性n (4)途中點:即有引入線又有引出線的結(jié)點,對應(yīng)LR類屬性n (5)孤立點:既無引入線又無引出線的結(jié)點,對應(yīng)N類屬性n (6)關(guān)鍵點:原始點和孤立點統(tǒng)稱為關(guān)鍵點n (7)關(guān)鍵屬性:關(guān)鍵點對應(yīng)的屬性稱為關(guān)鍵屬性n (8)獨立回

20、路:不能被其他結(jié)點到達回路- 29-函數(shù)依賴圖示例函數(shù)依賴圖示例ABCDEF原始點 途中點 終結(jié)點孤立點孤立點獨立回路R(A,B,C,D,E,F) F=A B,B C,E F,FE- 30- n 算法 單屬性依賴集候選關(guān)鍵字圖論求解法n 輸入:關(guān)系模式R,R的單屬性函數(shù)依賴集Fn 輸出:R的所有候選關(guān)鍵字n 方法n (1)求F的最小函數(shù)依賴集Fn (2)構(gòu)造函數(shù)依賴圖FDG(Functional Dependencies Graph)n (3)從圖中找出關(guān)鍵屬性集X(X可為空)n (4)查看圖中有無獨立回路,若無則輸出X即為R的惟一候選關(guān)鍵字,轉(zhuǎn)(6);若有,則轉(zhuǎn)(5)n (5)從各獨立回路中

21、各取一結(jié)點對應(yīng)的屬性與X組合成一候選關(guān)鍵字,并重復(fù)這一過程取盡所有可能的組合,即為R的全部候選關(guān)鍵字n (6)完畢.- 31-SDOIBo(3)關(guān)鍵屬性Qo(4)共有兩個獨立回路,SDS,IBOBI,所以共有2*3=6個候選關(guān)鍵字o(5)R的所有候選關(guān)鍵字為:QSI,QSB,QSO,QDI,QDB,QDO- 32-n 5.5.3 多屬性依賴集候選關(guān)鍵字求解法n 算法 多屬性依賴集候選關(guān)鍵字求解法n 輸入:關(guān)系模式R與函數(shù)依賴集Fn 輸出:R的所有候選關(guān)鍵字n 方法:n (1)將R的所有屬性分為L,R,N和LR四類,并令X代表L,N兩類,Y代表LR類n (2)求X+,若X+包含了R的全部屬性,則

22、X為R的惟一候選關(guān)鍵字,轉(zhuǎn)(4),否則轉(zhuǎn)(3)n (3)在Y任取所有一個屬性A,求(XA)+,若它包含了R的全部屬性,則為一個候選關(guān)鍵字,否則依次取兩個,三個.直至其屬性閉包包含了R的全部屬性n (4)完畢,輸出結(jié)果- 33- 34-Exercises on Functional Dependenciesn Questions:- 35-Consider a relation R(A, B, C, D, E) with the following dependencies:AB C, CD E, DE BIs AB a candidate key of this relation? If no

23、t, is ABD? Explain your answer. 設(shè)有關(guān)系R(A,B,C,D,E),F=(AB)-C,(AB)-D,A-E請解答如下問題：（1指出其全部候選關(guān)鍵字設(shè)有關(guān)系R(A,B,C,D,E),F=A-B,A-C,（AD）-E 請解答如下問題：（1指出其全部候選關(guān)鍵字- 36-5.6 關(guān)系模式分解的級別關(guān)系模式分解的級別-范式范式n 5.6.1. 屬性鍵n 1) 全碼n (1) 整個屬性組合是關(guān)系鍵n 2) 主屬性(鍵屬性)n (1) 包含在任何一個候選鍵候選關(guān)鍵字中的屬性n 3) 非主屬性(非鍵屬性)n (1) 不包含在任何候選鍵中的屬性n 例子n 1) S(SNO,SN,A

24、GE,SEX,DEPT)n (1) SNO是主屬性(2) SN,AGE,SEX,DEPT是非主屬性n 2) SC(SNO,CNO,G)n (1) SNO,CNO是主屬性 (2) G是非主屬性n 3) PWA(演奏者P,作品W,聽眾A)n (1) 之間為多對多關(guān)系，無函數(shù)依賴(2) 全屬性集(P,W,A)是鍵、主鍵、全碼(3) P,W,A都是主屬性- 37-5.6.2范式范式n 1. 范式(NF, Normal Formula)n 1) 定義n (1) 符合某種級別的關(guān)系模式的集合n (2) 如果一個關(guān)系滿足某個特定的約束值，則稱它屬于某種特定的范式n 2) 各級范式的要求n (1) 第一范式：

25、關(guān)系滿足只包含原子值的約束n (2) 第二范式：每個非主屬性都完全函數(shù)依賴于R的每個鍵n (3) 第三范式：每個非主屬性都不傳遞依賴于R的任何鍵n (4) BC范式：R中每個決定因數(shù)都是候選鍵n (5) 第四范式：對于R的每個非平凡多值依賴XY，X都含有候選碼n (6) 第五范式：投影連接范式- 38-n 3) 各級范式的關(guān)系n (1) 5NF4NFBCNF3NF2NF1NFn (2) 如果關(guān)系滿足某個范式要求，也會滿足級別較低的所有范式的要求n (3) 較高層次的范式比較低層次的范式具有更合乎要求n 4) 模式分解也叫規(guī)范化）n 將一個低一級范式的關(guān)系模式通過投影運算轉(zhuǎn)化為若干個高一級范式的

26、關(guān)系模式的集合的過程- 39-第一范式第一范式(1NF)n 1) 定義n (1) 若關(guān)系模式R的所有屬性都是不可分的基本數(shù)據(jù)項n (2) 則R1NFn 2) 說明n (1) 1NF是關(guān)系模式的最起碼要求n (2) 若R1NF，則R不是關(guān)系數(shù)據(jù)庫n 3) 例子n (1) UN(Sno,Cno,Dname,Dm,G)n (2) (Sno,Cn)為關(guān)系鍵、候選鍵、主鍵n (3) 函數(shù)依賴關(guān)系n 1. (SNO,CNo) Gn 2. SnoDnamen 3.DnDm- 40-n (4) 存在的問題n 1. 插入異常n 2. 刪除異常n 3. 冗余太大n 4. 修改異常- 41-第二范式第二范式(2NF

27、)n 1) 定義n (1) 在關(guān)系模式R1NF的基礎(chǔ)上n (2) 且每個非主屬性都完全依賴于R的每個關(guān)系鍵n (3) 則R2NFn 2) 例子n (1) S(SNO,SN,AGE,SEX,DEPT)1NFn (2) SNO(SN,AGE,SEX,DEPT)n (3) SN(SNO,AGE,SEX,DEPT)n (4) SNO為候選鍵n (5) SNO,AGE,SEX,DEPT是非主屬性n (6) SNO,AGE,SEX,DEPT完全依賴于每個鍵n (7) S2NF- 42-n 3) 注意n (1) 如果關(guān)系R的全體屬性都是R的主屬性，或者R的所有鍵僅含有一個屬性，那么R2NF。n (2) 從1

28、NF中消除非主屬性對鍵的部分函數(shù)依賴，則可獲得2NF關(guān)系n 4) 三個問題的解決n 1. 插入異常有所改善n 2. 刪除異常仍然存在n 3. 冗余得到改善- 43-n 例如:現(xiàn)有關(guān)系模式SC(SNO,CNO,CTITLE,GRADE)問其屬于第幾范式,為什么? 解: (1)求候選鍵 由題意 F=(SNO,CNO)-G,CNO-CTITLE，L 類屬性為SNO,CNO,又(SNO,CNO)+=U,那么(SNO,CNO)為唯一候選關(guān)鍵字 (2)關(guān)系模式S最高為1NF 因為存在CNO-CTITLE,即非主屬性對碼的部分函數(shù)依賴.- 44- 第三范式第三范式(3NF)n (1) 定義n 若關(guān)系模式R(

29、U,F)中若不存在這樣的碼X,屬性組Y及非主屬性Z(ZY),使得X Y,Y Z且Y不能函數(shù)決定X,那么 R3NFn 即n (1) 若R2NFn (2) 且每個非主屬性都不傳遞依賴于R的任何鍵n (3) 則R3NFn 2) 說明n (1) 每個非主屬性既不部分依賴，也不傳遞依賴于R的任何鍵n (2) 從1NF2NF：消除非主屬性對鍵的部分函數(shù)依賴n (3) 從2NF3NF：消除非主屬性對鍵的傳遞函數(shù)依賴- 45-n 3) 3NF的題解n 設(shè)有關(guān)系 R(課程名,教師名,教師地址)(注:每門課程只由一名教師講解)n 問:它能否達到第三范式,為什么? 解: (1)求候選鍵 由題意 F=課程名-教師名,

30、教師名-教師地址 L 類屬性為課程名,又(課程名)+=U,那么(課程名)為唯一候選關(guān)鍵字 (2)關(guān)系模式R最高為2NF 因為存在教師地址傳遞函數(shù)依賴于課程名,即非主屬性對碼的傳遞函數(shù)依賴.- 46- Boyce-Codd范式范式(BCNF)簡稱簡稱BC范式范式n 1) 3NF的不完善性n (1) 3NF排除了非主屬性對鍵的部分函數(shù)依賴和傳遞函數(shù)依賴n (2) 把能夠分離的屬性盡可能地分解為單獨的關(guān)系n (3) 但3NF沒有限制有些主屬性對鍵具有的函數(shù)依賴- 47-n 2) BCNF定義n (1) 若R1NFn (2) 如果對于R的每個函數(shù)依賴XY，X必含有候選鍵n (3) R中的每個(決定因素

31、)決定屬性集X都是候選鍵n (4) 則RBCNFn 3) 說明n (1) 在滿足BCNF的關(guān)系中，除候選鍵之外沒有其他的決定因素(決定屬性集)n (2) 滿足BCNF的關(guān)系將消除任何屬性(主屬性或非主屬性)對鍵的部分依賴或傳遞依賴n (3)屬于BCNF的關(guān)系必然屬于3NF，但屬于3NF的關(guān)系卻不一定屬于BCNF - 48-Consider this Relation and FDs- 49-Outlinen In this section, we describe some of the relational database design algorithms that utilize fu

32、nctional dependency and normalization theory.n We first describe the two desirable properties of decompositions, namely, the dependency preservation property and the lossless join property.n We then introduce the decompositions algorithms to achieve higher normal forms like 3NF,and BCNF- 50-What is

33、Decomposition?n Decomposition the process of breaking down in parts or elements.n Decomposition in database means breaking tables down into multiple tablesn From Database perspective means going to a higher normal form- 51-DecompositionTwo Characteristics of Good Decompositions1) Lossless2) Preserve

34、 dependencies- 52-What is lossless?nLossless means functioning without a loss.nIn other words, retain everything.nImportant for databases to have this feature. - 53-Lossless Join Decompositions- 54-Algorithm : Testing for Lossless (nonadditive) Join Propertyn Input: A universal relation R, a decompo

35、sition 0 = R1, R2, . , Rml of R, and a set F of functional dependencies.n 1. Create an initial matrix S with one row i for each relation Ri in D, and one column j for each attribute Aj in R.n 2. Set S(i, j):= bij for all matrix entries.n (* each bij is a distinct symbol associated with index (i, j)

36、*)- 55- 56- 57-Example 1 for lossless join testing- 58-Example 2 for lossless join testingn Consider the following relation schema R(A,B,C,D,E) and a set of FDs F=AC,B C,C D,DE C,CE A. Determine whether the following decomposition has the lossless join property.n =R1(A,D)，R2(A,B)，R3(B,E), R4(C,D,E),

37、R5(A,E )- 59-構(gòu)造二維表構(gòu)造二維表 A B C D ER1R2R3a1a3a2a1b23R4R5a5a4a2a4a1a5a5b13b33b53b12b15b24b25b34b31b54b52b42b41- 60-由由AC,做的修改做的修改 A B C D ER1R2R3a1a3a2a1b23R4R5a5a4a2a4a1a5a5b13b33b53b12b15b24b25b34b31b54b52b42b41b13b13- 61-由由BC,做的修改做的修改 A B C D ER1R2R3a1a3a2a1b13R4R5a5a4a2a4a1a5a5b13b33b12b15b24b25b34b

38、31b54b52b42b41b13b13- 62-由由CD做的修改做的修改 A B C D ER1R2R3a1a3a2a1b13R4R5a5a4a2a4a1a5a5b13b13b13b12b15b24b25b34b31b54b52b42b41a4a4a4- 63-由由DEC做的修改做的修改 A B C D ER1R2R3a1a3a2a1b13R4R5a5a4a2a4a1a5a5b13b13b13b12b15b25b31b52b42b41a4a4a4a3- 64-結(jié)果二維表結(jié)果二維表 A B C D ER1R2R3a1a3a2a1R4R5a5a4a2a4a1a5a5b12b15b25b52b42

39、a3a3b13a3a1a1a4a4a4算法輸出算法輸出true 是無損的是無損的- 65-Dependency PreservationProperty of a Decompositionn We say that a decomposition D = R1, R2, . , Rm of R is dependency-preserving with respect to F ifn the union of the projections of F on each Ri in D is equivalent to F; that is,- 66-Example for dependency preservationn Consider the relation R(A,B,C,D) with F=AB,CD, Determine whether each following decomposition D OF R has the dependency-preserving property.n a) R1(A,B) ,R2(C,D)n b) R1(A,B,C),R2(A,D) - 67-Algorithm : Decomposition into 3NF with Dependency Preservation and lossless joinn1. F