數(shù)據(jù)庫原理第6章(最終稿).ppt

1、數(shù)據(jù)庫系統(tǒng)概論 An Introduction to Database System 第六章 關(guān)系數(shù)據(jù)理論,問題的提出,數(shù)據(jù)庫設(shè)計 數(shù)據(jù)庫概念設(shè)計(ER模型) 數(shù)據(jù)庫邏輯設(shè)計 數(shù)據(jù)庫物理設(shè)計,問題? 1.針對一個具體問題，應(yīng)如何構(gòu)造一個適合于它的數(shù)據(jù)模式，即應(yīng)該構(gòu)造幾個關(guān)系，每個關(guān)系由哪些屬性組成等 2.設(shè)計的工具:規(guī)范化理論,例:職員部門數(shù)據(jù)庫的兩種可能設(shè)計,冗余數(shù)據(jù)多 容易出現(xiàn)數(shù)據(jù)不一致,方案一,方案二,第六章 關(guān)系數(shù)據(jù)理論,6.1 問題的提出 6.2 規(guī)范化 6.3 數(shù)據(jù)依賴的公理系統(tǒng) *6.4 模式的分解,概念回顧,關(guān)系：描述實體、屬性、實體間的聯(lián)系。 從形式上看，它是一張二維表，是所

2、涉及屬性的笛卡爾積的一個子集。 關(guān)系模式：關(guān)系的描述。 關(guān)系數(shù)據(jù)庫：基于關(guān)系模型的數(shù)據(jù)庫，利用關(guān)系來描述現(xiàn)實世界。 從形式上看，它由一組關(guān)系組成。 關(guān)系數(shù)據(jù)庫的模式：定義這組關(guān)系的關(guān)系模式的全體。,概念回顧(續(xù)),關(guān)系模式的形式化定義: R(U, D, DOM, F) R： 關(guān)系名 U： 組成該關(guān)系的屬性名集合 D： 屬性組U中屬性所來自的域 DOM：屬性向域的映象集合 F： 屬性間數(shù)據(jù)的依賴關(guān)系集合 可以將關(guān)系模式看成一個三元組： R(U, F),本章討論: F,函數(shù)依賴 Functional Dependency 簡記為FD,多值依賴 Multivalued Dependency 簡記為M

3、VD,函數(shù)依賴的舉例,例：描述學(xué)校的數(shù)據(jù)庫： 學(xué)生的學(xué)號（Sno）、所在系（Sdept） 系主任姓名（Mname）、課程名（Cname） 成績（Grade） 設(shè)計為關(guān)系模式 ： Student 其中: U Sno, Sdept, Mname, Cname, Grade F是什么?,關(guān)系模式Student中存在的問題, 數(shù)據(jù)冗余太大 見教材P171頁 浪費大量的存儲空間 例：每一個系主任的姓名重復(fù)出現(xiàn)、學(xué)生姓名也重復(fù) 更新異常（Update Anomalies） 數(shù)據(jù)冗余 ，更新數(shù)據(jù)時，維護(hù)數(shù)據(jù)完整性代價大。 例：某系更換系主任后，系統(tǒng)必須修改與該系學(xué)生有關(guān)的每一個元組,關(guān)系模式Student中

4、存在的問題, 插入異常（Insertion Anomalies） 該插的數(shù)據(jù)插不進(jìn)去 例，如果一個系剛成立，尚無學(xué)生，我們就無法把這個系及其系主任的信息存入數(shù)據(jù)庫。 刪除異常（Deletion Anomalies） 不該刪除的數(shù)據(jù)不得不刪 例，如果某個系的學(xué)生全部畢業(yè)了， 我們在刪除該系學(xué)生信息的同時，把這個系及其系主任的信息也丟掉了。,數(shù)據(jù)依賴對關(guān)系模式的影響,結(jié)論： Student關(guān)系模式不是一個好的模式。 “好”的模式： 不會發(fā)生插入異常、刪除異常、更新異常， 數(shù)據(jù)冗余應(yīng)盡可能少。 原因：由存在于模式中的某些數(shù)據(jù)依賴引起的 解決方法：通過分解關(guān)系模式來消除其中不合適 的數(shù)據(jù)依賴。,什么是

5、函數(shù)依賴,1. 非形式化定義: ”函數(shù)”依賴表示為： X1X2X3XnY，類似于Y=f(X) 即：取一組值，分別對應(yīng)于屬性X1X2X3Xn，結(jié)果對應(yīng)于Y產(chǎn)生唯一值(或者是空值),是通過一個關(guān)系中屬性間值的相等與否體現(xiàn)出來的數(shù) 據(jù)間的相互關(guān)系 是現(xiàn)實世界屬性間相互聯(lián)系的抽象 是數(shù)據(jù)內(nèi)在的性質(zhì) 是語義的體現(xiàn),函數(shù)依賴的舉例（續(xù)）,F是由如下的語義來體現(xiàn)： 一個系有若干學(xué)生， 一個學(xué)生只屬于一個系； 一個系只有一名主任； 一個學(xué)生可以選修多門課 程,每門課程有若干學(xué)生選修; 每個學(xué)生所學(xué)的每門課程都有一個成績。,例：描述學(xué)校的數(shù)據(jù)庫： 學(xué)生的學(xué)號（Sno）、所在系（Sdept）系主任姓名Mname）

6、、 課程名（Cname）、績（Grade） 設(shè)計為關(guān)系模式 ： Student 其中: U Sno, Sdept, Mname, Cname, Grade F是什么?,函數(shù)依賴的舉例（續(xù)）,屬性組U上的一組函數(shù)依賴F： F Sno Sdept, Sdept Mname, (Sno, Cname) Grade ,6.2 規(guī)范化,規(guī)范化理論是用來改造關(guān)系模式，通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問題。,6.2.1 函數(shù)依賴,一、函數(shù)依賴 二、平凡函數(shù)依賴與非平凡函數(shù)依賴 三、完全函數(shù)依賴與部分函數(shù)依賴 四、傳遞函數(shù)依賴,一、函數(shù)依賴,定義6.1

7、設(shè)R(U)是一個屬性集U上的關(guān)系模式，X和Y是U的子集，r為R(U) 的任意一個可能的關(guān)系。,t1,t2,A,t1,t2r 當(dāng)t1X=t2X時， 必有 t1 Y=t2Y成立 則稱 “X函數(shù)確定Y” 或 “Y函數(shù)依賴于X”。 X稱為這個函數(shù)依賴的決定屬性集 記作XY。,類似Y=f(X),XY的進(jìn)一步解釋,新關(guān)系X,Y(R)的元組在X分量上的值不重復(fù),對于R的任意一個可能的關(guān)系r中的元組，由X上的分量可惟一確定Y上的分量,對于R的任意一個可能的關(guān)系r，r中不可能存在兩個元組在X上的屬性值相等， 而在Y上的屬性值不等。,函數(shù)依賴（續(xù)）,說明：,1. 函數(shù)依賴不是指關(guān)系模式R的某個或某些關(guān)系實例滿足的

8、約束條件，而是指R的所有關(guān)系實例均要滿足的約束條件。 2. 函數(shù)依賴是語義范疇的概念，只能根據(jù)數(shù)據(jù)的語義來確定函數(shù)依賴。 3. 數(shù)據(jù)庫設(shè)計者可以對現(xiàn)實世界作強(qiáng)制的規(guī)定。例如規(guī)定不允許同名人出現(xiàn)，函數(shù)依賴“姓名年齡”成立。所插入的元組必須滿足規(guī)定的函數(shù)依賴，若發(fā)現(xiàn)有同名人存在， 則拒絕裝入該元組。,函數(shù)依賴的相關(guān)符號含義,若XY，并且YX, 則記為XY。 若Y不函數(shù)依賴于X, 則記為XY。,函數(shù)依賴（續(xù)）,例: Student(Sno, Sname, Ssex, Sage, Sdept) 假設(shè)不允許重名，則有: Sno Ssex，Sno Sage , Sno Sdept， Sno Sname,

9、Sname Ssex，Sname Sage，Sname Sdept 但Ssex Sage,二、平凡函數(shù)依賴與非平凡函數(shù)依賴,在關(guān)系模式R(U)中，對于U的子集X和Y， 如果XY，但Y X，則稱XY是非平凡的函數(shù)依賴 若XY，但Y X, 則稱XY是平凡的函數(shù)依賴 例：在關(guān)系SC(Sno, Cno, Grade)中， 非平凡函數(shù)依賴： (Sno, Cno) Grade 平凡函數(shù)依賴： (Sno, Cno) Sno ，(Sno, Cno) Cno,對于任一關(guān)系模式，平凡函數(shù)依賴都是必然成立的。僅需討論非平凡函數(shù)依賴,三、完全函數(shù)依賴與部分函數(shù)依賴,定義6.2 在關(guān)系模式R(U)中，如果XY，并且對于

10、X的任何一個真子集X，都有 X Y, 則稱Y完全函數(shù)依賴于X，記作X F Y。 若XY，但Y不完全函數(shù)依賴于X，則稱Y部分函數(shù)依賴于X，記作X P Y。,完全函數(shù)依賴與部分函數(shù)依賴（續(xù)）,例: 在關(guān)系SC(Sno, Cno, Grade)中， 由于：Sno Grade，Cno Grade， 因此：(Sno, Cno) F Grade,四、傳遞函數(shù)依賴,定義6.3 在關(guān)系模式R(U)中，如果XY，YZ，且Y X，YX，則稱Z傳遞函數(shù)依賴于X。 注: 如果YX， 即XY，則Z直接依賴于X。 例: 在關(guān)系Std(Sno, Sdept, Mname)中，有： Sno Sdept，Sdept Mname

11、 Mname傳遞函數(shù)依賴于Sno,6.2.2 碼,定義6.4 設(shè)K為關(guān)系模式R中的屬性或?qū)傩越M合。若K F U，則K稱為R的一個侯選碼（Candidate Key）。若關(guān)系模式R有多個候選碼，則選定其中的一個做為主碼（Primary key）。 主屬性與非主屬性 ALL KEY,外部碼,定義6.5 關(guān)系模式 R 中屬性或?qū)傩越MX 并非R的碼，但 X 是另一個關(guān)系模式的碼，則稱 X 是R 的外部碼（Foreign key）也稱外碼 主碼又和外部碼一起提供了表示關(guān)系間聯(lián)系的手段。,6.2.3 范式,范式是符合某一種級別的關(guān)系模式的集合。 范式的種類： 第一范式(1NF) 第二范式(2NF) 第三范

12、式(3NF) BC范式(BCNF) 第四范式(4NF) 第五范式(5NF),6.2.3 范式,各種范式之間存在聯(lián)系： 某一關(guān)系模式R為第n范式，可簡記為RnNF。,6.2.4 1NF,1NF的定義 如果一個關(guān)系模式R的所有屬性值都是不可分的基本數(shù)據(jù)項，則R1NF。 第一范式是對關(guān)系模式的最起碼的要求。不滿足第一范式的數(shù)據(jù)庫模式不能稱為關(guān)系數(shù)據(jù)庫。 但是滿足第一范式的關(guān)系模式并不一定是一個好的關(guān)系模式。,例: 關(guān)系模式 SLC(Sno, Sdept, Sloc, Cno, Grade) Sloc為學(xué)生住處，假設(shè)每個系的學(xué)生住在同一個地方。 函數(shù)依賴包括： (Sno, Cno) F Grade S

13、no Sdept (Sno, Cno) P Sdept Sno Sloc (Sno, Cno) P Sloc Sdept Sloc,SLC的一個實例,候選碼？,SLC的候選碼為(Sno, Cno) SLC滿足第一范式。 非主屬性Sdept和Sloc部分函數(shù)依賴于碼(Sno, Cno),SLC存在的問題,插入異常,刪除異常,數(shù)據(jù)冗余度大,修改復(fù)雜,SLC不是一個好的關(guān)系模式,原因 Sdept、 Sloc部分函數(shù)依賴于碼。 解決方法 SLC分解為兩個關(guān)系模式，以消除這些部分函數(shù)依賴 SC（Sno， Cno， Grade） SL（Sno， Sdept， Sloc）,原來的函數(shù)依賴圖：,SLC的碼為(

14、Sno, Cno) SLC滿足第一范式。 非主屬性Sdept和Sloc部分函數(shù)依賴于碼(Sno, Cno),分解后的函數(shù)依賴圖：,第二范式：2NF,2NF的定義 定義6.6 若關(guān)系模式R1NF，并且每一個非主屬性都完全函數(shù)依賴于R的碼，則R2NF。 例：SLC(Sno, Sdept, Sloc, Cno, Grade) 1NF SLC(Sno, Sdept, Sloc, Cno, Grade) 2NF SC（Sno， Cno， Grade） 2NF SL（Sno， Sdept， Sloc） 2NF,第二范式（續(xù)）,采用投影分解法將一個1NF的關(guān)系分解為多個2NF的關(guān)系，可以在一定程度上減輕原1

15、NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問題。 將一個1NF關(guān)系分解為多個2NF的關(guān)系，并不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。,6.2.5 第三范式：3NF,例：2NF關(guān)系模式SL(Sno, Sdept, Sloc)中 （Sno， Sdept， Sloc） 2NF 函數(shù)依賴： SnoSdept SdeptSloc SnoSloc Sloc傳遞函數(shù)依賴于Sno，即SL中存在非主屬性對碼的傳遞函數(shù)依賴。,T,3NF,函數(shù)依賴圖：,T,3NF,解決方法 采用投影分解法，把SL分解為兩個關(guān)系模式，以消除傳遞函數(shù)依賴： SD（Sno， Sdept） DL（Sdept， S

16、loc） SD的碼為Sno， DL的碼為Sdept。,3NF,SD的碼為Sno， DL的碼為Sdept。,3NF,3NF的定義 定義6.8 關(guān)系模式R 中若不存在這樣的碼X、屬性組Y及非主屬性Z（Z Y）, 使得XY，Y X，YZ，成立，則稱R 3NF。 例， SL(Sno, Sdept, Sloc) 2NF SL(Sno, Sdept, Sloc) 3NF SD（Sno， Sdept） 3NF DL（Sdept， Sloc） 3NF,3NF,若R3NF，則R的每一個非主屬性既不部分函數(shù)依賴于候選碼也不傳遞函數(shù)依賴于候選碼。 若R中屬性全部為主屬性，則R3NF。 如果R3NF，則R中非主屬性之

17、間無依賴性 (3NF中消除了非關(guān)鍵字屬性間的函數(shù)依賴) 如果R3NF，則R也是2NF。 (如何證明：如果R3NF，則R也是2NF),證明:若 R3NF，則R2NF,反證法： 假設(shè)R3NF，而R2NF,則R中存在非主屬性Z （Z X）,部分函數(shù)依賴于碼X，即： X Z ,因此有屬性組Y （Y X）使得XY，Y X，YZ，成立, 顯然這與R3NF的定義矛盾。假設(shè)不成立。,P,注意:3NF中不存在這樣的碼X、屬性組Y及非主屬性Z（Z Y）, 使得XY，Y X，YZ，成立,6.2.6 BC范式（BCNF）,定義6.9 設(shè)關(guān)系模式R1NF，如果對于R的每個函數(shù)依賴XY，若Y不屬于X，則X必含有候選碼，那

18、么RBCNF。,等價定義：每個非平凡的函數(shù)依賴的左邊必須包含候選碼,若RBCNF，則： 每一個決定屬性集（因素）都包含（候選）碼 R中的所有屬性（主、非主屬性）都完全函數(shù)依賴于碼 若R3NF 則 R不一定BCNF 若RBCNF ，則R3NF（如何證明?）,證明:若 RBCNF，則R3NF,反證法： 假設(shè)RBCNF，而R3NF,則R中存在傳遞函數(shù)依賴，即： X Y (Y X)、YZ（Z Y） 顯然Y不是候選碼（因為Y X） 因此， YZ（Z Y）中左邊不含碼,這與RBCNF矛盾。假設(shè)不成立。,如何區(qū)別BCNF與3NF,3NF是放寬條件的BCNF： BCNF：對于任何非平凡的依賴XY， X必須包含

19、候選碼。 3NF：對于任何非平凡的依賴XY， 或者X包含候選碼， 或者Y是某個候選碼的組成部分。,舉例分析,例1：在關(guān)系模式STJ（S，T，J）中，S表示學(xué)生，T表示教師，J表示課程。 每一教師只教一門課，每門課由若干教師教：TJ 某一學(xué)生選定某門課，就確定了一個固定的教師： (S，J)T 某個學(xué)生選修某個教師的課就確定了所選課的名稱 ： (S，T)J 所以：F=(S，J)T，(S，T)J，TJ,舉例分析（續(xù)）,(S，J)和(S，T)都可以作為候選碼,舉例分析（續(xù)）, 每個FD的左邊或是候選碼，或者 每個FD的右邊是候選碼的組成部分 STJ3NF 但STJBCNF 因為存在: TJ，T是決定屬

20、性集，T不是碼，J屬于候選碼的組成部分。,F=(S，J)T，(S，T)J，TJ,舉例分析（續(xù)）,解決方法：將STJ分解為二個關(guān)系模式： SJ(S，J) BCNF， TJ(T，J) BCNF,BCNF的相關(guān)結(jié)論,如果關(guān)系模式RBCNF，必定有R3NF 如果R3NF，且R只有一個候選碼，則R必屬于BCNF。 任何二元關(guān)系模式的最高范式屬于BCNF 如果R的碼為全碼（all-key）, 則RBCNF 若RBCNF，則在函數(shù)依賴的范疇內(nèi)R已經(jīng)實現(xiàn)了徹底的分離（消除了插、刪、改異常，但尚不能消除冗余）,BCNF的關(guān)系模式所具有的性質(zhì), 所有非主屬性都完全函數(shù)依賴于每個候選碼 所有主屬性都完全函數(shù)依賴于每

21、個不包含它的候選碼 沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性,總結(jié)：怎樣判斷3NF和BCNF？,若R3NF，則R的每一個非主屬性既不部分函數(shù)依賴于候選碼也不傳遞函數(shù)依賴于候選碼。 若R中屬性全部為主屬性，則R3NF。 3NF：對于任何非平凡的依賴XY， 或者X包含候選碼， 或者Y是某個候選碼的組成部分。,RBCNF： 每一個決定屬性集（因素）都包含（候選）碼，即對于任何非平凡的依賴XY， X必須包含候選碼。 R中的所有屬性（主、非主屬性）都完全函數(shù)依賴于碼。 如果R3NF，且R只有一個候選碼，則R必屬于BCNF。 任何二元關(guān)系模式的最高范式屬于BCNF。 如果R的碼為全碼（all-key）

22、, 則RBCNF。 沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性,怎樣判斷3NF和BCNF：,分析下列關(guān)系的范式：,例2:R(Sno,ID,Sdept,Sage),1、碼：Sno或ID 2、非主屬性對碼不部分依賴，也不傳遞依賴 R 3NF 3、在所有的函數(shù)依賴中，左部均含碼 R BCNF,分析下列關(guān)系的范式：,R(Sno,Cno,Pno) 名次(假設(shè)同一同課程無并列名次),1、碼：（Sno,Cno)或(Cno,Pno) 2、在所有的函數(shù)依賴中，左部均含碼 R BCNF,分析下列關(guān)系的范式：,例3:Booking(title，cinema，city) 訂票（電影名，電影院，城市）,小結(jié),cine

23、macity 一個電影院只能建在一個城市中 (title,city) cinema 在同一個城市中預(yù)訂的同一種電影票 不會是兩個不同的電影院的,1、碼： (title,city)或(title, cinema) 2、在所有的函數(shù)依賴中，或左部含碼，或右部是 碼的組成部分 R 3NF， R BCNF,例4: 學(xué)校中某一門課程由多個教師講授，他們使用相同的一套參考書。 關(guān)系模式Teaching(C, T, B) 課程C、教師T 和 參考書B,表6.3,用二維表表示Teaching,多值依賴（續(xù)）,TeachingBCNF: Teach具有唯一候選碼(C，T，B)， 即全碼 Teaching模式中存

24、在的問題 (1)數(shù)據(jù)冗余度大：有多少名任課教師，參考書就要存儲多少次,多值依賴（續(xù)）,(2)插入操作復(fù)雜：當(dāng)某一課程增加一名任課教師時，該課程有多少本參照書，就必須插入多少個元組 例如物理課增加一名教師劉明，需要插入三個元組： （物理，劉明，普通物理學(xué)） （物理，劉明，光學(xué)原理） （物理，劉明，物理習(xí)題集）,多值依賴與第四范式（續(xù)）,(3) 刪除操作復(fù)雜：某一門課要去掉一本參考書，該課程有多少名教師，就必須刪除多少個元組 (4) 修改操作復(fù)雜：某一門課要修改一本參考書，該課程有多少名教師，就必須修改多少個元組 產(chǎn)生原因: 存在多值依賴,一、多值依賴,定義6.9 (p179) 設(shè)R(U)是一個屬

25、性集U上的一個關(guān)系模式， X、 Y和Z是U的子集，并且ZUXY，多值依賴 XY成立當(dāng)且僅當(dāng)對R的任一關(guān)系r，r在（X，Z）上的每個值對應(yīng)一組Y的值，這組值僅僅決定于X值而與Z值無關(guān) 例 Teaching（C, T, B） 對于每一門課程值（C），有一組教師值與之對應(yīng)（T），而不論是什么參考書（B）。所以,C T,多值依賴另一定義（p179),在R（U）的任一關(guān)系r中，如果存在元組t，s 使得tX=sX，那么就必然存在元組 w，v r，（w，v可以與s，t相同），使得wX=vX=tX，而wY=tY，wZ=sZ，vY=sY，vZ=tZ（即交換s，t元組的Y值所得的兩個新元組必在r中），則Y多值依賴

26、于X，記為XY。 這里，X，Y是U的子集，Z=U-X-Y。 t x y1 z2 s x y2 z1 w x y1 z1 v x y2 z2,多值依賴XY的另一定義, t s (r(t)r(s) tX=sX w(r(w) w(X)=t(X) w(Y)=t(Y) w(Z)=s(Z) ),t x y1 z2 s x y2 z1 w x y1 z1 v x y2 z2, t s (r(t)r(s) tX=sX v(r(v) v(X)=s(X) v(Y)=s(Y) v(Z)=t(Z) ),X Y Z,多值依賴直觀的含義:,t,w,s,v,若R中有兩個元組在X屬性上取值相等，則交換這兩個元組在Y屬性上的取

27、值得到的兩個元組也必在R中,R,相等,思考：,課程、教師、時間、教室、學(xué)生、分?jǐn)?shù) R（C，T，H，R，S，G） c1 t1 h1 r2 s1 g1 c1 t1 h2 r3 s1 g1 c1 t1 h3 r2 s1 g1 c1 t1 h1 r2 s2 g2 c1 t1 h2 r3 s2 g2 c1 t1 h3 r2 s2 g2,語義：對于某教師所教的某門課（C，T）可有一組“時間教室”（H，R）與之對應(yīng)，而與“學(xué)生成績”無關(guān),(C,T) (H,R) (C,T) (S,G),多值依賴（續(xù)）,平凡多值依賴和非平凡的多值依賴 若XY，而Z，則稱 XY為平凡的多值依賴 否則稱XY為非平凡的多值依賴,多值

28、依賴的性質(zhì),（1）多值依賴具有對稱性 若XY，則XZ，其中ZUXY 多值依賴的對稱性可以用完全二分圖直觀地表示出來。,多值依賴的對稱性,X Y , X Z,多值依賴的對稱性,課程C 教師T 課程C 參考書B,多值依賴的性質(zhì)（P180）,2）多值依賴具有傳遞性 若XY，YZ， 則XZ -Y 3）函數(shù)依賴是多值依賴的特殊情況: 若XY，則XY。(復(fù)制規(guī)則) 4）若XY，XZ，則XY Z。 5）若XY，XZ，則XYZ。 6）若XY, XZ,則XY-Z, XZ -Y。,多值依賴與函數(shù)依賴的聯(lián)系與區(qū)別,聯(lián)系：函數(shù)依賴是多值依賴的特殊情況 XY：描述的是X與Y之間的一對一的聯(lián)系 XY：描述的是X與Y之間的

29、一對多的聯(lián)系 但是，在XY中，若對于X的每一個值，Y僅有一個值與之對應(yīng)時則XY 變成XY 。 區(qū)別： XY在R上是否成立僅與X、Y有關(guān) XY在R上是否成立不僅與X、Y有關(guān),而且與UXY有關(guān) XY在R上成立，則必有XY(其中Y Y) XY在R上成立，則不一定有XY(其中Y Y ),6.2.8 第四范式（4NF）,定義6.10 關(guān)系模式R1NF，如果對于R的每個非平凡多值依賴XY（Y X），X都含有候選碼，則R4NF。 如果R 4NF， 則R BCNF 不允許有非平凡且非函數(shù)依賴的多值依賴 允許的非平凡多值依賴實際上是函數(shù)依賴,第四范式（續(xù)）,例1： Teach(C,T,B) 4NF 存在非平凡的

30、多值依賴CT，且C不是候選碼 用投影分解法把Teach分解為如下兩個關(guān)系模式： CT(C, T) 4NF CB(C, B) 4NF CT， CB是平凡多值依賴,幾條結(jié)論,當(dāng)R中的依賴只含F(xiàn)D時，4NF就是BCNF 4NF必定為BCNF，反之不然 若一個R的碼為全碼，且無MFD，則R4NF 若R的依賴集中所有的候選關(guān)鍵字都是決定因素，則R4NF。,6.2.9 規(guī)范化小結(jié),關(guān)系數(shù)據(jù)庫的規(guī)范化理論是數(shù)據(jù)庫邏輯設(shè)計的工具。 一個關(guān)系只要其分量都是不可分的數(shù)據(jù)項，它就是規(guī)范化的關(guān)系，但這只是最基本的規(guī)范化。 規(guī)范化程度可以有多個不同的級別,規(guī)范化（續(xù)）,規(guī)范化程度過低的關(guān)系不一定能夠很好地描述現(xiàn)實世界，

31、可能會存在插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問題 一個低一級范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換為若干個高一級范式的關(guān)系模式集合，這種過程就叫關(guān)系模式的規(guī)范化,規(guī)范化（續(xù)）,關(guān)系模式規(guī)范化的基本步驟 1NF 消除非主屬性對碼的部分函數(shù)依賴 消除決定屬性 2NF 集非碼的非平 消除非主屬性對碼的傳遞函數(shù)依賴 凡函數(shù)依賴 3NF 消除主屬性對碼的部分和傳遞函數(shù)依賴 BCNF 消除非平凡且非函數(shù)依賴的多值依賴 4NF,規(guī)范化的基本思想,消除不合適的數(shù)據(jù)依賴 使各關(guān)系模式達(dá)到某種程度的“分離” 采用“一事一地”的模式設(shè)計原則 讓一個關(guān)系描述一個概念、一個實體或者實體間的一種聯(lián)系。若多于一個概念就

32、把它“分離”出去 所謂規(guī)范化實質(zhì)上是概念的單一化,規(guī)范化（續(xù)）,不能說規(guī)范化程度越高的關(guān)系模式就越好 在設(shè)計數(shù)據(jù)庫模式結(jié)構(gòu)時，必須對現(xiàn)實世界的實際情況和用戶應(yīng)用需求作進(jìn)一步分析，確定一個合適的、能夠反映現(xiàn)實世界的模式 上面的規(guī)范化步驟可以在其中任何一步終止,第六章 關(guān)系數(shù)據(jù)理論,6.1 問題的提出 6.2 規(guī)范化 6.3 數(shù)據(jù)依賴的公理系統(tǒng) * 6.4 模式的分解,6.3 數(shù)據(jù)依賴的公理系統(tǒng),邏輯蘊(yùn)含 定義6.11 對于滿足一組函數(shù)依賴 F 的關(guān)系模式R ，其任何一個關(guān)系r，若函數(shù)依賴XY都成立, 則稱F邏輯蘊(yùn)含X Y,Armstrong公理系統(tǒng),一套推理規(guī)則（1974年） 用途 求給定關(guān)系模

33、式的碼 從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴,1. Armstrong公理系統(tǒng),設(shè)有關(guān)系模式R Al.自反律（Reflexivity）： 若Y X U，則X Y為F所蘊(yùn)含。 A2.增廣律（Augmentation）：若XY為F所蘊(yùn)含，且Z U，則XZYZ為F所蘊(yùn)含。 A3.傳遞律（Transitivity）：若XY及YZ為F所蘊(yùn)含，則XZ為F所蘊(yùn)含。 注意：由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴。,定理 6.l Armstrong推理規(guī)則是正確的,（l）自反律:若Y X U，則X Y為F所蘊(yùn)含 證: 設(shè)Y X U 對R 的任一關(guān)系r中的任意兩個元組t，s： 若tX=sX，由于Y X，有ty=s

34、y， 所以XY成立. 自反律得證,定理6.l,(2)增廣律: 若XY為F所蘊(yùn)含，且Z U，則XZYZ 為F所蘊(yùn)含。 證：設(shè)XY為F所蘊(yùn)含，且Z U。 設(shè)R 的任一關(guān)系r中任意的兩個元組t，s； 若tXZ=sXZ，則有tX=sX和tZ=sZ； 由XY，于是有tY=sY，所以tYZ=sYZ，所以XZYZ為F所蘊(yùn)含. 增廣律得證。,定理6.l,(3) 傳遞律：若XY及YZ為F所蘊(yùn)含，則 XZ為 F所蘊(yùn)含。 證：設(shè)XY及YZ為F所蘊(yùn)含。 對R 的任一關(guān)系 r中的任意兩個元組 t，s。 若tX=sX，由于XY，有 tY=sY； 再由YZ，有tZ=sZ，所以XZ為F所蘊(yùn)含. 傳遞律得證。,2. 導(dǎo)出規(guī)則,

35、1.根據(jù)A1，A2，A3這三條推理規(guī)則可以得到下面三條推理規(guī)則： 合并規(guī)則：由XY，XZ，有XYZ。 （A2， A3） 偽傳遞規(guī)則：由XY，WYZ，有XWZ。 （A2， A3） 分解規(guī)則：由XY及 ZY，有XZ。 （A1， A3）,導(dǎo)出規(guī)則,2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理5.1 引理6.l XA1 A2Ak成立的充分必要條件是XAi成立（i=l，2，k）。,3. 函數(shù)依賴閉包F+,定義6.l2 在關(guān)系模式R中為F所邏輯 蘊(yùn)含的函數(shù)依賴的全體叫作 F的閉包，記為F+。,求F的閉包舉例：,設(shè)有F=X Y,Y Z, 求F+ F+= X , Y , Z , XY , XZ , YZ , XYZ

36、, X X, Y Y, Z Z, XY X, XZ X, YZ Y, XYZ X, X Y, Y Z , XY Y, XZ Y, YZ Z, XYZ Y, X Z, Y YZ, XY Z, XZ Z, YZ YZ, XYZ Z, X XY, XY XY, XZ XY, XYZ XY, X XZ, XY YZ, XZ XZ, XYZ YZ X YZ, XY XZ, XZ XY, XYZ XZ, X ZYZ, XY XYZ, XZ XYZ, XYZ XYZ ,共計42個，計算F+是NP完全問題，若有F=XA1A2An, F+2n,函數(shù)依賴的判定-屬性閉包XF+,定義6.13 設(shè)F為屬性集U上的一組

37、函數(shù)依賴，X U， XF+ = A|XA能由F 根據(jù)Armstrong公理導(dǎo)出，XF+稱為屬性集X關(guān)于函數(shù)依賴集F 的閉包,函數(shù)依賴的判定-屬性閉包XF+,引理6.2 設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y U，XY能由F 根據(jù)Armstrong公理導(dǎo)出的充分必要條件是Y XF+ 用途 將判定XY是否能由F根據(jù)Armstrong公理導(dǎo)出的問題， 就轉(zhuǎn)化為求出XF+ ，判定Y是否為XF+的子集的問題,XYY XF+,如何求屬性閉包XF+（P184）,算法6.1 求屬性集X（X U）關(guān)于U上的函數(shù)依 賴集F 的閉包XF+ 輸入：X，F(xiàn) 輸出：XF+ 步驟： （1）令X（0）=X，i=0 （2）求B

38、，這里B = A |( V)( W)(VWF V X（i）A W)； （3）X（i+1）=BX（i）,A來自F中某個依賴的右部成員，而該依賴的左部是當(dāng)前X（i）的子集,算法6.l,（4）判斷X（i+1）= X （i）嗎? （5）若相等或X（i）=U , 則X（i）就是XF+ , 算法終止。 （6）若否，則 i=i+l，返回第（2）步。 對于算法6.l， 令ai =|X（i）|，ai 形成一個步長大 于1的嚴(yán)格遞增的序列，序列的上界是 | U |，因 此該算法最多 |U| - |X| 次循環(huán)就會終止。,U=A, B, C, D; F=A B, BC D; A+ = AB. C+ = C. (AC

39、)+ = ?,Example,A C,B,Example,A C,D,B,U=A, B, C, D; A B, BC D. (AC)+ = ABCD.,求XF+舉例:,例1 已知關(guān)系模式R，其中 U=A，B，C，D，E； F=ABC，BD，CE，ECB，ACB。 求（AB）F+ 。 解 設(shè)X（0）=AB； (1)計算X（1）: 逐一的掃描F集合中各個函數(shù)依賴， 找左部為A，B或AB的函數(shù)依賴。得到兩個： ABC，BD。 于是X（1）=ABCD=ABCD。,求XF+舉例:,(2)因為X（0） X（1） ，所以再找出左部為ABCD子集的那些函數(shù)依賴，又得到ABC，BD， CE，ACB， 于是X（2

40、）=X（1）BCDE=ABCDE。 (3)因為X（2）=U，算法終止 所以（AB）F+ =ABCDE。,輸入:R的U及R上的F 輸出:R的所有候選碼Key (1)將R的所有屬性分為L、R、N、LR四類 并令X代表L、N兩類，Y代表LR類 (2)求X+，若X+=U，則X是惟一Key，轉(zhuǎn)(4) (3)從 Y中取一個屬性A，求(XA)+，若(XA)+=U，則 XA是Key，否則，從 Y中取二個屬性，重復(fù)(3) (4) 停止，輸出所有Key,設(shè)有關(guān)系模式：R 其中U為R的屬性集，即：U=A1，A2 ， An F為R的函數(shù)依賴集。 求候選碼=？,練習(xí),設(shè)有關(guān)系模式R(A,B,C,D),其上的函數(shù)依賴集為

41、：F=A C, CA, B AC, DAC 1、計算(AD)F+ 2、求R的候選碼,4. Armstrong公理系統(tǒng)的有效性與完備性,有效性：由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來的每一個函數(shù)依賴一定在F+中 /* Armstrong正確 完備性：F+中的每一個函數(shù)依賴f，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來 /* Armstrong公理夠用，完全 完備性的逆否命題: 若 f 不能用Armstrong公理推導(dǎo)出來，則 f F+,5. 函數(shù)依賴集等價(p186),定義6.14 如果G+=F+，就說函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價。 討論函數(shù)依賴集

42、等價的意義： 一個大的FD集如何用一個等價的小的FD集代替,函數(shù)依賴集等價的充要條件,引理6.3 F+ = G+ 的充分必要條件是 F G+ ，和G F+ 證: 必要性顯然，只證充分性。 （1）若FG+ ，則XF+ XG+ 。 （2）任取XYF+ 則有 Y XF+ XG+ 。 所以XY (G+）+= G+。即F+ G+。 （3）同理可證G+ F+ ，所以F+ = G+。,6. 最小依賴集,定義6.15 如果函數(shù)依賴集F滿足下列條件，則稱F為一個極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋或正則覆蓋。 (1) F中任一函數(shù)依賴的右部僅含有一個屬性。 (2) F中不存在這樣的函數(shù)依賴XA，使得F與

43、F-XA等價。 (3) F中不存在這樣的函數(shù)依賴XA， X有真 子集Z使得F-XAZA與F等價。,最小依賴集,例2 對于6.l節(jié)中的關(guān)系模式S，其中： U= SNO，SDEPT，MN，CNAME，G ， F= SNOSDEPT，SDEPTMN， （SNO，CNAME）G 設(shè)F=SNOSDEPT，SNOMN， SDEPTMN，(SNO，CNAME)G， (SNO，SDEPT)SDEPT F是最小覆蓋，而F 不是。因為： F -SNOMN與F 等價 F -(SNO，SDEPT)SDEPT也與F 等價 F -(SNO，SDEPT)SDEPTSNOSDEPT也與F 等價,7. 極小化過程,定理6.3

44、每一個函數(shù)依賴集F均等價于一個極小 函數(shù)依賴集Fm。此Fm稱為F的最小依賴集 證:構(gòu)造性證明，依據(jù)定義分三步對F進(jìn)行“極小化處理”，找出F的一個最小依賴集。 (1)逐一檢查F中各函數(shù)依賴FDi：XY， 若Y=A1A2 Ak，k 2， 則用 XAj |j=1，2， k 來取代XY。 引理6.1保證了F變換前后的等價性。,極小化過程,(2)逐一檢查F中各函數(shù)依賴FDi：XA， 令G=F-XA， 若AXG+， 則從F中去掉此函數(shù)依賴。 由于F與G =F-XA等價的充要條件是AXG+ 因此F變換前后是等價的。,極小化過程,(3)逐一取出F中各函數(shù)依賴FDi：XA， 設(shè)X=B1B2Bm， 逐一考查Bi

45、（i=l，2，m）， 若A （X-Bi ）F+ ， 則以X-Bi 取代X。 由于F與F-XAZA等價的充要條件是AZF+ ，其中Z=X-Bi 因此F變換前后是等價的。,極小化過程,由定義，最后剩下的F就一定是極小依賴集。 因為對F的每一次“改造”都保證了改造前后的兩個函數(shù)依賴集等價，因此剩下的F與原來的F等價。 證畢 定理6.3的證明過程 也是求F極小依賴集的過程,極小化步驟(記憶)：,第一步：使每一個FD的右部屬性單一化 (采用分解規(guī)則) 第二步：消除多余FD XA多余？，只看 AXG+ ？ (令G=F-XA) 第三步：消除每一個FD的左部多余屬性 對于B1B2Bm A ， Bi 多余？只看

46、 A (X-Bi )F+ ? (令X=B1B2Bm),極小化過程,例3 F = AB，BA，BC， AC，CA Fm1、Fm2都是F的最小依賴集： Fm1= AB，BC，CA Fm2= AB，BA，AC，CA F的最小依賴集Fm不一定是唯一的它與對各函數(shù)依賴FDi 及XA中X各屬性的處置順序有關(guān),極小化過程,極小化過程( 定理6.3的證明 )也是檢驗F是否為極小依賴集的一個算法 若改造后的F與原來的F相同，說明F本身就是一個最小依賴集,極小化過程,練習(xí) F = AB, AC , BC , AB C 求F的最小依賴集,F = AB, BC,第六章 關(guān)系數(shù)據(jù)理論,6.1 數(shù)據(jù)依賴 6.2 規(guī)范化

47、6.3 數(shù)據(jù)依賴的公理系統(tǒng) 6.4 模式的分解,6.4 模式的分解(選學(xué)內(nèi)容),把低一級的關(guān)系模式分解為若干個高一級的關(guān)系模式的方法并不是唯一的 只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價，分解方法才有意義,關(guān)系模式分解的標(biāo)準(zhǔn),三種模式分解的等價定義 分解具有無損連接性 分解要保持函數(shù)依賴 分解既要保持函數(shù)依賴，又要具有無損連接性,模式的分解（續(xù)）,定義6.16 關(guān)系模式R的一個分解： = R1，R2，Rn U=U1U2Un，且不存在 Ui Uj，F(xiàn)i 為 F在 Ui 上的投影 定義6.17 函數(shù)依賴集合XY | XY F+XY Ui 的一個覆蓋 Fi 叫作 F 在屬性 Ui 上的投影,模式

48、的分解（續(xù)）,例: SL（Sno， Sdept， Sloc） F= SnoSdept,SdeptSloc,SnoSloc SL2NF 存在插入異常、刪除異常、冗余度大和修改復(fù)雜等問題 分解方法可以有多種,模式的分解（續(xù)）,SL SnoSdeptSloc 95001 CS A 95002 IS B 95003 MA C 95004 IS B 95005 PH B ,模式的分解（續(xù)）,1. SL分解為下面三個關(guān)系模式： SN(Sno) SD(Sdept) SO(Sloc),分解后的關(guān)系為：,SN SD SO Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 PH 95005 ,模式的分解（續(xù)）,分解后的數(shù)據(jù)庫丟失了許多信息 例如無法查詢95001學(xué)生所在系或所在宿舍。 如果分解后的關(guān)系可以通過自然連接恢復(fù)為原來的關(guān)系，那么這種分解就沒有丟失信息,模式的分解（續(xù)）,2. SL分解為下面二個關(guān)系模式： NL(Sno, Sloc) DL(Sdept, Sloc) 分解后的關(guān)系為： NL DL Sno Sloc Sdept Sloc 95001 A CS A 95002 B IS B 95003 C MA C 95004 B PH B 9