基于某個數據庫管理系統設計數據庫，如何基于數據庫系統編程第6章關系數據理論第7章數據庫設計第8章數據庫編程問題的提出規范化數據依賴的公理系統*6.4

模式的分解6.5

小結An

Introdr

uctiotnioto

Do

ataabasae

System關系數據庫邏輯設計針對具體問題，如何構造一個適合于它的數據模式數據庫邏輯設計的工具──關系數據庫的規范化理論*關系模式由五部分組成，是一個五元組：R(U,

D,

DOM,

F)關系名R是符號化的元組語義U為一組屬性D為屬性組U中的屬性所來自的域DOM為屬性到域的F為屬性組U上的一組數據依賴由于D、DOM與模式設計關系不大，因此在本章中把關系模式看作一個三元組：R<U,F>當且僅當U上的一個關系r滿足F時，r稱為關系模式R<U,F>的一個關系作為二維表，關系要符合一個最基本的條件：每個分量必須是不可分開的數據項。滿足了這個條件的關系模式就屬于第一范式（1NF）數據依賴是一個關系

屬性與屬性之間的一種約束關系通過屬性間值的相等與否體現出來的數據間相互聯系是現實世界屬性間相互聯系的抽象是數據內在的性質是語義的體現**數據依賴的主要類型函數依賴（Functional

Dependency，簡記為FD）多值依賴（Multi-Valued

Dependency，簡記為MVD）函數依賴普遍存在于現實生活中描述一個學生關系，可以有學號、

、系名等屬性。一個學號只對應一個學生，一個學生只在一個系中學習“學號”值確定后，學生的

及所在系的值就被唯一確定。Sname=

o)，Sdept=

o)即Sno函數決定SnameSno函數決定Sdept記作Sno→Sname，Sno→Sdept*[例6.1]

建立一個描述學校教務的數據庫。涉及的對象包括：學生的學號（Sno）所在系（Sdept）系

（Mname）課程號（Cno）成績（Grade）*假設學校教務的數據庫模式用一個單一的關系模式Student來表示，則該關系模式的屬性集合為：U

＝{Sno,

Sdept,

Mname,

Cno,

Grade}現實世界的已知事實（語義）：一個系有若干學生，

但一個學生只屬于一個系；一個系只有一名（正職）

；一個學生可以選修多門課程，每門課程有若干學生選修；每個學生學習每一門課程有一個成績。*由此可得到屬性組U上的一組函數依賴F：F={Sno→Sdept,

Sdept→

Mname,

(Sno,

Cno)→

Grade}SnoCnoSdeptMnameGrade*關系模式Student<U,F>中存在的問題：1

數據冗余浪費大量的每一個系空間的

重復出現，重復次數與該系所有學生的所有課程成績出現次數相同。*（2）更新異常（Update

Anomalies）數據冗余

，更新數據時，

數據完整性代價大。某系更換系

后，必須修改與該系學生有關的每一個元組。*（3）

異常（Insertion

Anomalies）如果一個系剛成立，尚無學生，則無法把這個系及其系

的信息存入數據庫。*（4）刪除異常（Deletion

Anomalies）如果某個系的學生全部畢業了，

則在刪除該系學生信息的同時，把這個系及其系

的信息也丟掉了。*結論Student關系模式不是一個好的模式。異常、刪除異常和更一個“好”的模式應當不會發生新異常，數據冗余應盡可能少。原因由存在于模式中的某些數據依賴引起的。解決方法用規范化理論改造關系模式來消除其中不合適的數據依賴*把這個單一的模式分成三個關系模式：S(Sno,Sdept,Sno

→

Sdept);SC(

o,Grade,( o)

→

Grade);DEPT(Sdept,Mname,Sdept

→

Mname);這三個模式都不會發生

異常、刪除異常的問題，數據的冗余也得到了控制。*問題的提出規范化數據依賴的公理系統*6.4

模式的分解6.5

小結函數依賴碼范式2NF3NFBCNF多值依賴4NF規范化小結函數依賴平凡函數依賴與非平凡函數依賴完全函數依賴與部分函數依賴傳遞函數依賴*定義6.1設R(U)是一個屬性集U上的關系模式，X和Y是U的子集。若對于R(U)的任意一個可能的關系r，r

中不可能存在兩個元組在X上的屬性值相等，而在Y上的屬性值不等，則稱“X函數確定Y”或“Y函數依賴于X”，記作X→Y。[例]Student(Sno,Sname,Ssex,

Sage,

Sdept),假設不允許重名，則有:Sno

→

Ssex，Sno

→

Sdept，Sno

→

SageSno

←→

SnameSname

→

Ssex，

Sname

→SageSname

→

Sdept但Ssex

→Sage,Ssex→Sdept若X→Y，并且Y→X,則記為X←→Y。若Y不函數依賴于X,則記為X→Y。SnoSnameeptS1S1S3S4男

20

計算機系女

21

自動化系男

20

計算機系男

21

計算機系S5男

20計算機系.........

......違背了Sno

→Snames

g由下面的關系表,能否得出Sno→SnameSnoSnameSsexSageSdeptS1男20計算機系S2女21自動化系S3男20計算機系S4男21計算機系S5男20計算機系..........函數依賴不是指關系模式R的某個或某些關系實例滿足的

約束條件，而是指R的所有關系實例均要滿足的約束條件。函數依賴是語義范疇的概念，只能根據數據的語義來確定一個函數依賴。例如“

→

”這個函數依賴只有在不允許有同名人的條件下成立*X→Y，但Y?X則稱X→Y是非平凡的函數依賴。X→Y，但Y?X

則稱X→Y是平凡的函數依賴。對于任一關系模式，平凡函數依賴都是必然成立的，它不反映新的語義。若不特別

， 總是 非平凡函數依賴。**若X→Y，則X稱為這個函數依賴的決定因素（Determinant）。若X→Y，Y→X，則記作X←→Y。若Y不函數依賴于X，則記作X?Y。*定義6.2

在R(U)中，如果X→Y，并且對于X的任何一個真子集X’,

都有

X’

?Y,

則稱Y對X完全函數依賴，記作X

→F

Y。若X→Y，但Y不完全函數依賴于X，則稱Y對X部分函數依賴，記作X

P→Y*[例]在關系SC(Sno,Cno,Grade)中，有：由于：Sno

?Grade，Cno

?Grade，因此：(Sno,

Cno)

GradeF→(Sno,

Cno)→P

Sno(Sno,

Cno)

→P

Cno*定義6.3

在R(U)中，如果X→Y(Y?X)，Y?X，Y→Z，Z?Y,

則稱Z對X傳遞函數依賴(transitivefunctional

dependency)。記為：X

傳→遞

Z。注:如果Y→X,即X←→Y，則Z直接依賴于X，而不是傳遞函數依賴。[例]在關系Std(Sno,Sdept,

Mname)中，有：Sno

→

Sdept，Sdept

→

Mname，Mname傳遞函數依賴于Sno函數依賴碼范式2NF3NFBCNF多值依賴4NF規范化小結*Key)。如果U部分函數依賴于K，即K

→U,則K稱為超碼（Surpkey）。候選碼是最小的超碼，即K的任意一個真子集都不是候選碼。若關系模式R有多個候選碼，則選定其中的一個做為主碼(Primary

key)。定義6.4

設K為R<U,F>中的屬性或屬性組合。若K

→F

U，則K稱為R的一個候選碼(CandidateP*主屬性與非主屬性包含在任何一個候選碼中的屬性，稱為主屬性（Prime

attribute）不包含在任何碼中的屬性稱為非主屬性（Nonprimeattribute）或非碼屬性（Non-key

attribute）全碼：整個屬性組是碼，稱為全碼（All-key）*[例6.2]S(Sno,Sdept,Sage)，單個屬性Sno是碼SC(Sno,Cno,

Grade)中，(Sno,Cno)是碼[例6.3]R(P,W,A)P：演奏者

W：作品

A：聽眾一個演奏者可以演奏多個作品某一作品可被多個演奏者演奏聽眾可以欣賞不同演奏者的不同作品碼為(P,W,A)，即All-Key定義6.5

關系模式

R中屬性或屬性組X

并非

R的碼，但

X

是另一個關系模式的碼，則稱

X

是R

的外部碼（Foreign

key）也稱外碼。SC(

o,Grade)中，Sno不是碼Sno是S(Sno,Sdept,Sage)的碼，則Sno是SC的外碼主碼與外部碼一起提供了表示關系間聯系

段*函數依賴碼范式2NF3NFBCNF多值依賴4NF規范化小結6.2.3

范式*An

Introduction

to

Database

System范式是符合某一種級別的關系模式的集合。關系數據庫中的關系必須滿足一定的要求。滿足不同程度要求的為不同范式。范式的種類：第一范式(1NF)第二范式(2NF)第三范式(3NF)BC范式(BCNF)第四范式(4NF)第五范式(5NF)各種范式之間存在聯系：*1NF

2NF

3NF

BCNF

4NF

5NF某一關系模式R為第n范式，可簡記為R∈nNF。一個低一級范式的關系模式，通過模式分解（schemaposition）可以轉換為若干個高一級范式的關系模式的集合，這種過程就叫規范化（normalization）。函數依賴碼范式2NF3NFBCNF多值依賴4NF規范化小結*定義6.6

若關系模式R∈1NF，并且每一個非主屬性都完全函數依賴于任何一個候選碼，則R∈2NF[例6.4]

S-L-C(

o,Grade)，Sloc為學生的住處，并且每個系的學生住在同一個地方。S-L-C的碼為(

o)。函數依賴有(

o)→F

GradeSno→Sdept,

(Sno→Sloc,

(Sdept→Sloco)→P

Sdepto)→P

SlocSnoCnoGradeSdeptSloc非主屬性Sdept、Sloc并不完全依賴于碼關系模式S-L-C不屬于2NF*一個關系模式不屬于2NF，會產生以下問題：異常如果

一個新學生，但該生未選課，即該生無Cno，由于

元組時，必須給定碼值，因此

失敗。刪除異常如果S4只選了一門課C3，現在他不再選這門課，則刪除C3后，整個元組的其他信息也被刪除了。修改復雜如果一個學生選了多門課，則Sdept，Sloc被

了多次。如果該生轉系，則需要修改所有相關的Sdept和Sloc，造成修改的復雜化。**出現這種問題的原因例子中有兩類非主屬性：一類如Grade，它對碼完全函數依賴另一類如Sdept、Sloc，它們對碼不是完全函數依賴解決方法：用投影分解把關系模式S-L-C分解成兩個關系模式SC(

o,Grade)S-L(Sno,Sdept,Sloc)SnoCnoGradeSnoSdeptSloc圖6.4

SC中的函數依賴

圖6.5S-L中的函數依賴SC的碼為(

o),SL的碼為Sno，這樣使得非主屬性對碼都是完全函數依賴了函數依賴碼范式2NF3NFBCNF多值依賴4NF規范化小結定義6.7

設關系模式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*函數依賴碼范式2NF3NFBCNF多值依賴4NF規范化小結BCNF（Boyce

Codd

Normal

Form）由Boyce和Codd提出，比3NF更進了一步。通常認為

BCNF是修正的第三范式，有時也稱為擴充的第三范式。定義6.8

設關系模式R<U,F>∈1NF，若X

→Y且Y?

X時X必含

，則R<U,F>∈BCNF。換言之，在關系模式R<U,F>中，如果每一個決定屬性集都包含候選碼，則R∈BCNF。**BCNF的關系模式所具有的性質所有非主屬性都完全函數依賴于每個候選碼所有主屬性都完全函數依賴于每個不包含它的候選碼沒有任何屬性完全函數依賴于非碼的任何一組屬性如果一個關系數據庫中的所有關系模式都屬于

BCNF，那么在函數依賴范疇內，它已實現了模式的徹底分解，達到了最高的規范化程度，消除了插入異常和刪除異常。[例6.5]

關系模式C(

o)它只有一個碼Cno，沒有任何屬性對Cno部分依賴或傳遞依賴，所以C∈3NF。同時C中Cno是唯一的決定因素，所以C∈BCNF。對于關系模式SC(

o,Grade)可作同樣分析。[例6.6]關系模式S(Sno,Sname,Sdept,Sage)，假定Sname也具有唯一性，那么S就有兩個碼，這兩個碼都由單個屬性組成，彼此不相交。其他屬性不存在對碼的傳遞依賴與部分依賴，所以S∈3NF。同時S中除Sno，Sname外沒有其他決定因素，所以S也屬于BCNF。[例6.7]關系模式SJP(S,J,P)中，S是學生，J表示課程，P表示名次。每一個學生選修每門課程的成績有一定的名次，每門課程中每一名次只有一個學生（即沒有并列名次）。由語義可得到函數依賴：(S,J)→P；(J,P)→S(S,J)與(J,P)都可以作為候選碼。關系模式中沒有屬性對碼傳遞依賴或部分依賴，所以SJP∈3NF。除(S,J)與(J,P)以外沒有其他決定因素，所以SJP∈BCNF。[例6.8]關系模式STJ(S,T,J)中，S表示學生，T表示教師，J表示課程。每一教師只教一門課。每門課有若干教師，某一學生選定某門課，就對應一個固定的教師。由語義可得到函數依賴：(S,J)→T；(S,T)→J；T→J因為沒有任何非主屬性對碼傳遞依賴或部分依賴，STJ

∈3NF。因為T是決定因素，而T不包含碼，所以STJ

∈BCNF關系。圖6.6

STJ中的函數依賴對于不是BCNF的關系模式，仍然存在不合適的地方。非

的關系模式也可以通過分解成為

F。例如STJ可分解為ST(S,T)與TJ(T,J)，它們都是BCNF。

和

F是在函數依賴的條件下對模式分解所能達到的分離程度的測度。一個模式中的關系模式如果都屬于BCNF，那么在函數依賴范疇內，它已實現了徹底的分離，已消除了和刪除的異常。3NF的“不徹底”性表現在可能存在主屬性對碼的部分依賴和傳遞依賴。函數依賴碼范式2NF3NFBCNF多值依賴4NF規范化小結*例[6.9]設學校中某一門課程由多個教師講授，他們使用相同的一套參考書。每個教員可以講授多門課程，每種參考書可以供多門課程使用用關系模式Teaching(C,T,B)來表示課程C、教師T和參考書B之間的關系。多值依賴（續）表6.3

非規范化關系示例課程

C教員

T參考書

B物理數學計算數學…張平張平周峰…普通物理學光學原理

物理習題集數學分析微分方程高等代數數學分析……An

Introduction

to

Database

System表6.4

規范化的二維表

Teaching課程C教員T參考書B物理普通物理學物理光學原理物理物理習題集物理普通物理學物理光學原理物理物理習題集數學普通物理學數學光學原理數學物理習題集數學張平普通物理學數學張平光學原理數學張平物理習題集………**Teaching具有唯一候選碼(C,T,B)，即全碼。Teaching∈BCNF(1)數據冗余度大：有多課程C教員T參考課書少名任

教師，參考書儲多少次。物理普通物就要存物理光學原理物理物理習題集物理普通物理學物理光學原理物理物理習題集數學普通物理學數學光學原理數學物理習題集數學張平普通物理學數學張平光學原理數學張平物理習題集………*課程C教員T參考物理物理光學物理物理普通物理學物理光學原理物理物理習題集數學普通物理學數學光學原理數學物理習題集數學張平普通物理學數學張平光學原理數學張平物理習題集………(2)增加操作復雜：當某一課程增加一名任普通物課教師時，該課程有多少本參照書，就必物理習

須

多少個元組。*課程C物理物理物理教員T參考(3)刪除操作復雜：某一普通物門課要去掉一本參考書，光學

該課程有多少名教師，就必須刪除多少個元組。物理習題集物理普通物理學物理光學原理物理物理習題集數學普通物理學數學光學原理數學物理習題集數學張平普通物理學數學數學…張平張平…光學原理物理習題集…*課程C教員T物理物理物理物理習題集物理普通物理學物理光學原理物理物理習題集數學普通物理學數學光學原理數學物理習題集數學張平普通物理學數學張平光學原理參考(4)修改操作復雜：某一普通門課要修改一本參考書，該課程有多少名教師，光學就必須修改多少個元組。產生原因:存在多值依賴**定義6.9

設R(U)是屬性集U上的一個關系模式。X,Y,Z是U的子集，并且Z=U-X-Y。關系模式R(U)中多值依賴X→→Y成立，當且僅當對R(U)的任一關系r，給定的一對(x,z)值，有一組Y的值，這組值僅僅決定于x值而與z值無關。例

Teaching（C,

T,

B）對于C的每一個值，T有一組值與之對應，而不論B取何值。因此T多值依賴于C，即C→→T。多值依賴的另一個等價的定義在R(U)的任一關系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值所得的兩個新元組必在r中則Y多值依賴于X，記為X→→Y。這里X，Y是U的子集，Z=U-X-Y。，普通物理學或者W1，S1，C1倉庫

-保管員

-商品w，光學原理，光學原理或者W1，S2，C2或者

W1，S1，C2t：物理，s：物理，：物理，v：物理，，普通物理學或者W1，S2，C1w[X]=v[X]=t[X]=物理=W1w[Y]=t[Y]=v[Y]=s[Y]==S1，w[Z]=s[Z]=光學原理=C2，=S2，v[Z]=t[Z]=普通物理學=C1XYZXYZtt[X]t[Y]t[Z]t

t[X]t[Y]t[Z]ss[X]s[Y]s[Z]s

s[X]s[Y]s[Z]ww[X]w[Y]w[Z]w

w[X]w[Y]w[Z]vv[X]v[Y]v[Z]v

v[X]v[Y]v[Z]*平凡多值依賴和非平凡的多值依賴

若X→→Y，而Z＝Ф，即Z為空，則稱X→→Y為平凡的多值依賴。否則稱X→→Y為非平凡的多值依賴。WSCW1S1C1W1S1C2W1S1C3W1S2C1W1S2C2W1S2C3W2S3C4W2S3C5W2S4C4W2S4C5[例6.10]關系模式WSC(W,S,C)中，W表示倉庫，S表示保管員，C表示商品。假設每個倉庫有若干個保管員，有若干種商品。每個保管員保管所在倉庫的所有商品，每種商品被所有保管員保管。按照語義對于W的每一個值Wi，S有一個完整的集合與之對應而

C取何值。所以W→→S。如圖6.7所示對應W的某一個值Wi的全部S值記作{S}Wi（表示此倉庫工作的全部保管員）全部C值記作{C}Wi（表示在此倉庫中存放的所有商品）應當有{S}Wi中的每一個值和{C}Wi中的每一個C值對應于是{S}Wi與{C}Wi之間正好形成一個完全二分圖，因而W→→S。由于C與S的完全對稱性，必然有W→→C成立。圖6.7

W→→S且W→→C多值依賴的性質1

多值依賴具有對稱性。即若X→→Y，則X→→Z，其中Z＝U－X－Y多值依賴的對稱性可以用完全二分圖直觀地表示出來。從[例6.10]

容易看出，因為每個保管員保管所有商品，同時每種商品被所有保管員保管，顯然若W→→S，必然有W→→C。多值依賴具有傳遞性。即若X→→Y，Y→→Z，則X→→Z

-Y。函數依賴是多值依賴的特殊情況。即若X→Y，則X→→Y。若X→→Y，X→→Z，則X→→YZ。若X→→Y，X→→Z，則X→→Y∩Z。若X→→Y，X→→Z，則X→→Y-Z，X→→Z

-Y。多值依賴與函數依賴的區別1

多值依賴的有效性與屬性集的范圍有關若X→→Y在U上成立，則在W（XY

W

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

U）上成立，在

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

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

WU)上成立。（2）若函數依賴X→Y在R(U)上成立，則對于任何Y‘

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

Y有X→→Y’

成立。*An

Introduction

to

Database

SystemABCDa1b1c1d1a1b1c1d2a1b2c2d1a1b2c2d2多值依賴（續）例如，關系R(A,B,C,D)，A→→BC成立，當然也有

A→→D成立。有R的一個關系實例，在此實例上

A→→B是不成立的。表6.6

R的一個實例函數依賴碼范式2NF3NFBCNF多值依賴4NF規范化小結定義6.10關系模式R<U,F>∈1NF，如果對于R的每個非平凡多值依賴X→→Y（Y?X），X都含，則R<U,F>∈4NF。4NF就是限制關系模式的屬性之間不允許有非平凡且非函數依賴的多值依賴。4NF所允許的非平凡多值依賴實際上是函數依賴。*如果一個關系模式是4NF，則必為BCNF。在[例6.10]的WSC中，W

→→S,

W→→C,他們都是非平凡多值依賴。而W不是碼，關系模式WSC的碼是(W,S,C)，即All-key，因此WSC

∈

4NF。可以把WSC分解成WS(W,S),WC(W,C)，WS∈4NF，WC∈4NF。*函數依賴碼范式2NF3NFBCNF多值依賴4NF規范化小結在關系數據庫中，對關系模式的基本要求是滿足第一范式。規范化程度過低的關系不一定能夠很好地描述現實世界可能存在

異常、刪除異常、修改復雜、數據冗余等問題解決方法就是對其進行規范化，轉換成高級范式。**一個低一級范式的關系模式，通過模式分解可以轉換為若干個高一級范式的關系模式集合，這種過程就叫關系模式的規范化。關系數據庫的規范化理論是數據庫邏輯設計的工具。*規范化的基本思想是逐步消除數據依賴中不合適的部分，使模式中的各關系模式達到某種程度的“分離”。即采用“一事一地”的模式設計原則讓一個關系描述一個概念、一個實體或者實體間的一種聯系。若多于一個概念就把它“分離”出去。因此規范化實質上是概念的單一化。關系模式規范化的基本步驟消除非主屬性對碼的傳遞函數依賴消除決定因素非碼的非平凡函數依賴1NF↓

消除非主屬性對碼的部分函數依賴2NF↓3NF↓消除主屬性對碼的部分和傳遞函數依賴BCNF↓

消除非平凡且非函數依賴的多值依賴4NF圖6.8

規范化過程**不能說規范化程度越高的關系模式就越好。必須對現實世界的實際情況和用戶應用需求作進一步分析，確定一個合適的、能夠反映現實世界的模式。上面的規范化步驟可以在其中任何一步終止。問題的提出規范化數據依賴的公理系統*6.4

模式的分解6.5

小結*定義6.11

對于滿足一組函數依賴F的關系模式R

<U,F>，其任何一個關系r，若函數依賴X→Y都成立（即r中任意兩元組t、s，若t[X]=s[X]，則t[Y]=s[Y]），則稱F邏輯蘊涵X

→Y。*Armstrong公理系統一套推理規則，是模式分解算法的理論基礎用途求給定關系模式的碼從一組函數依賴求得蘊涵的函數依賴Armstrong公理系統

設U為屬性集總體，F是U上的一組函數依賴，

于是有關系模式R

<U,F

>。對R

<U,F>

來說有以下的推理規則：A1自反律（reflexivity

rule）：若Y

X

U，則X→Y

為F所蘊涵。A2

增廣律（augmentation

rule）：若X→Y為F所蘊涵，且Z

U，則XZ→YZ

為F所蘊涵。A3

傳遞律（transitivity

rule）：若X→Y及Y→Z為F所蘊涵，則X→Z

為F所蘊涵。注意：由自反律所得到的函數依賴均是平凡的函數依賴,自反律的使用并不依賴于F。定理6.1

Armstrong推理規則是正確的。證明A1

自反律設Y

X

U

。對R

<U,F>的任一關系r中的任意兩個元組t、s：若t[X]=s[X]，由于Y

X，有t[Y]=s[Y]，所以X→Y成立，自反律得證。A2

增廣律設X→Y為F所蘊涵，且Z

U。對R<U,F>的任一關系r中任意的兩個元組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所蘊涵，增廣律得證。A3

傳遞律設X→Y及Y→Z為F所蘊涵。對R<U,F>的任一關系r中的任意兩個元組t、s：若t[X]=s[X]，由于X→Y，有t[Y]=s[Y]；再由Y→Z，有t[Z]=s[Z]，所以X→Z為F所蘊涵，傳遞律得證。根據A1，A2，A3這三條推理規則可以得到下面三條推理規則：合并規則（union

rule）：由X→Y，X→Z，有X→YZ。偽傳遞規則（pseudo

transitivity

rule）：由X→Y，WY→Z，有XW→Z。分解規則（

position

rule）：由X→Y及ZY，有X→Z。根據合并規則和分解規則，可得引理6.1引理6.1

X→A1

A2…Ak成立的充分必要條件是X→Ai成立（i=1，2，…，k）。定義6.12

在關系模式R<U,F>中為F所邏輯蘊涵的函數依賴的全體叫作F的閉包，記為F

+。定義6.13

設F為屬性集U上的一組函數依賴，X、Y

U，XF+={A|X→A能由F根據Armstrong公理導出}，X

+稱為屬性集X關于函數依賴集F的閉包。F引理6.2

設F為屬性集U上的一組函數依賴，X、Y

U，X→Y能由F根據Armstrong公理導出的充分必要條件是Y

XF

。+引理6.2的用途判定X→Y是否能由F根據Armstrong公理導出的問題，就轉化為求出XF

，判定Y是否為XF

的子集的問題。+

+數據依賴的公理系統（續）An

Introduction

to

Database

System求閉包的算法算法6.1

求屬性集X（X

U）關于U上的函數依賴集F的閉包X

+F輸入：X，F輸出：XF+步驟：迭代③X(i+1)=B∪X(i)。④

判斷X(i+1)=X(i)。⑤

若X(i+1)與X(i)相等或X(i)=U

，則X(i)就是X+，F算法終止。⑥

若否，則i=i+1，返回第②步。對X(i)中的每個元素，依次檢查相應的函數依賴,將依賴它的屬性加入B①

令X(0)=X，i=0②

求B，這里B

={A

|(

V)(

W)(V→WF∧V

X(i)∧A

W)}。[例6.11]

已知關系模式R<U,

F>，其中U={A,

B,

C,

D,

E}；F={AB→C,B→D,C→E,EC→B,AC→B}。求(AB)+。F解：由算法6.1，設X(0)=AB。計算X(1)：逐一的掃描F集合中各個函數依賴，找左部為

A、B或AB的函數依賴。得到兩個：AB→C，B→D。于是X(1)=AB∪CD=ABCD。因為X(0)≠X(1)，所以再找出左部為ABCD子集的那些函數依賴，又得到C→E，AC→B，于是

X(2)=X(1)∪BE=ABCDE。因為X(2)已等于全部屬性集合，所以(AB)F

=ABCDE。+有效性與完備性的含義有效性：由F

出發根據Armstrong公理推導出來的每一個函數依賴一定在F

+中完備性：F+中的每一個函數依賴，必定可以由F出發根據Armstrong公理推導出來定理6.2

Armstrong公理系統是有效的、完備的。證明：有效性有效性實際上是“正確性”可由定理6.1得證Armstrong推理規則是正確的在關系模式R<U,F>中為F所邏輯蘊涵的函數依賴的全體叫作F的閉包，記為F

+2.完備性只需證明逆否命題：若函數依賴X→Y不能由F從Armstrong公理導出，那么它必然不為F

所蘊涵分三步證明：（1）若V→W成立，且V

XF+，則W

XF+證：因為V

XF

，所以有X→V成立；+因為X

→V，V→W，于是X→W成立；所以W

XF+。*An

Introduction

to

Database

System（2）構造一張二維表r，它由下列兩個元組構成，可以證明r

必是R<U,F>的一個關系，即F中的全部函數依賴在r上成立。FX

+FU-X

+11......1

00......011......1

11......1若r

不是R<U,F>的關系，則必由于F中有某一個函數依賴V→W在r上

不成立所致。由r

的構成可知，V

必定是XF

的子集，而+W

不是

XF+

的子集，

由第（1）步，W

?

XF

，

。+所以r

必是R<U,F>的一個關系。數據依賴的公理系統（續）（3）若X→Y不能由F從Armstrong公理導出，則Y不是XF

的子集。（引理6.2）+F因此必有Y的子集Y’

滿足Y’U-X

+，則X→Y

在r

中不成立，即X→Y

必不為R<U,F>蘊涵。若函數依賴X→Y不能由F從Armstrong公理導出，那么它必然不為F所蘊涵若函數依賴X→Y能由F從Armstrong公理導出，那么它必然為F

所蘊涵F+中的每一個函數依賴，必定可以由F出發根據Armstrong公理推導出來Armstrong公理的完備性及有效性說明:“導出”與“蘊涵”是兩個完全等價的概念F+：為F所邏輯蘊涵的函數依賴的全體（定義6.12

）F+：可以說成由F出發借助Armstrong公理導出的函數依賴的集合*定義6.14

如果G+=F+，就說函數依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價。兩個函數依賴集等價是指它們的閉包等價（3）同理可證G

+F+，所以F

+=G+。函數依賴集等價的充要條件引理6.3F+=G+的充分必要條件是F

G+和G

F+。證:

必要性顯然，只證充分性。引理6.3給出了判斷兩個函數依賴集等價的可行算法Y

是否如何判定F

G+？只需逐一對F中的函數依賴X→Y屬于XG++定義6.15

如果函數依賴集F滿足下列條件，則稱F為一個極小函最小覆蓋。（2）F中不存在這樣的函數依賴XF-{X→A}等價。即F中的函數依賴均最小依賴集或不能由F中其他函數依賴導出（1）F中任一函數依 的右部僅含有 個屬性。F中各函數依賴左部均*為最小屬性集（不存（3）F中不存在這樣的函數依賴X→A

在冗余屬性）有真子集Z使得F-{X→A}∪{Z→A}與F等價。[例6.12]

6.1節中的關系模式S<U,F>，其中：U={Sno,

Sdept,

Mname,

Cno,

Grade}，

F={Sno→Sdept,Sdept→Mname,

(

o)→Grade}F是最小覆蓋F

'

={Sno→Sdept,

Sno→Mname,

Sdept→Mname,( o)→Grade,

(Sno,Sdept)→Sdept}F

'不是最小覆蓋因為：F

'-

{Sno→Mname}

與

F

'等價F

'-{(Sno,Sdept)→Sdept}

也與F

'等價**定理6.3

每一個函數依賴集F均等價于一個極小函數依賴集Fm。此Fm稱為F的最小依賴集。證：構造性證明，分三步對F進行“極小化處理”，找出F的一個最小依賴集。（1）逐一檢查F中各函數依賴FDi：X→Y，若Y=A1A2

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

|

j=1,2,…,k}來取代X→Y。引理6.1保證了F變換前后的等價性。*（2）逐一檢查F中各函數依賴FDi：X→A，令G=F-{X→A}，若AX

+，則從F中去掉此函數依賴。G由于F與G

等價的充要條件是AXG+因此F變換前后是等價的。*（3）逐一取出F中各函數依賴FDi：X→A，設X=B1B2…Bm，m≥2，逐一考查Bi（i=1，2，…，m），若A

(X-Bi

)

+，則以X-B

取代X。F

i由于F與F-{X→A}∪{Z→A}等價的充要條件是

AZF+，其中Z=X-Bi

，因此F變換前后是等價的。最后剩下的F就一定是極小依賴集。因為對F的每一次“改造”都保證了改造前后的兩個函數依賴集等價，因此剩下的F與原來的F等價。證畢*定理6.3的證明過程是求F極小依賴集的過程也是檢驗F是否為極小依賴集的一個算法若改造后的F與原來的F相同，說明F就是一個最小依賴集*[例6.13]

F={A→B,

B→A,

B→C,

A→C,

C→A}F的最小依賴集：Fm1=

{A→B,

B→C,

C→A}*F的最小依賴集Fm不一定是唯一的，它與對各函數依賴FDi

及X→A中X各屬性的處置順序有關。*[例6.13]（續）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}*在R<U,F>中可以用與F等價的依賴集G來取代F原因：兩個關系模式R1

<U,F>，R2<U,G>，如果F與G