關(guān)系數(shù)據(jù)理論課件

廈門大學(xué)計(jì)算機(jī)科學(xué)系2016版林子雨廈門大學(xué)計(jì)算機(jī)科學(xué)系E-mail:ziyulin@主頁(yè)：/linziyu

第6章關(guān)系數(shù)據(jù)理論

（2016版）

廈門大學(xué)計(jì)算機(jī)科學(xué)系本科生課程《數(shù)據(jù)庫(kù)系統(tǒng)原理》廈門大學(xué)計(jì)算機(jī)科學(xué)系6.1問題的提出6.2規(guī)范化6.3數(shù)據(jù)依賴的公理系統(tǒng)6.4模式的分解第6章關(guān)系數(shù)據(jù)理論6.1問題的提出第6章關(guān)系數(shù)據(jù)理論關(guān)系數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)針對(duì)具體問題，如何構(gòu)造一個(gè)適合于它的數(shù)據(jù)模式數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)的工具──關(guān)系數(shù)據(jù)庫(kù)的規(guī)范化理論6.1問題的提出關(guān)系數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)6.1問題的提出一、概念回顧二、關(guān)系模式的形式化定義三、什么是數(shù)據(jù)依賴四、關(guān)系模式的簡(jiǎn)化定義五、數(shù)據(jù)依賴對(duì)關(guān)系模式影響6.1問題的提出一、概念回顧6.1問題的提出關(guān)系：描述實(shí)體、屬性、實(shí)體間的聯(lián)系。從形式上看，它是一張二維表，是所涉及屬性的笛卡爾積的一個(gè)子集。關(guān)系模式：用來定義關(guān)系。關(guān)系數(shù)據(jù)庫(kù)：基于關(guān)系模型的數(shù)據(jù)庫(kù)，利用關(guān)系來描述現(xiàn)實(shí)世界。從形式上看，它由一組關(guān)系組成。關(guān)系數(shù)據(jù)庫(kù)的模式：定義這組關(guān)系的關(guān)系模式的全體。6.1問題的提出概念回顧關(guān)系：描述實(shí)體、屬性、實(shí)體間的聯(lián)系。6.1問題的提出概念回關(guān)系模式由五部分組成，即它是一個(gè)五元組：

R(U,D,DOM,F)R：關(guān)系名U：組成該關(guān)系的屬性名集合D：屬性組U中屬性所來自的域DOM：屬性向域的映象集合F：屬性間數(shù)據(jù)的依賴關(guān)系集合6.1問題的提出關(guān)系模式的形式化定義關(guān)系模式由五部分組成，即它是一個(gè)五元組：6.1問題的提出關(guān)1.完整性約束的表現(xiàn)形式限定屬性取值范圍：例如學(xué)生成績(jī)必須在0-100之間定義屬性值間的相互關(guān)連（主要體現(xiàn)于值的相等與否）這就是數(shù)據(jù)依賴，它是數(shù)據(jù)庫(kù)模式設(shè)計(jì)的關(guān)鍵2.數(shù)據(jù)依賴是通過一個(gè)關(guān)系中屬性間值的相等與否體現(xiàn)出來的數(shù)據(jù)間的相互關(guān)系是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象是數(shù)據(jù)內(nèi)在的性質(zhì)是語義的體現(xiàn)3.數(shù)據(jù)依賴的類型函數(shù)依賴（FunctionalDependency，簡(jiǎn)記為FD）多值依賴（MultivaluedDependency，簡(jiǎn)記為MVD）其他6.1問題的提出什么是數(shù)據(jù)依賴1.完整性約束的表現(xiàn)形式6.1問題的提出什么是數(shù)據(jù)依賴關(guān)系模式R（U,D,DOM,F）簡(jiǎ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)系6.1問題的提出關(guān)系模式的簡(jiǎn)化表示關(guān)系模式R（U,D,DOM,F）6.1問題的提出關(guān)系例：描述學(xué)校的數(shù)據(jù)庫(kù)： 學(xué)生的學(xué)號(hào)（Sno）、所在系（Sdept） 系主任姓名（Mname）、課程名（Cname） 成績(jī)（Grade）6.1問題的提出數(shù)據(jù)依賴對(duì)關(guān)系模式的影響｛Sno,Sdept,Mname,Cname,Grade｝單一的關(guān)系模式：Student<U、F>U＝例：描述學(xué)校的數(shù)據(jù)庫(kù)：6.1問題的提出數(shù)據(jù)依賴對(duì)關(guān)系模式的學(xué)校數(shù)據(jù)庫(kù)的語義：⒈一個(gè)系有若干學(xué)生，一個(gè)學(xué)生只屬于一個(gè)系；⒉一個(gè)系只有一名主任；⒊一個(gè)學(xué)生可以選修多門課程，每門課程有若干學(xué)生選修；⒋每個(gè)學(xué)生所學(xué)的每門課程都有一個(gè)成績(jī)。6.1問題的提出數(shù)據(jù)依賴對(duì)關(guān)系模式的影響U＝｛Sno,Sdept,Mname,Cname,Grade｝屬性組U上的一組函數(shù)依賴F：

F＝

｛Sno→Sdept,Sdept→Mname,(Sno,Cname)→Grade｝學(xué)校數(shù)據(jù)庫(kù)的語義：6.1問題的提出數(shù)據(jù)依賴對(duì)關(guān)系模式的影響6.1問題的提出數(shù)據(jù)依賴對(duì)關(guān)系模式的影響

SnoCnameSdeptMnameGrade6.1問題的提出數(shù)據(jù)依賴對(duì)關(guān)系模式的影響SnoCname6.1問題的提出關(guān)系模式Student<U,F>中存在的問題學(xué)號(hào)Sno系主任Mname課程名Cname成績(jī)Grade所在系Sdept95001李勇高數(shù)80IS95002李勇高數(shù)73IS95003王敏

高數(shù)91MA95004李勇外語67IS6.1問題的提出關(guān)系模式Student<U,F>中存在的6.1問題的提出關(guān)系模式Student<U,F>中存在的問題⒈數(shù)據(jù)冗余太大浪費(fèi)大量的存儲(chǔ)空間例：每一個(gè)系主任的姓名重復(fù)出現(xiàn)⒉更新異常（UpdateAnomalies）數(shù)據(jù)冗余，更新數(shù)據(jù)時(shí)，維護(hù)數(shù)據(jù)完整性代價(jià)大。 例：某系更換系主任后，系統(tǒng)必須修改與該系學(xué)生有關(guān)的每一個(gè)元組⒊插入異常（InsertionAnomalies）該插的數(shù)據(jù)插不進(jìn)去例，如果一個(gè)系剛成立，尚無學(xué)生，我們就無法把這個(gè)系及其系主任的信息存入數(shù)據(jù)庫(kù)。⒋刪除異常（DeletionAnomalies）不該刪除的數(shù)據(jù)不得不刪 例，如果某個(gè)系的學(xué)生全部畢業(yè)了，我們?cè)趧h除該系學(xué)生信息的同時(shí)，把這個(gè)系及其系主任的信息也丟掉了。6.1問題的提出關(guān)系模式Student<U,F>中存在的6.1問題的提出結(jié)論：Student關(guān)系模式不是一個(gè)好的模式。“好”的模式：不會(huì)發(fā)生插入異常、刪除異常、更新異常，數(shù)據(jù)冗余應(yīng)盡可能少。原因：由存在于模式中的某些數(shù)據(jù)依賴引起的解決方法：通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴。數(shù)據(jù)依賴對(duì)關(guān)系模式的影響6.1問題的提出結(jié)論：數(shù)據(jù)依賴對(duì)關(guān)系模式的影響6.1問題的提出6.2規(guī)范化6.3數(shù)據(jù)依賴的公理系統(tǒng)6.4模式的分解第6章關(guān)系數(shù)據(jù)理論6.1問題的提出第6章關(guān)系數(shù)據(jù)理論6.2規(guī)范化

規(guī)范化理論正是用來改造關(guān)系模式，通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問題。6.2規(guī)范化6.2.1函數(shù)依賴一、函數(shù)依賴二、平凡函數(shù)依賴與非平凡函數(shù)依賴三、完全函數(shù)依賴與部分函數(shù)依賴四、傳遞函數(shù)依賴6.2.1函數(shù)依賴一、函數(shù)依賴6.2.1函數(shù)依賴定義6.1設(shè)R(U)是一個(gè)屬性集U上的關(guān)系模式，X和Y是U的子集。若對(duì)于R(U)的任意一個(gè)可能的關(guān)系r，r中不可能存在兩個(gè)元組在X上的屬性值相等，而在Y上的屬性值不等，則稱“X函數(shù)確定Y”

或“Y函數(shù)依賴于X”，記作X→Y。

X稱為這個(gè)函數(shù)依賴的決定屬性集(Determinant)。

Y=f(x)一、函數(shù)依賴6.2.1函數(shù)依賴定義6.1設(shè)R(U)是一個(gè)屬性集U6.2.1函數(shù)依賴

1.函數(shù)依賴不是指關(guān)系模式R的某個(gè)或某些關(guān)系實(shí)例滿足的約束條件，而是指R的所有關(guān)系實(shí)例均要滿足的約束條件。2.函數(shù)依賴是語義范疇的概念。只能根據(jù)數(shù)據(jù)的語義來確定函數(shù)依賴。例如“姓名→年齡”這個(gè)函數(shù)依賴只有在不允許有同名人的條件下成立3.數(shù)據(jù)庫(kù)設(shè)計(jì)者可以對(duì)現(xiàn)實(shí)世界作強(qiáng)制的規(guī)定。例如規(guī)定不允許同名人出現(xiàn)，函數(shù)依賴“姓名→年齡”成立。所插入的元組必須滿足規(guī)定的函數(shù)依賴，若發(fā)現(xiàn)有同名人存在，則拒絕裝入該元組。說明：6.2.1函數(shù)依賴1.函數(shù)依賴不是指關(guān)系模式R的某個(gè)或例: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,則記為X→Y。6.2.1函數(shù)依賴?yán)?Student(Sno,Sname,Ssex,S6.2.1函數(shù)依賴在關(guān)系模式R(U)中，對(duì)于U的子集X和Y，如果X→Y，但YX，則稱X→Y是非平凡的函數(shù)依賴若X→Y，但YX,則稱X→Y是平凡的函數(shù)依賴?yán)涸陉P(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.1函數(shù)依賴在關(guān)系模式R(U)中，對(duì)于U的子集X和Y6.2.1函數(shù)依賴定義6.2在關(guān)系模式R(U)中，如果X→Y，并且對(duì)于X的任何一個(gè)真子集X'，都有X'Y,則稱Y完全函數(shù)依賴于X，記作Xｆ

Y。若X→Y，但Y不完全函數(shù)依賴于X，則稱Y部分函數(shù)依賴于X，記作XPY。

三、完全函數(shù)依賴與部分函數(shù)依賴?yán)?在關(guān)系SC(Sno,Cno,Grade)中，由于：Sno→Grade，Cno→Grade，因此：(Sno,Cno)ｆGrade

6.2.1函數(shù)依賴定義6.2在關(guān)系模式R(U)中，如果6.2.2碼定義6.4設(shè)K為關(guān)系模式R<U,F>中的屬性或?qū)傩越M合。若KｆU，則K稱為R的一個(gè)侯選碼（CandidateKey）。若關(guān)系模式R有多個(gè)候選碼，則選定其中的一個(gè)做為主碼（Primarykey）。主屬性與非主屬性ALLKEY6.2.2碼定義6.4設(shè)K為關(guān)系模式R<U,F>中的屬6.2.2碼外部碼定義6.5關(guān)系模式R中屬性或?qū)傩越MX并非R的碼，但X是另一個(gè)關(guān)系模式的碼，則稱X是R的外部碼（Foreignkey）也稱外碼。主碼又和外部碼一起提供了表示關(guān)系間聯(lián)系的手段。6.2.2碼外部碼6.2.3范式范式是符合某一種級(jí)別的關(guān)系模式的集合。關(guān)系數(shù)據(jù)庫(kù)中的關(guān)系必須滿足一定的要求。滿足不同程度要求的為不同范式。范式的種類：

第一范式(1NF)

第二范式(2NF)

第三范式(3NF) BC范式(BCNF)

第四范式(4NF)

第五范式(5NF)6.2.3范式范式是符合某一種級(jí)別的關(guān)系模式的集合。6.2.3范式各種范式之間存在聯(lián)系：某一關(guān)系模式R為第n范式，可簡(jiǎn)記為R∈nNF。6.2.3范式各種范式之間存在聯(lián)系：6.2.42NF1NF的定義 如果一個(gè)關(guān)系模式R的所有屬性都是不可分的基本數(shù)據(jù)項(xiàng)，則R∈1NF。第一范式是對(duì)關(guān)系模式的最起碼的要求。不滿足第一范式的數(shù)據(jù)庫(kù)模式不能稱為關(guān)系數(shù)據(jù)庫(kù)。但是滿足第一范式的關(guān)系模式并不一定是一個(gè)好的關(guān)系模式。6.2.42NF1NF的定義6.2.42NF例:關(guān)系模式SLC(Sno,Sdept,Sloc,Cno,Grade)Sloc為學(xué)生住處，假設(shè)每個(gè)系的學(xué)生住在同一個(gè)地方。函數(shù)依賴包括：

(Sno,Cno)

GradeSnoSdept(Sno,Cno)Sdept(?)SnoSloc(Sno,Cno)

SlocSdeptSloc→f→→p→→p→6.2.42NF例:關(guān)系模式SLC(Sno,S6.2.42NF例:關(guān)系模式SLC(Sno,Sdept,Sloc,Cno,Grade)Sloc為學(xué)生住處，假設(shè)每個(gè)系的學(xué)生住在同一個(gè)地方。函數(shù)依賴包括：

(Sno,Cno)

GradeSnoSdept(Sno,Cno)SdeptSnoSloc(Sno,Cno)

SlocSdeptSloc→f→→p→→p→6.2.42NF例:關(guān)系模式SLC(Sno,S6.2.42NFSLC的碼為(Sno,Cno)SLC滿足第一范式非主屬性Sdept和Sloc部分函數(shù)依賴于碼(Sno,Cno)SnoCnoGradeSdeptSlocSLC6.2.42NFSLC的碼為(Sno,Cno)SnoC課堂練習(xí)已知學(xué)生關(guān)系模式S(Sno,Sname,SD,Sdname,Course,Grade)其中，Sno是學(xué)號(hào)，Sname是姓名，SD是系名，Sdname是系主任名，Course是課程，Grade是成績(jī)（1）寫出關(guān)系模式S的基本函數(shù)依賴和主碼；（做本題）（2）原關(guān)系模式是第幾范式？如何分解成高一級(jí)范式？（3）將關(guān)系模式分解成3NF，并說明為什么？課堂練習(xí)已知學(xué)生關(guān)系模式6.2.42NFSLC不是一個(gè)好的關(guān)系模式(1)插入異常 假設(shè)Sno＝95102，Sdept＝IS，Sloc＝N的學(xué)生還未選課，因課程號(hào)是主屬性，因此該學(xué)生的信息無法插入SLC。(2)刪除異常假定某個(gè)學(xué)生本來只選修了3號(hào)課程這一門課?，F(xiàn)在因身體不適，他連3號(hào)課程也不選修了。因課程號(hào)是主屬性，此操作將導(dǎo)致該學(xué)生信息的整個(gè)元組都要?jiǎng)h除。SLC(Sno,Sdept,Sloc,Cno,Grade)6.2.42NFSLC不是一個(gè)好的關(guān)系模式SLC(Sno6.2.42NF(3)數(shù)據(jù)冗余度大如果一個(gè)學(xué)生選修了10門課程，那么他的Sdept和Sloc值就要重復(fù)存儲(chǔ)了10次。(4)修改復(fù)雜例如學(xué)生轉(zhuǎn)系，在修改此學(xué)生元組的Sdept值的同時(shí)，還可能需要修改住處（Sloc）。如果這個(gè)學(xué)生選修了K門課，則必須無遺漏地修改K個(gè)元組中全部Sdept、Sloc信息。SLC(Sno,Sdept,Sloc,Cno,Grade)6.2.42NF(3)數(shù)據(jù)冗余度大SLC(Sno,S6.2.42NF原因

Sdept、Sloc部分函數(shù)依賴于碼。解決方法

SLC分解為兩個(gè)關(guān)系模式，以消除這些部分函數(shù)依賴

SC（Sno，Cno，Grade）

SL（Sno，Sdept，Sloc）6.2.42NF原因6.2.42NF函數(shù)依賴圖：SnoCnoGradeSCSLSnoSdeptSloc1NF2NF6.2.42NF函數(shù)依賴圖：SnoCnoGradeSCS6.2.42NF采用投影分解法將一個(gè)1NF的關(guān)系分解為多個(gè)2NF的關(guān)系，可以在一定程度上減輕原1NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問題。將一個(gè)1NF關(guān)系分解為多個(gè)2NF的關(guān)系，并不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。6.2.42NF采用投影分解法將一個(gè)1NF的關(guān)系分解為多6.2.42NF2NF的定義 定義6.6若關(guān)系模式R∈1NF，并且每一個(gè)非主屬性都完全函數(shù)依賴于R的碼，則R∈2NF。 例：SLC(Sno,Sdept,Sloc,Cno,Grade)∈1NFSLC(Sno,Sdept,Sloc,Cno,Grade)∈2NF SC（Sno，Cno，Grade）∈2NFSL（Sno，Sdept，Sloc）∈2NFSnoCnoGradeSC6.2.42NF2NF的定義SnoCnoGradeSC課堂練習(xí)已知學(xué)生關(guān)系模式S(Sno,Sname,SD,Sdname,Course,Grade)其中，Sno是學(xué)號(hào)，Sname是姓名，SD是系名，Sdname是系主任名，Course是課程，Grade是成績(jī)（1）寫出關(guān)系模式S的基本函數(shù)依賴和主碼；（2）原關(guān)系模式是第幾范式？如何分解成高一級(jí)范式？（做本題）（3）將關(guān)系模式分解成3NF，并說明為什么？課堂練習(xí)已知學(xué)生關(guān)系模式6.2.42NF定義6.3在關(guān)系模式R(U)中，如果X→Y，Y→Z，且YX，Y→X，則稱Z傳遞函數(shù)依賴于X。注:如果Y→X，即X←→Y，則Z直接依賴于X。例:在關(guān)系Std(Sno,Sdept,Mname)中，有：

Sno→Sdept，Sdept→MnameMname傳遞函數(shù)依賴于Sno四、傳遞函數(shù)依賴6.2.42NF定義6.3在關(guān)系模式R(U)中，如果6.2.53NF例：2NF關(guān)系模式SL(Sno,Sdept,Sloc)中函數(shù)依賴：

Sno→SdeptSdept→SlocSno→Sloc Sloc傳遞函數(shù)依賴于Sno，即SL中存在非主屬性對(duì)碼的傳遞函數(shù)依賴。SLSnoSdeptSloc6.2.53NF例：2NF關(guān)系模式SL(Sno,Sd6.2.53NF解決方法采用投影分解法，把SL分解為兩個(gè)關(guān)系模式，以消除傳遞函數(shù)依賴：SD（Sno，Sdept）

DL（Sdept，Sloc）SD的碼為Sno，DL的碼為Sdept。6.2.53NF解決方法6.2.53NFSD的碼為Sno，DL的碼為Sdept。SnoSdeptSDSdeptSlocDL2NF3NF6.2.53NFSD的碼為Sno，DL的碼為Sdep6.2.53NF3NF的定義 定義6.8關(guān)系模式R<U，F(xiàn)>

中若不存在這樣的碼X、屬性組Y及非主屬性Z（ZY）,使得X→Y，Y→X，Y→Z，成立，則稱R<U，F(xiàn)>∈3NF。例，SL(Sno,Sdept,Sloc)∈2NFSL(Sno,Sdept,Sloc)∈3NFSD（Sno，Sdept）∈3NFDL（Sdept，Sloc）∈3NF6.2.53NF3NF的定義6.2.53NF若R∈3NF，則R的每一個(gè)非主屬性既不部分函數(shù)依賴于候選碼也不傳遞函數(shù)依賴于候選碼。如果R∈3NF，則R也是2NF。采用投影分解法將一個(gè)2NF的關(guān)系分解為多個(gè)3NF的關(guān)系，可以在一定程度上解決原2NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問題。將一個(gè)2NF關(guān)系分解為多個(gè)3NF的關(guān)系后，并不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。6.2.53NF若R∈3NF，則R的每一個(gè)非主屬性既不課堂練習(xí)已知學(xué)生關(guān)系模式S(Sno,Sname,SD,Sdname,Course,Grade)其中，Sno是學(xué)號(hào)，Sname是姓名，SD是系名，Sdname是系主任名，Course是課程，Grade是成績(jī)（1）寫出關(guān)系模式S的基本函數(shù)依賴和主碼；（2）原關(guān)系模式是第幾范式？如何分解成高一級(jí)范式？（3）將關(guān)系模式分解成3NF，并說明為什么？（做本題）課堂練習(xí)已知學(xué)生關(guān)系模式6.2.6BCNF定義6.9設(shè)關(guān)系模式R<U，F(xiàn)>∈1NF，如果對(duì)于R的每個(gè)函數(shù)依賴X→Y，若Y不屬于X，則X必含有碼，那么R∈BCNF。若R∈BCNF每一個(gè)決定屬性集（因素）都包含（候選）碼R中的所有屬性（主，非主屬性）都完全函數(shù)依賴于碼沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性R∈3NF(?)若R∈3NF則R不一定∈BCNF即在第三范式的基礎(chǔ)上，數(shù)據(jù)庫(kù)表中不存在任何屬性對(duì)任一候選碼的傳遞函數(shù)依賴和部分函數(shù)依賴6.2.6BCNF定義6.9設(shè)關(guān)系模式R<U，F(xiàn)6.2.6BCNF證明題：若關(guān)系模式R∈BCNF，則R∈2NF。6.2.6BCNF證明題：若關(guān)系模式R∈BCNF，則R∈6.2.6BCNF例子：關(guān)系模式C(Cno,Cname,Pcno)，它只有一個(gè)碼Cno，這里沒有任何屬性對(duì)Cno部分依賴或傳遞依賴，所以，C∈3NF同時(shí)，C中Cno是唯一的決定因素，C同時(shí)又是碼，根據(jù)定義，C∈BCNF6.2.6BCNF例子：關(guān)系模式C(Cno,Cname6.2.6BCNF例子：關(guān)系模式SJP（S,J,P）中，S是學(xué)生，J表示課程，P表示名次，每一個(gè)學(xué)生選修每門課程的成績(jī)有一定的名次，每門課程中每一名次只有一個(gè)學(xué)生（即沒有并列名次），可以得到以下依賴：（S，J）→P;(J,P)→S所以(S,J)和(J,P)都可以作為候選碼，這個(gè)關(guān)系模式中沒有屬性對(duì)碼傳遞依賴或部分依賴，所以，SJP∈3NF，而且除(S,J)和(J,P)以外沒有其他決定因素，所以SJP∈BCNF6.2.6BCNF例子：關(guān)系模式SJP（S,J,P）中6.2.6BCNF例：在關(guān)系模式STJ（S，T，J）中，S表示學(xué)生，T表示教師，J表示課程。每一教師只教一門課。每門課由若干教師教，某一學(xué)生選定某門課，就確定了一個(gè)固定的教師。某個(gè)學(xué)生選修某個(gè)教師的課就確定了所選課的名稱：

T→J，(S，J)→T，(S，T)→J6.2.6BCNF例：在關(guān)系模式STJ（S，T，J）中6.2.6BCNF

SJTSTJSTJ6.2.6BCNFSJTSTJSTJ6.2.6BCNFSTJ∈3NF

(S，J)和(S，T)都可以作為候選碼

S、T、J都是主屬性STJ∈BCNFT→J，T是決定屬性集，T不是候選碼6.2.6BCNFSTJ∈3NF

T→J，T是決定屬性6.2.6BCNF

解決方法：將STJ分解為二個(gè)關(guān)系模式：

SJ(S，J)∈BCNF，TJ(T，J)∈BCNF

沒有任何屬性對(duì)碼的部分函數(shù)依賴和傳遞函數(shù)依賴SJSTTJTJ6.2.6BCNF 解決方法：將STJ分解為二個(gè)關(guān)系模課堂作業(yè)有一個(gè)配件管理表WPE(WNO,PNO,ENO,QNT)，其中，WNO表示倉(cāng)庫(kù)號(hào)，PNO表示配件號(hào)，ENO表示職工號(hào)，QNT表示數(shù)量。有以下約束要求：（1）一個(gè)倉(cāng)庫(kù)有多名職工（2）一個(gè)職工僅在一個(gè)倉(cāng)庫(kù)工作（3）每個(gè)倉(cāng)庫(kù)里一種型號(hào)的配件由一個(gè)職工負(fù)責(zé)，但一個(gè)人可以管理幾種配件；（4）同一個(gè)型號(hào)的配件可以分別放在幾個(gè)倉(cāng)庫(kù)中（5）一個(gè)倉(cāng)庫(kù)存儲(chǔ)某種配件的數(shù)量是一定的（6）一個(gè)職工管理某種配件的數(shù)量是一定的問題：（1）請(qǐng)寫出表中的函數(shù)依賴關(guān)系（2）判斷該表是否是3NF？（3）判斷該表是否是BCNF？課堂作業(yè)有一個(gè)配件管理表課堂作業(yè)答案函數(shù)依賴關(guān)系：ENO→WNO(WNO,PNO)→QNT(WNO,PNO)→ENO(ENO,PNO)→QNT課堂作業(yè)答案函數(shù)依賴關(guān)系：課堂作業(yè)答案候選碼包括：(WNO,PNO)和(ENO,PNO)ENO,PNO,WNO都是主屬性，QNT是非主屬性所有非主屬性都是直接依賴于候選碼，因此是3NF關(guān)于主屬性：(WNO,PNO)→ENO；ENO→WNO，得到傳遞依賴(WNO,PNO)→WNO，所以不是BCNF課堂作業(yè)答案候選碼包括：(WNO,PNO)和(ENO,PN課堂作業(yè)答案可以繼續(xù)分拆成兩個(gè)表管理表EP（ENO,PNO,QNT）工作表EW（ENO,WNO）兩個(gè)表屬于BCNF課堂作業(yè)答案可以繼續(xù)分拆成兩個(gè)表多值依賴與第四范式（4NF）例:學(xué)校中某一門課程由多個(gè)教師講授，他們使用相同的一套參考書。每個(gè)教師可以講多門課程，每種參考書可供多門課使用。 關(guān)系模式Teaching(C,T,B)

課程C、教師T和參考書B多值依賴與第四范式（4NF）例:學(xué)校中某一門課程由多個(gè)教師表6.1表6.1普通物理學(xué)光學(xué)原理物理習(xí)題集普通物理學(xué)光學(xué)原理物理習(xí)題集數(shù)學(xué)分析微分方程高等代數(shù)數(shù)學(xué)分析微分方程高等代數(shù)…李勇李勇李勇王軍王軍王軍李勇李勇李勇張平張平張平

…物理物理物理物理物理物理數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)

…參考書B教員T課程C用二維表表示Teaching

普通物理學(xué)李勇物理參考書B教員T課程C用二維表表示Tea多值依賴與第四范式（續(xù)）Teaching∈BCNF:Teach具有唯一候選碼(C，T，B)，即全碼Teaching模式中存在的問題

(1)數(shù)據(jù)冗余度大：有多少名任課教師，參考書就要存儲(chǔ)多少次(2)插入操作復(fù)雜：當(dāng)某一課程增加一名任課教師時(shí)，該課程有多少本參照書，就必須插入多少個(gè)元組例如物理課增加一名教師劉關(guān)，需要插入兩個(gè)元組：（物理，劉關(guān)，普通物理學(xué)）（物理，劉關(guān)，光學(xué)原理）多值依賴與第四范式（續(xù)）Teaching∈BCNF:多值依賴與第四范式（續(xù)）(3)刪除操作復(fù)雜：某一門課要去掉一本參考書，該課程有多少名教師，就必須刪除多少個(gè)元組(4)修改操作復(fù)雜：某一門課要修改一本參考書，該課程有多少名教師，就必須修改多少個(gè)元組產(chǎn)生原因 存在多值依賴多值依賴與第四范式（續(xù)）(3)刪除操作復(fù)雜：某一門課要去掉6.2.7多值依賴定義6.10

設(shè)R(U)是一個(gè)屬性集U上的一個(gè)關(guān)系模式，X、Y和Z是U的子集，并且Z＝U－X－Y，多值依賴X→→Y成立當(dāng)且僅當(dāng)對(duì)R的任一關(guān)系r，r在（X，Z）上的每個(gè)值對(duì)應(yīng)一組Y的值，這組值僅僅決定于X值而與Z值無關(guān) 例Teaching（C,T,B）

對(duì)于C的每一個(gè)值，B有一組值與之對(duì)應(yīng)，而不論T取何值6.2.7多值依賴定義6.106.2.7多值依賴在R（U）的任一關(guān)系r中，如果存在元組t，s使得t[X]=s[X]，那么就必然存在元組w，vr，（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。6.2.7多值依賴在R（U）的任一關(guān)系r中，如果存在元組t6.2.7多值依賴txy1z2sxy2z1wxy1z1vxy2z26.2.7多值依賴t6.2.7多值依賴平凡多值依賴和非平凡的多值依賴

若X→→Y，而Z＝φ，則稱

X→→Y為平凡的多值依賴 否則稱X→→Y為非平凡的多值依賴6.2.7多值依賴平凡多值依賴和非平凡的多值依賴6.2.84NF定義6.10關(guān)系模式R<U，F(xiàn)>∈1NF，如果對(duì)于R的每個(gè)非平凡多值依賴X→→Y（YX），X都含有候選碼，則R∈4NF。

如果R∈4NF，則R∈BCNF

不允許有非平凡且非函數(shù)依賴的多值依賴

允許的是函數(shù)依賴（是非平凡多值依賴）6.2.84NF定義6.10關(guān)系模式R<U，F(xiàn)>∈16.2.84NF例：Teach(C,T,B)∈4NF存在非平凡的多值依賴C→→T，且C不是候選碼用投影分解法把Teach分解為如下兩個(gè)關(guān)系模式：

CT(C,T)∈4NF CB(C,B)∈4NF

C→→T，C→→B是平凡多值依賴6.2.84NF例：Teach(C,T,B)∈4NF6.2.9規(guī)范化關(guān)系數(shù)據(jù)庫(kù)的規(guī)范化理論是數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)的工具。一個(gè)關(guān)系只要其分量都是不可分的數(shù)據(jù)項(xiàng)，它就是規(guī)范化的關(guān)系，但這只是最基本的規(guī)范化。規(guī)范化程度可以有多個(gè)不同的級(jí)別6.2.9規(guī)范化關(guān)系數(shù)據(jù)庫(kù)的規(guī)范化理論是數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)的工6.2.9規(guī)范化規(guī)范化程度過低的關(guān)系不一定能夠很好地描述現(xiàn)實(shí)世界，可能會(huì)存在插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問題一個(gè)低一級(jí)范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換為若干個(gè)高一級(jí)范式的關(guān)系模式集合，這種過程就叫關(guān)系模式的規(guī)范化6.2.9規(guī)范化規(guī)范化程度過低的關(guān)系不一定能夠很好地描述現(xiàn)6.2.9規(guī)范化關(guān)系模式規(guī)范化的基本步驟

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

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

4NF6.2.9規(guī)范化關(guān)系模式規(guī)范化的基本步驟6.2.9規(guī)范化消除不合適的數(shù)據(jù)依賴將各關(guān)系模式達(dá)到某種程度的“分離”采用“一事一地”的模式設(shè)計(jì)原則讓一個(gè)關(guān)系描述一個(gè)概念、一個(gè)實(shí)體或者實(shí)體間的一種聯(lián)系。若多于一個(gè)概念就把它“分離”出去所謂規(guī)范化實(shí)質(zhì)上是概念的單一化不能一味追求規(guī)范化程度高規(guī)范化的基本思想6.2.9規(guī)范化消除不合適的數(shù)據(jù)依賴規(guī)范化的基本思想6.2.9規(guī)范化在設(shè)計(jì)數(shù)據(jù)庫(kù)模式結(jié)構(gòu)時(shí)，必須對(duì)現(xiàn)實(shí)世界的實(shí)際情況和用戶應(yīng)用需求作進(jìn)一步分析，確定一個(gè)合適的、能夠反映現(xiàn)實(shí)世界的模式上面的規(guī)范化步驟可以在其中任何一步終止6.2.9規(guī)范化在設(shè)計(jì)數(shù)據(jù)庫(kù)模式結(jié)構(gòu)時(shí)，必須對(duì)現(xiàn)實(shí)世界的實(shí)第六章關(guān)系數(shù)據(jù)理論6.1數(shù)據(jù)依賴6.2規(guī)范化6.3數(shù)據(jù)依賴的公理系統(tǒng)6.4模式的分解第六章關(guān)系數(shù)據(jù)理論6.1數(shù)據(jù)依賴6.3數(shù)據(jù)依賴的公理系統(tǒng)邏輯蘊(yùn)含

定義6.11對(duì)于滿足一組函數(shù)依賴F的關(guān)系模式R<U，F(xiàn)>，函數(shù)依賴X→Y都成立,即r中任意兩元組t,s，若t[X]=s[X]，則t[Y]=s[Y]，則稱F邏輯蘊(yùn)含X→Y6.3數(shù)據(jù)依賴的公理系統(tǒng)邏輯蘊(yùn)含Armstrong公理系統(tǒng)一套推理規(guī)則，是模式分解算法的理論基礎(chǔ)用途求給定關(guān)系模式的碼從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴Armstrong公理系統(tǒng)一套推理規(guī)則，是模式分解算法的理論1.Armstrong公理系統(tǒng)

關(guān)系模式R<U，F(xiàn)>來說有以下的推理規(guī)則：

A1.自反律（Reflexivity）：

若Y

X

U，則X→Y為F所蘊(yùn)含。A2.增廣律（Augmentation）：

若X→Y為F所蘊(yùn)含，且ZU，則XZ→YZ為F所蘊(yùn)含。A3.傳遞律（Transitivity）：

若X→Y及Y→Z為F所蘊(yùn)含，則X→Z為F所蘊(yùn)含。1.Armstrong公理系統(tǒng)關(guān)系模式R<U，F(xiàn)定理6.lArmstrong推理規(guī)則是正確的（1）自反律:若Y

X

U，則X→Y為F所蘊(yùn)含證:設(shè)Y

X

U

對(duì)R<U，F(xiàn)>

的任一關(guān)系r中的任意兩個(gè)元組t，s：若t[X]=s[X]，由于Y

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

自反律得證定理6.lArmstrong推理規(guī)則是正確的定理6.lArmstrong推理規(guī)則是正確的（1）自反律定理6.l(2)增廣律:若X→Y為F所蘊(yùn)含，且Z

U，則XZ→YZ為F所蘊(yùn)含。證：設(shè)X→Y為F所蘊(yùn)含，且Z

U。設(shè)R<U，F(xiàn)>

的任一關(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)含.增廣律得證。定理6.l(2)增廣律:若X→Y為F所蘊(yùn)含，且Z定理6.l(3)傳遞律：若X→Y及Y→Z為F所蘊(yùn)含，則X→Z為F所蘊(yùn)含。證：設(shè)X→Y及Y→Z為F所蘊(yùn)含。對(duì)R<U，F(xiàn)>

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

合并規(guī)則：由X→Y，X→Z，有X→YZ。（A2，A3）

偽傳遞規(guī)則：由X→Y，WY→Z，有XW→Z。（A2，A3）

分解規(guī)則：由X→Y及ZY，有X→Z。（A1，A3）2.導(dǎo)出規(guī)則1.根據(jù)A1，A2，A3這三條推理規(guī)則可以得到導(dǎo)出規(guī)則2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理6.1

引理6.lX→A1A2…Ak成立的充分必要條件是X→Ai成立（i=l，2，…，k）。導(dǎo)出規(guī)則2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理6.13.函數(shù)依賴閉包定義6.12在關(guān)系模式R<U，F(xiàn)>中為F所邏輯蘊(yùn)含的函數(shù)依賴的全體叫作F的閉包，記為F+。3.函數(shù)依賴閉包定義6.12在關(guān)系模式R<U，F(xiàn)>3.函數(shù)依賴閉包人們把自反律、傳遞律和增廣律稱為Armstrong公理系統(tǒng)3.函數(shù)依賴閉包人們把自反律、傳遞律和增廣律稱為ArmstArmstrong公理系統(tǒng)有效性：由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來的每一個(gè)函數(shù)依賴一定在F+中

/*Armstrong正確完備性：F+中的每一個(gè)函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來

/*Armstrong公理夠用，完全Armstrong公理系統(tǒng)有效性：由F出發(fā)根據(jù)ArmstroArmstrong公理系統(tǒng)要證明完備性，就首先要解決如何判定一個(gè)函數(shù)依賴是否屬于由F根據(jù)Armstrong公理系統(tǒng)推導(dǎo)出來的函數(shù)依賴的集合如果能夠求出這個(gè)集合，問題就解決了但是，這個(gè)是一個(gè)NP完全問題Armstrong公理系統(tǒng)要證明完備性，就首先要解決如何判定F的閉包,F+計(jì)算是NP完全問題，XA1A2...An

F+={Xφ,Yφ,Zφ,XYφ,XZφ,YZφ,XYZφ,XX,YY,ZZ,XYX,XZX,YZY,XYZX,XY,YZ,XYY,XZY,YZZ,XYZY,XZ,YYZ,XYZ,XZZ,YZYZ,XYZZ,XXY,XYXY,XZXY,XYZXY,XXZ,XYYZ,XZXZ,XYZYZXYZ,XYXZ,XZXY,XYZXZ,XZYZ,XYXYZ,XZXYZ,XYZXYZ}F={XY,YZ}F的閉包,F3.函數(shù)依賴閉包定義6.13設(shè)F為屬性集U上的一組函數(shù)依賴，X

U，XF+={A\X→A能由F根據(jù)Armstrong公理導(dǎo)出}，XF+稱為屬性集X關(guān)于函數(shù)依賴集F的閉包為了證明Armstrong公理系統(tǒng)完備性，需要引入以下概念：3.函數(shù)依賴閉包定義6.13設(shè)F為屬性集U上的一組函關(guān)于閉包的引理引理6.2

設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y

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

XF+用途

將判定X→Y是否能由F根據(jù)Armstrong公理導(dǎo)出的問題，就轉(zhuǎn)化為求出XF+

，判定Y是否為XF+的子集的問題（不再是NP完全問題）根據(jù)引理6.1可以進(jìn)一步得到：關(guān)于閉包的引理引理6.2

設(shè)F為屬性集U上的一組函數(shù)依賴

U={A,B,C,D};F={AB,BCD};A+=C+=(AC)+=實(shí)例AB.C.ABCDU={A,B,C,D};F={AB,B求閉包的算法算法6.l求屬性集X（X

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

輸入：X，F(xiàn)輸出：XF+步驟：求閉包的算法算法6.l求屬性集X（XU）關(guān)于U上的算法6.l（1）令X（0）=X，i=0（2）求B，這里B={A|(

V)(

W)(V→WF

∧VX（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（1）令X（0）=X，i=0算法6.l對(duì)于算法6.l，令ai=|X（i）|，{ai

}形成一個(gè)步長(zhǎng)大于1的嚴(yán)格遞增的序列，序列的上界是|U|，因此該算法最多|U|-|X|次循環(huán)就會(huì)終止。算法6.l對(duì)于算法6.l，令ai=|X（i）|，{ai函數(shù)依賴閉包[例1]已知關(guān)系模式R<U，F(xiàn)>，其中

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

F={AB→C，B→D，C→E，EC→B，AC→B}。求（AB）F+

。解設(shè)X（0）=AB；(1)計(jì)算X（1）:逐一的掃描F集合中各個(gè)函數(shù)依賴，找左部為A，B或AB的函數(shù)依賴。得到兩個(gè)：AB→C，B→D。于是X（1）=AB∪CD=ABCD。函數(shù)依賴閉包[例1]已知關(guān)系模式R<U，F(xiàn)>，其中

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

課堂練習(xí)例：設(shè)有關(guān)系模式R(U,F)，其中4.Armstrong公理系統(tǒng)的有效性與完備性建立公理系統(tǒng)體系目的：從已知的

f

推導(dǎo)出未知的f明確：1.公理系統(tǒng)推導(dǎo)出來的f正確？2.F+中的每一個(gè)f都能推導(dǎo)出來？f不能由F導(dǎo)出,f∈F+

F+fF4.Armstrong公理系統(tǒng)的有效性與完備性建立公理系統(tǒng)4.Armstrong公理系統(tǒng)的有效性與完備性有效性：由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來的每一個(gè)函數(shù)依賴一定在F+中

/*Armstrong正確完備性：F+中的每一個(gè)函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來

/*Armstrong公理夠用，完全完備性：所有不能用Armstrong公理推導(dǎo)出來f,都不為真

若

f不能用Armstrong公理推導(dǎo)出來，

f∈F+4.Armstrong公理系統(tǒng)的有效性與完備性有效性：由F有效性與完備性的證明證明： 有效性根據(jù)定理6.1可以得證定理6.lArmstrong推理規(guī)則是正確的Armstrong公理系統(tǒng)推理規(guī)則

關(guān)系模式R<U，F(xiàn)>來說有以下的推理規(guī)則：

A1.自反律（Reflexivity）：

若Y

X

U，則X→Y為F所蘊(yùn)含。A2.增廣律（Augmentation）：

若X→Y為F所蘊(yùn)含，且ZU，則XZ→YZ為F所蘊(yùn)含。A3.傳遞律（Transitivity）：

若X→Y及Y→Z為F所蘊(yùn)含，則X→Z為F所蘊(yùn)含。有效性與完備性的證明證明： 定理6.lArmstrong有效性與完備性的證明證明：2.完備性

要證明的題目：F+中的每一個(gè)函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來 只需證明逆否命題:

若函數(shù)依賴X→Y不能由F從Armstrong公理導(dǎo)出，那么它必然不為F所蘊(yùn)含分三步證明：有效性與完備性的證明證明：有效性與完備性的證明(1)引理:若V→W成立，且V

XF+，則W

XF+

證因?yàn)閂

XF+，所以有X→V成立；（？）因?yàn)閄→V，V→W，于是X→W成立所以W

XF+(2)構(gòu)造一張二維表r，它由下列兩個(gè)元組構(gòu)成

可以證明r必是R（U，F(xiàn)）的一個(gè)關(guān)系，即F+中的全部函數(shù)依賴在r上成立。引理6.2

設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y

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

XF+有效性與完備性的證明(1)引理:若V→W成立，且VXArmstrong公理系統(tǒng)的有效性與完備性(續(xù)) XF+

U-XF+

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

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

若r不是R<U，F(xiàn)>的關(guān)系，則必由于F中有函數(shù)依賴V→W在r上不成立所致。由r的構(gòu)成可知，V必定是XF+的子集，而W不是XF+的子集，可是由第（1）步，W

XF+，矛盾。所以r必是R<U，F(xiàn)>的一個(gè)關(guān)系。Armstrong公理系統(tǒng)的有效性與完備性(續(xù)) Armstrong公理系統(tǒng)的有效性與完備性(續(xù))(3)若X→Y不能由F從Armstrong公理導(dǎo)出，則Y不是XF+的子集。（引理6.2）因此必有Y的子集Y’

滿足Y’U-XF+，則X→Y在r中不成立，即X→Y必不為R<U，F(xiàn)>蘊(yùn)含

/*因?yàn)?/p>

F+中的全部函數(shù)依賴在r上成立。引理6.2

設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y

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

XF+Armstrong公理系統(tǒng)的有效性與完備性(續(xù))(3)若X5.函數(shù)依賴集等價(jià)

定義6.14如果G+=F+，就說函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價(jià)。5.函數(shù)依賴集等價(jià) 定義6.14如果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.2

設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y

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

XF+函數(shù)依賴集等價(jià)的充要條件 引理6.3F+=G+的充函數(shù)依賴集等價(jià)要判定F

G+，只須逐一對(duì)F中的函數(shù)依賴X→Y，考察Y是否屬于XG++

就行了。因此引理6.3給出了判斷兩個(gè)函數(shù)依賴集等價(jià)的可行算法。函數(shù)依賴集等價(jià)要判定FG+，只須逐一對(duì)F中的函數(shù)依賴X6.最小依賴集

定義6.15如果函數(shù)依賴集F滿足下列條件，則稱F為一個(gè)極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。

(1)F中任一函數(shù)依賴的右部?jī)H含有一個(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à)。6.最小依賴集定義6.15如果函數(shù)依賴集F滿足下最小依賴集[例2]對(duì)于6.1節(jié)中的關(guān)系模式S<U，F(xiàn)>，其中：

U={SNO，SDEPT，MN，CNAME，G}，

F={SNO→SDEPT，SDEPT→MN，（SNO，CNAME）→G}

設(shè)F’={SNO→SDEPT，SNO→MN，

SDEPT→MN，(SNO，CNAME)→G，

(SNO，SDEPT)→SDEPT}F是最小覆蓋，而F’不是。因?yàn)椋篎’-{SNO→MN}與F’等價(jià)

F’-{(SNO，SDEPT)→SDEPT}也與F’等價(jià)

F’-{(SNO，SDEPT)→SDEPT}∪{SNO→SDEPT}也與F’等價(jià)最小依賴集[例2]對(duì)于6.1節(jié)中的關(guān)系模式S<U，F(xiàn)>，其7.極小化過程定理6.3每一個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)極小函數(shù)依賴集Fm。此Fm稱為F的最小依賴集證:構(gòu)造性證明，依據(jù)定義分三步對(duì)F進(jìn)行“極小化處理”，找出F的一個(gè)最小依賴集。(1)逐一檢查F中各函數(shù)依賴FDi：X→Y，若Y=A1A2

…Ak，k>2，則用{X→Aj

|j=1，2，…，k}來取代X→Y。引理6.1（？）保證了F變換前后的等價(jià)性。引理6.lX→A1A2…Ak成立的充分必要條件是X→Ai成立（i=l，2，…，k）。7.極小化過程定理6.3每一個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)極小化過程(2)逐一檢查F中各函數(shù)依賴FDi：X→A，令G=F-{X→A}，若AXG+，則從F中去掉此函數(shù)依賴。由于F與G=F-{X→A}等價(jià)的充要條件是AXG+

因此F變換前后是等價(jià)的。引理6.2

設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y

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

XF+極小化過程(2)逐一檢查F中各函數(shù)依賴FDi：X→A，引理6極小化過程(3)逐一取出F中各函數(shù)依賴FDi：X→A，設(shè)X=B1B2…Bm，逐一考查Bi

（i=l，2，…，m），若A（X-Bi

）F+，則以X-Bi

取代X。由于F與F-{X→A}∪{Z→A}等價(jià)的充要條件是AZF+，其中Z=X-Bi

因此F變換前后是等價(jià)的。定義6.15(3)F中不存在這樣的函數(shù)依賴X→A，X有真子集Z使得F-{X→A}∪{Z→A}與F等價(jià)。極小化過程(3)逐一取出F中各函數(shù)依賴FDi：X→A，定義6極小化過程

由定義，最后剩下的F就一定是極小依賴集。因?yàn)閷?duì)F的每一次“改造”都保證了改造前后的兩個(gè)函數(shù)依賴集等價(jià)，因此剩下的F與原來的F等價(jià)。證畢定理6.3的證明過程也是求F極小依賴集的過程極小化過程 由定義，最后剩下的F就一定是極小依賴集。極小化過程[例3]F={A→B，B→A，B→C，

A→C，C→A}

Fm1、Fm2都是F的最小依賴集：

Fm1={A→B，B→C，C→A}

Fm2={A→B，B→A，A→C，C→A}F的最小依賴集Fm不一定是唯一的它與對(duì)各函數(shù)依賴FDi

及X→A中X各屬性的處置順序有關(guān)Fm2是先驗(yàn)證B→C得到的結(jié)果極小化過程[例3]F={A→B，B→A，B→C，F(xiàn)m例子：計(jì)算F的最小函數(shù)依賴集例1：關(guān)系模式R<U,F>，其中U={C,T,H,R,S,G}，F(xiàn)={CS→G,C→T,TH→R,HR→C,HS→R}

請(qǐng)計(jì)算F的最小函數(shù)依賴集例子：計(jì)算F的最小函數(shù)依賴集例1：關(guān)系模式R<U,F>，其中例子：計(jì)算F的最小函數(shù)依賴集

①利用分解規(guī)則，將所有的函數(shù)依賴變成右邊都是單個(gè)屬性的函數(shù)依賴。由于F的所有函數(shù)依賴的右邊都是單個(gè)屬性，故不用分解。例子：計(jì)算F的最小函數(shù)依賴集

①利用分解規(guī)則，將所有的函數(shù)例子：計(jì)算F的最小函數(shù)依賴集②去掉F中多余的函數(shù)依賴

A．設(shè)CS→G為冗余的函數(shù)依賴，則去掉CS→G，得：

F1={C→T,TH→R,HR→C,HS→R}

計(jì)算(CS)F1+：

設(shè)X(0)=CS

計(jì)算X(1)：掃描F1中各個(gè)函數(shù)依賴，找到左部為CS或CS子集的函數(shù)依賴，找到一個(gè)C→T函數(shù)依賴。故有X(1)=X(0)∪T=CST。

計(jì)算X(2)：掃描F1中的各個(gè)函數(shù)依賴，找到左部為CST或CST子集的函數(shù)依賴，沒有找到任何函數(shù)依賴。故有X(2)=X(1)。算法終止。

(CS)F1+=CST不包含G，故CS→G不是冗余的函數(shù)依賴，不能從F1中去掉。例子：計(jì)算F的最小函數(shù)依賴集②去掉F中多余的函數(shù)依賴?yán)樱河?jì)算F的最小函數(shù)依賴集B．設(shè)C→T為冗余的函數(shù)依賴，則去掉C→T，得：

F2={CS→G,TH→R,HR→C,HS→R}

計(jì)算(C)F2+：

設(shè)X(0)=C

計(jì)算X(1)：掃描F2中的各個(gè)函數(shù)依賴，沒有找到左部為C的函數(shù)依賴。故有X(1)=X(0)。算法終止。故C→T不是冗余的函數(shù)依賴，不能從F2中去掉。例子：計(jì)算F的最小函數(shù)依賴集B．設(shè)C→T為冗余的函數(shù)依賴，例子：計(jì)算F的最小函數(shù)依賴集C．設(shè)TH→R為冗余的函數(shù)依賴，則去掉TH→R，得：

F3={CS→G,C→T,HR→C,HS→R}

計(jì)算(TH)F3+：

設(shè)X(0)=TH

計(jì)算X(1)：掃描F3中的各個(gè)函數(shù)依賴，沒有找到左部為TH或TH子集的函數(shù)依賴。故有X(1)=X(0)。算法終止。故TH→R不是冗余的函數(shù)依賴，不能從F3中去掉。例子：計(jì)算F的最小函數(shù)依賴集C．設(shè)TH→R為冗余的函數(shù)依賴，例子：計(jì)算F的最小函數(shù)依賴集D．設(shè)HR→C為冗余的函數(shù)依賴，則去掉HR→C，得：

F4={CS→G,C→T,TH→R,HS→R}

計(jì)算(HR)F4+：

設(shè)X(0)=HR

計(jì)算X(1)：掃描F4中的各個(gè)函數(shù)依賴，沒有找到左部為HR或HR子集的函數(shù)依賴。故有X(1)=X(0)。算法終止。故HR→C不是冗余的函數(shù)依賴，不能從F4中去掉。例子：計(jì)算F的最小函數(shù)依賴集D．設(shè)HR→C為冗余的函數(shù)依賴，例子：計(jì)算F的最小函數(shù)依賴集E．設(shè)HS→R為冗余的函數(shù)依賴，則去掉HS→R，得：

F5={CS→G,C→T,TH→R,HR→C}

計(jì)算(HS)F5+：

設(shè)X(0)=HS

計(jì)算X(1)：掃描F5中的各個(gè)函數(shù)依賴，沒有找到左部為HS或HS子集的函數(shù)依賴。故有X(1)=X(0)。算法終止。故HS→R不是冗余的函數(shù)依賴，不能從F5中去掉。即：F5={CS→G,C→T,TH→R,HR→C,HS→R}例子：計(jì)算F的最小函數(shù)依賴集E．設(shè)HS→R為冗余的函數(shù)依賴，例子：計(jì)算F的最小函數(shù)依賴集③去掉F5中各函數(shù)依賴左邊多余的屬性（只檢查左部不是單個(gè)屬性的函數(shù)依賴）,沒有發(fā)現(xiàn)左邊有多余屬性的函數(shù)依賴。故最小函數(shù)依賴集為：F={CS→G,C→T,TH→R,HR→C,HS→R}例子：計(jì)算F的最小函數(shù)依賴集③去掉F5中各函數(shù)依賴左邊多余極小化過程極小化過程(定理6.3的證明)也是檢驗(yàn)F是否為極小依賴集的一個(gè)算法若改造后的F與原來的F相同，說明F本身就是一個(gè)最小依賴集極小化過程極小化過程(定理6.3的證明)也是檢驗(yàn)F是否為極小化過程在R<U，F(xiàn)>中可以用與F等價(jià)的依賴集G來取代F原因：兩個(gè)關(guān)系模式R1<U，F(xiàn)>，R2<U，G>，如果F與G等價(jià)，那么R1的關(guān)系一定是R2的關(guān)系。反過來，R2的關(guān)系也一定是R1的關(guān)系。極小化過程在R<U，F(xiàn)>中可以用與F等價(jià)的依賴集G來取代F候選碼的求解對(duì)于給定的關(guān)系R(A1,A2,…,An)和函數(shù)依賴集F，可以將其屬性分為4類：L類：僅出現(xiàn)在F的函數(shù)依賴左邊的屬性R類：僅出現(xiàn)在F的函數(shù)依賴右邊的屬性N類：在F的函數(shù)依賴左右兩邊均未出現(xiàn)的屬性LR類：在F的函數(shù)依賴左右兩邊均出現(xiàn)的屬性候選碼的求解對(duì)于給定的關(guān)系R(A1,A2,…,An)和函數(shù)依候選碼的求解（1）快速求解候選碼的一個(gè)充分條件定理：對(duì)于給定的關(guān)系模式R及其函數(shù)依賴集F，若X（XR）是L類屬性，則X必為R的任一候選碼的成員候選碼的求解（1）快速求解候選碼的一個(gè)充分條件候選碼的求解例子：設(shè)有關(guān)系模式R(A,B,C,D)，其函數(shù)依賴集F={D→B，B→D，AD→B，AC→D}，求R的所有候選碼解：可以發(fā)現(xiàn)，A和C屬性都是L類屬性，由前面定理可知，AC必是R的一候選碼的成員又因?yàn)?AC)+=ACBD，所以，AC是R的候選碼候選碼的求解例子：設(shè)有關(guān)系模式R(A,B,C,D)，其函數(shù)依候選碼的求解推論：對(duì)于給定的關(guān)系模式R及其函數(shù)依賴集F，若

XF+包含了R的全部屬性，則X必為R的唯一候選碼定理：對(duì)于給定的關(guān)系模式R及其函數(shù)依賴集F，如果X（XR）是R類屬性，則X不在任何候選碼中定理：設(shè)有關(guān)系模式R及其函數(shù)依賴集F，X（XR）是N類屬性，則X必包含在R的任一候選碼中候選碼的求解推論：對(duì)于給定的關(guān)系模式R及其函數(shù)依賴集F，若候選碼的求解推論：對(duì)于給定的關(guān)系模式R及其函數(shù)依賴集F，如果X是R的N類和L類組成的屬性集，且

XF+包含了R