廈門大學計算機科學系

1、,廈門大學計算機科學系 2017版,林子雨廈門大學計算機科學系E-mail: ziyulin@xmu.edu.cn主頁：http://www.cs.xmu.edu.cn/linziyu,第6章 關(guān)系數(shù)據(jù)理論（2017版）,,,,廈門大學計算機科學系本科生課程《數(shù)據(jù)庫系統(tǒng)原理》,6.

2、1 問題的提出6.2 規(guī)范化6.3 數(shù)據(jù)依賴的公理系統(tǒng)6.4 模式的分解,第6章 關(guān)系數(shù)據(jù)理論,關(guān)系數(shù)據(jù)庫邏輯設(shè)計針對具體問題，如何構(gòu)造一個適合于它的數(shù)據(jù)模式數(shù)據(jù)庫邏輯設(shè)計的工具──關(guān)系數(shù)據(jù)庫的規(guī)范化理論,6.1 問題的提出,一、概念回顧二、關(guān)系模式的形式化定義三、什么是數(shù)據(jù)依賴四、關(guān)系模式的簡化定義五、數(shù)據(jù)依賴對關(guān)系模式影響,6.1 問題的提出,關(guān)系：描述實體、屬性、實體間的聯(lián)系。從形式上看，它是一張二維表，是所

3、涉及屬性的笛卡爾積的一個子集。關(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)系模式的全體。,6.1 問題的提出,概念回顧,關(guān)系模式由五部分組成，即它是一個五元組： R(U, D, DOM, F)R： 關(guān)系名U： 組成該關(guān)系的屬性名集合D： 屬性組

4、U中屬性所來自的域DOM：屬性向域的映象集合F： 屬性間數(shù)據(jù)的依賴關(guān)系集合,6.1 問題的提出,關(guān)系模式的形式化定義,1. 完整性約束的表現(xiàn)形式限定屬性取值范圍：例如學生成績必須在0-100之間定義屬性值間的相互關(guān)連（主要體現(xiàn)于值的相等與否） 這就是數(shù)據(jù)依賴，它是數(shù)據(jù)庫模式設(shè)計的關(guān)鍵2. 數(shù)據(jù)依賴是通過一個關(guān)系中屬性間值的相等與否體現(xiàn)出來的數(shù)據(jù)間的相互關(guān)系是現(xiàn)實世界屬性間相互聯(lián)系的抽象是數(shù)據(jù)內(nèi)在的性質(zhì)是語

5、義的體現(xiàn)3. 數(shù)據(jù)依賴的類型函數(shù)依賴（Functional Dependency，簡記為FD）多值依賴（Multivalued Dependency，簡記為MVD）其他,6.1 問題的提出,什么是數(shù)據(jù)依賴,關(guān)系模式R（U, D, DOM, F） 簡化為一個三元組： R（U, F）當且僅當U上的一個關(guān)系r 滿足F時，r稱為關(guān)系模式 R（U, F）的一個關(guān)系,6.1 問題的提出,關(guān)系

6、模式的簡化表示,例：描述學校的數(shù)據(jù)庫：學生的學號（Sno）、所在系（Sdept）系主任姓名（Mname）、課程名（Cname）成績（Grade）,6.1 問題的提出,數(shù)據(jù)依賴對關(guān)系模式的影響,｛ Sno, Sdept, Mname, Cname, Grade ｝,單一的關(guān)系模式 ： Student U ＝,學校數(shù)據(jù)庫的語義： ⒈ 一個系有若干學生， 一個學生只屬于一個系； ⒉ 一個系只有一名主任

7、； ⒊ 一個學生可以選修多門課程， 每門課程有若干學生選修； ⒋ 每個學生所學的每門課程都有一個成績。,6.1 問題的提出,數(shù)據(jù)依賴對關(guān)系模式的影響,U ＝ ｛ Sno, Sdept, Mname, Cname, Grade ｝屬性組U上的一組函數(shù)依賴F： F ＝ ｛ Sno → Sdept, Sdept → Mname, (Sno, Cname) → Grade ｝,6

8、.1 問題的提出,數(shù)據(jù)依賴對關(guān)系模式的影響,6.1 問題的提出,關(guān)系模式Student中存在的問題,,6.1 問題的提出,關(guān)系模式Student中存在的問題,⒈ 數(shù)據(jù)冗余太大浪費大量的存儲空間 例：每一個系主任的姓名重復出現(xiàn)⒉ 更新異常（Update Anomalies）數(shù)據(jù)冗余 ，更新數(shù)據(jù)時，維護數(shù)據(jù)完整性代價大。例：某系更換系主任后，系統(tǒng)必須修改與該系學生有關(guān)的每一個元組⒊ 插入異常（Insertion Anom

9、alies）該插的數(shù)據(jù)插不進去 例，如果一個系剛成立，尚無學生，我們就無法把這個系及其系主任的信息存入數(shù)據(jù)庫。⒋ 刪除異常（Deletion Anomalies）不該刪除的數(shù)據(jù)不得不刪例，如果某個系的學生全部畢業(yè)了， 我們在刪除該系學生信息的同時，把這個系及其系主任的信息也丟掉了。,6.1 問題的提出,結(jié)論：Student關(guān)系模式不是一個好的模式?！昂谩钡哪Ｊ剑翰粫l(fā)生插入異常、刪除異常、更新異常，數(shù)據(jù)冗余應盡

10、可能少。原因：由存在于模式中的某些數(shù)據(jù)依賴引起的解決方法：通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴。,數(shù)據(jù)依賴對關(guān)系模式的影響,6.1 問題的提出6.2 規(guī)范化6.3 數(shù)據(jù)依賴的公理系統(tǒng)6.4 模式的分解,第6章 關(guān)系數(shù)據(jù)理論,6.2 規(guī)范化,規(guī)范化理論正是用來改造關(guān)系模式，通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問題。,6.2.1 函數(shù)依賴,一、函數(shù)依賴二、平凡函數(shù)

11、依賴與非平凡函數(shù)依賴三、完全函數(shù)依賴與部分函數(shù)依賴四、傳遞函數(shù)依賴,6.2.1 函數(shù)依賴,定義6.1 設(shè)R(U)是一個屬性集U上的關(guān)系模式，X和Y是U的子集。 若對于R(U)的任意一個可能的關(guān)系r，r中不可能存在兩個元組在X上的屬性值相等， 而在Y上的屬性值不等， 則稱 “X函數(shù)確定Y” 或 “Y函數(shù)依賴于X”，記作X→Y。 X稱為這個函數(shù)依賴的決定屬性集(Determinant)。 Y=f(x),

12、一、函數(shù)依賴,6.2.1 函數(shù)依賴,1. 函數(shù)依賴不是指關(guān)系模式R的某個或某些關(guān)系實例滿足的約束條件，而是指R的所有關(guān)系實例均要滿足的約束條件。2. 函數(shù)依賴是語義范疇的概念。只能根據(jù)數(shù)據(jù)的語義來確定函數(shù)依賴。 例如“姓名→年齡”這個函數(shù)依賴只有在不允許有同名人的條件下成立3. 數(shù)據(jù)庫設(shè)計者可以對現(xiàn)實世界作強制的規(guī)定。例如規(guī)定不允許同名人出現(xiàn)，函數(shù)依賴“姓名→年齡”成立。所插入的元組必須滿足規(guī)定的函數(shù)依賴，若發(fā)現(xiàn)有同名人存在

13、， 則拒絕裝入該元組。,說明：,例: Student(Sno, Sname, Ssex, Sage, Sdept) 假設(shè)不允許重名，則有:Sno → Ssex， Sno → Sage , Sno → Sdept， Sno ←→ Sname, Sname → Ssex， Sname → SageSname → Sdept但Ssex →Sage若X→Y，并且Y→X, 則記為X←→Y。 若Y不函數(shù)依賴于X,

14、 則記為X→Y。,6.2.1 函數(shù)依賴,,,6.2.1 函數(shù)依賴,在關(guān)系模式R(U)中，對于U的子集X和Y，如果X→Y，但Y ? X，則稱X→Y是非平凡的函數(shù)依賴若X→Y，但Y ? X, 則稱X→Y是平凡的函數(shù)依賴例：在關(guān)系SC(Sno, Cno, Grade)中， 非平凡函數(shù)依賴： (Sno, Cno) → Grade 平凡函數(shù)依賴： (Sno, Cno) → Sno

15、 (Sno, Cno) → Cno于任一關(guān)系模式，平凡函數(shù)依賴都是必然成立的，它不反映新的語義，因此若不特別聲明， 我們總是討論非平凡函數(shù)依賴。,,二、平凡函數(shù)依賴與非平凡函數(shù)依賴,6.2.1 函數(shù)依賴,定義6.2 在關(guān)系模式R(U)中，如果X→Y，并且對于X的任何一個真子集X'，都有 X ' Y, 則稱Y完全函數(shù)依賴于X，記作X ｆ Y。 若X→Y

16、，但Y不完全函數(shù)依賴于X，則稱Y部分函數(shù)依賴于X，記作X P Y。,,,,三、完全函數(shù)依賴與部分函數(shù)依賴,,例: 在關(guān)系SC(Sno, Cno, Grade)中， 由于：Sno →Grade，Cno → Grade， 因此：(Sno, Cno) ｆ Grade,,,,6.2.2 碼,定義6.4 設(shè)K為關(guān)系模式R中的屬性或?qū)傩越M合。若K ｆ U，則K稱為R的一個侯選碼（Candidate Key）。若關(guān)系模式R有多個候

17、選碼，則選定其中的一個做為主碼（Primary key）。主屬性與非主屬性ALL KEY,,6.2.2 碼,外部碼定義6.5 關(guān)系模式 R 中屬性或?qū)傩越MX 并非 R的碼，但 X 是另一個關(guān)系模式的碼，則稱 X 是R 的外部碼（Foreign key）也稱外碼。主碼又和外部碼一起提供了表示關(guān)系間聯(lián)系的手段。,6.2.3 范式,范式是符合某一種級別的關(guān)系模式的集合。關(guān)系數(shù)據(jù)庫中的關(guān)系必須滿足一定的要求。滿足不同程度要求的為不同范

18、式。范式的種類：第一范式(1NF)第二范式(2NF)第三范式(3NF)BC范式(BCNF)第四范式(4NF)第五范式(5NF),,6.2.3 范式,各種范式之間存在聯(lián)系：某一關(guān)系模式R為第n范式，可簡記為R∈nNF。,6.2.4 2NF,1NF的定義如果一個關(guān)系模式R的所有屬性都是不可分的基本數(shù)據(jù)項，則R∈1NF。第一范式是對關(guān)系模式的最起碼的要求。不滿足第一范式的數(shù)據(jù)

19、庫模式不能稱為關(guān)系數(shù)據(jù)庫。但是滿足第一范式的關(guān)系模式并不一定是一個好的關(guān)系模式。,6.2.4 2NF,例: 關(guān)系模式 SLC(Sno, Sdept, Sloc, Cno, Grade) Sloc為學生住處，假設(shè)每個系的學生住在同一個地方。函數(shù)依賴包括： (Sno, Cno) Grade Sno Sdept (Sno, Cno

20、) Sdept (?) Sno Sloc (Sno, Cno) Sloc Sdept Sloc,→,→,→,6.2.4 2NF,例: 關(guān)系模式 SLC(Sno, Sdept, Sloc, Cno, Grade) Sloc為學生住處，假設(shè)每個系的學生住在同一個地方。函數(shù)依賴包括： (Sn

21、o, Cno) Grade Sno Sdept (Sno, Cno) Sdept Sno Sloc (Sno, Cno) Sloc Sdept Sloc,→,→,→,6.2.4 2NF,SLC的碼為(Sno, Cno)SLC滿足第一范式 非主屬性S

22、dept和Sloc部分函數(shù)依賴于碼(Sno, Cno),課堂練習,已知學生關(guān)系模式S(Sno,Sname,SD,Sdname,Course,Grade)其中，Sno是學號，Sname是姓名，SD是系名，Sdname是系主任名，Course是課程，Grade是成績（1）寫出關(guān)系模式S的基本函數(shù)依賴和主碼； （做本題）（2）原關(guān)系模式是第幾范式？如何分解成高一級范式？（3）將關(guān)系模式分解成3NF，并說明為什么？,6.2.4 2N

23、F,SLC不是一個好的關(guān)系模式(1) 插入異常假設(shè)Sno＝95102，Sdept＝IS，Sloc＝N的學生還未選課，因課程號是主屬性，因此該學生的信息無法插入SLC。(2) 刪除異常 假定某個學生本來只選修了3號課程這一門課?，F(xiàn)在因身體不適，他連3號課程也不選修了。因課程號是主屬性，此操作將導致該學生信息的整個元組都要刪除。,SLC(Sno, Sdept, Sloc, Cno, Grade),6.2.4 2NF,(3)

24、數(shù)據(jù)冗余度大 如果一個學生選修了10門課程，那么他的Sdept和Sloc值就要重復存儲了10次。(4) 修改復雜 例如學生轉(zhuǎn)系，在修改此學生元組的Sdept值的同時，還可能需要修改住處（Sloc）。如果這個學生選修了K門課，則必須無遺漏地修改K個元組中全部Sdept、Sloc信息。,SLC(Sno, Sdept, Sloc, Cno, Grade),6.2.4 2NF,原因 Sdept、 Sloc部分函數(shù)依賴

25、于碼。解決方法 SLC分解為兩個關(guān)系模式，以消除這些部分函數(shù)依賴 SC（Sno， Cno， Grade） SL（Sno， Sdept， Sloc）,6.2.4 2NF,函數(shù)依賴圖：,,,1NF,2NF,6.2.4 2NF,采用投影分解法將一個1NF的關(guān)系分解為多個2NF的關(guān)系，可以在一定程度上減輕原1NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗

26、余度大、修改復雜等問題。將一個1NF關(guān)系分解為多個2NF的關(guān)系，并不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。,6.2.4 2NF,2NF的定義定義6.6 若關(guān)系模式R∈1NF，并且每一個非主屬性都完全函數(shù)依賴于R的碼，則R∈2NF。例：SLC(Sno, Sdept, Sloc, Cno, Grade) ∈1NF SLC(Sno, Sdept, Sloc, Cno, Grade) ∈2NF

27、 SC（Sno， Cno， Grade） ∈ 2NF SL（Sno， Sdept， Sloc） ∈ 2NF,,課堂練習,已知學生關(guān)系模式S(Sno,Sname,SD,Sdname,Course,Grade)其中，Sno是學號，Sname是姓名，SD是系名，Sdname是系主任名，Course是課程，Grade是成績（1）寫出關(guān)系模式S的基本函數(shù)依賴和主碼；（2）原關(guān)系模式是第幾范式？如何分解成高一級

28、范式？（做本題）（3）將關(guān)系模式分解成3NF，并說明為什么？,6.2.4 2NF,定義6.3 在關(guān)系模式R(U)中，如果X→Y，Y→Z，且Y ?X，Y→X，則稱Z傳遞函數(shù)依賴于X。注: 如果Y→X， 即X←→Y，則Z直接依賴于X。例: 在關(guān)系Std(Sno, Sdept, Mname)中，有：Sno → Sdept，Sdept → Mname Mname傳遞函數(shù)依賴于Sno,四、傳遞函數(shù)依賴,6.2.5 3N

29、F,例：2NF關(guān)系模式SL(Sno, Sdept, Sloc)中函數(shù)依賴： Sno→Sdept Sdept→Sloc Sno→SlocSloc傳遞函數(shù)依賴于Sno，即SL中存在非主屬性對碼的傳遞函數(shù)依賴。,6.2.5 3NF,解決方法 采用投影分解法，把SL分解為兩個關(guān)系模式，以消除傳遞函數(shù)依賴： SD（Sno， Sdep

30、t） DL（Sdept， Sloc）SD的碼為Sno， DL的碼為Sdept。,6.2.5 3NF,SD的碼為Sno， DL的碼為Sdept。,2NF,3NF,6.2.5 3NF,3NF的定義定義6.8 關(guān)系模式R 中若不存在這樣的碼X、屬性組Y及非主屬性Z（Z ? Y）, 使得X→Y，Y → X，Y→Z，成立，則稱R ∈ 3NF。例， SL(Sno, Sdept, Sloc) ∈

31、2NF SL(Sno, Sdept, Sloc) ∈ 3NF SD（Sno， Sdept） ∈ 3NF DL（Sdept， Sloc）∈ 3NF,,,,6.2.5 3NF,若R∈3NF，則R的每一個非主屬性既不部分函數(shù)依賴于候選碼也不傳遞函數(shù)依賴于候選碼。如果R∈3NF，則R也是2NF。采用投影分解法將一個2NF的關(guān)系分解為多個3NF的關(guān)系，可以在一定程度上解決原2NF關(guān)系中存在的

32、插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復雜等問題。 將一個2NF關(guān)系分解為多個3NF的關(guān)系后，并不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。,課堂練習,已知學生關(guān)系模式S(Sno,Sname,SD,Sdname,Course,Grade)其中，Sno是學號，Sname是姓名，SD是系名，Sdname是系主任名，Course是課程，Grade是成績（1）寫出關(guān)系模式S的基本函數(shù)依賴和主碼；（2）原關(guān)系模式是第幾范式？如何分解

33、成高一級范式？（3）將關(guān)系模式分解成3NF，并說明為什么？（做本題）,6.2.6 BCNF,定義6.9 設(shè)關(guān)系模式R∈1NF，如果對于R的每個函數(shù)依賴X→Y，若Y不屬于X，則X必含有碼，那么R∈BCNF。若R∈BCNF 每一個決定屬性集（因素）都包含（候選）碼R中的所有屬性（主，非 主屬性）都完全函數(shù)依賴于碼沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性R∈3NF(?) 若R∈3NF 則 R不一定∈BCNF即在

34、第三范式的基礎(chǔ)上，數(shù)據(jù)庫表中不存在任何屬性對任一候選碼的傳遞函數(shù)依賴和部分函數(shù)依賴,6.2.6 BCNF,證明題：若關(guān)系模式R∈BCNF，則R∈2NF。,6.2.6 BCNF,例子：關(guān)系模式C(Cno,Cname,Pcno)，它只有一個碼Cno，這里沒有任何屬性對Cno部分依賴或傳遞依賴，所以，C ∈ 3NF同時，C中Cno是唯一的決定因素，C同時又是碼，根據(jù)定義，C ∈ BCNF,6.2.6 BCNF,例子：關(guān)系模式SJP（S

35、,J,P）中，S是學生，J表示課程，P表示名次，每一個學生選修每門課程的成績有一定的名次，每門課程中每一名次只有一個學生（即沒有并列名次），可以得到以下依賴：（S，J）→ P; (J, P) → S所以(S,J)和(J,P)都可以作為候選碼，這個關(guān)系模式中沒有屬性對碼傳遞依賴或部分依賴，所以，SJP ∈ 3NF，而且除(S,J)和(J,P)以外沒有其他決定因素，所以SJP ∈ BCNF,6.2.6 BCNF,例：在關(guān)系模式STJ

36、（S，T，J）中，S表示學生，T表示教師，J表示課程。每一教師只教一門課。每門課由若干教師教，某一學生選定某門課，就確定了一個固定的教師。某個學生選修某個教師的課就確定了所選課的名稱 ： T→J， (S，J)→T，(S，T)→J,6.2.6 BCNF,,6.2.6 BCNF,STJ∈3NF (S，J)和(S，T)都可以作為候選碼 S、T、J都是主屬性STJ∈BCNF,,T→J，T是決定屬性集，T不是候選

37、碼,6.2.6 BCNF,解決方法：將STJ分解為二個關(guān)系模式： SJ(S，J) ∈ BCNF， TJ(T，J)∈ BCNF 沒有任何屬性對碼的部分函數(shù)依賴和傳遞函數(shù)依賴,課堂作業(yè),有一個配件管理表WPE(WNO,PNO,ENO,QNT)，其中，WNO表示倉庫號，PNO表示配件號，ENO表示職工號，QNT表示數(shù)量。有以下約束要求：（1）一個倉庫有多名職工（2）一個職工僅在一個倉庫工作（3）每個倉庫里一種

38、型號的配件由一個職工負責，但一個人可以管理幾種配件；（4）同一個型號的配件可以分別放在幾個倉庫中（5）一個倉庫存儲某種配件的數(shù)量是一定的（6）一個職工管理某種配件的數(shù)量是一定的問題：（1）請寫出表中的函數(shù)依賴關(guān)系（2）判斷該表是否是3NF？（3）判斷該表是否是BCNF？,課堂作業(yè)答案,函數(shù)依賴關(guān)系：ENO →WNO(WNO,PNO) →QNT(WNO,PNO) →ENO(ENO,PNO) →QNT,課堂作業(yè)答案,候

39、選碼包括： (WNO,PNO)和(ENO,PNO)ENO,PNO,WNO都是主屬性，QNT是非主屬性所有非主屬性都是直接依賴于候選碼，因此是3NF關(guān)于主屬性：(WNO,PNO) →ENO；ENO →WNO，得到傳遞依賴(WNO,PNO) →WNO，所以不是BCNF,課堂作業(yè)答案,可以繼續(xù)分拆成兩個表管理表EP（ENO,PNO,QNT）工作表EW（ENO,WNO）兩個表屬于BCNF,多值依賴與第四范式（4NF）,例: 學校

40、中某一門課程由多個教師講授，他們使用相同的一套參考書。每個教師可以講多門課程，每種參考書可供多門課使用。關(guān)系模式Teaching(C, T, B) 課程C、教師T 和 參考書B,表6.1,用二維表表示Teaching,多值依賴與第四范式（續(xù)）,Teaching∈BCNF:Teach具有唯一候選碼(C，T，B)， 即全碼Teaching模式中存在的問題 (1)數(shù)據(jù)冗余度大：有多少名任課教師，參考書就要存儲多少次 (2)插入

41、操作復雜：當某一課程增加一名任課教師時，該課程有多少本參照書，就必須插入多少個元組例如物理課增加一名教師劉關(guān)，需要插入兩個元組： （物理，劉關(guān)，普通物理學） （物理，劉關(guān)，光學原理）,多值依賴與第四范式（續(xù)）,(3) 刪除操作復雜：某一門課要去掉一本參考書，該課程有多少名教師，就必須刪除多少個元組(4) 修改操作復雜：某一門課要修改一本參考書，該課程有多少名教師，就必須修改多少個元組

42、產(chǎn)生原因存在多值依賴,6.2.7 多值依賴,定義6.10 設(shè)R(U)是一個屬性集U上的一個關(guān)系模式， X、 Y和Z是U的子集，并且Z＝U－X－Y，多值依賴 X→→Y成立當且僅當對R的任一關(guān)系r，r在（X，Z）上的每個值對應一組Y的值，這組值僅僅決定于X值而與Z值無關(guān) 例 Teaching（C, T, B） 對于C的每一個值，B有一組值與之對應，而不論T取何值,6.2.7 多值依賴,在R（U）的任一關(guān)

43、系r中，如果存在元組t，s 使得t[X]=s[X]，那么就必然存在元組 w，v? r，（w，v可以與s，t相同），使得w[X]=v[X]=t[X]，而w[Y]=t[Y]，w[Z]=s[Z]，v[Y]=s[Y]，v[Z]=t[Z]（即交換s，t元組的Y值所得的兩個新元組必在r中），則Y多值依賴于X，記為X→→Y。 這里，X，Y是U的子集，Z=U-X-Y。,6.2.7 多值依賴,t x y1 z2

44、 s x y2 z1 w x y1 z1 v x y2 z2,X,Y,Z,6.2.7 多值依賴,平凡多值依賴和非平凡的多值依賴若X→→Y，而Z＝φ，則稱 X→→Y為平凡的多值依賴否則稱X→→Y為非平凡的多值依賴,6.2.8 4NF,定義6.10

45、 關(guān)系模式R∈1NF，如果對于R的每個非平凡多值依賴X→→Y（Y ? X），X都含有候選碼，則R∈4NF。 如果R ∈ 4NF， 則R ∈ BCNF 不允許有非平凡且非函數(shù)依賴的多值依賴 允許的是函數(shù)依賴（是非平凡多值依賴）,,6.2.8 4NF,例： Teach(C,T,B) ∈ 4NF,,存在非平凡的多值依賴C→→T，且C不是候選碼用投影分解法把Teach分解為如下兩個關(guān)系模式：

46、 CT(C, T) ∈ 4NF CB(C, B) ∈ 4NF C→→T， C→→B是平凡多值依賴,6.2.9 規(guī)范化,關(guān)系數(shù)據(jù)庫的規(guī)范化理論是數(shù)據(jù)庫邏輯設(shè)計的工具。一個關(guān)系只要其分量都是不可分的數(shù)據(jù)項，它就是規(guī)范化的關(guān)系，但這只是最基本的規(guī)范化。規(guī)范化程度可以有多個不同的級別,6.2.9 規(guī)范化,規(guī)范化程度過低的關(guān)系不一定能夠很好地描述現(xiàn)實世界，可能會存在插入異常、刪除異常、修改復雜、數(shù)

47、據(jù)冗余等問題一個低一級范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換為若干個高一級范式的關(guān)系模式集合，這種過程就叫關(guān)系模式的規(guī)范化,,6.2.9 規(guī)范化,關(guān)系模式規(guī)范化的基本步驟 1NF ↓ 消除非主屬性對碼的部分函數(shù)依賴消除決定屬性 2NF集非碼的非平 ↓ 消除非主屬性對碼的傳遞函數(shù)依賴凡函數(shù)依賴 3NF

48、 ↓ 消除主屬性對碼的部分和傳遞函數(shù)依賴 BCNF ↓ 消除非平凡且非函數(shù)依賴的多值依賴 4NF,,6.2.9 規(guī)范化,消除不合適的數(shù)據(jù)依賴將各關(guān)系模式達到某種程度的“分離”采用“一事一地”的模式設(shè)計原則 讓一個關(guān)系描述一個概念、一個實體或者實體間的一種聯(lián)系。若多于一個概念就把它“分離”出去

49、所謂規(guī)范化實質(zhì)上是概念的單一化不能一味追求規(guī)范化程度高,規(guī)范化的基本思想,6.2.9 規(guī)范化,在設(shè)計數(shù)據(jù)庫模式結(jié)構(gòu)時，必須對現(xiàn)實世界的實際情況和用戶應用需求作進一步分析，確定一個合適的、能夠反映現(xiàn)實世界的模式上面的規(guī)范化步驟可以在其中任何一步終止,第六章 關(guān)系數(shù)據(jù)理論,6.1 數(shù)據(jù)依賴6.2 規(guī)范化6.3 數(shù)據(jù)依賴的公理系統(tǒng)6.4 模式的分解,6.3 數(shù)據(jù)依賴的公理系統(tǒng),邏輯蘊含定義6.11 對于滿足一組函數(shù)依賴 F

50、 的關(guān)系模式R ，函數(shù)依賴X→Y都成立,即r中任意兩元組t,s，若t[X]=s[X]，則t[Y]=s[Y]，則稱 F邏輯蘊含X →Y,Armstrong公理系統(tǒng),一套推理規(guī)則，是模式分解算法的理論基礎(chǔ)用途求給定關(guān)系模式的碼從一組函數(shù)依賴求得蘊含的函數(shù)依賴,1. Armstrong公理系統(tǒng),關(guān)系模式R 來說有以下的推理規(guī)則： A1.自反律（Reflexivity）： 若Y ? X ? U，則X →Y為F所蘊含。A2.增廣律（A

51、ugmentation）：若X→Y為F所蘊含，且Z ? U，則XZ→YZ為F所蘊含。A3.傳遞律（Transitivity）：若X→Y及Y→Z為F所蘊含，則X→Z為F所蘊含。,定理 6.l Armstrong推理規(guī)則是正確的,（1）自反律:若Y ? X ? U，則X →Y為F所蘊含證: 設(shè)Y ? X ? U 對R 的任一關(guān)系r中的任意兩個元組t，s： 若t[X]=s[X]，由于Y ? X，有t[Y]=s[Y]，

52、 所以X→Y成立. 自反律得證,定理 6.l Armstrong推理規(guī)則是正確的,定理6.l,(2)增廣律: 若X→Y為F所蘊含，且Z ? U，則XZ→YZ 為F所蘊含。 證：設(shè)X→Y為F所蘊含，且Z ? U。 設(shè)R 的任一關(guān)系r中任意的兩個元組t，s；若t[XZ]=s[XZ]，則有t[X]=s[X]和t[Z]=s[Z]；由X→Y，于是有t[Y]=s[Y]，所以t[YZ]=s[YZ]，所以XZ→YZ為F所蘊含.

53、增廣律得證。,定理6.l,(3) 傳遞律：若X→Y及Y→Z為F所蘊含，則X→Z為 F所蘊含。證：設(shè)X→Y及Y→Z為F所蘊含。對R 的任一關(guān)系 r中的任意兩個元組 t，s。若t[X]=s[X]，由于X→Y，有 t[Y]=s[Y]；再由Y→Z，當t[Y]=s[Y]時，一定有t[Z]=s[Z]所以X→Z為F所蘊含.傳遞律得證。,2. 導出規(guī)則,1.根據(jù)A1，A2，A3這三條推理規(guī)則可以得到下面三條推理規(guī)則： 合并規(guī)則：由X→Y

54、，X→Z，有X→YZ。 （A2， A3） 偽傳遞規(guī)則：由X→Y，WY→Z，有XW→Z。 （A2， A3） 分解規(guī)則：由X→Y及 Z?Y，有X→Z。 （A1， A3）,導出規(guī)則,2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理6.1 引理6.l X→A1 A2…Ak成立的充分必要條件是X→Ai成立（i=l，2，…，k）。,3. 函數(shù)依賴閉包,定義6.12 在關(guān)系模式R中為F所邏輯蘊含的函數(shù)依

55、賴的全體叫作 F的閉包，記為F+。,3. 函數(shù)依賴閉包,人們把自反律、傳遞律和增廣律稱為Armstrong公理系統(tǒng),Armstrong公理系統(tǒng),有效性：由F出發(fā)根據(jù)Armstrong公理推導出來的每一個函數(shù)依賴一定在F+中 /* Armstrong正確完備性：F+中的每一個函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導出來 /* Armstrong公理夠用，完全,Armstrong公理系統(tǒng),要證

56、明完備性，就首先要解決如何判定一個函數(shù)依賴是否屬于由F根據(jù)Armstrong公理系統(tǒng)推導出來的函數(shù)依賴的集合如果能夠求出這個集合，問題就解決了但是，這個是一個NP完全問題,F的閉包,, F+計算是NP完全問題，X A1A2...An F+={X φ, Y φ, Z φ, XY φ, XZ φ, YZ φ, XYZ φ, X X, Y Y, Z Z, XY X, XZ

57、 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,

58、 XY YZ, XZ XZ, XYZ YZX YZ, XY XZ, XZ XY, XYZ XZ,X ZYZ, XY XYZ, XZ XYZ, XYZ XYZ },F={X Y,Y Z},,,3. 函數(shù)依賴閉包,定義6.1

59、3 設(shè)F為屬性集U上的一組函數(shù)依賴，X ?U， XF+ ={ A\X→A能由F 根據(jù)Armstrong公理導出}，XF+稱為屬性集X關(guān)于函數(shù)依賴集F 的閉包,為了證明Armstrong公理系統(tǒng)完備性，需要引入以下概念：,關(guān)于閉包的引理,引理6.2 設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y ? U，X→Y能由F 根據(jù)Armstrong公理導出的充分必要條件是Y ?XF+用途將判定X→Y是否能由F根據(jù)Armstrong公理導出的問

60、題，就轉(zhuǎn)化為求出XF+ ，判定Y是否為XF+的子集的問題（不再是NP完全問題）,根據(jù)引理6.1可以進一步得到：,U={A, B, C, D}; F={A B, BC D};A+ =C+ =(AC)+ =,實例,,,AB.C. ABCD,求閉包的算法,算法6.l 求屬性集X（X ? U）關(guān)于U上的函數(shù)依賴集F 的閉包XF+ 輸入：X，F(xiàn)輸出：XF+步驟：,算法6.l,（1）令X（0）=X，i

61、=0（2）求B，這里B = { A |(? V)( ? W)(V→W?F ∧V ? X（i）∧A? W)}；（3）X（i+1）=B∪X（i）（4）判斷X（i+1）= X （i）嗎?（5）若相等或X（i）=U , 則X（i）就是XF+ , 算法終止。（6）若否，則 i=i+l，返回第（2）步。,算法6.l,對于算法6.l， 令ai =|X（i）

62、|，{ai }形成一個步長大于1的嚴格遞增的序列，序列的上界是 | U |，因此該算法最多 |U| - |X| 次循環(huán)就會終止。,函數(shù)依賴閉包,[例1] 已知關(guān)系模式R，其中U={A，B，C，D，E}；F={AB→C，B→D，C→E，EC→B，AC→B}。求（AB）F+ 。解 設(shè)X（0）=AB； (1)計算X（1）: 逐一的掃描F集合中各個函數(shù)依賴， 找左部為A，B或AB的函數(shù)依賴。得到兩個：AB→C，B→D。

63、于是X（1）=AB∪CD=ABCD。,函數(shù)依賴閉包,(2)因為X（0）≠ X（1） ，所以再找出左部為ABCD子集的那些函數(shù)依賴，又得到AB→C，B→D， C→E，AC→B， 于是X（2）=X（1）∪BCDE=ABCDE。(3)因為X（2）=U，算法終止所以（AB）F+ =ABCDE。,課堂練習,例：設(shè)有關(guān)系模式R(U,F)，其中U={A,B,C,D,E,I}F={A → D,AB → E,BI → E,CD → I,E

64、 → C}請計算（AE）F+,4. Armstrong公理系統(tǒng)的有效性與完備性,建立公理系統(tǒng)體系目的：從已知的 f 推導出未知的f明確：1.公理系統(tǒng)推導出來的 f 正確？ 2. F+中的每一個 f 都能推導出來？,4. Armstrong公理系統(tǒng)的有效性與完備性,有效性：由F出發(fā)根據(jù)Armstrong公理推導出來的每一個函數(shù)依賴一定在F+中 /* Armstrong正確完備性：F+中的每

65、一個函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導出來 /* Armstrong公理夠用，完全完備性：所有不能用Armstrong公理推導出來f, 都不為真 若 f 不能用Armstrong公理推導出來， f∈ F+,,有效性與完備性的證明,證明：有效性根據(jù)定理6.1可以得證,定理 6.l Armstrong推理規(guī)則是正確的,Armstrong公理系統(tǒng)推理規(guī)則 關(guān)系模

66、式R 來說有以下的推理規(guī)則： A1.自反律（Reflexivity）： 若Y ? X ? U，則X →Y為F所蘊含。A2.增廣律（Augmentation）：若X→Y為F所蘊含，且Z ? U，則XZ→YZ為F所蘊含。A3.傳遞律（Transitivity）：若X→Y及Y→Z為F所蘊含，則X→Z為F所蘊含。,有效性與完備性的證明,證明：2. 完備性 要證明的題目：F+中的每一個函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armst

67、rong公理推導出來 只需證明逆否命題: 若函數(shù)依賴X→Y不能由F從Armstrong公理導出，那么它必然不為F所蘊含分三步證明：,有效性與完備性的證明,(1)引理: 若V→W成立，且V ? XF+，則W ? XF+ 證 因為 V ? XF+ ，所以有X→V成立；（？） 因為X →V，V→W，于是X→W成立 所以W ? XF+ (2) 構(gòu)造一張二維表r，它由下列兩個元組構(gòu)成

68、 可以證明r必是R（U，F(xiàn)）的一個關(guān)系，即F+中的全部函數(shù)依賴在 r上成立。,引理6.2 設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y ? U，X→Y能由F 根據(jù)Armstrong公理導出的充分必要條件是Y ?XF+,Armstrong公理系統(tǒng)的有效性與完備性(續(xù)),XF+ U-XF+ 11......1 00......0