數(shù)據(jù)庫系統(tǒng)概論(第五版)課件第6章

數(shù)據(jù)庫系統(tǒng)概論AnIntroductiontoDatabaseSystem第六章關(guān)系數(shù)據(jù)理論

xx大學(xué)信息學(xué)院數(shù)據(jù)庫系統(tǒng)概論xx大學(xué)信息學(xué)院基于某個(gè)數(shù)據(jù)庫管理系統(tǒng)設(shè)計(jì)數(shù)據(jù)庫，如何基于數(shù)據(jù)庫系統(tǒng)編程第6章關(guān)系數(shù)據(jù)理論第7章數(shù)據(jù)庫設(shè)計(jì)第8章數(shù)據(jù)庫編程

第二篇設(shè)計(jì)與應(yīng)用開發(fā)篇基于某個(gè)數(shù)據(jù)庫管理系統(tǒng)設(shè)計(jì)數(shù)據(jù)庫，如何基于數(shù)據(jù)庫系統(tǒng)編程第二第六章關(guān)系數(shù)據(jù)理論6.1問題的提出6.2規(guī)范化6.3數(shù)據(jù)依賴的公理系統(tǒng)*6.4模式的分解6.5小結(jié)第六章關(guān)系數(shù)據(jù)理論6.1問題的提出AnIntroductiontoDatabaseSystem6.1問題的提出關(guān)系數(shù)據(jù)庫邏輯設(shè)計(jì)針對具體問題，如何構(gòu)造一個(gè)適合于它的數(shù)據(jù)模式數(shù)據(jù)庫邏輯設(shè)計(jì)的工具──關(guān)系數(shù)據(jù)庫的規(guī)范化理論AnIntroductiontoDatabaseSy*問題的提出（續(xù)）關(guān)系模式由五部分組成，是一個(gè)五元組：

R(U,D,DOM,F)關(guān)系名R是符號(hào)化的元組語義U為一組屬性D為屬性組U中的屬性所來自的域DOM為屬性到域的映射F為屬性組U上的一組數(shù)據(jù)依賴*問題的提出（續(xù)）關(guān)系模式由五部分組成，是一個(gè)五元組：

問題的提出（續(xù)）由于D、DOM與模式設(shè)計(jì)關(guān)系不大，因此在本章中把關(guān)系模式看作一個(gè)三元組：R<U,F>當(dāng)且僅當(dāng)U上的一個(gè)關(guān)系r滿足F時(shí)，r稱為關(guān)系模式R<U,F>的一個(gè)關(guān)系作為二維表，關(guān)系要符合一個(gè)最基本的條件：每個(gè)分量必須是不可分開的數(shù)據(jù)項(xiàng)。滿足了這個(gè)條件的關(guān)系模式就屬于第一范式（1NF）問題的提出（續(xù)）由于D、DOM與模式設(shè)計(jì)關(guān)系不大，因此在本章*問題的提出（續(xù)）數(shù)據(jù)依賴是一個(gè)關(guān)系內(nèi)部屬性與屬性之間的一種約束關(guān)系通過屬性間值的相等與否體現(xiàn)出來的數(shù)據(jù)間相互聯(lián)系是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象是數(shù)據(jù)內(nèi)在的性質(zhì)是語義的體現(xiàn)*問題的提出（續(xù)）數(shù)據(jù)依賴*問題的提出（續(xù)）數(shù)據(jù)依賴的主要類型函數(shù)依賴（FunctionalDependency，簡記為FD）多值依賴（Multi-ValuedDependency，簡記為MVD）*問題的提出（續(xù)）數(shù)據(jù)依賴的主要類型*問題的提出（續(xù)）函數(shù)依賴普遍存在于現(xiàn)實(shí)生活中描述一個(gè)學(xué)生關(guān)系，可以有學(xué)號(hào)、姓名、系名等屬性。一個(gè)學(xué)號(hào)只對應(yīng)一個(gè)學(xué)生，一個(gè)學(xué)生只在一個(gè)系中學(xué)習(xí)“學(xué)號(hào)”值確定后，學(xué)生的姓名及所在系的值就被唯一確定。Sname=f(Sno)，Sdept=f(Sno)即Sno函數(shù)決定SnameSno函數(shù)決定Sdept記作Sno→Sname，Sno→Sdept*問題的提出（續(xù)）函數(shù)依賴普遍存在于現(xiàn)實(shí)生活中*

問題的提出（續(xù)）[例6.1]建立一個(gè)描述學(xué)校教務(wù)的數(shù)據(jù)庫。

涉及的對象包括： 學(xué)生的學(xué)號(hào)（Sno）所在系（Sdept）系主任姓名（Mname）課程號(hào)（Cno）成績（Grade）*問題的提出（續(xù)）[例6.1]建立一個(gè)描述學(xué)校教務(wù)的數(shù)據(jù)*問題的提出（續(xù)）假設(shè)學(xué)校教務(wù)的數(shù)據(jù)庫模式用一個(gè)單一的關(guān)系模式Student來表示，則該關(guān)系模式的屬性集合為：

U＝{Sno,Sdept,Mname,Cno,Grade}現(xiàn)實(shí)世界的已知事實(shí)（語義）：一個(gè)系有若干學(xué)生，但一個(gè)學(xué)生只屬于一個(gè)系；一個(gè)系只有一名（正職）負(fù)責(zé)人；一個(gè)學(xué)生可以選修多門課程，每門課程有若干學(xué)生選修；每個(gè)學(xué)生學(xué)習(xí)每一門課程有一個(gè)成績。*問題的提出（續(xù)）假設(shè)學(xué)校教務(wù)的數(shù)據(jù)庫模式用一個(gè)單一的關(guān)系模*問題的提出（續(xù)）由此可得到屬性組U上的一組函數(shù)依賴F：

F={Sno→Sdept,Sdept→Mname,(Sno,Cno)→Grade}SnoCnoSdeptMnameGrade*問題的提出（續(xù)）由此可得到屬性組U上的一組函數(shù)依賴F：S*問題的提出（續(xù)）關(guān)系模式Student<U,F>中存在的問題：（1）數(shù)據(jù)冗余浪費(fèi)大量的存儲(chǔ)空間每一個(gè)系主任的姓名重復(fù)出現(xiàn)，重復(fù)次數(shù)與該系所有學(xué)生的所有課程成績出現(xiàn)次數(shù)相同。*問題的提出（續(xù)）關(guān)系模式Student<U,F>中存在的*問題的提出（續(xù)）（2）更新異常（UpdateAnomalies）數(shù)據(jù)冗余，更新數(shù)據(jù)時(shí)，維護(hù)數(shù)據(jù)完整性代價(jià)大。某系更換系主任后，必須修改與該系學(xué)生有關(guān)的每一個(gè)元組。*問題的提出（續(xù)）（2）更新異常（UpdateAnomal*問題的提出（續(xù)）（3）插入異常（InsertionAnomalies）如果一個(gè)系剛成立，尚無學(xué)生，則無法把這個(gè)系及其系主任的信息存入數(shù)據(jù)庫。*問題的提出（續(xù)）（3）插入異常（InsertionAno*問題的提出（續(xù)）（4）刪除異常（DeletionAnomalies）如果某個(gè)系的學(xué)生全部畢業(yè)了，則在刪除該系學(xué)生信息的同時(shí)，把這個(gè)系及其系主任的信息也丟掉了。*問題的提出（續(xù)）（4）刪除異常（DeletionAnom*問題的提出（續(xù)）結(jié)論Student關(guān)系模式不是一個(gè)好的模式。一個(gè)“好”的模式應(yīng)當(dāng)不會(huì)發(fā)生插入異常、刪除異常和更新異常，數(shù)據(jù)冗余應(yīng)盡可能少。原因由存在于模式中的某些數(shù)據(jù)依賴引起的。解決方法用規(guī)范化理論改造關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴*問題的提出（續(xù)）結(jié)論*問題的提出（續(xù)）把這個(gè)單一的模式分成三個(gè)關(guān)系模式：S(Sno,Sdept,Sno→Sdept);SC(Sno,Cno,Grade,(Sno,Cno)→Grade);DEPT(Sdept,Mname,Sdept→Mname);這三個(gè)模式都不會(huì)發(fā)生插入異常、刪除異常的問題，數(shù)據(jù)的冗余也得到了控制。*問題的提出（續(xù)）把這個(gè)單一的模式分成三個(gè)關(guān)系模式：第六章關(guān)系數(shù)據(jù)理論6.1問題的提出6.2規(guī)范化6.3數(shù)據(jù)依賴的公理系統(tǒng)*6.4模式的分解6.5小結(jié)第六章關(guān)系數(shù)據(jù)理論6.1問題的提出6.2規(guī)范化6.2.1函數(shù)依賴6.2.2碼6.2.3范式6.2.42NF6.2.53NF6.2.6BCNF6.2.7多值依賴6.2.84NF6.2.9規(guī)范化小結(jié)6.2規(guī)范化6.2.1函數(shù)依賴6.2.1函數(shù)依賴1.函數(shù)依賴2.平凡函數(shù)依賴與非平凡函數(shù)依賴3.完全函數(shù)依賴與部分函數(shù)依賴4.傳遞函數(shù)依賴6.2.1函數(shù)依賴1.函數(shù)依賴*1.函數(shù)依賴定義6.1設(shè)R(U)是一個(gè)屬性集U上的關(guān)系模式，X和Y是U的子集。若對于R(U)的任意一個(gè)可能的關(guān)系r，r中不可能存在兩個(gè)元組在X上的屬性值相等，而在Y上的屬性值不等，則稱“X函數(shù)確定Y”或“Y函數(shù)依賴于X”，記作X→Y。*1.函數(shù)依賴定義6.1設(shè)R(U)是一個(gè)屬性集U上的函數(shù)依賴（續(xù)）[例]Student(Sno,Sname,Ssex,Sage,Sdept),

假設(shè)不允許重名，則有:

Sno→Ssex，Sno→Sage Sno→Sdept，Sno←→Sname

Sname→Ssex，Sname→Sage Sname→Sdept但Ssex→Sage,Ssex→Sdept若X→Y，并且Y→X,則記為X←→Y。若Y不函數(shù)依賴于X,則記為X→Y。函數(shù)依賴（續(xù)）[例]Student(Sno,Sname,函數(shù)依賴（續(xù)）SnoSnameSsexSageSdeptS1

張三男20計(jì)算機(jī)系S1李四女21自動(dòng)化系S3王五男20計(jì)算機(jī)系S4趙六男21計(jì)算機(jī)系S5田七男20計(jì)算機(jī)系...............違背了Sno→Sname函數(shù)依賴（續(xù)）SnoSnameSsexSageSdeptS1函數(shù)依賴（續(xù)）由下面的關(guān)系表,能否得出Sno→SnameSnoSnameSsexSageSdeptS1

張三男20計(jì)算機(jī)系S2李四女21自動(dòng)化系S3王五男20計(jì)算機(jī)系S4趙六男21計(jì)算機(jī)系S5田七男20計(jì)算機(jī)系...............函數(shù)依賴不是指關(guān)系模式R的某個(gè)或某些關(guān)系實(shí)例滿足的約束條件，而是指R的所有關(guān)系實(shí)例均要滿足的約束條件。函數(shù)依賴（續(xù)）由下面的關(guān)系表,能否得出Sno→Snam*函數(shù)依賴（續(xù)）函數(shù)依賴是語義范疇的概念，只能根據(jù)數(shù)據(jù)的語義來確定一個(gè)函數(shù)依賴。例如“姓名→年齡”這個(gè)函數(shù)依賴只有在不允許有同名人的條件下成立*函數(shù)依賴（續(xù)）函數(shù)依賴是語義范疇的概念，只能根據(jù)數(shù)據(jù)的語義*2.平凡函數(shù)依賴與非平凡函數(shù)依賴X→Y，但Y?X則稱X→Y是非平凡的函數(shù)依賴。X→Y，但Y?X

則稱X→Y是平凡的函數(shù)依賴。對于任一關(guān)系模式，平凡函數(shù)依賴都是必然成立的，它不反映新的語義。若不特別聲明，我們總是討論非平凡函數(shù)依賴。*2.平凡函數(shù)依賴與非平凡函數(shù)依賴X→Y，但Y?X則稱X→*平凡函數(shù)依賴與非平凡函數(shù)依賴（續(xù)）若X→Y，則X稱為這個(gè)函數(shù)依賴的決定因素（Determinant）。若X→Y，Y→X，則記作X←→Y。若Y不函數(shù)依賴于X，則記作X?Y。*平凡函數(shù)依賴與非平凡函數(shù)依賴（續(xù)）若X→Y，則X稱為這個(gè)函*3.完全函數(shù)依賴與部分函數(shù)依賴定義6.2在R(U)中，如果X→Y，并且對于X的任何一個(gè)真子集X’,都有X’?Y,則稱Y對X完全函數(shù)依賴，記作X→

Y。若X→Y，但Y不完全函數(shù)依賴于X，則稱Y對X部分函數(shù)依賴，記作X→YFP*3.完全函數(shù)依賴與部分函數(shù)依賴定義6.2在R(U)中*完全函數(shù)依賴與部分函數(shù)依賴（續(xù)）[例]在關(guān)系SC(Sno,Cno,Grade)中，有：由于：Sno?Grade，Cno?Grade，

因此：(Sno,Cno)→

Grade

(Sno,Cno)→Sno(Sno,Cno)→CnoFPP*完全函數(shù)依賴與部分函數(shù)依賴（續(xù)）[例]在關(guān)系SC(Sno*4.傳遞函數(shù)依賴定義6.3在R(U)中，如果X→Y(Y?X)，Y?X，Y→Z，Z?Y,則稱Z對X傳遞函數(shù)依賴(transitivefunctionaldependency)。記為：X→Z。注:如果Y→X,即X←→Y，則Z直接依賴于X，而不是傳遞函數(shù)依賴。[例]在關(guān)系Std(Sno,Sdept,Mname)中，有：Sno→Sdept，Sdept→Mname，Mname傳遞函數(shù)依賴于Sno傳遞*4.傳遞函數(shù)依賴定義6.3在R(U)中，如果X→Y(6.2規(guī)范化6.2.1函數(shù)依賴6.2.2碼6.2.3范式6.2.42NF6.2.53NF6.2.6BCNF6.2.7多值依賴6.2.84NF6.2.9規(guī)范化小結(jié)6.2規(guī)范化6.2.1函數(shù)依賴*6.2.2碼定義6.4設(shè)K為R<U,F>中的屬性或?qū)傩越M合。若K→U，則K稱為R的一個(gè)候選碼(CandidateKey)。如果U部分函數(shù)依賴于K，即K→U,則K稱為超碼（Surpkey）。候選碼是最小的超碼，即K的任意一個(gè)真子集都不是候選碼。若關(guān)系模式R有多個(gè)候選碼，則選定其中的一個(gè)做為主碼(Primarykey)。FP*6.2.2碼定義6.4設(shè)K為R<U,F>中的屬性或*碼（續(xù)）主屬性與非主屬性包含在任何一個(gè)候選碼中的屬性，稱為主屬性（Primeattribute）不包含在任何碼中的屬性稱為非主屬性（Nonprimeattribute）或非碼屬性（Non-keyattribute）全碼：整個(gè)屬性組是碼，稱為全碼（All-key）*碼（續(xù)）主屬性與非主屬性*碼（續(xù)）[例6.2]S(Sno,Sdept,Sage)，單個(gè)屬性Sno是碼

SC(Sno,Cno,Grade)中，(Sno,Cno)是碼[例6.3]R(P,W,A)

P：演奏者W：作品A：聽眾

一個(gè)演奏者可以演奏多個(gè)作品 某一作品可被多個(gè)演奏者演奏 聽眾可以欣賞不同演奏者的不同作品

碼為(P,W,A)，即All-Key*碼（續(xù)）[例6.2]S(Sno,Sdept,Sage)*碼（續(xù)）定義6.5關(guān)系模式R中屬性或?qū)傩越MX

并非R的碼，但X

是另一個(gè)關(guān)系模式的碼，則稱X

是R

的外部碼（Foreignkey）也稱外碼。SC(Sno,Cno,Grade)中，Sno不是碼Sno是S(Sno,Sdept,Sage)的碼，則Sno是SC的外碼主碼與外部碼一起提供了表示關(guān)系間聯(lián)系的手段*碼（續(xù)）定義6.5關(guān)系模式R中屬性或?qū)傩越MX并非6.2規(guī)范化6.2.1函數(shù)依賴6.2.2碼6.2.3范式6.2.42NF6.2.53NF6.2.6BCNF6.2.7多值依賴6.2.84NF6.2.9規(guī)范化小結(jié)6.2規(guī)范化6.2.1函數(shù)依賴*6.2.3范式范式是符合某一種級(jí)別的關(guān)系模式的集合。關(guān)系數(shù)據(jù)庫中的關(guān)系必須滿足一定的要求。滿足不同程度要求的為不同范式。范式的種類：

第一范式(1NF)第二范式(2NF)第三范式(3NF)BC范式(BCNF)第四范式(4NF)第五范式(5NF)*6.2.3范式范式是符合某一種級(jí)別的關(guān)系模式的集合。第*范式（續(xù)）各種范式之間存在聯(lián)系：某一關(guān)系模式R為第n范式，可簡記為R∈nNF。一個(gè)低一級(jí)范式的關(guān)系模式，通過模式分解（schemadecomposition）可以轉(zhuǎn)換為若干個(gè)高一級(jí)范式的關(guān)系模式的集合，這種過程就叫規(guī)范化（normalization）。*范式（續(xù)）各種范式之間存在聯(lián)系：一個(gè)低一級(jí)范式的關(guān)系模式，6.2規(guī)范化6.2.1函數(shù)依賴6.2.2碼6.2.3范式6.2.42NF6.2.53NF6.2.6BCNF6.2.7多值依賴6.2.84NF6.2.9規(guī)范化小結(jié)6.2規(guī)范化6.2.1函數(shù)依賴*6.2.4

2NF定義6.6若關(guān)系模式R∈1NF，并且每一個(gè)非主屬性都完全函數(shù)依賴于任何一個(gè)候選碼，則R∈2NF[例6.4]

S-L-C(Sno,Sdept,Sloc,Cno,Grade)，

Sloc為學(xué)生的住處，并且每個(gè)系的學(xué)生住在同一個(gè)地方。S-L-C的碼為(Sno,Cno)。

函數(shù)依賴有(Sno,Cno)→GradeSno→Sdept,(Sno,Cno)→SdeptSno→Sloc,(Sno,Cno)→SlocSdept→SlocFPP*6.2.42NF定義6.6若關(guān)系模式R∈1NF，并*2NF（續(xù)）SnoCnoGradeSdeptSloc關(guān)系模式S-L-C不屬于2NF非主屬性Sdept、Sloc并不完全依賴于碼*2NF（續(xù)）SnoCnoGradeSdeptSloc關(guān)系模*2NF（續(xù)）一個(gè)關(guān)系模式不屬于2NF，會(huì)產(chǎn)生以下問題：插入異常如果插入一個(gè)新學(xué)生，但該生未選課，即該生無Cno，由于插入元組時(shí)，必須給定碼值，因此插入失敗。刪除異常如果S4只選了一門課C3，現(xiàn)在他不再選這門課，則刪除C3后，整個(gè)元組的其他信息也被刪除了。修改復(fù)雜如果一個(gè)學(xué)生選了多門課，則Sdept，Sloc被存儲(chǔ)了多次。如果該生轉(zhuǎn)系，則需要修改所有相關(guān)的Sdept和Sloc，造成修改的復(fù)雜化。*2NF（續(xù)）一個(gè)關(guān)系模式不屬于2NF，會(huì)產(chǎn)生以下問題：*2NF（續(xù)）出現(xiàn)這種問題的原因例子中有兩類非主屬性：一類如Grade，它對碼完全函數(shù)依賴另一類如Sdept、Sloc，它們對碼不是完全函數(shù)依賴解決方法：用投影分解把關(guān)系模式S-L-C分解成兩個(gè)關(guān)系模式SC(Sno,Cno,Grade)S-L(Sno,Sdept,Sloc)*2NF（續(xù)）出現(xiàn)這種問題的原因2NF（續(xù)）SC的碼為(Sno,Cno),SL的碼為Sno，這樣使得非主屬性對碼都是完全函數(shù)依賴了SnoCnoGradeSnoSdeptSloc圖6.4SC中的函數(shù)依賴圖6.5S-L中的函數(shù)依賴2NF（續(xù)）SC的碼為(Sno,Cno),SL的碼為Sno，6.2規(guī)范化6.2.1函數(shù)依賴6.2.2碼6.2.3范式6.2.42NF6.2.53NF6.2.6BCNF6.2.7多值依賴6.2.84NF6.2.9規(guī)范化小結(jié)6.2規(guī)范化6.2.1函數(shù)依賴*6.2.53NF定義6.7設(shè)關(guān)系模式R<U,F>∈1NF,若R中不存在這樣的碼X、屬性組Y及非主屬性Z（Z?Y）,使得X→Y，Y→Z成立，Y?X不成立，則稱R<U,F>∈3NF。SC沒有傳遞依賴，因此SC∈3NFS-L中Sno→Sdept(Sdept?Sno),Sdept→Sloc，可得Sno→Sloc。解決的辦法是將S-L分解成S-D(Sno,Sdept)∈3NFD-L(Sdept,Sloc)∈3NF傳遞*6.2.53NF定義6.7設(shè)關(guān)系模式R<U,F>∈6.2規(guī)范化6.2.1函數(shù)依賴6.2.2碼6.2.3范式6.2.42NF6.2.53NF6.2.6BCNF6.2.7多值依賴6.2.84NF6.2.9規(guī)范化小結(jié)6.2規(guī)范化6.2.1函數(shù)依賴*6.2.6

BCNFBCNF（BoyceCoddNormalForm）由Boyce和Codd提出，比3NF更進(jìn)了一步。通常認(rèn)為BCNF是修正的第三范式，有時(shí)也稱為擴(kuò)充的第三范式。定義6.8設(shè)關(guān)系模式R<U,F>∈1NF，若X→Y且Y?X時(shí)X必含有碼，則R<U,F>∈BCNF。換言之，在關(guān)系模式R<U,F>中，如果每一個(gè)決定屬性集都包含候選碼，則R∈BCNF。*6.2.6BCNFBCNF（BoyceCoddN*BCNF（續(xù)）BCNF的關(guān)系模式所具有的性質(zhì)所有非主屬性都完全函數(shù)依賴于每個(gè)候選碼所有主屬性都完全函數(shù)依賴于每個(gè)不包含它的候選碼沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性如果一個(gè)關(guān)系數(shù)據(jù)庫中的所有關(guān)系模式都屬于BCNF，那么在函數(shù)依賴范疇內(nèi)，它已實(shí)現(xiàn)了模式的徹底分解，達(dá)到了最高的規(guī)范化程度，消除了插入異常和刪除異常。*BCNF（續(xù)）BCNF的關(guān)系模式所具有的性質(zhì)[例6.5]考察關(guān)系模式C(Cno,Cname,Pcno)它只有一個(gè)碼Cno，沒有任何屬性對Cno部分依賴或傳遞依賴，所以C∈3NF。同時(shí)C中Cno是唯一的決定因素，所以C∈BCNF。對于關(guān)系模式SC(Sno,Cno,Grade)可作同樣分析。BCNF（續(xù)）[例6.5]考察關(guān)系模式C(Cno,Cname,Pcno)B[例6.6]關(guān)系模式S(Sno,Sname,Sdept,Sage)，假定Sname也具有唯一性，那么S就有兩個(gè)碼，這兩個(gè)碼都由單個(gè)屬性組成，彼此不相交。其他屬性不存在對碼的傳遞依賴與部分依賴，所以S∈3NF。同時(shí)S中除Sno，Sname外沒有其他決定因素，所以S也屬于BCNF。BCNF（續(xù)）[例6.6]關(guān)系模式S(Sno,Sname,Sdept,S[例6.7]關(guān)系模式SJP(S,J,P)中，S是學(xué)生，J表示課程，P表示名次。每一個(gè)學(xué)生選修每門課程的

成績有一定的名次，每門課程中每一名次只有一

個(gè)學(xué)生（即沒有并列名次）。由語義可得到函數(shù)依賴：(S,J)→P；(J,P)→S(S,J)與(J,P)都可以作為候選碼。關(guān)系模式中沒有屬性對碼傳遞依賴或部分依賴，所以SJP∈3NF。除(S,J)與(J,P)以外沒有其他決定因素，所以SJP∈BCNF。BCNF（續(xù)）[例6.7]關(guān)系模式SJP(S,J,P)中，S是學(xué)生，J表BCNF（續(xù)）[例6.8]關(guān)系模式STJ(S,T,J)中，S表示學(xué)生，T表示教師，J表示課程。每一教師只教一門課。每

門課有若干教師，某一學(xué)生選定某門課，就對應(yīng)

一個(gè)固定的教師。由語義可得到函數(shù)依賴：(S,J)→T；(S,T)→J；T→J因?yàn)闆]有任何非主屬性對碼傳遞依賴或部分依賴，STJ∈3NF。因?yàn)門是決定因素，而T不包含碼，所以STJ∈BCNF

關(guān)系。圖6.6STJ中的函數(shù)依賴BCNF（續(xù)）[例6.8]關(guān)系模式STJ(S,T,J)中，BCNF（續(xù)）對于不是BCNF的關(guān)系模式，仍然存在不合適的地方。非BCNF的關(guān)系模式也可以通過分解成為BCNF。例如STJ可分解為ST(S,T)與TJ(T,J)，它們都是BCNF。BCNF（續(xù)）對于不是BCNF的關(guān)系模式，仍然存在不合適的地BCNF（續(xù)）3NF和BCNF是在函數(shù)依賴的條件下對模式分解所能達(dá)到的分離程度的測度。一個(gè)模式中的關(guān)系模式如果都屬于BCNF，那么在函數(shù)依賴范疇內(nèi)，它已實(shí)現(xiàn)了徹底的分離，已消除了插入和刪除的異常。3NF的“不徹底”性表現(xiàn)在可能存在主屬性對碼的部分依賴和傳遞依賴。BCNF（續(xù)）3NF和BCNF是在函數(shù)依賴的條件下對模式分解6.2規(guī)范化6.2.1函數(shù)依賴6.2.2碼6.2.3范式6.2.42NF6.2.53NF6.2.6BCNF6.2.7多值依賴6.2.84NF6.2.9規(guī)范化小結(jié)6.2規(guī)范化6.2.1函數(shù)依賴*6.2.7多值依賴?yán)齕6.9]設(shè)學(xué)校中某一門課程由多個(gè)教師講授，他們使用相同的一套參考書。每個(gè)教員可以講授多門課程，每種參考書可以供多門課程使用用關(guān)系模式Teaching(C,T,B)來表示課程C、教師T和參考書B之間的關(guān)系。*6.2.7多值依賴?yán)齕6.9]設(shè)學(xué)校中某一門課程由多個(gè)教多值依賴（續(xù)）表6.3非規(guī)范化關(guān)系示例………課程C教員T參考書B

物理

數(shù)學(xué)

計(jì)算數(shù)學(xué)李勇王軍

李勇張平張平

周峰

普通物理學(xué)光學(xué)原理物理習(xí)題集數(shù)學(xué)分析微分方程高等代數(shù)

數(shù)學(xué)分析

…多值依賴（續(xù)）表6.3非規(guī)范化關(guān)系示例………課程C教員*多值依賴（續(xù)）表6.4規(guī)范化的二維表Teaching課程C教員T參考書B物理李勇普通物理學(xué)物理李勇光學(xué)原理物理李勇物理習(xí)題集物理王軍普通物理學(xué)物理王軍光學(xué)原理物理王軍物理習(xí)題集數(shù)學(xué)李勇普通物理學(xué)數(shù)學(xué)李勇光學(xué)原理數(shù)學(xué)李勇物理習(xí)題集數(shù)學(xué)張平普通物理學(xué)數(shù)學(xué)張平光學(xué)原理數(shù)學(xué)張平物理習(xí)題集………*多值依賴（續(xù)）表6.4規(guī)范化的二維表Teaching*多值依賴（續(xù)）Teaching具有唯一候選碼(C,T,B)，即全碼。Teaching∈BCNF*多值依賴（續(xù)）Teaching具有唯一候選碼(C,T,B)*多值依賴（續(xù)）課程C教員T參考書B物理李勇普通物理學(xué)物理李勇光學(xué)原理物理李勇物理習(xí)題集物理王軍普通物理學(xué)物理王軍光學(xué)原理物理王軍物理習(xí)題集數(shù)學(xué)李勇普通物理學(xué)數(shù)學(xué)李勇光學(xué)原理數(shù)學(xué)李勇物理習(xí)題集數(shù)學(xué)張平普通物理學(xué)數(shù)學(xué)張平光學(xué)原理數(shù)學(xué)張平物理習(xí)題集………(1)數(shù)據(jù)冗余度大：有多少名任課教師，參考書就要存儲(chǔ)多少次。*多值依賴（續(xù)）課程C教員T參考書B物理李勇普通物*多值依賴（續(xù)）課程C教員T參考書B物理李勇普通物理學(xué)物理李勇光學(xué)原理物理李勇物理習(xí)題集物理王軍普通物理學(xué)物理王軍光學(xué)原理物理王軍物理習(xí)題集數(shù)學(xué)李勇普通物理學(xué)數(shù)學(xué)李勇光學(xué)原理數(shù)學(xué)李勇物理習(xí)題集數(shù)學(xué)張平普通物理學(xué)數(shù)學(xué)張平光學(xué)原理數(shù)學(xué)張平物理習(xí)題集………(2)增加操作復(fù)雜：當(dāng)某一課程增加一名任課教師時(shí)，該課程有多少本參照書，就必須插入多少個(gè)元組。*多值依賴（續(xù)）課程C教員T參考書B物理李勇普通物*多值依賴（續(xù)）課程C教員T參考書B物理李勇普通物理學(xué)物理李勇光學(xué)原理物理李勇物理習(xí)題集物理王軍普通物理學(xué)物理王軍光學(xué)原理物理王軍物理習(xí)題集數(shù)學(xué)李勇普通物理學(xué)數(shù)學(xué)李勇光學(xué)原理數(shù)學(xué)李勇物理習(xí)題集數(shù)學(xué)張平普通物理學(xué)數(shù)學(xué)張平光學(xué)原理數(shù)學(xué)張平物理習(xí)題集………(3)刪除操作復(fù)雜：某一門課要去掉一本參考書，該課程有多少名教師，就必須刪除多少個(gè)元組。*多值依賴（續(xù)）課程C教員T參考書B物理李勇普通物*多值依賴（續(xù)）課程C教員T參考書B物理李勇普通物理學(xué)物理李勇光學(xué)原理物理李勇物理習(xí)題集物理王軍普通物理學(xué)物理王軍光學(xué)原理物理王軍物理習(xí)題集數(shù)學(xué)李勇普通物理學(xué)數(shù)學(xué)李勇光學(xué)原理數(shù)學(xué)李勇物理習(xí)題集數(shù)學(xué)張平普通物理學(xué)數(shù)學(xué)張平光學(xué)原理數(shù)學(xué)張平物理習(xí)題集………(4)修改操作復(fù)雜：某一門課要修改一本參考書，該課程有多少名教師，就必須修改多少個(gè)元組。產(chǎn)生原因:

存在多值依賴*多值依賴（續(xù)）課程C教員T參考書B物理李勇普通物*多值依賴（續(xù)）定義6.9設(shè)R(U)是屬性集U上的一個(gè)關(guān)系模式。X,Y,Z是U的子集，并且Z=U-X-Y。關(guān)系模式R(U)中多值依賴X→→Y成立，當(dāng)且僅當(dāng)對R(U)的任一關(guān)系r，給定的一對(x,z)值，有一組Y的值，這組值僅僅決定于x值而與z值無關(guān)。例Teaching（C,T,B）對于C的每一個(gè)值，T有一組值與之對應(yīng)，而不論B取何值。因此T多值依賴于C，即C→→T。*多值依賴（續(xù)）定義6.9設(shè)R(U)是屬性集U上的一多值依賴（續(xù)）多值依賴的另一個(gè)等價(jià)的定義在R(U)的任一關(guān)系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值所得的兩個(gè)新元組必在r中則Y多值依賴于X，記為X→→Y。這里X，Y是U的子集，Z=U-X-Y。多值依賴（續(xù)）多值依賴的另一個(gè)等價(jià)的定義*多值依賴（續(xù)）平凡多值依賴和非平凡的多值依賴 若X→→Y，而Z＝Ф，即Z為空，則稱X→→Y為平凡的多值依賴。 否則稱X→→Y為非平凡的多值依賴。*多值依賴（續(xù)）平凡多值依賴和非平凡的多值依賴多值依賴（續(xù)）WSCW1S1C1W1S1C2W1S1C3W1S2C1W1S2C2W1S2C3W2S3C4W2S3C5W2S4C4W2S4C5[例6.10]關(guān)系模式WSC(W,S,C)中，W表示倉庫，S表示保管員，C表示商品。假設(shè)每個(gè)倉庫有若干個(gè)保管員，有若干種商品。每個(gè)保管員保管所在倉庫的所有商品，每種商品被所有保管員保管。多值依賴（續(xù)）WSCW1S1C1W1S1C2W1S1C3W1多值依賴（續(xù)）按照語義對于W的每一個(gè)值Wi，S有一個(gè)完整的集合與之對應(yīng)而不問C取何值。所以W→→S。如圖6.7所示對應(yīng)W的某一個(gè)值Wi的全部S值記作{S}Wi（表示此倉庫工作的全部保管員）全部C值記作{C}Wi（表示在此倉庫中存放的所有商品）應(yīng)當(dāng)有{S}Wi中的每一個(gè)值和{C}Wi中的每一個(gè)C值對應(yīng)于是{S}Wi與{C}Wi之間正好形成一個(gè)完全二分圖，因而W→→S。多值依賴（續(xù)）按照語義對于W的每一個(gè)值Wi，S有一個(gè)完整的集多值依賴（續(xù)）由于C與S的完全對稱性，必然有W→→C成立。圖6.7W→→S且W→→C多值依賴（續(xù)）由于C與S的完全對稱性，必然有W→→C成立。圖多值依賴（續(xù)）多值依賴的性質(zhì)（1）多值依賴具有對稱性。即若X→→Y，則X→→Z，其中Z＝U－X－Y多值依賴的對稱性可以用完全二分圖直觀地表示出來。從[例6.10]容易看出，因?yàn)槊總€(gè)保管員保管所有商品，同時(shí)每種商品被所有保管員保管，顯然若W→→S，必然有W→→C。多值依賴（續(xù)）多值依賴的性質(zhì)*多值依賴（續(xù)）（2）多值依賴具有傳遞性。即若X→→Y，Y→→Z，則

X→→Z-Y。（3）函數(shù)依賴是多值依賴的特殊情況。即若X→Y，則

X→→Y。（4）若X→→Y，X→→Z，則X→→YZ。（5）若X→→Y，X→→Z，則X→→Y∩Z。（6）若X→→Y，X→→Z，則X→→Y-Z，X→→Z-Y。*多值依賴（續(xù)）（2）多值依賴具有傳遞性。即若X→→Y，Y→*多值依賴（續(xù)）多值依賴與函數(shù)依賴的區(qū)別（1）多值依賴的有效性與屬性集的范圍有關(guān)若X→→Y在U上成立，則在W（XY

W

U）上一定成立；反之則不然，即X→→Y在W（W

U）上成立，在U上并不一定成立。原因：多值依賴的定義中不僅涉及屬性組X和Y，而且涉及U中其余屬性Z。*多值依賴（續(xù)）多值依賴與函數(shù)依賴的區(qū)別*多值依賴（續(xù)）多值依賴的有效性與屬性集的范圍有關(guān)（續(xù)）一般地，在R(U)上若有X→→Y在W(W

U)上成立，則稱X→→Y為R(U)的嵌入型多值依賴。函數(shù)依賴X→Y的有效性僅決定于X、Y這兩個(gè)屬性集的值只要在R(U)的任何一個(gè)關(guān)系r中，元組在X和Y上的值滿足定義6.l，則函數(shù)依賴X→Y在任何屬性集W(XY

W

U)上成立。*多值依賴（續(xù)）多值依賴的有效性與屬性集的范圍有關(guān)（續(xù)）*多值依賴（續(xù)）（2）若函數(shù)依賴X→Y在R(U)上成立，則對于任何Y‘

Y均有X→Y’成立。多值依賴X→→Y若在R(U)上成立，不能斷言對于任何Y’

Y有X→→Y’成立。*多值依賴（續(xù)）（2）若函數(shù)依賴X→Y在R(U)上成立，則*多值依賴（續(xù)）例如，關(guān)系R(A,B,C,D)，A→→BC成立，當(dāng)然也有A→→D成立。有R的一個(gè)關(guān)系實(shí)例，在此實(shí)例上A→→B是不成立的。ABCDa1b1c1d1a1b1c1d2a1b2c2d1a1b2c2d2

表6.6R的一個(gè)實(shí)例*多值依賴（續(xù)）例如，關(guān)系R(A,B,C,D)，A→→6.2規(guī)范化6.2.1函數(shù)依賴6.2.2碼6.2.3范式6.2.42NF6.2.53NF6.2.6BCNF6.2.7多值依賴6.2.84NF6.2.9規(guī)范化小結(jié)6.2規(guī)范化6.2.1函數(shù)依賴*6.2.84NF定義6.10關(guān)系模式R<U,F>∈1NF，如果對于R的每個(gè)非平凡多值依賴X→→Y（Y

?

X），X都含有碼，則R<U,F>∈4NF。4NF就是限制關(guān)系模式的屬性之間不允許有非平凡且非函數(shù)依賴的多值依賴。4NF所允許的非平凡多值依賴實(shí)際上是函數(shù)依賴。*6.2.84NF定義6.10關(guān)系模式R<U,F>∈*4NF（續(xù)）如果一個(gè)關(guān)系模式是4NF，則必為BCNF。在[例6.10]的WSC中，W→→S,W→→C,他們都是非平凡多值依賴。而W不是碼，關(guān)系模式WSC的碼是(W,S,C)，即All-key，因此WSC∈4NF?？梢园裌SC分解成WS(W,S),WC(W,C)，

WS∈4NF，WC∈4NF。*4NF（續(xù)）如果一個(gè)關(guān)系模式是4NF，則必為BCNF。6.2規(guī)范化6.2.1函數(shù)依賴6.2.2碼6.2.3范式6.2.42NF6.2.53NF6.2.6BCNF6.2.7多值依賴6.2.84NF6.2.9規(guī)范化小結(jié)6.2規(guī)范化6.2.1函數(shù)依賴*6.2.9規(guī)范化小結(jié)在關(guān)系數(shù)據(jù)庫中，對關(guān)系模式的基本要求是滿足第一范式。規(guī)范化程度過低的關(guān)系不一定能夠很好地描述現(xiàn)實(shí)世界可能存在插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問題解決方法就是對其進(jìn)行規(guī)范化，轉(zhuǎn)換成高級(jí)范式。*6.2.9規(guī)范化小結(jié)在關(guān)系數(shù)據(jù)庫中，對關(guān)系模式的基本要*規(guī)范化小結(jié)（續(xù)）一個(gè)低一級(jí)范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換為若干個(gè)高一級(jí)范式的關(guān)系模式集合，這種過程就叫關(guān)系模式的規(guī)范化。關(guān)系數(shù)據(jù)庫的規(guī)范化理論是數(shù)據(jù)庫邏輯設(shè)計(jì)的工具。*規(guī)范化小結(jié)（續(xù)）一個(gè)低一級(jí)范式的關(guān)系模式，通過模式分解可以*規(guī)范化小結(jié)（續(xù)）規(guī)范化的基本思想是逐步消除數(shù)據(jù)依賴中不合適的部分，使模式中的各關(guān)系模式達(dá)到某種程度的“分離”。即采用“一事一地”的模式設(shè)計(jì)原則讓一個(gè)關(guān)系描述一個(gè)概念、一個(gè)實(shí)體或者實(shí)體間的一種聯(lián)系。若多于一個(gè)概念就把它“分離”出去。因此規(guī)范化實(shí)質(zhì)上是概念的單一化。*規(guī)范化小結(jié)（續(xù)）規(guī)范化的基本思想*規(guī)范化小結(jié)（續(xù)）關(guān)系模式規(guī)范化的基本步驟

1NF ↓消除非主屬性對碼的部分函數(shù)依賴消除決定因素2NF非碼的非平凡↓消除非主屬性對碼的傳遞函數(shù)依賴函數(shù)依賴3NF ↓消除主屬性對碼的部分和傳遞函數(shù)依賴

BCNF ↓消除非平凡且非函數(shù)依賴的多值依賴

4NF圖6.8規(guī)范化過程*規(guī)范化小結(jié)（續(xù)）關(guān)系模式規(guī)范化的基本步驟圖6.8規(guī)范化過*規(guī)范化小結(jié)（續(xù)）不能說規(guī)范化程度越高的關(guān)系模式就越好。必須對現(xiàn)實(shí)世界的實(shí)際情況和用戶應(yīng)用需求作進(jìn)一步分析，確定一個(gè)合適的、能夠反映現(xiàn)實(shí)世界的模式。上面的規(guī)范化步驟可以在其中任何一步終止。*規(guī)范化小結(jié)（續(xù)）不能說規(guī)范化程度越高的關(guān)系模式就越好。第六章關(guān)系數(shù)據(jù)理論6.1問題的提出6.2規(guī)范化6.3數(shù)據(jù)依賴的公理系統(tǒng)*6.4模式的分解6.5小結(jié)第六章關(guān)系數(shù)據(jù)理論6.1問題的提出*6.3數(shù)據(jù)依賴的公理系統(tǒng)定義6.11對于滿足一組函數(shù)依賴F的關(guān)系模式R<U,F>，其任何一個(gè)關(guān)系r，若函數(shù)依賴X→Y都成立（即r中任意兩元組t、s，若t[X]=s[X]，則t[Y]=s[Y]），則稱F邏輯蘊(yùn)涵X→Y。*6.3數(shù)據(jù)依賴的公理系統(tǒng)定義6.11對于滿足一組函*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）Armstrong公理系統(tǒng)一套推理規(guī)則，是模式分解算法的理論基礎(chǔ)用途求給定關(guān)系模式的碼從一組函數(shù)依賴求得蘊(yùn)涵的函數(shù)依賴*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）Armstrong公理系統(tǒng)*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）Armstrong公理系統(tǒng)設(shè)U為屬性集總體，F(xiàn)是U上的一組函數(shù)依賴，于是有關(guān)系模式R<U,F>。對R<U,F>來說有以下的推理規(guī)則：A1自反律（reflexivity

rule）：若Y

X

U，則X→Y為F所蘊(yùn)涵。A2增廣律（augmentation

rule）：若X→Y為F所蘊(yùn)涵，且Z

U，則XZ→YZ為F所蘊(yùn)涵。A3傳遞律（transitivity

rule）：若X→Y及Y→Z為F所蘊(yùn)涵，則X→Z為F所蘊(yùn)涵。注意：由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴,

自反律的使用并不依賴于F。*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）Armstrong公理系統(tǒng)設(shè)U*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）定理6.1Armstrong推理規(guī)則是正確的。證明A1自反律 設(shè)Y

X

U

。 對R<U,F>的任一關(guān)系r中的任意兩個(gè)元組t、s： 若t[X]=s[X]，由于Y

X，有t[Y]=s[Y]， 所以X→Y成立，

自反律得證。*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）定理6.1Armstrong推*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）A2增廣律 設(shè)X→Y為F所蘊(yùn)涵，且Z

U。 對R<U,F>的任一關(guān)系r中任意的兩個(gè)元組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所蘊(yùn)涵， 增廣律得證。*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）A2增廣律*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）A3傳遞律 設(shè)X→Y及Y→Z為F所蘊(yùn)涵。 對R<U,F>的任一關(guān)系r中的任意兩個(gè)元組t、s： 若t[X]=s[X]，由于X→Y，有t[Y]=s[Y]； 再由Y→Z，有t[Z]=s[Z]，

所以X→Z為F所蘊(yùn)涵， 傳遞律得證。*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）A3傳遞律*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）根據(jù)A1，A2，A3這三條推理規(guī)則可以得到下面三條推理規(guī)則：合并規(guī)則（unionrule）：由X→Y，X→Z，有X→YZ。偽傳遞規(guī)則（pseudotransitivityrule）：

由X→Y，WY→Z，有XW→Z。分解規(guī)則（decompositionrule）：

由X→Y及ZY，有X→Z。

*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）根據(jù)A1，A2，A3這三條推理規(guī)則*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）根據(jù)合并規(guī)則和分解規(guī)則，可得引理6.1引理6.1

X→A1A2…Ak成立的充分必要條件是X→Ai成立（i=1，2，…，k）。*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）根據(jù)合并規(guī)則和分解規(guī)則，可得引理6*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）定義6.12在關(guān)系模式R<U,F>中為F所邏輯蘊(yùn)涵的函數(shù)依賴的全體叫作F的閉包，記為F+。定義6.13設(shè)F為屬性集U上的一組函數(shù)依賴，X、Y

U，XF+={A|X→A能由F根據(jù)Armstrong公理導(dǎo)出}，XF+稱為屬性集X關(guān)于函數(shù)依賴集F的閉包。*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）定義6.12在關(guān)系模式R<U,*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）引理6.2設(shè)F為屬性集U上的一組函數(shù)依賴，X、Y

U，X→Y能由F根據(jù)Armstrong公理導(dǎo)出的充分必要條件是Y

XF+。引理6.2的用途判定X→Y是否能由F根據(jù)Armstrong公理導(dǎo)出的問題，就轉(zhuǎn)化為求出XF+，判定Y是否為XF+的子集的問題。*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）引理6.2設(shè)F為屬性集U上的一*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）求閉包的算法算法6.1

求屬性集X（X

U）關(guān)于U上的函數(shù)依賴集F的閉包XF+

輸入：X，F(xiàn)輸出：XF+步驟：迭代*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）求閉包的算法迭代*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）令X(0)=X，i=0求B，這里B={A|(

V)(

W)(V→WF∧V

X(i)∧A

W)}。

X(i+1)=B∪X(i)。判斷X(i+1)=X(i)。若X(i+1)與X(i)相等或X(i)=U

，則X(i)就是XF+，

算法終止。若否，則i=i+1，返回第②步。對X(i)中的每個(gè)元素，依次檢查相應(yīng)的函數(shù)依賴,將依賴它的屬性加入B

*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）令X(0)=X，i=0對X(i)中*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）[例6.11]已知關(guān)系模式R<U,F>，其中

U={A,B,C,D,E}；

F={AB→C,B→D,C→E,EC→B,AC→B}。 求(AB)F+

。*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）[例6.11]已知關(guān)系模式R<*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）解：由算法6.1，設(shè)X(0)=AB。計(jì)算X(1)：逐一的掃描F集合中各個(gè)函數(shù)依賴，找左部為A、B或AB的函數(shù)依賴。得到兩個(gè)：AB→C，B→D。于是X(1)=AB∪CD=ABCD。因?yàn)閄(0)≠X(1)，所以再找出左部為ABCD子集的那些函數(shù)依賴，又得到C→E，AC→B，于是X(2)=X(1)∪BE=ABCDE。因?yàn)閄(2)已等于全部屬性集合，所以(AB)F+=ABCDE。參見愛課程網(wǎng)數(shù)據(jù)庫系統(tǒng)概論6.3節(jié)動(dòng)畫《求閉包》*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）解：由算法6.1，設(shè)X(0)=A*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）有效性與完備性的含義有效性：由F

出發(fā)根據(jù)Armstrong公理推導(dǎo)出來的每一個(gè)函數(shù)依賴一定在F

+中完備性：F

+中的每一個(gè)函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）有效性與完備性的含義*定理6.2

Armstrong公理系統(tǒng)是有效的、完備的。證明： 1.有效性有效性實(shí)際上是“正確性”可由定理6.1得證數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）*定理6.2Armstrong公理系統(tǒng)是有效的、完備的。數(shù)*2.完備性

只需證明逆否命題：若函數(shù)依賴X→Y不能由F從Armstrong公理導(dǎo)出，那么它必然不為F

所蘊(yùn)涵分三步證明：（1）

若V→W成立，且V

XF+，則W

XF+證：因?yàn)?/p>

V

XF+，所以有X→V成立；

因?yàn)閄→V，V→W，于是X→W

成立；所以W

XF+。

數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）*2.完備性數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）*（2）構(gòu)造一張二維表r，它由下列兩個(gè)元組構(gòu)成，可以證明r必是R<U,F>的一個(gè)關(guān)系，即F中的全部函數(shù)依賴在r上成立。

XF+

U-XF+

11......100......0

11......111......1

若r不是R<U,F>的關(guān)系，則必由于F中有某一個(gè)函數(shù)依賴V→W

在r上不成立所致。由r的構(gòu)成可知，V

必定是XF+

的子集，而

W

不是XF+

的子集，可是由第（1）步，W

?

XF+，矛盾。

所以r

必是R<U,F>的一個(gè)關(guān)系。數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）*（2）構(gòu)造一張二維表r，它由下列兩個(gè)元組構(gòu)成，可以證明r*（3）若X→Y不能由F從Armstrong公理導(dǎo)出，則Y不是XF+的子集。（引理6.2）因此必有Y的子集Y’

滿足Y’U-XF+，

則X→Y

在r中不成立，

即X→Y

必不為R<U,F>蘊(yùn)涵。數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）*（3）若X→Y不能由F從Armstrong公理導(dǎo)出，則Y不*Armstrong公理的完備性及有效性說明:“導(dǎo)出”與“蘊(yùn)涵”是兩個(gè)完全等價(jià)的概念F+

：為F所邏輯蘊(yùn)涵的函數(shù)依賴的全體（定義6.12）F+

：可以說成由F出發(fā)借助Armstrong公理導(dǎo)出的函數(shù)依賴的集合數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）*Armstrong公理的完備性及有效性說明:數(shù)據(jù)依賴的公理*定義6.14如果G+=F+，就說函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價(jià)。兩個(gè)函數(shù)依賴集等價(jià)是指它們的閉包等價(jià)數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）*定義6.14如果G+=F+，就說函數(shù)依賴集F覆蓋G（F函數(shù)依賴集等價(jià)的充要條件引理6.3F+=G+的充分必要條件是F

G+和G

F+。證:必要性顯然，只證充分性。（1）若FG+

，則XF+

XG++。（2）任取X→YF+

則有Y

XF+XG++。所以X→Y

(G

+)+=G+。即F+

G+。（3）同理可證G

+F+，所以F+=G+。引理6.3給出了判斷兩個(gè)函數(shù)依賴集等價(jià)的可行算法如何判定F

G+？只需逐一對F中的函數(shù)依賴X→Y考察

Y

是否屬于XG++

數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）函數(shù)依賴集等價(jià)的充要條件引理6.3給出了判斷兩個(gè)函數(shù)依賴集等*定義6.15如果函數(shù)依賴集F滿足下列條件，則稱F為一個(gè)極小函數(shù)依賴集，亦稱為最小依賴集或最小覆蓋。（1）F中任一函數(shù)依賴的右部僅含有一個(gè)屬性。（2）F中不存在這樣的函數(shù)依賴X→A，

使得F與

F-{X→A}等價(jià)。（3）F中不存在這樣的函數(shù)依賴X→A，X有真子集Z使得F-{X→A}∪{Z→A}與F等價(jià)。即F中的函數(shù)依賴均不能由F中其他函數(shù)依賴導(dǎo)出F中各函數(shù)依賴左部均為最小屬性集（不存在冗余屬性）數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）*定義6.15如果函數(shù)依賴集F滿足下列條件，則稱F為一個(gè)*[例6.12]考察6.1節(jié)中的關(guān)系模式S<U,F>，其中：

U={Sno,Sdept,Mname,Cno,Grade}，

F={Sno→Sdept,Sdept→Mname,(Sno,Cno)→Grade}

F是最小覆蓋

F'={Sno→Sdept,Sno→Mname,Sdept