關(guān)系數(shù)據(jù)庫理論(規(guī)范化、求解候選碼、范式)

第4部分

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

4.1問題的提出4.1.1概念回顧4.1.2關(guān)系模式的形式化定義4.1.3什么是數(shù)據(jù)依賴4.1.4關(guān)系模式的簡化定義4.1.5數(shù)據(jù)依賴對關(guān)系模式影響4.1.1概念回顧關(guān)系：描述實(shí)體、屬性、實(shí)體間的聯(lián)系。關(guān)系模式：用來定義關(guān)系的邏輯結(jié)構(gòu)。關(guān)系數(shù)據(jù)庫：基于關(guān)系模型的數(shù)據(jù)庫，利用關(guān)系來描述現(xiàn)實(shí)世界。關(guān)系數(shù)據(jù)庫模式：定義這組關(guān)系的關(guān)系模式的全體。4.1.2關(guān)系模式的形式化定義關(guān)系模式由五部分組成，即它是一個(gè)五元組：

R(U,D,DOM,F)R：關(guān)系名U：組成該關(guān)系的屬性名集合D：屬性組U中屬性所來自的域DOM：屬性向域的映象集合F：屬性間數(shù)據(jù)的依賴關(guān)系集合4.1.3什么是數(shù)據(jù)依賴(1)完整性約束的表現(xiàn)形式限定屬性取值范圍：例如學(xué)生成績必須在0-100之間。定義屬性值間的相互關(guān)連（主要體現(xiàn)于值的相等與否），這就是數(shù)據(jù)依賴，它是數(shù)據(jù)庫模式設(shè)計(jì)的關(guān)鍵。4.1.3什么是數(shù)據(jù)依賴(2)數(shù)據(jù)依賴是通過一個(gè)關(guān)系中屬性間值的相等與否體現(xiàn)出來的數(shù)據(jù)間的相互關(guān)系是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象是數(shù)據(jù)內(nèi)在的性質(zhì)是語義的體現(xiàn)4.1.3什么是數(shù)據(jù)依賴(3)數(shù)據(jù)依賴的類型函數(shù)依賴（FunctionalDependency，簡記為FD）多值依賴（MultivaluedDependency，簡記為MVD）其他4.1.4關(guān)系模式的簡化表示關(guān)系模式R（U,D,DOM,F）簡化為一個(gè)三元組：

R（U,F）當(dāng)且僅當(dāng)U上的一個(gè)關(guān)系r滿足F時(shí)，r稱為關(guān)系模式R（U,F）的一個(gè)關(guān)系4.1.5數(shù)據(jù)依賴對關(guān)系模式的影響例：描述學(xué)校的信息： 學(xué)生的學(xué)號(hào)（Sno）、所在系（Sdept） 系主任姓名（Mname）、課程名（Cname） 成績（Grade）4.1.5數(shù)據(jù)依賴對關(guān)系模式的影響學(xué)校數(shù)據(jù)庫的語義：

(1)

一個(gè)系有若干學(xué)生，一個(gè)學(xué)生只屬于一個(gè)系；

(2)一個(gè)系只有一名主任；

(3)一個(gè)學(xué)生可以選修多門課程，每門課程有若干學(xué)生選修；

(4)

每個(gè)學(xué)生所學(xué)的每門課程都有一個(gè)成績。4.1.5數(shù)據(jù)依賴對關(guān)系模式的影響

屬性組U上的一組函數(shù)依賴F：

F＝｛Sno→Sdept,Sdept→Mname,(Sno,Cname)→Grade｝單一的關(guān)系模式：Student<U、F>U＝｛Sno,Sdept,Mname,Cname,Grade｝關(guān)系模式Student<U,F>中存在的問題(1)數(shù)據(jù)冗余太大浪費(fèi)大量的存儲(chǔ)空間(2)

更新異常（UpdateAnomalies）數(shù)據(jù)冗余，更新數(shù)據(jù)時(shí)，維護(hù)數(shù)據(jù)完整性代價(jià)大。(3)插入異常（InsertionAnomalies）該插的數(shù)據(jù)插不進(jìn)去(4)

刪除異常（DeletionAnomalies）不該刪除的數(shù)據(jù)不得不刪

4.1.5數(shù)據(jù)依賴對關(guān)系模式的影響結(jié)論：Student關(guān)系模式不是一個(gè)好的模式?！昂谩钡哪Ｊ讲粫?huì)發(fā)生插入異常、刪除異常、更新異常，數(shù)據(jù)冗余應(yīng)盡可能少。原因：由存在于模式中的某些數(shù)據(jù)依賴引起的解決方法：通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴4關(guān)系數(shù)據(jù)理論4.1問題的提出4.2規(guī)范化4.3模式的分解4.2規(guī)范化

規(guī)范化理論用來改造關(guān)系模式，通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問題。4.2.1函數(shù)依賴(1)函數(shù)依賴(2)平凡函數(shù)依賴與非平凡函數(shù)依賴(3)完全函數(shù)依賴與部分函數(shù)依賴(4)傳遞函數(shù)依賴(1)函數(shù)依賴【定義】設(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。

X稱為這個(gè)函數(shù)依賴的決定屬性集(Determinant)。(1)函數(shù)依賴1)函數(shù)依賴不是指關(guān)系模式R的某個(gè)或某些關(guān)系實(shí)例滿足的約束條件，而是指R的所有關(guān)系實(shí)例均要滿足的約束條件。2)函數(shù)依賴是語義范疇的概念。只能根據(jù)數(shù)據(jù)的語義來確定函數(shù)依賴。3)

數(shù)據(jù)庫設(shè)計(jì)者可以對現(xiàn)實(shí)世界作強(qiáng)制的規(guī)定。(1)函數(shù)依賴?yán)?Student(Sno,Sname,Ssex,Sage,Sdept)

假設(shè)不允許重名，則有:Sno→Ssex，Sno→Sage,Sno→Sdept，Sno←→Sname,Sname→Ssex，Sname→SageSname→Sdept若X→Y，并且Y→X,則記為X←→Y。若Y不函數(shù)依賴于X,則記為X─→Y。(2)平凡函數(shù)依賴與非平凡函數(shù)依賴在關(guān)系模式R(U)中，對于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(2)平凡函數(shù)依賴與非平凡函數(shù)依賴于任一關(guān)系模式，平凡函數(shù)依賴都是必然成立的，它不反映新的語義，因此若不特別聲明，我們總是討論非平凡函數(shù)依賴。三、完全函數(shù)依賴與部分函數(shù)依賴【定義6.2】在關(guān)系模式R(U)中，如果X→Y，并且對于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

四、傳遞函數(shù)依賴【定義6.3】

在關(guān)系模式R(U)中，如果X→Y，Y→Z，且YX，Y→X，則稱Z傳遞函數(shù)依賴于X。注:如果Y→X，即X←→Y，則Z直接依賴于X。Sno→Sdept，Sdept→MnameMname傳遞函數(shù)依賴于Sno例:在關(guān)系Std(Sno,Sdept,Mname)中，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）。主屬性與非主屬性ALLKEY外部碼【定義6.5】關(guān)系模式R中屬性或?qū)傩越MX并非R的碼，但X是另一個(gè)關(guān)系模式的碼，則稱X是R的外部碼（Foreignkey）也稱外碼。主碼又和外部碼一起提供了表示關(guān)系間聯(lián)系的手段。候選碼求解給定關(guān)系模式和函數(shù)依賴集F，可將屬性分成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)的屬性。候選碼求解（1）L類屬性一定是候選碼中的成員；（2）R類屬性一定不在任何候選碼中；（3）N類屬性一定是候選碼中的成員；（4）LR類屬性需要進(jìn)一步判斷。候選碼求解輸入：關(guān)系模式R及其函數(shù)依賴集F輸出：R的所有候選碼候選碼求解方法：（1）將R所有屬性分為L、R、N、LR四類，并令X代表L、N兩類，Y代表LR類；（2）求X+，若X+包含了R的全部屬性，則X即為R的唯一候選碼，轉(zhuǎn)（5）；否則轉(zhuǎn)（3）（3）在Y中取一屬性A，求（XA）+。若它包含了R的全部屬性，則XA是一個(gè)候選碼；調(diào)換一屬性反復(fù)進(jìn)行這一過程，直到試完Y中的屬性；（4）如果已經(jīng)找出所有候選碼，則轉(zhuǎn)（5）；否則在Y中依次取兩個(gè)、三個(gè)、...，求它們的閉包，直到閉包含有R的所有屬性。（5）停止，輸出結(jié)果。6.2.3范式范式是符合某一種級(jí)別的關(guān)系模式的集合。關(guān)系數(shù)據(jù)庫中的關(guān)系必須滿足一定的要求。滿足不同程度要求的為不同范式。范式的種類：

第一范式(1NF)

第二范式(2NF)

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

第四范式(4NF)

第五范式(5NF)6.2.3范式各種范式之間存在聯(lián)系：某一關(guān)系模式R為第n范式，可簡記為R∈nNF。6.2.42NF1NF的定義 如果一個(gè)關(guān)系模式R的所有屬性都是不可分的基本數(shù)據(jù)項(xiàng)，則R∈1NF。第一范式是對關(guān)系模式的最起碼的要求。不滿足第一范式的數(shù)據(jù)庫模式不能稱為關(guān)系數(shù)據(jù)庫。但是滿足第一范式的關(guān)系模式并不一定是一個(gè)好的關(guān)系模式。2NF2NF的定義

【定義6.6】若關(guān)系模式R∈1NF，并且每一個(gè)非主屬性都完全函數(shù)依賴于R的碼，則R∈2NF。2NF采用投影分解法將一個(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.53NF

【定義6.7】關(guān)系模式R<U，F(xiàn)>

中若不存在這樣的碼X、屬性組Y及非主屬性Z（ZY）,使得X→Y，Y→X，Y→Z，成立，則稱R<U，F(xiàn)>∈3NF。3NF若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ù)冗余。3NF例：在關(guān)系模式STJ（S，T，J）中，S表示學(xué)生，T表示教師，J表示課程。每一教師只教一門課。每門課由若干教師教，某一學(xué)生選定某門課，就確定了一個(gè)固定的教師。某個(gè)學(xué)生選修某個(gè)教師的課就確定了所選課的名稱：

(S，J)→T，(S，T)→J，T→J6.2.6BC范式（BCNF）【定義6.8】設(shè)關(guān)系模式R<U，F(xiàn)>∈1NF，如果對于R的每個(gè)函數(shù)依賴X→Y，若Y不屬于X，則X必含有候選碼，那么R∈BCNF。若R∈BCNF每一個(gè)決定屬性集（因素）都包含（候選）碼R中的所有屬性（主，非主屬性）都完全函數(shù)依賴于碼R∈3NFBCNF例：在關(guān)系模式STJ（S，T，J）中，S表示學(xué)生，T表示教師，J表示課程。每一教師只教一門課。每門課由若干教師教，某一學(xué)生選定某門課，就確定了一個(gè)固定的教師。某個(gè)學(xué)生選修某個(gè)教師的課就確定了所選課的名稱：

(S，J)→T，(S，T)→J，T→J6.2.6BCNF

SJTSTJSTJBCNFSTJ∈3NF

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

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

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

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

沒有任何屬性對碼的部分函數(shù)依賴和傳遞函數(shù)依賴SJSTTJTJ3NF與BCNF的關(guān)系如果關(guān)系模式R∈BCNF，必定有R∈3NF如果R∈3NF，且R只有一個(gè)候選碼，則R必屬于BCNF。BCNF的關(guān)系模式所具有的性質(zhì)⒈所有非主屬性都完全函數(shù)依賴于每個(gè)候選碼⒉所有主屬性都完全函數(shù)依賴于每個(gè)不包含它的候選碼⒊沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性函數(shù)依賴總結(jié)⒈3NF和BCNF是在函數(shù)依賴的條件下對模式分解所能達(dá)到的分離程度的測度。⒉一個(gè)模式中的關(guān)系模式如果都屬于BCNF，那么在函數(shù)依賴范疇內(nèi)，它已經(jīng)實(shí)現(xiàn)了徹底分離，已經(jīng)解決了插入異常、刪除異常等問題。*6.2.7多值依賴與第四范式（4NF）例:學(xué)校中某一門課程由多個(gè)教師講授，他們使用相同的一套參考書。 關(guān)系模式Teaching(C,T,B)

課程C、教師T和參考書B………課程C教員T參考書B

物理

數(shù)學(xué)

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

李勇張平

張平周峰

普通物理學(xué)光學(xué)原理物理習(xí)題集

數(shù)學(xué)分析微分方程高等代數(shù)

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

表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

6.2.7多值依賴與第四范式（4NF）Teaching∈BCNF:Teach具有唯一候選碼(C，T，B)，即全碼Teaching模式中存在的問題

(1)數(shù)據(jù)冗余度大：有多少名任課教師，參考書就要存儲(chǔ)多少次

6.2.7多值依賴與第四范式（4NF）

(2)插入操作復(fù)雜：當(dāng)某一課程增加一名任課教師時(shí)，該課程有多少本參照書，就必須插入多少個(gè)元組例如物理課增加一名教師劉關(guān)，需要插入兩個(gè)元組：

（物理，劉關(guān)，普通物理學(xué)）（物理，劉關(guān)，光學(xué)原理）6.2.7多值依賴與第四范式（4NF）(3)刪除操作復(fù)雜：某一門課要去掉一本參考書，該課程有多少名教師，就必須刪除多少個(gè)元組(4)修改操作復(fù)雜：某一門課要修改一本參考書，該課程有多少名教師，就必須修改多少個(gè)元組產(chǎn)生原因 存在多值依賴（MVD）一、多值依賴【定義6.9】設(shè)R(U)是一個(gè)屬性集U上的一個(gè)關(guān)系模式，X、Y和Z是U的子集，并且Z＝U－X－Y，多值依賴

X→→Y成立當(dāng)且僅當(dāng)對R的任一關(guān)系r，r在（X，Z）上的每個(gè)值對應(yīng)一組Y的值，這組值僅僅決定于X值而與Z值無關(guān)。

例：Teaching（C,T,B）對于C的每一個(gè)值，T有一組值與之對應(yīng)，而不論B取何值一、多值依賴在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。

sxy2z2txy1

z1wx

y1z1vxy2z2一、多值依賴平凡多值依賴和非平凡的多值依賴

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

X→→Y為平凡的多值依賴 否則稱X→→Y為非平凡的多值依賴多值依賴的性質(zhì)（1）多值依賴具有對稱性若X→→Y，則X→→Z，其中Z＝U－X－Y

（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。多值依賴與函數(shù)依賴的區(qū)別(1)有效性多值依賴的有效性與屬性集的范圍有關(guān)若X→→Y在U上成立，則在W（XYWU）上一定成立；反之則不然，即X→→Y在W（WU）上成立，在U上并不一定成立。多值依賴的定義中不僅涉及屬性組X和Y，而且涉及U中其余屬性Z。一般地，在R（U）上若有X→→Y在W（WU）上成立，則稱X→→Y為R（U）的嵌入型多值依賴多值依賴與函數(shù)依賴的區(qū)別只要在R（U）的任何一個(gè)關(guān)系r中，元組在X和Y上的值滿足【定義6.l】（函數(shù)依賴），則函數(shù)依賴X→Y在任何屬性集W（XYWU）上成立。一、多值依賴(2)

若函數(shù)依賴X→Y在R（U）上成立，則對于任何Y'Y均有X→Y'成立多值依賴X→→Y若在R(U)上成立，不能斷言對于任何Y'Y有X→→Y'成立二、第四范式（4NF）【定義6.10】關(guān)系模式R<U，F(xiàn)>∈1NF，如果對于R的每個(gè)非平凡多值依賴X→→Y（YX），X都含有候選碼，則R∈4NF。

如果R∈4NF，則R∈BCNF

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

允許的是函數(shù)依賴（是平凡多值依賴）第四范式（續(xù)）例：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.8規(guī)范化關(guān)系數(shù)據(jù)庫的規(guī)范化理論是數(shù)據(jù)庫邏輯設(shè)計(jì)的工具。一個(gè)關(guān)系只要其分量都是不可分的數(shù)據(jù)項(xiàng)，它就是規(guī)范化的關(guān)系，但這只是最基本的規(guī)范化。規(guī)范化程度可以有多個(gè)不同的級(jí)別6.2.8規(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.8規(guī)范化關(guān)系模式規(guī)范化的基本步驟

1NF

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

↓消除主屬性對碼的部分和傳遞函數(shù)依 賴

BCNF

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

4NF規(guī)范化的基本思想消除不合適的數(shù)據(jù)依賴采用“一事一地”的模式設(shè)計(jì)原則所謂規(guī)范化實(shí)質(zhì)上是概念的單一化6.2.8規(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ī)范化步驟可以在其中任何一步終止練習(xí)關(guān)系規(guī)范化中的刪除異常是指（），插入操作異常是指（）。關(guān)系規(guī)范化是為解決關(guān)系數(shù)據(jù)庫中（）問題而引入的。在關(guān)系DB中，任何一個(gè)二元關(guān)系模式的最高范式必定是（）。當(dāng)屬性B函數(shù)依賴于屬性A時(shí)，屬性A和B的聯(lián)系是（）。關(guān)系模式中各范式之間的關(guān)系是（）。如下所示的關(guān)系R是（）范式。零件號(hào)單價(jià)P125P28P325P49練習(xí)7.關(guān)系模式STJ(S#,T,J#)中，存在函數(shù)依賴(S#,J#)→T，(S#,T)→J#，T→J#，則關(guān)系STJ滿足（）范式。8.設(shè)有如下關(guān)系R，R的候選碼是（），R中的函數(shù)依賴有（），R屬于（）范式。ADEA1d1e2A2d6e2A3d4e3A4d4e49.對非規(guī)范化的模式，經(jīng)過（）轉(zhuǎn)變?yōu)?NF，將1NF經(jīng)過（）轉(zhuǎn)變?yōu)?NF，將2NF經(jīng)過（）轉(zhuǎn)變?yōu)?NF，將3NF經(jīng)過（）轉(zhuǎn)變?yōu)锽CNF。練習(xí)10.判斷以下關(guān)系屬于第幾范式（1）R(X,Y,Z)，F(xiàn)={Y→Z,Y→X,X→Y,X→Z}X、Y是候選碼。Z是非主屬性。不存在Z對碼的部分和傳遞依賴，每個(gè)決定因素都包含碼。是BC范式。

（2）R(X,Y,Z)，F(xiàn)={YZ→X，X→Z}XY、YZ是候選碼。沒有非主屬性。決定因素X不包含碼，所以是第3范式。練習(xí)10.判斷以下關(guān)系屬于第幾范式（3）R(X,Y,Z)，F(xiàn)={XY→Z}XY是候選碼。是BC范式。

（4）R（W,X,Y,Z}，F(xiàn)={WX→Z,Z→Y}WX是候選碼。非主屬性Z和Y。存在Y對碼的傳遞依賴，是第2范式。練習(xí)11.求解以下關(guān)系的候選碼(1).R（ABCDE），F(xiàn)＝{A→D,E→D,D→B,BC→D,CD→AL={CE},CE是候選碼

2．R(F,G,H,I,J),F={F→I,J→I,I→G,GH→I,IH→F}L={JH},JH是候選碼

3.

W(C,P,S,G,T,R),F={C→G,SC→G,TR→C,TP→R,TS→R}關(guān)系模式W的碼是()，W的規(guī)范化程度最高達(dá)到()。L={PST},PST是碼，存在R對碼的部分依賴，最高達(dá)到1NF

*6.3數(shù)據(jù)依賴的公理系統(tǒng)邏輯蘊(yùn)含

【定義6.11】對于滿足一組函數(shù)依賴

F的關(guān)系模式R<U，F(xiàn)>，其任何一個(gè)關(guān)系r，若函數(shù)依賴X→Y都成立,則稱

F邏輯蘊(yùn)含X→YArmstrong公理系統(tǒng)一套推理規(guī)則，是模式分解算法的理論基礎(chǔ)。用途求給定關(guān)系模式的碼從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴1.Armstrong公理系統(tǒng)

對關(guān)系模式R<U,F>來說有以下的推理規(guī)則：Al.自反律（Reflexivity）：若Y

X

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

U，則XZ→YZ為F所蘊(yùn)含。A3.傳遞律（Transitivity）：若X→Y及Y→Z為F所蘊(yùn)含，則X→Z為F所蘊(yùn)含。 注意：由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴，自反律的使用并不依賴于F定理6.lArmstrong推理規(guī)則是正確的

（了解）（l）自反律:若Y

X

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

X

U

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

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

X，有t[y]=s[y]，所以X→Y成立.自反律得證定理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)含.增廣律得證。(3)傳遞律：若X→Y及Y→Z為F所蘊(yùn)含，則X→Z為F所蘊(yùn)含。證：設(shè)X→Y及Y→Z為F所蘊(yùn)含。對R<U，F(xiàn)>

的任一關(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.導(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）導(dǎo)出規(guī)則2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理6.1

【引理6.l】

X→A1A2…Ak成立的充分必要條件是X→Ai成立（i=l，2，…，k）。3.函數(shù)依賴閉包【定義6.l2】在關(guān)系模式R<U，F(xiàn)>中為F所邏輯蘊(yùn)含的函數(shù)依賴的全體叫作F的閉包，記為F+?！径x6.13】設(shè)F為屬性集U上的一組函數(shù)依賴，X

U，XF+={A|X→A能由F根據(jù)Armstrong公理導(dǎo)出}，XF+稱為屬性集X關(guān)于函數(shù)依賴集F的閉包。F的閉包R(X,Y,Z),F={XY,YZ}F+={Xφ,Yφ,Zφ,XYφ,XZφ,YZφ,XYZφ,XX,XY,XZ,XXY,XXZ,XYZ,XXYZ,YY,YZ,YYZ,ZZ,XYX,XYY,XYZ,XYXY,XYYZ,XYXZ,XYXYZ,XZX,XZY,XZZ,XZXY,XZXZ,XZXY,XZXYZ,YZY,YZZ,YZYZ,XYZX,XYZY,XYZZ,XYZXY,XYZYZ,XYZXZ,XYZXYZ}關(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+的子集的問題求閉包的算法算法6.l求屬性集X（X

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

輸入：X，F(xiàn)輸出：XF+步驟：（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）

算法6.l（4）判斷X（i+1）=X

（i）嗎?（5）若相等或X（i）=U,則X（i）就是XF+,

算法終止。（6）若否，則i=i+l，返回第（2）步。對于算法6.l，令ai=|X（i）|，{ai}形成一個(gè)步長大1的嚴(yán)格遞增的序列，序列的上界是|U|，因此該算法最多|U|-|X|次循環(huán)就會(huì)終止。函數(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ù)依賴閉包(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。

U={A,B,C,D};F={AB,BCD};A+=？C+=？(AC)+=？例：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+5.函數(shù)依賴集等價(jià) 【定義6.14】如果G+=F+，就說函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價(jià)。函數(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+。函數(shù)依賴集等價(jià)要判定F

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

就行了。因此引理6.3給出了判斷兩個(gè)函數(shù)依賴集等價(jià)的可行算法。6.最小依賴集【定義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à)。最小依賴集[例2]對于6.l節(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à)7.極小化過程【定理6.3】每一個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)極小函數(shù)依賴集Fm。此Fm稱為F的最小依賴集

引理6.1保證了F變換前后的等價(jià)性。依據(jù)定義分三步對F進(jìn)行“極小化處理”，找出F的一個(gè)最小依賴集。(1)逐一檢查F中各函數(shù)依賴FDi：X→Y，若Y=A1A2

…Ak，k>2，則用{X→Aj|j=1，2，…，k}來取代X→Y。

極小化過程(2)逐一檢查F中各函數(shù)依賴FDi：X→A，令G=F-{X→A}，若AXG+，則從F中去掉此函數(shù)依賴。由于F與G=F-{X→A}等價(jià)的充要條件是AXG+

因此F變換前后是等價(jià)的。極小化過程(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à)的。極小化過程

由定義，最后剩下的F就一定是極小依賴集。因?yàn)閷的每一次“改造”都保證了改造前后的兩個(gè)函數(shù)依賴集等價(jià)，因此剩下的F與原來的F等價(jià)。證畢定理6.3的證明過程也是求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}極小化過程極小化過程(定理6.3的證明)也是檢驗(yàn)F是否為極小依賴集的一個(gè)算法若改造后的F與原來的F相同，說明F本身就是一個(gè)最小依賴集F的最小依賴集Fm不一定是唯一的，它與對各函數(shù)依賴FDi

及X→A中X各屬性的處置順序有關(guān)。極小化過程在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)系。6.4模式的分解把低一級(jí)的關(guān)系模式分解為若干個(gè)高一級(jí)的關(guān)系模式的方法并不是唯一的只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價(jià)，分解方法才有意義關(guān)系模式分解的標(biāo)準(zhǔn)三種模式分解的等價(jià)定義⒈分解具有無損連接性⒉分解要保持函數(shù)依賴⒊分解既要保持函數(shù)依賴，又要具有無損連接性模式的分解（續(xù)）定義5.16關(guān)系模式R<U,F>的一個(gè)分解：ρ={R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>}U=U1∪U2∪…∪Un，且不存在Ui

Uj，F(xiàn)i為F在Ui上的投影定義5.17函數(shù)依賴集合{X→Y|X→Y

F+∧XY

Ui}的一個(gè)覆蓋Fi

叫作F在屬性Ui上的投影模式的分解（續(xù)）例:SL（Sno，Sdept，Sloc）

F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}SL∈2NF存在插入異常、刪除異常、冗余度大和修改復(fù)雜等問題分解方法可以有多種模式的分解（續(xù)）SL──────────────────Sno Sdept Sloc──────────────────95001CSA95002ISB95003MAC95004ISB95005 PH B──────────────────模式的分解（續(xù)）1.SL分解為下面三個(gè)關(guān)系模式：

SN(Sno)SD(Sdept)SO(Sloc)分解后的關(guān)系為：SN────SD─────SO────SnoSdeptSloc─────────────95001CSA95002ISB95003MAC95004PH────95005─────────模式的分解（續(xù)）

分解后的數(shù)據(jù)庫丟失了許多信息例如無法查詢95001學(xué)生所在系或所在宿舍。如果分解后的關(guān)系可以通過自然連接恢復(fù)為原來的關(guān)系，那么這種分解就沒有丟失信息模式的分解（續(xù)）2.SL分解為下面二個(gè)關(guān)系模式：

NL(Sno,Sloc)DL(Sdept,Sloc)分解后的關(guān)系為：

NL────────────DL───────────SnoSlocSdeptSloc──────────────────────95001A CSA95002B ISB95003C MAC95004B PHB95005B──────────────────模式的分解（續(xù)）NLDL─────────────SnoSlocSdept─────────────95001ACS95002BIS95002BPH95003CMA95004BIS95004BPH95005BIS95005BPH模式的分解（續(xù)） NLDL比原來的SL關(guān)系多了3個(gè)元組

無法知道95002、95004、95005

究竟是哪個(gè)系的學(xué)生

元組增加了，信息丟失了第三種分解方法3.將SL分解為下面二個(gè)關(guān)系模式：

ND(Sno,Sdept)NL(Sno,Sloc)

分解后的關(guān)系為：

模式的分解（續(xù)）ND──────