第四章關(guān)系規(guī)范化理論本章內(nèi)容函數(shù)依賴4.2范式和規(guī)范化方法4.3數(shù)據(jù)依賴的公理系統(tǒng)4.4關(guān)系模式的分解4.5

規(guī)范問題的提出4.1

小結(jié)4.6教學(xué)目的

掌握函數(shù)依賴的概念掌握1NF、2NF、3NF和BCNF范式掌握模式分解的方法教學(xué)要求

牢記有關(guān)概念，掌握關(guān)系模式規(guī)范化的方法教學(xué)重點(diǎn)規(guī)范化問題的存在的原因函數(shù)依賴、完全函數(shù)依賴、傳遞依賴規(guī)范化過程概念回顧關(guān)系關(guān)系模式關(guān)系數(shù)據(jù)庫關(guān)系數(shù)據(jù)庫的模式

規(guī)范問題的提出4.1關(guān)系數(shù)據(jù)庫邏輯設(shè)計(jì)針對具體問題，如何構(gòu)造一個(gè)適合于它的數(shù)據(jù)模式數(shù)據(jù)庫邏輯設(shè)計(jì)的工具──關(guān)系數(shù)據(jù)庫的規(guī)范化理論

規(guī)范問題的提出4.14.1.1規(guī)范化理論的主要內(nèi)容規(guī)范化理論研究了關(guān)系模式中各屬性之間的依賴關(guān)系及其對關(guān)系模式性能的影響，探討好的關(guān)系模式應(yīng)該具備的性質(zhì)，以及達(dá)到好的關(guān)系模式的方法。規(guī)范化理論為我們提供了判斷關(guān)系模式好壞的理論標(biāo)準(zhǔn)，幫助我們預(yù)測可能出現(xiàn)的問題。關(guān)系數(shù)據(jù)庫的規(guī)范化理論主要包括3方面的內(nèi)容：函數(shù)依賴、范式（NormalForm）和規(guī)范化方法。其中函數(shù)依賴起著核心作用，是模式分解和模式設(shè)計(jì)的基礎(chǔ)；范式是模式分解的標(biāo)準(zhǔn)。

為了討論關(guān)系數(shù)據(jù)庫規(guī)范化理論，先分析下面一個(gè)實(shí)例。

【例4-1】以學(xué)生選課為背景，設(shè)計(jì)一個(gè)關(guān)系模式SCS。設(shè)計(jì)關(guān)系模式SCS如下：

SCS(Sno,Sname,Ssexk,Sdept,Cno,Cname,Sorce)

其中，Sno、Sname、Ssex、Sdept、Cno、Cname、Sorce是屬性名，分別表示學(xué)號(hào)、學(xué)生姓名、學(xué)生性別、學(xué)院、課程號(hào)、課程名、成績，加下劃線的屬性為主鍵。表4-1是關(guān)系模式SCS的一個(gè)實(shí)例，即一個(gè)具體關(guān)系。4.1.2不合理的關(guān)系模式存在的數(shù)據(jù)冗余和異?，F(xiàn)象表4-1關(guān)系SCSSnoSnameSsexSdeptCnoCnameScore100101100101100101120102120102130103姜珊姜珊姜珊陳默陳默孫浩女女女女女男信電學(xué)院信電學(xué)院信電學(xué)院管理學(xué)院管理學(xué)院外語學(xué)院C150110C150101C150103C150102C150103C150100離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)庫操作系統(tǒng)數(shù)據(jù)庫計(jì)算機(jī)基礎(chǔ)787085688272從表4-1中不難看出，關(guān)系模式SCS存在以下問題：（1）數(shù)據(jù)冗余。當(dāng)一個(gè)學(xué)生選修多門課程時(shí)，就會(huì)導(dǎo)致姓名、性別、學(xué)院名等多次重復(fù)存儲(chǔ)；每一門課程名均對選修該門課程的學(xué)生重復(fù)存儲(chǔ)，因而造成數(shù)據(jù)冗余。（2）操作異常。由于存在數(shù)據(jù)冗余，就可能導(dǎo)致數(shù)據(jù)庫操作過程中出現(xiàn)異常，這主要表現(xiàn)在以下幾個(gè)方面。

①插入異常。如果某個(gè)學(xué)生還沒有選課，學(xué)生的有關(guān)信息就不能插入。同樣，沒有被學(xué)生選修的課程信息也無法存入數(shù)據(jù)庫。從表4-1中不難看出，關(guān)系模式SCS存在以下問題：

②刪除異常。如果關(guān)系中某位同學(xué)因某種原因退學(xué)或轉(zhuǎn)學(xué)，那么就需要將其信息從關(guān)系中刪除。但如果某課程只有該同學(xué)一個(gè)人選修，則在刪除該生信息的同時(shí)，也把相應(yīng)課程的信息刪除了。那么，一旦查詢所開課程信息時(shí)，就不會(huì)出現(xiàn)被刪除課程的信息，就會(huì)認(rèn)為沒有開設(shè)該課程，可實(shí)際情況并非如此。因此，這也是該數(shù)據(jù)庫的一種功能缺陷，稱為刪除異常。

③修改異常。由于數(shù)據(jù)的冗余，當(dāng)修改數(shù)據(jù)庫中的某些數(shù)據(jù)項(xiàng)時(shí)，可能一部分修改了，而另一部分沒有修改，造成存儲(chǔ)數(shù)據(jù)的不一致性。例如，某個(gè)學(xué)生從信電學(xué)院轉(zhuǎn)到管理學(xué)院，那么與該學(xué)生相關(guān)的所有記錄都需要逐一修改屬性Sdept的值，如有遺漏，就會(huì)造成SCS中數(shù)據(jù)的不一致。結(jié)論

SCS關(guān)系模式不是一個(gè)好的，合理的模式?！昂谩钡哪Ｊ剑翰粫?huì)發(fā)生插入異常、刪除異常、更新異常，數(shù)據(jù)冗余應(yīng)盡可能少原因：是因?yàn)樵撽P(guān)系模式?jīng)]有設(shè)計(jì)好，使得某些屬性之間存在著“不良”的依賴關(guān)系，導(dǎo)致數(shù)據(jù)冗余。解決方法：通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴

如果將SCS分解為：

S(Sno,Sname,Ssex,Sdept)C(Cno,Cname)SC(Sno,Cno,Score)

就不會(huì)出現(xiàn)上述異常，數(shù)據(jù)冗余也得到較好控制。

規(guī)范化理論正是用來改造關(guān)系模式，通過把一個(gè)較大的關(guān)系模式分解成兩個(gè)或多個(gè)關(guān)系模式，在分解的過程中消除關(guān)系模式中不合適的問題，解決數(shù)據(jù)冗余、插入異常、刪除異常、修改異常等問題，其中，函數(shù)依賴是規(guī)范化理論的基礎(chǔ)。函數(shù)依賴4.2

函數(shù)依賴（FunctionalDependency）是數(shù)據(jù)依賴的一種。數(shù)據(jù)依賴是指一個(gè)關(guān)系中屬性值之間的相互聯(lián)系，它是現(xiàn)實(shí)世界屬性間相互聯(lián)系的體現(xiàn)，是數(shù)據(jù)之間的內(nèi)在性質(zhì)，是語義的體現(xiàn)?，F(xiàn)在已經(jīng)提出了多種類型的數(shù)據(jù)依賴，其中最重要的是函數(shù)依賴和多值依賴。函數(shù)依賴是關(guān)系規(guī)范化的理論基礎(chǔ)。函數(shù)依賴4.24.2.1函數(shù)依賴的定義

定義4.1：設(shè)R(U)是一個(gè)關(guān)系模式，U是R的屬性集合，X和Y是U的子集。如果對于R(U)的任意一個(gè)可能的關(guān)系r，t、s是r中的任意兩個(gè)元組，由t[X]=s[X]可以推導(dǎo)出t[Y]=s[Y]，則稱X函數(shù)決定Y或Y函數(shù)依賴于X，記作X→Y。定義中t[X]、t[Y]分別是元組t在屬性集X、Y上的分量；s[X]、s[Y]是元組s在X、Y上的分量。由定義可知，如果元組t和與元組s在X上的分量相等，則t、s在Y上的分量也相等，則稱X、Y間存在函數(shù)依賴關(guān)系，X屬性集函數(shù)決定Y屬性集。

說明所有關(guān)系實(shí)例均要滿足語義范疇的概念數(shù)據(jù)庫設(shè)計(jì)者可以對現(xiàn)實(shí)世界作強(qiáng)制的規(guī)定4.2.1函數(shù)依賴的定義

對于函數(shù)依賴的討論，有一些相關(guān)的概念：（1）如果X→Y，且YX，則稱X→Y是平凡的函數(shù)依賴。（2）如果X→Y，但YX，則稱X→Y是非平凡的函數(shù)依賴?！咀⒁狻吭谌我魂P(guān)系模式中，平凡的函數(shù)依賴都是必然成立的，其自身語義不言自明且不含其他語義。下面的討論如果沒有特別說明，均是討論非平凡的函數(shù)依賴。4.2.1函數(shù)依賴的定義

（3）如果X→Y，則稱X為決定因素（Determinant），稱Y

為依賴因素（Dependent）。（4）如果X→Y且Y→X，則記作X←→Y。（5）如果Y不函數(shù)依賴于X，則記作XY。

需要注意的是，函數(shù)依賴不是指關(guān)系模式R的某個(gè)或某些關(guān)系滿足的約束條件，而是指R的一切關(guān)系均要滿足的約束條件。4.2.2完全函數(shù)依賴和部分函數(shù)依賴

定義4.2：在關(guān)系模式R(U)中，U是R的屬性集合，X和Y是U的子集。如果X→Y，并且對于X的任何一個(gè)真子集X′，都有X′Y，則稱Y完全函數(shù)依賴（FullFunctionalDependency）于X，記作XY；若X→Y，但Y不完全函數(shù)依賴于X，則稱Y部分函數(shù)依賴（PartialFunctionalDependency）于X，記作XY。

【例4-2】在關(guān)系SC(Sno,Cno,Cname,Score)中，SnoScore且CnoScore，關(guān)系中有(Sno,Cno)Score。而Cno→Cname，所以(Sno,Cno)Cname。該關(guān)系中(Sno,Cno)是候選鍵。Cno單獨(dú)決定Cname。所以關(guān)系中的函數(shù)依賴(Sno,Cno)Cno是部分函數(shù)依賴。由定義及上例可知，當(dāng)函數(shù)依賴中的決定因素是組合屬性時(shí)，討論部分函數(shù)依賴才有意義；當(dāng)決定因素是單屬性時(shí)，該函數(shù)依賴是完全函數(shù)依賴。4.2.3傳遞函數(shù)依賴

定義4.3：在關(guān)系模式R(U)中，U是R的屬性集合，X和Y是U的子集。如果X→Y，Y→Z，且YX，YX，則稱Z傳遞函數(shù)依賴（TransitiveFunctionalDependency）于X，記作XZ；否則稱Z非傳遞函數(shù)依賴于X。

【例4-3】在關(guān)系S(Sno，Sname,Ssex,Sdept,Dean)中，有函數(shù)依賴關(guān)系SnoSname，由于SnoSdept，SdeptDean，有SnoDean。

由函數(shù)依賴的定義可以知道，如果Z傳遞依賴于X，則Z必然函數(shù)依賴于X，如果Z傳遞依賴于X，說明Z是間接依賴于X，從而表明X和Z之間的關(guān)聯(lián)較弱，表現(xiàn)出間接的弱函數(shù)依賴，因而亦是產(chǎn)生數(shù)據(jù)冗余的原因之一。4.2.4超鍵、候選鍵、主鍵1．超鍵和候選鍵定義4.4設(shè)K為R（U）的屬性或?qū)傩越M合，若K→U，則K為關(guān)系R的超鍵（Superkey）。如果K→U在R上成立，但對K的任一真子集K'?K，都有K'U，則稱K為R的候選鍵（Candidatekey）。

超鍵是可以唯一地標(biāo)識(shí)一個(gè)元組的屬性或?qū)傩约?。超鍵包含了候選鍵，但超鍵含有多余屬性，不是候選鍵。候選鍵是去掉了多余屬性的超鍵，是最小的超鍵。超鍵的超集仍然是超鍵。超鍵和候選鍵都具有唯一性，而候選鍵具有最小性。4.2.4超鍵、候選鍵、主鍵【例4-4】在關(guān)系模式S(Sno,Sname,Sage,Ssex,BP)中，存在函數(shù)依賴關(guān)系Sno→Sname，Sno→Sage，Sno→Ssex，Sno→BP及Sno→Sno。關(guān)系模式S中所有屬性都函數(shù)依賴于Sno，即有Sno→U，Sno是超鍵。Sno是單屬性，無多余屬性，故Sno是候選鍵。另一方面，關(guān)系模式S中也存在函數(shù)依賴關(guān)系(Sno,Sname)→U，(Sno,Sname)能夠在關(guān)系中唯一地標(biāo)識(shí)一個(gè)元組，是S的一個(gè)超鍵，但它有多余屬性，不是候選鍵。4.2.4超鍵、候選鍵、主鍵2．主鍵和主屬性

候選鍵多于一個(gè)時(shí)，從候選鍵中選擇一個(gè)作為主鍵（PrimaryKey）。主鍵的選擇是任意的。

關(guān)系模式中包含在任何一個(gè)候選碼中的屬性稱為主屬性（Primeattribute），不包含在候選碼中的屬性稱為非主屬性（Nonprimeattribute）或非碼屬性（Non-keyattribute）?！纠?-5】在關(guān)系模式SC(Sno,Cno,Score)中，(Sno,Cno)為候選鍵，其中的屬性Sno、Cno是主屬性，Score是非主屬性（非碼屬性）。主屬性和非主屬性的概念在下面規(guī)范化問題的討論中常會(huì)用到。

范式和規(guī)范化方法4.3

范式（NormalForms，NF）的概念是E.F.Codd在1971年提出的。1971—1972年，E.F.Codd提出了1NF、2NF與3NF。1974年，Codd與Boyce又共同提出了BCNF。1976年，F(xiàn)agin提出了4NF，后來又有人提出了5NF，這些范式是關(guān)系規(guī)范化的理論基礎(chǔ)。雖然規(guī)范化理論中還有新的范式出現(xiàn)，在這些范式中，最重要的是3NF和BCNF，它們是關(guān)系規(guī)范化的主要目標(biāo)。范式和規(guī)范化方法4.3

一個(gè)質(zhì)量良好的關(guān)系模式必須滿足一定的規(guī)范化要求，對于不同的規(guī)范化程度可用范式來衡量。范式是滿足一定要求的關(guān)系模式的集合，是衡量關(guān)系模式規(guī)范化程度的標(biāo)準(zhǔn)，滿足不同程度要求的為不同范式。目前主要有6種范式：第一范式（1NF）第二范式（2NF）第三范式（3NF）

BC范式（BCNF）第四范式（4NF）第五范式（5NF）范式和規(guī)范化方法4.3

范式的級(jí)別越高，條件越嚴(yán)格。滿足基本規(guī)范化要求的關(guān)系模式稱為第一范式，簡稱為1NF；在第一范式基礎(chǔ)上進(jìn)一步滿足一定要求的范式為第二范式，簡稱為2NF；其余以此類推。各種范式之間存在聯(lián)系：

1NF?2NF?3NF?BCNF?4NF?5NF

通常把某一關(guān)系模式R為第n范式簡記為R∈nNF。一個(gè)滿足低級(jí)范式的關(guān)系模式通過模式分解可以轉(zhuǎn)換為若干個(gè)高級(jí)范式的關(guān)系模式的集合，這個(gè)過程稱為關(guān)系模式的規(guī)范化。范式和規(guī)范化方法4.34.3.1第一范式（1NF）

定義4.5：如果關(guān)系模式R的每個(gè)屬性都是不可分解的基本數(shù)據(jù)項(xiàng)，則稱R屬于第一范式，記為R∈1NF。第一范式是對關(guān)系模式的最起碼的要求。不滿足第一范式的數(shù)據(jù)庫模式不能稱為關(guān)系數(shù)據(jù)庫。但是滿足第一范式的關(guān)系模式并不一定是一個(gè)好的關(guān)系模式如表4-2所示的關(guān)系模式是一個(gè)非規(guī)范化的關(guān)系模式，因?yàn)楸碇械臄?shù)據(jù)項(xiàng)“高級(jí)職稱人數(shù)”不是基本的數(shù)據(jù)項(xiàng)，它是由兩個(gè)基本數(shù)據(jù)項(xiàng)組成的復(fù)合數(shù)據(jù)項(xiàng)。將非第一范式的關(guān)系模式轉(zhuǎn)換成滿足第一范式的關(guān)系模式，只需將所有數(shù)據(jù)項(xiàng)都分解為不可再分的最小數(shù)據(jù)項(xiàng)即可。由表4-2轉(zhuǎn)換后的滿足第一范式的表如表4-3所示。

表4-2非第一范式的表

學(xué)院名稱高級(jí)職稱人數(shù)

教授副教授信電學(xué)院315管理學(xué)院526外語學(xué)院3124.3.1第一范式（1NF）學(xué)院名稱教授副教授信電學(xué)院315管理學(xué)院526外語學(xué)院312表4-3滿足第一范式的表4.3.1第一范式（1NF）4.3.2第二范式（2NF）

定義4.6：如果關(guān)系模式R∈1NF，且每個(gè)非主屬性都完全函數(shù)依賴于主鍵，則稱R屬于第二范式，記為R∈2NF。由定義可知，如果某個(gè)1NF的關(guān)系的主鍵只由一個(gè)屬性組成或關(guān)系的全體屬性均為主屬性，那么這個(gè)關(guān)系就是2NF。如果主鍵是由多個(gè)屬性列共同構(gòu)成的復(fù)合主鍵，并且存在非主屬性對主屬性的部分函數(shù)依賴，則這個(gè)關(guān)系就不是2NF。

【例4-6】對于關(guān)系S(Sno,Sname,Ssex,Sdept,Dean,Cno,Cname,Sorce)，主鍵為(Sno,Cno)。由于存在非主屬性姓名（Sname）、性別（Ssex）、課程名（Cname）部分函數(shù)依賴于(Sno,Cno)，因此S不屬于2NF。不滿足2NF的關(guān)系模式存在冗余及操作異常，需要進(jìn)一步規(guī)范化?？梢酝ㄟ^模式分解將非2NF的關(guān)系模式分解為多個(gè)滿足2NF的關(guān)系模式。分解步驟如下：

（1）首先用組成主鍵的屬性集合的每個(gè)子集作為主鍵構(gòu)成若干關(guān)系，對于關(guān)系S分解為如下3個(gè)子關(guān)系：

S1(Sno,…)，Sno為主鍵

S2(Cno,…)，Cno為主鍵

S3(Sno,Cno,…)，(Sno,Cno)為主鍵4.3.2第二范式（2NF）

（2）對于每個(gè)子關(guān)系，將依賴于此主鍵的屬性放置到此關(guān)系中，則有：

S1(Sno,Sname,Ssex,Sdept,Dean)，Sno為主鍵

S2(Cno,Cname)，Cno為主鍵

S3(Sno,Cno,Sorce)，(Sno,Cno)為主鍵

模式分解后，消除了原關(guān)系S中的部分函數(shù)依賴，即S1、S2、S33個(gè)關(guān)系模式都不存在部分函數(shù)依賴，S1、S2、S3都屬于2NF。分析一下S1存在的問題：（1）數(shù)據(jù)冗余。每個(gè)學(xué)院都有多名學(xué)生，都要存儲(chǔ)學(xué)院名和院長名，會(huì)出現(xiàn)數(shù)據(jù)冗余。（2）插入異常。學(xué)院剛成立，無在校學(xué)生，無法插入該學(xué)院信息。（3）刪除異常。假設(shè)某學(xué)院的全部學(xué)生都畢業(yè)了，則該學(xué)院的信息也會(huì)丟失。（4）修改復(fù)雜。若某學(xué)院更換了院長，需要修改所有學(xué)生的Dean屬性值。由此可見，滿足第二范式的關(guān)系模式仍然可能出現(xiàn)數(shù)據(jù)冗余和操作異常。這是因?yàn)榈诙妒經(jīng)]有排除傳遞函數(shù)依賴。因此，還需要對滿足第二范式的關(guān)系模式進(jìn)行進(jìn)一步分解。4.3.3第三范式（3NF）

定義4.7：如果關(guān)系模式R∈2NF，且所有非主屬性都不傳遞函數(shù)依賴于任何候選鍵，則R∈3NF。

【例4-7】分解例4-6中的關(guān)系S1，使其滿足3NF的要求。解：在關(guān)系S1中，院長（Dean）傳遞函數(shù)依賴于學(xué)號(hào)（Sno），即SnoDean，所以S1不屬于3NF。將關(guān)系S1(Sno,Sname,Ssex,Sdept,Dean)進(jìn)一步分解，消除傳遞依賴。分解步驟如下：（1）對于不是候選鍵的每個(gè)決定因素，從關(guān)系中刪除依賴它的所有屬性。在關(guān)系S1中，學(xué)院（Sdept）不是候選鍵，但卻是決定因素，從關(guān)系S1中刪除依賴它的屬性院長（Dean），得到新的關(guān)系S11(Sno,Sname,Ssex,Sdept)。（2）新建一個(gè)關(guān)系，該關(guān)系中包含原關(guān)系中不是候選鍵的決定因素以及所有依賴該決定因素的屬性，并將決定因素作為該關(guān)系的主鍵。對于關(guān)系S1，新建的關(guān)系為S12(Sdept,Dean)，主鍵為Sdept。關(guān)系S1分解后消除了傳遞函數(shù)依賴，因此S11和S12都滿足3NF。

由于3NF關(guān)系模式中不存在非主屬性對主鍵的部分依賴和傳遞依賴，因而在很大程度上消除了數(shù)據(jù)冗余和操作異常，因此在通常的數(shù)據(jù)庫設(shè)計(jì)中，一般要求達(dá)到3NF。3NF只是規(guī)定了非主屬性對鍵的依賴關(guān)系，而沒有限制主屬性對鍵的依賴關(guān)系。若存在主屬性對鍵的部分函數(shù)依賴和傳遞函數(shù)依賴關(guān)系，同樣會(huì)出現(xiàn)數(shù)據(jù)冗余、插入異常、刪除異常以及修改異常問題。【例4-8】假設(shè)有關(guān)系CSC(City,Street,Code)，其中各屬性分別代表城市、街道和郵政編碼，其語義為：城市和街道可以決定郵政編碼，郵政編碼可以決定城市。因此有：(City,Street)→Code,Code→City其候選鍵為(City,Street)和(Code,Street)，此關(guān)系模式中不存在非主屬性，故CSC∈3NF。

現(xiàn)在分析一下此關(guān)系模式存在的問題。假設(shè)取(City,Street)為主鍵，則當(dāng)插入數(shù)據(jù)時(shí)，如果沒有街道信息，則一個(gè)郵政編碼所屬城市這樣的信息就無法保存到數(shù)據(jù)庫中，因?yàn)镾treet不能為空。由此可見，即使是滿足3NF的表，也有可能存在異常。4.3.4BCNF

在3NF關(guān)系模式中存在異常的原因主要是3NF并沒有排除主屬性對候選鍵的部分依賴和傳遞依賴。如在此例中，Code→City，Code是決定因素，但不是候選鍵。CSC中存在主屬性City對候選鍵(Code,Street)的部分依賴。在此情況下產(chǎn)生了BCNF。

1974年，Boyce和Codd等人從另一個(gè)角度研究了范式，發(fā)現(xiàn)函數(shù)依賴中的決定因素和鍵之間的聯(lián)系與范式有關(guān)，從而創(chuàng)立了另一種第三范式，稱為Boyce-Codd范式，簡稱BCNF，但其條件比3NF更苛刻。通常認(rèn)為BCNF是修正的第三范式。4.3.4BCNF4.3.4BCNF

定義4.8：設(shè)關(guān)系模式R∈1NF，如果對于R的任意一個(gè)函數(shù)依賴X→Y，X必為候選鍵，則R∈BCNF。等價(jià)于：每個(gè)決定屬性集（因素）都包含（候選）碼。

BCNF的關(guān)系模式都具有如下3個(gè)性質(zhì)。（1）所有非主屬性都完全函數(shù)依賴于每個(gè)候選鍵。（2）所有主屬性都完全函數(shù)依賴于每個(gè)不包含它的候選鍵。（3）沒有任何屬性完全函數(shù)依賴于非候選鍵的任何一組屬性。4.3.4BCNF若R∈BCNF

所有非主屬性對每一個(gè)碼都是完全函數(shù)依賴所有的主屬性對每一個(gè)不包含它的碼，也是完全函數(shù)依賴沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性R∈BCNFR∈3NF

4.3.4BCNF

【例4-9】分析關(guān)系模式T(Tno,Tname,Tsex)中，各屬性分別代表教師號(hào)、教師姓名、性別。

解：T只有一個(gè)主鍵Tno，沒有任何屬性對Tno部分依賴或傳遞依賴，所以T∈3NF。同時(shí)Tno是T中唯一的決定因素，所以T∈BCNF。

4.3.4BCNF

【例4-10】分析關(guān)系模式STC(S,T,C)中，S表示學(xué)生，T表示教師，C表示課程。每一教師只教一門課。解：每門課程有若干教師，某一學(xué)生選定某門課程，就對應(yīng)一個(gè)固定的教師。由語義可得到函數(shù)依賴，如圖4-1所示：(S,C)→T,(S,T)→C,T→C

4.3.4BCNF

該關(guān)系模式中，(S,C)和(S,T)都是候選鍵。

因?yàn)闆]有任何非主屬性部分依賴和傳遞依賴于候選鍵所以STC∈3NF。但STC不是BCNF關(guān)系，因?yàn)門是決定因素，但它不是候選鍵。

STC可以分解為ST(S,T)與TC(T,C)，它們都是BCNF。

3NF和BCNF是對以函數(shù)依賴為基礎(chǔ)的關(guān)系模式規(guī)范化程度的衡量標(biāo)準(zhǔn)。3NF與BCNF的關(guān)系

R∈BCNFR∈3NF如果R∈3NF，且R只有一個(gè)候選碼

R∈BCNFR∈3NF

如果一個(gè)關(guān)系數(shù)據(jù)庫中的所有關(guān)系模式都屬于BCNF，那么在函數(shù)依賴范疇內(nèi)，它已實(shí)現(xiàn)了模式的徹底分解，達(dá)到了最高的規(guī)范化程度，消除了插入異常和刪除異常。至此，分別討論了1NF、2NF、3NF和BCNF，其中1NF是關(guān)系模式所隱含的，2NF只具有歷史意義，最重要、應(yīng)用最廣泛的是BCNF和3NF，因?yàn)樗鼈兡軡M足一般應(yīng)用的數(shù)據(jù)處理需求。4.3.5多值依賴與第四范式1．多值依賴定義4.9：設(shè)有關(guān)系模式R(U)，X、Y、Z是U的子集，且Z=U?X?Y。當(dāng)且僅當(dāng)R的任一關(guān)系r在（X、Z）上的每一個(gè)值對應(yīng)一組Y的值，這組值僅僅決定于X值而與Z值無關(guān)時(shí)，稱Y多值依賴于X，記作X→→Y。

如果X→→Y，但Z=U?X?Y=Ф，則稱X→→Y為平凡的多值依賴，否則為非平凡的多值依賴。4.3.5多值依賴與第四范式

【例4-11】某大學(xué)某一門課程由多個(gè)教師講授，他們使用相同的一套參考書。每個(gè)教員可以講授多門課程，每種參考書可以供多門課程使用。用關(guān)系模式Teach(C,T,B)表示，其中C表示課程，T表示教師，B表示參考書。表4-4表示了關(guān)系模式Teach的一個(gè)關(guān)系實(shí)例。表4-4關(guān)系模式Teach的一個(gè)關(guān)系實(shí)例課程C教師T參考書B數(shù)據(jù)庫原理及應(yīng)用數(shù)據(jù)庫原理及應(yīng)用數(shù)據(jù)庫原理及應(yīng)用數(shù)據(jù)庫原理及應(yīng)用數(shù)據(jù)庫原理及應(yīng)用數(shù)據(jù)庫原理及應(yīng)用數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法周曉明周曉明周曉明程羽姍程羽姍程羽姍程羽姍程羽姍程羽姍王宏偉王宏偉王宏偉數(shù)據(jù)庫系統(tǒng)概論SQLServer2000離散數(shù)學(xué)數(shù)據(jù)庫系統(tǒng)概論SQLServer2000離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)離散數(shù)學(xué)4.3.5多值依賴與第四范式Teach∈BCNFTeach具有唯一候選鍵(C，T，B)，即全鍵Teach模式中存在的問題(1)數(shù)據(jù)冗余度大(2)插入操作復(fù)雜(3)刪除操作復(fù)雜

經(jīng)過分析可以發(fā)現(xiàn)，在關(guān)系模式Teach中，每個(gè)(C,B)上的值對應(yīng)一組T值，而且這種對應(yīng)與B無關(guān)。如與(C,B)對應(yīng)的兩個(gè)元組(數(shù)據(jù)庫原理與應(yīng)用,數(shù)據(jù)庫系統(tǒng)概論)和(數(shù)據(jù)庫原理與應(yīng)用,離散數(shù)學(xué))在B屬性上的值不同，但它們對應(yīng)同一組T值{周曉明,程羽姍}，由此得出T多值依賴于C，即C→→T。也就是關(guān)系模式Teach中存在的這種多值依賴的數(shù)據(jù)依賴，造成了上述問題的存在。存在多值依賴4.3.5多值依賴與第四范式多值依賴具有以下性質(zhì)：（1）替代性。若X→Y，則X→→Y，即X→Y是X→→Y的特例。（2）對稱性。若X→→Y，則X→→U?X?Y。（3）傳遞性。若X→→Y，Y→→Z，則X→→Z?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。4.3.5多值依賴與第四范式2．第四范式（4NF）定義4.10：關(guān)系模式R∈1NF，如果對于R的每個(gè)非平凡多值依賴X→→Y（YX），X都含有候選鍵，則稱R屬于第四范式，記為R∈4NF。

由4NF的定義可以知道，4NF限制了關(guān)系模式的屬性之間不允許出現(xiàn)非平凡且非函數(shù)依賴的多值依賴。因?yàn)閷τ诿恳粋€(gè)非平凡的多值依賴X→→Y，X都含有候選鍵，所以X→Y，故4NF所允許的非平凡的多值依賴實(shí)際上就是函數(shù)依賴。如果一個(gè)關(guān)系模式滿足BCNF，但不是4NF，這樣的關(guān)系模式仍然可能存在問題，還需要繼續(xù)規(guī)范化使其達(dá)到4NF。如果一個(gè)關(guān)系模式滿足4NF，則它一定滿足BCNF；反之不然。4.3.5多值依賴與第四范式

例4-11的關(guān)系模式Teach中，主鍵是(C,T,B)，即全鍵。C→→T，C→→B，它們都是非平凡的多值依賴，但C不是候選鍵，所以Teach不屬于4NF。將Teach分解為T(C,T)和B(C,B)，雖然存在C→→T，C→→B，但它們是平凡的多值依賴，所以T∈4NF，B∈4NF，這樣關(guān)系模式Teach存在的問題得到了較好地解決，如表4-5和表4-6所示。表4-5關(guān)系T表4-6關(guān)系B課程C教師T課程C參考書B數(shù)據(jù)庫原理及應(yīng)用數(shù)據(jù)庫原理及應(yīng)用數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法周曉明程羽姍程羽姍王宏偉數(shù)據(jù)庫原理及應(yīng)用數(shù)據(jù)庫原理及應(yīng)用數(shù)據(jù)庫原理及應(yīng)用數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)庫系統(tǒng)概論SQLServer2000離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)離散數(shù)學(xué)4.3.5多值依賴與第四范式

函數(shù)依賴和多值依賴是兩種最重要的數(shù)據(jù)依賴。如果只考慮函數(shù)依賴，則屬于BCNF的關(guān)系模式規(guī)范化程度是最高的；如果考慮多值依賴，則屬于4NF的關(guān)系模式規(guī)范化程度是最高的。實(shí)際上，數(shù)據(jù)依賴中除函數(shù)依賴和多值依賴之外，還有其他數(shù)據(jù)依賴，如連接依賴。函數(shù)依賴是多值依賴的一種特殊情況，而多值依賴實(shí)際上又是連接依賴的一種特殊情況。但連接依賴不像函數(shù)依賴和多值依賴可由語義直接導(dǎo)出，而是在關(guān)系的連接運(yùn)算時(shí)反映出來。存在連接依賴的關(guān)系模式仍然可能存在數(shù)據(jù)冗余、操作異常等問題。如果消除了屬于4NF的關(guān)系模式中存在的連接依賴，則可以進(jìn)一步達(dá)到滿足5NF的關(guān)系模式。

4.3.6關(guān)系模式的規(guī)范化

關(guān)系數(shù)據(jù)庫的規(guī)范化理論是數(shù)據(jù)庫邏輯設(shè)計(jì)的工具目的：盡量消除插入、刪除異常，修改復(fù)雜，數(shù)據(jù)冗余基本思想：逐步消除數(shù)據(jù)依賴中不合適的部分實(shí)質(zhì)：概念的單一化4.3.6關(guān)系模式的規(guī)范化一個(gè)關(guān)系模式的規(guī)范化過程如圖4-2。圖4-2各種范式及規(guī)范化過程4.3.6關(guān)系模式的規(guī)范化不能說規(guī)范化程度越高的關(guān)系模式就越好在設(shè)計(jì)數(shù)據(jù)庫模式結(jié)構(gòu)時(shí)，必須對現(xiàn)實(shí)世界的實(shí)際情況和用戶應(yīng)用需求作進(jìn)一步分析，確定一個(gè)合適的、能夠反映現(xiàn)實(shí)世界的模式上面的規(guī)范化步驟可以在其中任何一步終止數(shù)據(jù)依賴的公理系統(tǒng)4.41．函數(shù)依賴集F的邏輯蘊(yùn)含

定義4.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。例如，關(guān)系模式S中存在函數(shù)依賴Sno→(Sname,Sage)它蘊(yùn)含兩個(gè)函數(shù)依賴：Sno→Sname，Sno→Sage。對于關(guān)系模式R(U,F)，考慮到F所蘊(yùn)含的所有函數(shù)依賴，就有函數(shù)依賴集閉包的概念。4.4.1函數(shù)依賴的邏輯蘊(yùn)含與函數(shù)依賴集的閉包4.4.1函數(shù)依賴集的閉包2．函數(shù)依賴集閉包

定義4.12：所有被一個(gè)已知函數(shù)依賴集F邏輯蘊(yùn)含的那些函數(shù)依賴的集合稱為F的閉包（Closure），記為F+。為了用一套系統(tǒng)的方法求F+，還必須遵循一組函數(shù)依賴的推理規(guī)則。

1．Armstrong公理系統(tǒng)（Armstrong’saxiom）

對于關(guān)系模式R(U,F)，X、Y、Z是U的子集，F(xiàn)是U上的一組函數(shù)依賴。對R(U,F)有以下推理規(guī)則：（1）A1：自反律。如果YX，則X→Y。

注意：由自反律得到的函數(shù)依賴均是平凡的函數(shù)依賴，自反律的使用并不依賴于F。（2）A2：增廣律。如果ZW且X→Y，則XZ→YZ。（3）A3：傳遞律。如果X→Y且Y→Z，則X→Z。4.4.2函數(shù)依賴的推理規(guī)則2．其他推理規(guī)則

由3條獨(dú)立推理規(guī)則，可得到3條推論

推論1：合并規(guī)則若X→Y，X→Z，有X→YZ。

證明：由X→Y，可知X→XY（增廣律）；由X→Z，知XY→YZ（增廣律），所以X→YZ（傳遞律）。

推論2：分解規(guī)則。若X→Y，ZY，有X→Z。

證明：由ZY，可知Y→Z（自反律），又因?yàn)閄→Y，所以X→Z（傳遞律）。

推論3：偽傳遞規(guī)則。若X→Y，WY→Z，有XW→Z。

證明：由X→Y，得到WX→WY（增廣律），又因?yàn)閃Y→Z，所以有XW→Z（傳遞律）。

【例4-12】設(shè)有關(guān)系模式R(A,B,C,D,E)及其上的函數(shù)依賴集F={AB→CD,A→B,D→E}，求證F必蘊(yùn)含A→E。證明：∵A→B（已知）

∴A→AB（增廣律）

∵AB→CD（已知）

∴A→CD（傳遞律）

∴A→C，A→D（分解規(guī)則）

∵D→E（已知）

∴A→E（傳遞律）

證畢4.4.3屬性集的閉包及其算法1．屬性集閉包定義4.13:

設(shè)有關(guān)系模式R(U)，F(xiàn)為屬性集U上的一組函數(shù)依賴，X包含于U，定義={A|X→A能由F根據(jù)Armstrong公理導(dǎo)出}，稱為屬性集X關(guān)于函數(shù)依賴集F的閉包。2.F邏輯蘊(yùn)含的充要條件

定理4.2設(shè)F為屬性集U上的一組函數(shù)依賴，X、YU，X→Y能由F根據(jù)Armstrong公理導(dǎo)出的充分必要條件是Y。于是，判定X→Y是否能由F根據(jù)Armstrong公理導(dǎo)出的問題，就轉(zhuǎn)化為求，并判定Y是否包含于的問題。該問題可由算法4.1解決。4.4.3屬性集的閉包及其算法3．求屬性集閉包算法算法4.1求屬性集X（XU）關(guān)于U上的函數(shù)依賴集F的閉包。

輸入：屬性全集U、U上的函數(shù)依賴集F，以及屬性集XU。輸出：X關(guān)于F的閉包。方法：根據(jù)下列步驟計(jì)算一系列屬性集合X(0),X(1),…（1）令X(0)=X，i=0。（2）令X(i+1)=X(i)∪B。其中：B={A|(V)(W)(V→WF∧VX(i)∧AW)}，即B是這樣的集合：在F中尋找滿足條件VX(i)的所有函數(shù)依賴V→W，并記屬性W的并集為B。（3）判斷X(i+1)是否等于X(i)。（4）若X(i+1)≠X(i)，則用i+1取代i，返回第（2）步。（5）若X(i+1)=X(i)，則X(i)即為，算法終止。該算法中的U、X和F都是有限集，它們的任何子集也是有限集；另外，算法每一步的中間結(jié)果均滿足X(i)U，BU，從而X(i)不可能無限擴(kuò)大，即計(jì)算過程是有限的，經(jīng)過有限次循環(huán)后，一定有X(i)=X(i+1)=X(i+2)=…。4.4.3屬性集的閉包及其算法【例4-13】F{AB→C,C→A,BC→D,ACD→B,D→EG,BE→C,CG→BD

CE→AG}令X=BD，求。

4.4.4候選鍵的計(jì)算

前面曾給出候選鍵的定義?？梢杂煤瘮?shù)集閉包的概念描述候選鍵：對于關(guān)系模式R(U,F)，X是U的子集，如果X→U，即UX+中，則稱X為R的一個(gè)超鍵，若X'是X的任一真子集，而UX'+，則X是R的候選鍵。4.4.4候選鍵的計(jì)算對于關(guān)系模式R(U,F)，屬性集合U中的屬性可以分為4類。（1）L類：僅出現(xiàn)在F中的函數(shù)依賴左邊的屬性。（2）R類：僅出現(xiàn)在F中的函數(shù)依賴右邊的屬性。（3）N類：F中的函數(shù)依賴左右兩邊都未出現(xiàn)的屬性。（4）LR類：在F中的函數(shù)依賴兩邊都出現(xiàn)過的屬性。

定理4.3對于給定的關(guān)系模式R及函數(shù)依賴集F，有如下結(jié)論：（1）若X、U是L類屬性，則X必定是R的某個(gè)候選鍵的成員。（2）若X、U是L類屬性，并且X+包含了U，則X必定是R的唯一候選鍵。（3）若X、U是R類屬性，則X不在任何候選鍵中。（4）若X、U是N類屬性，則X包含在R的任一個(gè)候選鍵中。（5）若X、U是R類和L類屬性組成的屬性集合，且X+包含了U，則X是R的唯一候選鍵。4.4.4候選鍵的計(jì)算【例4-14】設(shè)有關(guān)系模式R(A,B,C,D)，函數(shù)依賴集F={D→B,B→D,AD→B,AC→D},求R的所有候選鍵。

解：在F中，A、C屬性是L類，B、D屬性是LR類。A、C屬性必在R的候選鍵中。而(AC)+=ABCD，包含了R的全部屬性，且U不在A+、C+中。故AC是R的唯一候選鍵。算法4.2候選鍵算法

輸入：關(guān)系模式R，屬性集U及函數(shù)依賴集F。輸出：關(guān)系模式R的所有候選鍵。（1）由F，將R的所有屬性分為L、R、N和LR類，并用X代表L類和N類，Y代表LR類屬性。（2）求X+，若X+包含了R的全部屬性，則X即為R的唯一候選鍵，轉(zhuǎn)（5）否則轉(zhuǎn)（3）。（3）在Y中取一個(gè)屬性A，求(XA)+，若包含了R的全部屬性，則轉(zhuǎn)（4），否則，換一個(gè)屬性重復(fù)這一過程，直到試完所有Y中的屬性。（4）如果已經(jīng)找到所有的候選鍵，則轉(zhuǎn)（5），否則在Y中依次取2個(gè)屬性、3個(gè)屬性…，求它們的閉包，直到其閉包包含R的所有屬性。（5）停止，輸出結(jié)果。4.4.4候選鍵的計(jì)算【例4-15】設(shè)有關(guān)系模式R(A,B,C,D,E)，函數(shù)依賴集F={A→BC,CD→E,B→D,E→A}，求R的所有候選鍵。解：R中所有屬性都是LR類屬性，沒有L、R、N類屬性。根據(jù)算法4.2，需要從LR類中依次取出一個(gè)屬性并分別求它們的閉包：A+=ABCDE，B+=BD，C+=C，D+=D，E+=ABCDE。A+及E+都包含了R的全部屬性，A、E分別是R的候選鍵。下面再從BCD中取兩個(gè)屬性的集合計(jì)算閉包：(BC)+=ABCDE，(CD)+=ABCDE，(BD)+=BD。(BC)+和(CD)+都包含了R的全部屬性，屬性集BC和CD也分別是R的候選鍵。至此R中不可能存在其他的候選鍵了，所以R的候選鍵為A、E、BC、CD。定理4.4：Armstrong公理系統(tǒng)是正確的、完備的。1．正確性證明4.4.5函數(shù)依賴推理規(guī)則的完備性（1）正確性的概念：Armstrong公理系統(tǒng)是正確的。（2）證明：要證明Armstrong公理系統(tǒng)是正確的，只要證明規(guī)則A1、A2、A3是正確的即可。①自反律A1是正確的。證明：設(shè)YXU，對R(U,F)的任一關(guān)系r中的任意兩個(gè)元組t、s有：若t[X]=s[X]，由于YX，有t[Y]=s[Y]，所以X→Y成立，自反律得證。②增廣律A2是正確的。證明：設(shè)X→Y為F所蘊(yùn)含，且ZU，設(shè)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)含，增廣律得證。③傳遞律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)含，傳遞律得證。2．完備性證明4.4.5函數(shù)依賴推理規(guī)則的完備性（1）完備性的概念：F+中的每一個(gè)函數(shù)依賴，必定可以由F出發(fā)，根據(jù)Armstrong公理推導(dǎo)出來。即若X→Y屬于F+，則X→Y必定可以由F出發(fā)，根據(jù)Armstrong公理推導(dǎo)出來。（2）證明：證明完備性的逆否命題，即若函數(shù)依賴X→Y不能由F從Armstrong公理導(dǎo)出，那么它必然不為F所蘊(yùn)含，其證明分3步。①若V→W成立，且V，則W。證明：因V，所以X→V成立；于是X→W成立（因?yàn)閄→V，V→W），所以W。4.4.5函數(shù)依賴推理規(guī)則的完備性②構(gòu)成一張二維表r，它由圖4-3所示的兩個(gè)元組構(gòu)成，可以證明r必是R(U,F)的一個(gè)關(guān)系，即F中的全部函數(shù)依賴在r上成立。rU-t1111…1111...1t2111...1000...0

圖4-3二維表r及其元組

若r不是R(U,F)的關(guān)系，則必是由于F中有函數(shù)依賴V→W在r上不成立所致。由r的構(gòu)成可知，V必定是的子集，而W不是的子集，與第①步矛盾，所以r必是R(U,F)的一個(gè)關(guān)系。③若X→Y不能由F從Armstrong公理導(dǎo)出，則Y不是的子集，因此必有Y的子集Y′滿足Y′包含于U?，則X→Y在r中不成立，即X→Y必不為R(U,F)所蘊(yùn)含。4.4.5函數(shù)依賴集的等價(jià)、覆蓋和最小函數(shù)依賴集2．最小函數(shù)依賴集的定義

定義4.14：如果函數(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à)。

上述3個(gè)條件的作用分別如下：條件（1）保證每個(gè)函數(shù)依賴的右部都不會(huì)有重復(fù)的屬性。條件（2）保證F中沒有冗余的函數(shù)依賴。條件（3）保證每個(gè)函數(shù)依賴的左部沒有冗余的屬性。

定義4.15：每一個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)極小函數(shù)依賴集Fm，此Fm稱為F的最小依賴集。3．最小函數(shù)依賴集的求解算法【例4-16】F={A→B,B→A,B→C,A→C,C→A}，F(xiàn)m1={A→B,B→C,C→A}，F(xiàn)m2={A→B,B→A,A→C,C→A}，這里給出了F的兩個(gè)最小依賴集Fm1和Fm2。

若改造后的F與原來的F相同，那么就說明F本身就是一個(gè)最小依賴集，因此定義4.15的證明給出的極小化過程也可以看成是檢驗(yàn)F是否是極小依賴集的一個(gè)算法。兩個(gè)關(guān)系模式R1(U,F)和R2(U,G)，如果F與G等價(jià)，那么R1的關(guān)系一定是R2的關(guān)系。反過來，R2的關(guān)系也一定是R1的關(guān)系。所以在R(U,F)中用與F等價(jià)的依賴集G來取代F是允許的。關(guān)系模式的分解4.5把低一級(jí)的關(guān)系模式分解為若干個(gè)高一級(jí)的關(guān)系模式的方法不是唯一的只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價(jià)，分解方法才有意義關(guān)系模式的分解4.54.5.1模式分解的定義