第十一章關(guān)系數(shù)據(jù)庫(kù)規(guī)范化理論11.1函數(shù)依賴(lài)11.2關(guān)系規(guī)范化11.3模式分解11.4本章小結(jié)*11.1函數(shù)依賴(lài)規(guī)范化理論正是用來(lái)改造關(guān)系模式，通過(guò)分解關(guān)系模式來(lái)消除其中不合適的數(shù)據(jù)依賴(lài)，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問(wèn)題。11.1.1函數(shù)依賴(lài)的基本概念11.1.2屬性集閉包、候選碼及極小函數(shù)依賴(lài)集的求解方法11.1.3為什么要討論函數(shù)依賴(lài)*11.1.1函數(shù)依賴(lài)的基本概念1.關(guān)系模式的形式化定義首先介紹關(guān)系模式的形式化定義，關(guān)系模式的形式化定義是指關(guān)系模式由五部分組成，是一個(gè)五元組，形如：R（U，D，DOM，F(xiàn)）。其中R表示關(guān)系名，U表示組成該關(guān)系的屬性名集合，D表示屬性組U中屬性所來(lái)自的域，DOM表示屬性向域的映象集合，F(xiàn)表示屬性間數(shù)據(jù)的依賴(lài)關(guān)系集合。通常簡(jiǎn)化為如下形式R(U,D)。*2.函數(shù)依賴(lài)

函數(shù)的概念，大家都非常熟悉，對(duì)于公式：Y=f(x)

表示的是X和Y在數(shù)量上的對(duì)應(yīng)關(guān)系，給定一個(gè)X值，都會(huì)有一個(gè)Y值和它對(duì)應(yīng)，即X函數(shù)決定Y或者Y函數(shù)依賴(lài)于X。

函數(shù)依賴(lài)的一般定義：R(U)是一個(gè)屬性集U上的關(guān)系模式，X和Y是U的子集。若對(duì)于R(U)的任意一個(gè)可能的關(guān)系r，r中不可能存在兩個(gè)元組在X上的屬性值相等而在Y上的屬性值不等，也就是說(shuō)如果對(duì)于關(guān)系r中的任意一個(gè)X值，都只有一個(gè)Y值與之相對(duì)應(yīng)，則稱(chēng)“X函數(shù)決定Y”或“Y函數(shù)依賴(lài)于X”，

記作“XY”

*3、平凡函數(shù)依賴(lài)與非平凡函數(shù)依賴(lài)在關(guān)系模式R(U)中，對(duì)于U的子集X和Y，如果X→Y，但Y

X，則稱(chēng)X→Y是非平凡的函數(shù)依賴(lài)若X→Y，但Y

X,則稱(chēng)X→Y是平凡的函數(shù)依賴(lài)?yán)涸陉P(guān)系SC(Sno,Cno,Grade)中，

非平凡函數(shù)依賴(lài)：(Sno,Cno)→

Grade

平凡函數(shù)依賴(lài)：(Sno,Cno)→

Sno(Sno,Cno)→Cno*若X→Y，則X稱(chēng)為這個(gè)函數(shù)依賴(lài)的決定屬性組，也稱(chēng)為決定因素（Determinant）。若X→Y，Y→X，則記作X←→Y。若Y不函數(shù)依賴(lài)于X，則記作X→Y。*4、完全函數(shù)依賴(lài)與部分函數(shù)依賴(lài)

在R(U)中，如果X→Y，并且對(duì)于X的任何一個(gè)真子集X’，都有X’Y,則稱(chēng)Y對(duì)X完全函數(shù)依賴(lài)，記作XFY。若X→Y，但Y不完全函數(shù)依賴(lài)于X，則稱(chēng)Y對(duì)X部分函數(shù)依賴(lài)，記作XPY。

[例](Sno,Cno)→Grade是完全函數(shù)依賴(lài)，

(Sno,Cno)→Sdept是部分函數(shù)依賴(lài)因?yàn)镾no→Sdept成立，且Sno是（Sno，Cno）的真子集

FP*5、傳遞函數(shù)依賴(lài)在R(U)中，如果X→Y，(Y

X),Y→XY→Z，則稱(chēng)Z對(duì)X傳遞函數(shù)依賴(lài)。記為：X→Z

注:如果Y→X，即X←→Y，則Z直接依賴(lài)于X。

例:在關(guān)系Std(Sno,Sdept,Mname)中，有：

Sno→Sdept，Sdept→MnameMname傳遞函數(shù)依賴(lài)于Sno傳遞*（1）Armstrong公理系統(tǒng)

關(guān)系模式R<U，F(xiàn)>來(lái)說(shuō)有以下的推理規(guī)則：①自反律（Reflexivity）：若Y

X

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

U，則XZ→YZ為F所蘊(yùn)含。③傳遞律（Transitivity）：若X→Y及Y→Z為F所蘊(yùn)含，則X→Z為F所蘊(yùn)含。*6.函數(shù)依賴(lài)的推理規(guī)則（2）Armstrong公理推論根據(jù)①，②，③這三條推理規(guī)則可以得到下面三條推理規(guī)則：合并規(guī)則：由X→Y，X→Z，有X→YZ。（②，③）偽傳遞規(guī)則：由X→Y，WY→Z，有XW→Z。（②，③）分解規(guī)則：由X→Y及Z

Y，有X→Z。（①，③）復(fù)合規(guī)則：由X→Y及X→Z，有XW→YZ。

*1.屬性集閉包的求解方法定義

在關(guān)系模式R<U，F(xiàn)>中為F所邏輯蘊(yùn)含的函數(shù)依賴(lài)的全體叫作F的閉包，記為F+。定義

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

U，XF+={A|X→A能由F根據(jù)Armstrong公理導(dǎo)出}，XF+稱(chēng)為屬性集X關(guān)于函數(shù)依賴(lài)集F的閉包*11.1.2屬性集閉包、候選碼及極小函數(shù)依賴(lài)集的求解方法求閉包的算法算法

求屬性集X（X

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

輸入：X，F(xiàn)；輸出：XF+步驟：（1）令X（0）=X，i=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）步。*【例11-1】設(shè)有關(guān)系模式，其中屬性集，函數(shù)依賴(lài)集，計(jì)算X+、(XW)+。（1）計(jì)算X+第一步：初始X+=X。第二步：①對(duì)X+中的X，存在X→Y，所以X+=X+UY=XY；②對(duì)X+中的Y，存在Y→Z，所以X+=X+UY=XYZ。在函數(shù)依賴(lài)集F中，Z不出現(xiàn)在任何函數(shù)依賴(lài)關(guān)系的左邊，因此X+將不會(huì)再擴(kuò)大，所以最終X+=XYZ。*（2）計(jì)算第一步：初始(XW)+=XW。第二步：①對(duì)(XW)+中的X，存在X→Y，所以(XW)+=(XW)+UY=XWY；②對(duì)(XW)+中的W，存在W→Y，Y已經(jīng)在(XW)+中，所以(XW)+保持不變；③對(duì)(XW)+中的Y，存在Y→Z，所以(XW)+=(XW)+UZ=XWYZ；④對(duì)(XW)+中的Z，因?yàn)樵诤瘮?shù)依賴(lài)集F中，Z不出現(xiàn)在任何函數(shù)依賴(lài)關(guān)系的左邊，因此(XW)+將不會(huì)再擴(kuò)大，最終(XW)+=XWYZ

綜上，求屬性集閉包的作用是，如果屬性集X的閉包X+包含了R中的全部屬性，則X為R的一個(gè)候選碼。*2.候選碼的求解方法對(duì)于給定的關(guān)系和函數(shù)依賴(lài)集F，可將其屬性分為L(zhǎng)類(lèi)、R類(lèi)、N類(lèi)、LR類(lèi)。其中，L類(lèi)指僅出現(xiàn)在函數(shù)依賴(lài)關(guān)系左部的屬性，R類(lèi)指僅出現(xiàn)在函數(shù)依賴(lài)關(guān)系右部的屬性，N類(lèi)指在函數(shù)依賴(lài)關(guān)系左右兩邊均未出現(xiàn)的屬性，LR類(lèi)指在函數(shù)依賴(lài)關(guān)系左右兩邊均出現(xiàn)的屬性。*對(duì)于R中的屬性X，可有以下推論：推論1：對(duì)于給定的關(guān)系模式R及其函數(shù)依賴(lài)集F，若X是L類(lèi)屬性，則X必為R的任一候選碼的成員。推論2：對(duì)于給定的關(guān)系模式R及其函數(shù)依賴(lài)集F，若X是L類(lèi)屬性且X+包含了R的全部屬性，則X必為R的惟一候選關(guān)鍵字。推論3：對(duì)于給定的關(guān)系模式R及其函數(shù)依賴(lài)集F，若X是R類(lèi)屬性，則X不包含在任何候選碼中。推論4：對(duì)于給定的關(guān)系模式R及其函數(shù)依賴(lài)集F，若X是N類(lèi)屬性，則X必為R的任一候選碼的成員。推論5：對(duì)于給定的關(guān)系模式R及其函數(shù)依賴(lài)集F，若X是N類(lèi)和L類(lèi)組成的屬性集，且X+包含了R的全部屬性，則X必為R的惟一候選關(guān)鍵字。推論6：對(duì)于給定的關(guān)系模式R及其函數(shù)依賴(lài)集F，若X是LR類(lèi)屬性，則X可能包含在關(guān)系模式R的某個(gè)候選碼中。*定義6.14

：

如果G+=F+，就說(shuō)函數(shù)依賴(lài)集F覆蓋G（F是G的覆蓋或G是F的覆蓋）或F與G等價(jià)。引理6.3

：F+=G+的充分必要條件是F

G+和G

F+

*3.極小函數(shù)依賴(lài)集的求解方法（1）函數(shù)依賴(lài)集等價(jià)（2）最小依賴(lài)集定義

如果函數(shù)依賴(lài)集F滿足下列條件，則稱(chēng)F為一個(gè)極小函數(shù)依賴(lài)集。亦稱(chēng)為最小依賴(lài)集或最小覆蓋。

(1)F中任一函數(shù)依賴(lài)的右部?jī)H含有一個(gè)屬性。

(2)F中不存在這樣的函數(shù)依賴(lài)X→A，使得F與F-{X→A}等價(jià)。

(3)F中不存在這樣的函數(shù)依賴(lài)X→A，X有真子集Z使得F-{X→A}∪{Z→A}與F等價(jià)。*定理

每一個(gè)函數(shù)依賴(lài)集F均等價(jià)于一個(gè)極小函數(shù)依賴(lài)集Fm。此Fm稱(chēng)為F的最小依賴(lài)集。證明:構(gòu)造性證明，找出F的一個(gè)最小依賴(lài)集。

(1)逐一檢查F中各函數(shù)依賴(lài)FDi：X→Y，若Y=A1A2…Ak，k>=2，則用{X→Aj

|j=1，2，…，k}來(lái)取代X→Y。(2)逐一檢查F中各函數(shù)依賴(lài)FDi：X→A，令G=F-{X→A}，若A

XG+，則從F中去掉此函數(shù)依賴(lài)。(3)逐一取出F中各函數(shù)依賴(lài)FDi：X→A，設(shè)X=B1B2…Bm，逐一考查Bi

（i=l，2，…，m），若A

（X-Bi

）F+，則以X-Bi

取代X。*[例]F={A→B，B→A，B→C，A→C，C→A} Fm1、Fm2都是F的最小依賴(lài)集：

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

Fm2={A→B，B→A，A→C，C→A}F的最小依賴(lài)集Fm不唯一極小化過(guò)程(上述定理的證明)是檢驗(yàn)F是否為極小依賴(lài)集的一個(gè)算法*

討論關(guān)系模式中屬性之間的函數(shù)依賴(lài)有什么意義呢？首先需要明確屬性之間的數(shù)據(jù)依賴(lài)關(guān)系屬于完整性約束的表現(xiàn)形式，它定義屬性值間的相互關(guān)連（主要體現(xiàn)于值的相等與否），是數(shù)據(jù)庫(kù)模式設(shè)計(jì)的關(guān)鍵。數(shù)據(jù)依賴(lài)是數(shù)據(jù)內(nèi)在的性質(zhì)，是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象，在關(guān)系內(nèi)部表現(xiàn)為屬性與屬性之間的約束關(guān)系。其中函數(shù)依賴(lài)是最重要的一種數(shù)據(jù)依賴(lài)關(guān)系。接下來(lái)，通過(guò)一個(gè)示例來(lái)研究數(shù)據(jù)依賴(lài)對(duì)關(guān)系模式的影響。*11.1.3為什么要討論函數(shù)依賴(lài)【例11-4】設(shè)有關(guān)系模式學(xué)生(學(xué)號(hào),課程名,姓名,系名,系負(fù)責(zé)人,成績(jī))，討論這個(gè)關(guān)系模式設(shè)計(jì)的是否合理？如果不合理將產(chǎn)生哪些問(wèn)題？*

由表中可以發(fā)現(xiàn)以下問(wèn)題：（1）數(shù)據(jù)冗余問(wèn)題。（2）數(shù)據(jù)更新問(wèn)題。（3）數(shù)據(jù)插入問(wèn)題。（4）數(shù)據(jù)刪除問(wèn)題。像這樣的一些問(wèn)題，統(tǒng)稱(chēng)為操作異常。出現(xiàn)這些異常的原因是因?yàn)殛P(guān)系模式?jīng)]有設(shè)計(jì)好，也就是這個(gè)關(guān)系模式設(shè)計(jì)不合理，它的某些屬性存在著“不好”的函數(shù)依賴(lài)關(guān)系，導(dǎo)致在數(shù)據(jù)庫(kù)系統(tǒng)應(yīng)用過(guò)程中出現(xiàn)了數(shù)據(jù)冗余、更新異常、插入異常和刪除異常的問(wèn)題。*11.2關(guān)系規(guī)范化11.2.1范式11.2.2規(guī)范化實(shí)例*11.2.1范式范式是符合某一種級(jí)別的關(guān)系模式的集合關(guān)系數(shù)據(jù)庫(kù)中的關(guān)系必須滿足一定的要求。滿足不同程度要求的為不同范式范式的種類(lèi)：

第一范式(1NF)

第二范式(2NF)

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

第四范式(4NF)

第五范式(5NF)AnIntroductiontoDatabaseSystem*各種范式之間存在聯(lián)系：某一關(guān)系模式R為第n范式，可簡(jiǎn)記為R∈nNF。一個(gè)低一級(jí)范式的關(guān)系模式，通過(guò)模式分解可以轉(zhuǎn)換為若干個(gè)高一級(jí)范式的關(guān)系模式的集合，這種過(guò)程就叫規(guī)范化

AnIntroductiontoDatabaseSystem*1.第一范式（1NF）1NF的定義 如果一個(gè)關(guān)系模式R的所有屬性都是不可分的基本數(shù)據(jù)項(xiàng)，則R∈1NF第一范式是對(duì)關(guān)系模式的最起碼的要求。不滿足第一范式的數(shù)據(jù)庫(kù)模式不能稱(chēng)為關(guān)系數(shù)據(jù)庫(kù)但是滿足第一范式的關(guān)系模式并不一定是一個(gè)好的關(guān)系模式*【例11-5】說(shuō)明表11.2是否為第一范式關(guān)系*2NF的定義

定義

若R∈1NF，且每一個(gè)非主屬性完全函數(shù)依賴(lài)于碼，則R∈2NF。

*2.第二范式（2NF）

回顧【例11-4】，有關(guān)系模式學(xué)生(學(xué)號(hào),課程名,姓名,系名,系負(fù)責(zé)人,成績(jī))，在例題中已經(jīng)分析出學(xué)生關(guān)系模式的一組函數(shù)依賴(lài)F，將這些函數(shù)依賴(lài)關(guān)系可以用圖示（圖11.1）表示。由這些函數(shù)依賴(lài)關(guān)系可知：（1）滿足第一范式要求，是1NF；（2）主碼為(學(xué)號(hào),課程名)；（3）非主屬性“姓名”和“系名”部分函數(shù)依賴(lài)于主碼(學(xué)號(hào),課程名)；前面已經(jīng)分析出，這樣的關(guān)系模式不是一個(gè)好的關(guān)系模式，存在四個(gè)方面的問(wèn)題，包括：插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等。按照2NF的定義分析，發(fā)現(xiàn)產(chǎn)生問(wèn)題的原因是非主屬性“姓名”和“系名”部分函數(shù)依賴(lài)于主碼。解決方法進(jìn)行模式分解為兩個(gè)關(guān)系模式，去掉部分函數(shù)依賴(lài)。

*2.第二范式（2NF）采用投影分解法將一個(gè)1NF的關(guān)系分解為多個(gè)2NF的關(guān)系，可以在一定程度上減輕原1NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問(wèn)題。將一個(gè)1NF關(guān)系分解為多個(gè)2NF的關(guān)系，并不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。AnIntroductiontoDatabaseSystem*3.第三范式3NF3NF的定義

定義6.7

關(guān)系模式R<U，F(xiàn)>

中若不存在這樣的碼X、屬性組Y及非主屬性Z（Z

Y）,使得X→Y，Y→Z成立，Y→X，則稱(chēng)R<U，F(xiàn)>∈3NF。若R∈3NF，則每一個(gè)非主屬性既不部分依賴(lài)于碼也不傳遞依賴(lài)于碼。AnIntroductiontoDatabaseSystem*采用投影分解法將一個(gè)2NF的關(guān)系分解為多個(gè)3NF的關(guān)系，可以在一定程度上解決原2NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問(wèn)題。將一個(gè)2NF關(guān)系分解為多個(gè)3NF的關(guān)系后，仍然不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。AnIntroductiontoDatabaseSystem*11.2.2規(guī)范化實(shí)例下面仍然以【例11-4】的描述為例，完整的進(jìn)行規(guī)范化過(guò)程示例。1.已知關(guān)系模式描述設(shè)有關(guān)系模式：學(xué)生(學(xué)號(hào),課程名,姓名,系名,系負(fù)責(zé)人,成績(jī))。分析該關(guān)系模式中屬性間的依賴(lài)關(guān)系可描述為：一個(gè)學(xué)生只能在一個(gè)系中學(xué)習(xí)，一個(gè)系有若干學(xué)生；一個(gè)系對(duì)應(yīng)了一位系主任的姓名；一個(gè)學(xué)生可以選修多門(mén)課程，每學(xué)習(xí)一門(mén)課程會(huì)產(chǎn)生該課程的成績(jī)。通過(guò)學(xué)生學(xué)號(hào)可以確定學(xué)生所在的系，通過(guò)系可以確定系主任的姓名，通過(guò)學(xué)生學(xué)號(hào)和課程名可以確定該生該門(mén)課的成績(jī)。*2.規(guī)范化過(guò)程（1）判斷是否為1NF因?yàn)榇岁P(guān)系模式中，不存在屬性再分的情況，所以為1NF。（2）確定函數(shù)依賴(lài)關(guān)系根據(jù)描述得到一組函數(shù)依賴(lài)F，主碼是（學(xué)號(hào),課程名）。（3）分析該關(guān)系模式否存在問(wèn)題在第11.1.3小節(jié)中已經(jīng)分析了該關(guān)系模式存在數(shù)據(jù)冗余、插入異常、更新異常和刪除異常的問(wèn)題，說(shuō)明該關(guān)系模式規(guī)范化程度低，需要通過(guò)規(guī)范化理論對(duì)其進(jìn)行規(guī)范化，逐步降低或消除上述問(wèn)題。（4）模式分解為2NF按照2NF的定義將其進(jìn)行模式分解。由函數(shù)依賴(lài)關(guān)系出發(fā)，消除部分函數(shù)依賴(lài)，如圖11.3所示。**

將學(xué)生關(guān)系模式分解為①學(xué)生信息關(guān)系模式：學(xué)生信息(學(xué)號(hào),姓名,系名,系負(fù)責(zé)人)和②成績(jī)關(guān)系模式：成績(jī)(學(xué)號(hào),課程名,成績(jī))，這兩個(gè)關(guān)系模式符合2NF要求。表中數(shù)據(jù)如表11.4和表11.5所示。*（5）模式分解為3NF按照3NF的定義進(jìn)一步將其進(jìn)行模式分解。由符合2NF要求的關(guān)系模式函數(shù)依賴(lài)關(guān)系出發(fā)，消除傳遞函數(shù)依賴(lài)，如圖11.4所示。*

將學(xué)生信息關(guān)系模式分解為①-①學(xué)生基本信息關(guān)系模式：學(xué)生基本信息(學(xué)號(hào),姓名,系名)和①-②所在系關(guān)系模式：系(系名,系負(fù)責(zé)人)，這兩個(gè)關(guān)系模式符合3NF要求。表中數(shù)據(jù)如表11.6和表11.7所示。*

分解后得到的關(guān)系模式，可以解決11.1.3小節(jié)提出的問(wèn)題。（1）數(shù)據(jù)冗余方面，學(xué)生的基本信息和系的基本信息，可以分別存儲(chǔ)在對(duì)應(yīng)的關(guān)系模式中，不會(huì)出現(xiàn)大量的冗余和重復(fù)，節(jié)省了存儲(chǔ)空間，減少了維護(hù)數(shù)據(jù)庫(kù)為完整性的代價(jià)。（2）數(shù)據(jù)更新方面，由于進(jìn)行模式分解后，數(shù)據(jù)冗余大大減少，更新數(shù)據(jù)時(shí)的操作單一化，消除了數(shù)據(jù)不一致的隱患。（3）數(shù)據(jù)插入方面，需要插入的信息插入對(duì)應(yīng)模式即可，例如系及系負(fù)責(zé)人的信息插入系關(guān)系模式，學(xué)生信息插入學(xué)生基本信息關(guān)系模式。（4）數(shù)據(jù)刪除方面，如果某位學(xué)生放棄選修課程，需要?jiǎng)h除該生的選課信息，那么只需要在成績(jī)關(guān)系模式中刪除相應(yīng)的信息，不會(huì)影響到其他的信息*

3.問(wèn)題小結(jié)綜上所述，將最初的學(xué)生關(guān)系模式，分解為三個(gè)關(guān)系模式，分別是成績(jī)關(guān)系模式、系關(guān)系模式和學(xué)生基本信息關(guān)系模式：學(xué)生基本信息(學(xué)號(hào),姓名,系名)系(系名,系負(fù)責(zé)人),成績(jī)(學(xué)號(hào),課程名,成績(jī))這三個(gè)關(guān)系模式符合3NF要求，可以解決數(shù)據(jù)庫(kù)系統(tǒng)應(yīng)用過(guò)程中的一般問(wèn)題。*11.3模式分解11.3.1模式分解的基本要求11.3.2無(wú)損連接性和保持函數(shù)依賴(lài)11.3.32NF和3NF分解11.3.4BCNF分解*11.3.1模式分解的基本要求把低一級(jí)的關(guān)系模式分解為若干個(gè)高一級(jí)的關(guān)系模式的方法不是唯一的只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價(jià)，分解方法才有意義*關(guān)系模式分解的標(biāo)準(zhǔn)三種模式分解等價(jià)的定義：

⒈分解具有無(wú)損連接性 ⒉分解要保持函數(shù)依賴(lài)

⒊分解既要保持函數(shù)依賴(lài)，又要具有無(wú)損連接性*

設(shè)ρ=R1<U1,F1>，R2<U2,F2>，…，Rk<Uk,Fk>是R<U,F>的一個(gè)分解，U={A1，A2，…,An}，F(xiàn)為最小依賴(lài)集輸入：R、U、F、ρ

輸出：確定ρ是否具有無(wú)損連接性（1）構(gòu)造一個(gè)n列k行表。每一列對(duì)應(yīng)一個(gè)屬性，每一行對(duì)應(yīng)ρ中的一個(gè)分解Ri。若Aj∈Ui則j列i行交叉處填上aj，否則填bij。（2）檢查F中的每一個(gè)函數(shù)依賴(lài)X→A，找X所對(duì)應(yīng)的列中具有相同符號(hào)的那些行，考察這些行中A列上的元素。若其中有aj，則全部改為aj，否則全部改為bij（行號(hào)最小）。1.判別一個(gè)分解的無(wú)損連接性方法11.3.2無(wú)損連接性與保持函數(shù)依賴(lài)（3）反復(fù)進(jìn)行第二步，若發(fā)現(xiàn)某一行變成a1，a2，…，an，則分解ρ具有無(wú)損連接性；若直到檢驗(yàn)完F中的所有函數(shù)依賴(lài)也沒(méi)有發(fā)現(xiàn)這樣的行，則分解ρ是不具有無(wú)損連接性。定理:

對(duì)于R<U,F>的一個(gè)分解ρ={R1<U1,F1>，R2<U2,F2>}如果U1∩U2→U1-U2∈F+或者U1∩U2→U2-U1∈F+,

則ρ具有無(wú)損連接性。PrinciplesandAppliedofDatabase分解的無(wú)損連接性判別——舉例【例11-6】:已知R(U,F)U={A，B，C，D，E}F={AB→C，C→D，D→E}

ρ是R的一個(gè)分解R1(A,B,C),R2(C,D),R3(D,E)

請(qǐng)問(wèn)ρ是無(wú)損分解嗎?F={AB→C，C→D，D→E}第2步：使用F中的函數(shù)依賴(lài)修改表中符號(hào)第1步：構(gòu)造二維表3行5列ρ是無(wú)損分解設(shè)ρ=R1<U1,F1>，R2<U2,F2>，…，Rk<Uk,Fk>是R<U,F>的一個(gè)分解輸入：ρ

、F輸出：確定ρ是否保持函數(shù)依賴(lài)性

(1)令G=F1∪F2∪…∪Fk，檢驗(yàn)G是否覆蓋F。(2)對(duì)F中的每一個(gè)函數(shù)依賴(lài)X→Y進(jìn)行這樣的檢查：計(jì)算X在G上的屬性閉包，檢查Y是否是X在G上的屬性閉包的子集(即X→Y∈G+,)(3)若F中所有函數(shù)依賴(lài)經(jīng)檢查都屬于G+,則ρ保持函數(shù)依賴(lài)性,否則不保持函數(shù)依賴(lài)性。2.判別一個(gè)分解的函數(shù)依賴(lài)保持性方法分解的保持函數(shù)依賴(lài)性判別——舉例【例11-8】

已知R(U,F)U={A，B，C，D}F={A→B，B→C,C→D，D→A}

試判斷分解ρ={R1(A,B),R2(B,C)R3(C,D)}是否保持函數(shù)依賴(lài)。解：(1)令G=F1∪F2∪…∪FkF1={A→B，B→A}

F2={B→C，C→B}F3={C→D，D→C}G={A→B，B→A，B→C，C→B，C→D，D→C}(2)檢驗(yàn)G是否覆蓋F，F(xiàn)中前3個(gè)函數(shù)依賴(lài)已經(jīng)被G覆蓋，只需判斷

D→A是否被G覆蓋，在G上計(jì)算D的屬性閉包，檢查A是否是D在

G上的屬性閉包的子集(即D→A∈G)DG+=DCBA∵

A∈DG+

∴D→A∈G即在G上成立(3)

F中所有函數(shù)依賴(lài)經(jīng)檢查都屬于G+，即G覆蓋了F故ρ保持函數(shù)依賴(lài)性本節(jié)描述了無(wú)損連接性與保持函數(shù)依賴(lài)性的判別方法無(wú)損連接性的判別構(gòu)建二維表判別-------適合分解是任意多個(gè)關(guān)系模式采用定理判別----------僅適合分解是2個(gè)關(guān)系模式保持函數(shù)依賴(lài)性的判別基本思想------分解后各函數(shù)依賴(lài)集的并集覆蓋分解前的函數(shù)依賴(lài)集1.2NF分解方法輸入：R<U,F>輸出：2NF分解ρ（1）求出R的主碼。對(duì)于組成主碼的屬性集合的每一個(gè)子集，用它作為主碼構(gòu)成一個(gè)關(guān)系模式。（2）將那些依賴(lài)于這些主碼的屬性放到相應(yīng)的關(guān)系模式中。（3）去掉只由主碼的子集構(gòu)成的關(guān)系模式。

11.3.32NF分解和3NF分解2NF分解方法-----舉例【例11-9】:

S-M-C（Sno，Sdept，Mname，Cno，Grade）(Sno,Cno)→GradeSno→SdeptSdept→Mname(1)關(guān)系模式S-M-C惟一候的選碼為(Sno,Cno),也就是主碼。因?yàn)橛校?/p>

Sno→Sdept,Sno→Mname，存在非主屬性部分函數(shù)依賴(lài)于碼，所以該關(guān)系模式不是2NF。關(guān)系模式S-M-C主碼的屬性集合(Sno,Cno)的子集有3個(gè):

Sno、Cno、(Sno,Cno)分解為如下形式的三個(gè)關(guān)系模式：

S-M（Sno，…）

C（Cno，…）

S-C（Sno,Cno,…）

（2）將依賴(lài)于這些主碼的屬性放置到相應(yīng)的關(guān)系模式中，得到如下3個(gè)關(guān)系模式：

S-M（Sno,Sdept,Mname）

Sno→Sdept，Sdept→Mname，Sno→Mname

C（Cno）

S-C（Sno,Cno,Grade）(Sno,Cno)→Grade

（3）去掉只由主碼的子集構(gòu)成的關(guān)系模式

C（Cno）S-M-C關(guān)系模式最終分解的結(jié)果為：S-M（Sno,Sdept,Mname）S-C（Sno,Cno,Grade）分解后的關(guān)系模式的函數(shù)依賴(lài)關(guān)系：S-M：Sno→Sdept，Sno→Mname屬于2NFS-C:(Sno,Cno)→Grade屬于2NF

輸入：R<U,F>輸出：保持函數(shù)依賴(lài)的3NF分解ρ（1）對(duì)R<U,F>中F進(jìn)行“最小化處理”，處理后仍記為F。（2）找出不在F中出現(xiàn)的屬性，將這樣的屬性構(gòu)成一個(gè)關(guān)系模式。把這些屬性從U中去掉，剩余屬性仍記為U。（3）若有X→A∈F，且XA=U，則ρ={R}，算法終止。（4）否則，對(duì)F按具有左邊相同原則分組，設(shè)分為K組，每一組函數(shù)依賴(lài)Fi所涉及的全部屬性形成一個(gè)屬性集Ui。若Ui∈Uj(i≠j)，則去掉Ui，于是ρ={R1<U1,F1>，R2<U2,F2>，…，Rk<Uk,Fk>}就構(gòu)成R<U,F>的一個(gè)保持函數(shù)依賴(lài)的分解，且每個(gè)Ri<Ui,Fi>均屬于3NF。2.3NF分解方法輸入：R<U,F>輸出：既有無(wú)損連接性又保持函數(shù)依賴(lài)的3NF分解τ（1）設(shè)X是R<U,F>的一個(gè)候選碼。R<U,F>已由上面3NF方法分解得到ρ={R1<U1,F1>，R2<U2,F2>，…，Rk<Uk,Fk>}，令τ=ρ

∪{R*<X,Fx>}。（2）若有某個(gè)Ui，X屬于Ui，則將R*<X,Fx>從τ中去掉。（3）τ就是所求的既有無(wú)損連接性又保持函數(shù)依賴(lài)的達(dá)到3NF的分解。2.既有無(wú)損連接性又保持函數(shù)依賴(lài)的3NF分解方法3NF分解——舉例【例11-10】

已知R(U,F)U={C，H，R，S，G，T}Fm={C→T，CS→G,HT→R，HR→C，HS→R}

求:（1）R的一個(gè)具有保持函數(shù)依賴(lài)性的3NF分解；（2）R的一個(gè)具有保持函數(shù)依賴(lài)性和具有無(wú)損連接性的3NF分解。解（1）通過(guò)求屬性閉包得到R的碼為HS（2）按左邊相同的原則，將Fm分為5組R1（U1,F1）U1=CTF1=C→TR2（U2,F2）U2=CSGF2=CS→GR3（U3,F3）U3=HTRF3=HT→RR4（U4,F4）U4=HRCF4=HR→CR5（U5,F5）U5=HSRF5=HS→Rρ={R1<U1,F1>，R2<U2,F2>，R3<U3,F3>，R4<U4,F4>，

R5<U5,F5>}保持函數(shù)依賴(lài)性的3NF分解

（3）τ=ρ

∪{R*<X,Fx>}=ρ

∪{R*<HS,Φ>}

∵

R*中屬性HS是U5的子集∴去掉R*故τ=ρ

例題中的第3步還可以這樣做：判別ρ的無(wú)損連接性ρ={R1<U1,F1>,R2<U2,F2>,R3<U3,F3>,R4<U4,F4>,R5<U5,F5>}保持函數(shù)依賴(lài)性的3NF分解通過(guò)構(gòu)建二維表判別ρ的具有無(wú)損連接性本節(jié)講授了2NF和3NF的分解方法2NF的分解基本思想-------主要依據(jù)主碼的子集進(jìn)行分解3NF的分解分為兩個(gè)標(biāo)準(zhǔn)保持函數(shù)依賴(lài)的分解分解既要保持函數(shù)依賴(lài)，又要具有無(wú)損連接性基本步驟：（1）令ρ={R<U,F>}（2）檢查ρ中各關(guān)系模式是否均屬于BCNF。若是，則算法終止。（3）設(shè)ρ中Ri<Ui,Fi>不屬于BCNF，則必有X→A∈Fi+（A不屬于X），且X非Ri的碼。因此，XA是Ui的真子集。對(duì)Ri進(jìn)行分解：σ={Ri1，Ri2},URi1=XA，URi2=Ui-{A}，以σ代替Ri<Ui,Fi>返回第2步。

11.3.4BCNF分解BCNF分解——舉例【例11-11】

設(shè)有關(guān)系模式R（A，B，C，D）其函數(shù)依賴(lài)集Fm={A→C，C→A，B→C，D→C}；(1)求出R的所有碼；(2)將R分解為BCNF，使它具有無(wú)損連接性。解

(1)∵(BD)+=BDCA

又(B)+=BCA(D)+=DCA

可得（BD）→U故（BD）為R的惟一碼(2)將R分解為BCNF

F①令ρ={R<U,F>}②檢查ρ中各關(guān)系模式是否均屬于BCNF。若是，則算法終止。

∵A→C左邊非碼，∴R沒(méi)有達(dá)到BCNF③將R分解為R1和R2U1={A,C}U2=U