It計算機課件 數(shù)據(jù)庫原理第六章關(guān)系數(shù)據(jù)理論

。

AnIntroductiontoDatabaseSystem

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

AnIntroductiontoDatabaseSystem

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

6.1問題的提出

6.2規(guī)范化

6.3數(shù)據(jù)依賴的公理系統(tǒng)

*6,4模式的分解

6.5小結(jié)

AnIntroductiontoDatabaseSystem

6.1問題的提出

關(guān)系數(shù)據(jù)庫邏輯設(shè)計

針對具體問題，如何構(gòu)造一個適合于它的數(shù)據(jù)模式

數(shù)據(jù)庫邏輯設(shè)計的工具一關(guān)系數(shù)據(jù)庫的規(guī)范化理論

AnIntroductiontoDatabaseSystem

問題的提出

一、概念回顧

二、關(guān)系模式的形式化定義

三、什么是數(shù)據(jù)依賴

四、關(guān)系模式的簡化定義

五、數(shù)據(jù)依賴對關(guān)系模式影響

AnIntroductiontoDatabaseSystem

'、概念回顧

?:?關(guān)系

關(guān)系模式

關(guān)系數(shù)據(jù)庫

關(guān)系數(shù)據(jù)庫的模式

AnIntroductiontoDatabaseSystem

:、關(guān)系模式的形式化定義

關(guān)系模式由五部分組成，即它是一個五元組:

R(U,D,DOM,F)

R：關(guān)系名

U：組成該關(guān)系的屬性名集合

D：屬性組U中屬性所來自的域

DOM：屬性向域的映象集合

F：屬性間數(shù)據(jù)的依賴關(guān)系集合

AnIntroductiontoDatabaseSystem

三、什么是數(shù)據(jù)依賴

1.完整性約束的表現(xiàn)形式

?:?限定屬性取值范圍：例如學(xué)生成績必須在0-100之間

?:?定義屬性值間的相互關(guān)連（主要體現(xiàn)于值的相等與

否），這就是數(shù)據(jù)依賴，它是數(shù)據(jù)庫模式設(shè)計的關(guān)鍵

AnIntroductiontoDatabaseSystem

什么是數(shù)據(jù)依賴（續(xù)）

2.數(shù)據(jù)依賴

?:?一個關(guān)系內(nèi)部屬性與屬性之間的約束關(guān)系

?:?現(xiàn)實世界屬性間相互聯(lián)系的抽象

?:?數(shù)據(jù)內(nèi)在的性質(zhì)

?:?語義的體現(xiàn)

AnIntroductiontoDatabaseSystem

什么是數(shù)據(jù)依賴（續(xù)）

3.數(shù)據(jù)依賴的類型

?:?函數(shù)依賴（FunctionalDependency,簡記為FD）

?:?多值依賴（MultivaluedDependency,簡記為MVD）

其他

AnIntroductiontoDatabaseSystem

四、關(guān)系模式的簡化表示

關(guān)系模式R(U,D,DOM,F)

簡化為一個三元組：

R(U,F)

當(dāng)且僅當(dāng)U上的一個關(guān)系門黃足F時，r稱為關(guān)系模式R(U,

F)的一個關(guān)系

AnIntroductiontoDatabaseSystem

五、數(shù)據(jù)依賴對關(guān)系模式的影響

［例1］建立一個描述學(xué)校教務(wù)的數(shù)據(jù)庫：

學(xué)生的學(xué)號（Sno）、所在系（Sdept）

系主任姓名（Mname）、課程名（Cname）

成績（Grade）

單一的關(guān)系模式：Student<U>F>

U={Sno,Sdept,Mname,Cname,Grade)

AnIntroductiontoDatabaseSystem

數(shù)據(jù)依賴對關(guān)系模式的影響（續(xù)）

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

F={Sno—Sdept,Sdept-Mname,

(Sno,Cname)一Grade}

AnIntroductiontoDatabaseSystem

關(guān)系模式StudentvU,F＞中存在的問題

1.數(shù)據(jù)冗余太大

2.更新異常(UpdateAnomalies)

3.插入異常(InsertionAnomalies)

4.刪除異常(DeletionAnomalies)

AnIntroductiontoDatabaseSystem

數(shù)據(jù)依賴對關(guān)系模式的影響（續(xù)）

結(jié)論：

■Student關(guān)系模式不是一個好的模式。

■“好”的模式：

不會發(fā)生插入異常、刪除異常、更新異常，

數(shù)據(jù)冗余應(yīng)盡可能少

原因：由存在于模式中的某些數(shù)據(jù)依賴引起的

解決方法：通過分解關(guān)系模式來消除其中不合適

的數(shù)據(jù)依賴

AnIntroductiontoDatabaseSystem

分解關(guān)系模式

?:?把這個單一模式分成3個關(guān)系模式:

S(Sno,Sdept,Sno一Sd叩t);

SC(Sno,Cno,Grade,(Sno,Cno)一Grade);

DEPT(Sdept,Mname,Sdept—Mname)

AnIntroductiontoDatabaseSystem

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

6.1問題的提出

6.2規(guī)范化

6.3數(shù)據(jù)依賴的公理系統(tǒng)

*6,4模式的分解

6.5小結(jié)

AnIntroductiontoDatabaseSystem

規(guī)范化理論正是用來改造關(guān)系模式，通過分解關(guān)系模式來

消除其中不合適的數(shù)據(jù)依賴，以解決插入異常、刪除異常、

更新異常和數(shù)據(jù)冗余問題。

AnIntroductiontoDatabaseSystem

規(guī)范化

6.2.1函數(shù)依賴

6.2.2碼

6.2.3范式

6.2.42NF

6.2.53NF

6.2.6BCNF

6.2.7多值依賴

6.2.84NF

6.2.9規(guī)范化小結(jié)

AnIntroductiontoDatabaseSystem

6.2.1函數(shù)依賴

函數(shù)依賴

平凡函數(shù)依賴與非平凡函數(shù)依賴

完全函數(shù)依賴與部分函數(shù)依賴

傳遞函數(shù)依賴

AnIntroductiontoDatabaseSystem

、函數(shù)依賴

定義6.1設(shè)R(U)是一個屬性集U上的關(guān)系模式，X和Y是U的

子集。

若對于R(U)的任意一個可能的關(guān)系r,r中不可能存在兩個元

組在X上的屬性值相等，而在Y上的屬性值不等，則稱“X

函數(shù)確定Y”或“Y函數(shù)依賴于X”，記作X-丫。

AnIntroductiontoDatabaseSystem

1?所有關(guān)系實例均要滿足

2.語義范疇的概念

3.數(shù)據(jù)庫設(shè)計者可以對現(xiàn)實世界作強制的規(guī)定

AnIntroductiontoDatabaseSystem

、平凡函數(shù)依賴與非平凡函數(shù)依賴

在關(guān)系模式R(U)中，對于U的子集X和丫，

如果X—Y,但Y又X,則稱X—Y是非平凡的函數(shù)依賴

若X-Y,但Y=X,則稱X-Y是平凡的函數(shù)依賴

?:?例：在關(guān)系SC(Sno,Cno,Grade)中，

非平凡函數(shù)依賴：(Sno,Cno)一Grade

平凡函數(shù)依賴：(Sno,Cno)一Sno

(Sno,Cno)-Cno

AnIntroductiontoDatabaseSystem

平凡函數(shù)依賴與非平凡函數(shù)依賴(續(xù))

若X—Y,則X稱為這個函數(shù)依賴的決定屬性組，也

稱為決定因素(Determinant)。

若X—KY—X,則記作X<-->Yo

若丫不函數(shù)依賴于X,則記作

AnIntroductiontoDatabaseSystem

、完全函數(shù)依賴與部分函數(shù)依賴

定義6.2在R(U)中，如果X-Y,并且對于X的任何一個真

子集X、都有X，、Y,則稱丫對*完全函數(shù)依賴，記作

X-^Yo

若X—丫，但丫不完全函數(shù)依賴于X,則稱丫對X部分函數(shù)

依賴，記作XqY。

AnIntroductiontoDatabaseSystem

完全函數(shù)依賴與部分函數(shù)依賴（續(xù)）

［例1］中（Sno,Cno盧Grade是完全函數(shù)依賴，

（Sno,Cno）LSdept是部分函數(shù)依賴

因為Sno—Sdept成立，且Sno是（Sno,Cno）

的真子集

AnIntroductiontoDatabaseSystem

四、傳遞函數(shù)依賴

定義6.3在R(U)中,如果X—Y,(丫庫X),Y、XY—Z,

則稱Z對X傳遞函數(shù)依賴。

記為：X雪Z

注：如果Y-X,即*<-->Y,貝IJZ直接依賴于X。

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

Sno—Sdept,Sdept—Mname

Mname傳遞函數(shù)依賴于Sno

AnIntroductiontoDatabaseSystem

規(guī)范化

6.2.1函數(shù)依賴

6.2.2碼

6.2.3范式

6.2.42NF

6.2.53NF

6.2.6BCNF

6.2.7多值依賴

6.2.84NF

6.2.9規(guī)范化小結(jié)

AnIntroductiontoDatabaseSystem

6.2.2碼

定義6.4設(shè)K為R〈U,F＞中的屬性或?qū)傩越M合。若HAJ,

貝1JK稱為R的侯選碼(CandidateKey)。

若候選碼多于一個，則選定其中的一個做為主碼

(PrimaryKey)。

AnIntroductiontoDatabaseSystem

碼(續(xù))

主屬性與非主屬性

包含在任何一個候選碼中的屬性，稱為主屬性(Prime

attribute)

不包含在任何碼中的屬性稱為非主屬性(Nonprimeattribute)

或非碼屬性(Non-keyattribute)

?全碼

整個屬性組是碼，稱為全碼(All-key)

AnIntroductiontoDatabaseSystem

碼(續(xù))

[例2]

關(guān)系模式S(SnoSdept,Sage),單個屬性Sno是碼，

SC(Sno,Cno,Grade)中，(Sno,Cno)是碼

[例3]

關(guān)系模式R(P,W,A)

P：演奏者W：作品A：聽眾

一個演奏者可以演奏多個作品

某一作品可被多個演奏者演奏

聽眾可以欣賞不同演奏者的不同作品

碼為(P,W,A),即All-Key

AnIntroductiontoDatabaseSystem

碼(續(xù))

[例2]

關(guān)系模式S(SnoSdept,Sage),單個屬性Sno是碼，

SC(Sno,Cno,Grade)中，(Sno,Cno)是碼

[例3]

關(guān)系模式R(P,W,A)

P：演奏者W：作品A：聽眾

一個演奏者可以演奏多個作品

某一作品可被多個演奏者演奏

聽眾可以欣賞不同演奏者的不同作品

碼為(P,W,A),即All-Key

AnIntroductiontoDatabaseSystem

規(guī)范化

6.2.1函數(shù)依賴

6.2.2碼

6.2.3范式

6.2.42NF

6.2.53NF

6.2.6BCNF

6.2.7多值依賴

6.2.84NF

6.2.9規(guī)范化小結(jié)

AnIntroductiontoDatabaseSystem

6.2.3范式

?范式是符合某一種級別的關(guān)系模式的集合

?:?關(guān)系數(shù)據(jù)庫中的關(guān)系必須滿足一定的要求。滿足不同程度

要求的為不同范式

*范式的種類：

〃第一范式(1NF)

第二范式(2NF)

J第三范式(3NF)

]BC范式(BCNF)

第四范式(4NF)

t第五范式(5NF)

AnIntroductiontoDatabaseSystem

?:?各種范式之間存在聯(lián)系:

INFo2NFo3NFoBCNFo4NFn5NF

?:?某一關(guān)系模式R為第n范式，可簡記為R￡nNF。

?:?一個低一級范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換為若

干個高一級范式的關(guān)系模式的集合，這種過程就叫規(guī)范化

AnIntroductiontoDatabaseSystem

規(guī)范化

6.2.1函數(shù)依賴

6.2.2碼

6.2.3范式

6.2.42NF

6.2.53NF

6.2.6BCNF

6.2.7多值依賴

6.2.84NF

6.2.9規(guī)范化小結(jié)

AnIntroductiontoDatabaseSystem

6.2.42NF

?1NF的定義

如果一個關(guān)系模式R的所有屬性都是不可分的基本數(shù)據(jù)項，

則R&1NF

?:?第一范式是對關(guān)系模式的最起碼的要求。不滿足第一范式

的數(shù)據(jù)庫模式不能稱為關(guān)系數(shù)據(jù)庫

?:?但是滿足第一范式的關(guān)系模式并不一定是一個好的關(guān)系模

式

AnIntroductiontoDatabaseSystem

2NF(續(xù))

［例4］關(guān)系模式S-L-C(Sno,Sdept,Sloe,Cno,Grade)

Sloe為學(xué)生住處，假設(shè)每個系的學(xué)生住在同一個地方

函數(shù)依賴包括：

(Sno,Cno)_E->Grade

Sno—Sdept

(Sno,Cno)-^Sdept

Sno—Sloe

(Sno,Cno)JSIoc

Sdept-Sloe

AnIntroductiontoDatabaseSystem

2NF（續(xù)）

?S-L-C的碼為(Sno,Cno)

?：?S-L-C滿足第一范式。

?非主屬性Sdept和Sloe部分函數(shù)依賴于碼(Sno,Cno)

AnIntroductiontoDatabaseSystem

S?L?C不是一個好的關(guān)系模式(續(xù))

(1)插入異常

(2)刪除異常

(3)數(shù)據(jù)冗余度大

(4)修改復(fù)雜

AnIntroductiontoDatabaseSystem

S?L?C不是一個好的關(guān)系模式(續(xù))

原因

Sd叩t、Sloe部分函數(shù)依賴于碼。

解決方法

S-L-C分解為兩個關(guān)系模式，以消除這些部分函數(shù)依賴

SC(Sno,Cno,Grade)

S-L(Sno,Sdept,Sloe)

AnIntroductiontoDatabaseSystem

2NF（續(xù)）

函數(shù)依賴圖:

關(guān)系模式SC的碼為(Sno,Cno)

關(guān)系模式S-L的碼為Sn。

這樣非主屬性對碼都是完全函數(shù)依賴

AnIntroductiontoDatabaseSystem

2NF(續(xù))

2NF的定義

定義6.6若R&1NF,且每一個非主屬性完全函數(shù)依賴于

碼，則RW2NF。

例：S-L-C(Sno,Sdept,Sloe,Cno,Grade)e1NF

S-L-C(Sno,Sdept,Sloe,Cno,Grade)乓2NF

SC(Sno,Cno,Grade)e2NF

S-L(Sno,Sdept,Sloe)e2NF

AnIntroductiontoDatabaseSystem

2NF（續(xù)）

?：?采用投影分解法將一個1NF的關(guān)系分解為多個2NF的關(guān)系,

可以在一定程度上減輕原1NF關(guān)系中存在的插入異常、刪

除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問題。

?:?將一個1NF關(guān)系分解為多個2NF的關(guān)系，并不能完全消除

關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。

AnIntroductiontoDatabaseSystem

規(guī)范化

6.2.1函數(shù)依賴

6.2.2碼

6.2.3范式

6.2.42NF

6.2.53NF

6.2.6BCNF

6.2.7多值依賴

6.2.84NF

6.2.9規(guī)范化小結(jié)

AnIntroductiontoDatabaseSystem

6.2.53NF

03NF的定義

定義6.7關(guān)系模式R〈U,F>中若不存在這樣的碼X、屬性

組V及非主屬性ZCZ苦Y),使得X—KY—Z成立，

Y'X,則稱RvU,F>e3NF。

■若R￡3NF,則每一個非主屬性既不部分依賴于碼也不

傳遞依賴于碼。

AnIntroductiontoDatabaseSystem

3NF（續(xù)）

例：2NF關(guān)系模式S-L(Sno,Sdept,Sloe)中

函數(shù)依賴：

Sno—Sdept

SdeptVSno

Sdept一Sloe

可得：

Sno^bloc,即S-L中存在非主屬性對碼的傳遞函數(shù)依

賴，S-L&3NF

AnIntroductiontoDatabaseSystem

3NF（續(xù)）

函數(shù)依賴圖:

AnIntroductiontoDatabaseSystem

3NF（續(xù)）

?：?解決方法

采用投影分解法，把S-L分解為兩個關(guān)系模式，以消

除傳遞函數(shù)依賴：

S-D(Sno,Sdept)

D-L(Sdept,Sloe)

S-D的碼為Sno,D-L的碼為Sdept。

分解后的關(guān)系模式S-D與D-L中不再存在傳遞依賴

AnIntroductiontoDatabaseSystem

3NF(續(xù))

S-D的碼為Sno,D-L的碼為Sdept

Sno'SdeptSdept'Sloe

S-DD-L

S-L(Sno,Sdept,Sloe)e2NF

S-L(Sno,Sdept,Sloe)43NF

S-D(Sno,Sdept)e3NF

D-L(Sd叩t,Sloc)e3NF

AnIntroductiontoDatabaseSystem

3NF（續(xù)）

?采用投影分解法將一個2NF的關(guān)系分解為多個3NF的關(guān)系，可

以在一定程度上解決原2NF關(guān)系中存在的插入異常、刪除異常、

數(shù)據(jù)冗余度大、修改復(fù)雜等問題。

將一個2NF關(guān)系分解為多個3NF的關(guān)系后，仍然不能完全消除

關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。

AnIntroductiontoDatabaseSystem

規(guī)范化

6.2.1函數(shù)依賴

6.2.2碼

6.2.3范式

6.2.42NF

6.2.53NF

6.2.6BCNF

6.2.7多值依賴

6.2.84NF

6.2.9規(guī)范化小結(jié)

AnIntroductiontoDatabaseSystem

6.2.6BC范式(BCNF)

?:?定義6.8關(guān)系模式R〈U,F>e1NF,若X-y且

Y=X時X必含有碼，則RvU,F>eBCNFo

?:?等價于：每一個決定屬性因素都包含碼

AnIntroductiontoDatabaseSystem

BCNF（續(xù)）

?:?若R&BCNF

所有非主屬性對每一個碼都是完全函數(shù)依賴

所有的主屬性對每一個不包含它的碼，也是完全函數(shù)

依賴

沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性

充分

OR￡BCNF1tRE3NF

不必要

AnIntroductiontoDatabaseSystem

BCNF(續(xù))

［例5］關(guān)系模式C(Cno,Cname,Pcno)

Ce3NF

CeBCNF

［例6］關(guān)系模式S(Sno,Sname,Sdept,Sage)

假定S有兩個碼Sno,Sname

Se3NFo

S￡BCNF

AnIntroductiontoDatabaseSystem

BCNF(續(xù))

［例7］關(guān)系模式SJP(S,J,P)

函數(shù)依賴：(S,J)一P；(J,P)一S

(S,J)與(J,P)都可以作為候選碼，屬性相交

SJPe3NF,

SJPeBCNF

AnIntroductiontoDatabaseSystem

BCNF（續(xù)）

［例8］在關(guān)系模式STJ(S,T,J)中，S表示學(xué)生，T表

示教師，J表示課程。

函數(shù)依賴：

(S,J)—T,(S,T)-J,T—J

(S,J)和(S,T)都是候選碼

AnIntroductiontoDatabaseSystem

BCNF（續(xù)）

STJ中的函數(shù)依賴

AnIntroductiontoDatabaseSystem

BCNF（續(xù)）

STJe3NF

沒有任何非主屬性對碼傳遞依賴或部分依賴

STJ專BCNF

T是決定因素，T不包含碼

AnIntroductiontoDatabaseSystem

BCNF（續(xù)）

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

ST(S,T)eBCNF,TJ(T,J)eBCNF

H0H—2

STTJ

沒有任何屬性對碼的部分函數(shù)依賴和傳遞函數(shù)依賴

AnIntroductiontoDatabaseSystem

3NF與BCNF的關(guān)系

?ReBCNF；Re3NF

要

?:?如果RW3NF,且R只有一個候選碼

充分

ReBCNF^=!：Re3NF

必要

AnIntroductiontoDatabaseSystem

規(guī)范化

6.2.1函數(shù)依賴

6.2.2碼

6.2.3范式

6.2.42NF

6.2.53NF

6.2.6BCNF

6.2.7多值依賴

6.2.84NF

6.2.9規(guī)范化小結(jié)

AnIntroductiontoDatabaseSystem

6.2.7多值依賴

［例9］學(xué)校中某一門課程由多個教師講授，他們使用相

同的一套參考書。每個教員可以講授多門課程，每

種參考書可以供多門課程使用。

AnIntroductiontoDatabaseSystem

多值依賴（續(xù)）

非規(guī)范化關(guān)系

教員T參考書B

課程c

［李勇，

普通物理學(xué)

物理<>

王軍光學(xué)原理

伊理習(xí)題青

［李勇A

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

張平微分方程

［高等代到

張平A

【周峰1J

計算數(shù)學(xué)J

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

?*?

*???

AnIntroductiontoDatabaseSystem

多值依賴（續(xù)）

用二維表表示Teaching

課程c教員T參考書B

普通物理學(xué)

光學(xué)原理

物理習(xí)題集

普通物理學(xué)

光學(xué)原理

物理習(xí)題集

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

微分方程

高等代數(shù)

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

微分方程

高等代數(shù)

AnIntroductiontoDatabaseSystem

多值依賴(續(xù))

TeachingeBCNF

?:.Teaching具有唯一候選碼(C,T,B),即全碼

AnIntroductiontoDatabaseSystem

多值依賴(續(xù))

Teaching模式中存在的問題

(1)數(shù)據(jù)冗余度大

(2)插入操作復(fù)雜

(3)刪除操作復(fù)雜

(4)修改操作復(fù)雜

AnIntroductiontoDatabaseSystem

多值依賴(續(xù))

?定義6.9

設(shè)R(U)是一個屬性集U上的一個關(guān)系模式，X、Y和Z是U的子

集，并且Z=U—X—Y。關(guān)系模式R(U)中多值依賴X一一Y成立,

當(dāng)且僅當(dāng)對R(U)的任一關(guān)系r,給定的一對(x,z)值，有一組

丫的值，這組值僅僅決定于x值而與z值無關(guān)

。例Teaching(C,T,B)

AnIntroductiontoDatabaseSystem

多值依賴（續(xù)）

?:?多值依賴的另一個等價的形式化的定義：

在R（U）的任一關(guān)系r中，如果存在元組f,s使得電＜]飛兇，

那么就必然存在元組w,ver,（w,卜可以與s,f相同），使

得|/|/兇二RX]=f[X],而MY]=f[Y],w/[Z]=s[Z],y[V]=s[Y],

v[Z]=t[Z]（即交換s,f元組的丫值所得的兩個新元組必在r中），

則y多值依賴于x,記為x一一匕這里，x,Y是u的子集，

Z=U-X-Yo

AnIntroductiontoDatabaseSystem

多值依賴（續(xù)）

?:?平凡多值依賴和非平凡的多值依賴

若X一一丫，而Z=（p,則稱

X——Y為平凡的多值依賴

否則稱X--丫為非平凡的多值依賴

AnIntroductiontoDatabaseSystem

多值依賴(續(xù))

［例10］關(guān)系模式WSC(W,S,C)

w表示倉庫，s表示保管員，c表示商品

■假設(shè)每個倉庫有若干個保管員，有若干種商品

■每個保管員保管所在的倉庫的所有商品

每種商品被所有保管員保管

AnIntroductiontoDatabaseSystem

多值依賴

wsC

W1SICl

W1SIC2

W1SIC3

W1S2Cl

W1S2C2

W1S2C3

W2S3C4

W2S3C5

W2S4C4

W2S4C5

AnIntroductiontoDatabaseSystem

多值依賴（續(xù)）

用下圖表示這種對應(yīng)

AnIntroductiontoDatabaseSystem

多值依賴的性質(zhì)

(1)多值依賴具有對稱性

若X——Y,則X一一乙其中z=u—X—丫

(2)多值依賴具有傳遞性

若X——Y,丫―一乙貝以一一Z—丫

(3)函數(shù)依賴是多值依賴的特殊情況。

若X—丫，貝i」X―一丫。

(4)若X一一Y,X一一乙貝i」X一一YuZ。

(5)若X一一Y,X一一乙則X一一YCZ。

(6)若X一一丫，X一一乙則X一一Y-Z,X一一Z-丫。

AnIntroductiontoDatabaseSystem

多值依賴與函數(shù)依賴的區(qū)別

多值依賴的有效性與屬性集的范圍有關(guān)

1若函數(shù)依賴X-Y在R(U)上成立，則對于任何

Y'uY均有X—Y，成立

?多值依賴X-—Y若在R(U)上成立，不能斷言對于

任何Y，uY有X7—丫，成立

AnIntroductiontoDatabaseSystem

規(guī)范化

6.2.1函數(shù)依賴

6.2.2碼

6.2.3范式

6.2.42NF

6.2.53NF

6.2.6BCNF

6.2.7多值依賴

6.2.84NF

6.2.9規(guī)范化小結(jié)

AnIntroductiontoDatabaseSystem

6.2.84NF

?:?定義6.10關(guān)系模式R〈U,F>e1NF,如果對于R的每個

非平凡多值依賴X一一丫（Y'X）,X都含有碼，則

Re4NFo

?如果Re4NF,則ReBCNF

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

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

AnIntroductiontoDatabaseSystem

4NF（續(xù)）

例：Teachings,T,B)^4NF

存在非平凡的多值依賴C一一T,且C不是碼

用投影分解法把Teaching分解為如下兩個關(guān)系模式:

CT(C,T)e4NF

CB(C,B)e4NF

C一一T,C一一B是平凡多值依賴

AnIntroductiontoDatabaseSystem

規(guī)范化

6.2.1函數(shù)依賴

6.2.2碼

6.2.3范式

6.2.42NF

6.2.53NF

6.2.6BCNF

6.2.7多值依賴

6.2.84NF

6.2.9規(guī)范化小結(jié)

AnIntroductiontoDatabaseSystem

6.2.9規(guī)范化小結(jié)

關(guān)系數(shù)據(jù)庫的規(guī)范化理論是數(shù)據(jù)庫邏輯設(shè)計的工具

目的：盡量消除插入、刪除一場，修改復(fù)雜，數(shù)據(jù)冗余

?:?基本思想：逐步消除數(shù)據(jù)依賴中不合適的部分

實質(zhì)：概念的單一化

AnIntroductiontoDatabaseSystem

規(guī)范化小結(jié)（續(xù)）

?關(guān)系模式規(guī)范化的基本步驟

1NF

1消除非主屬性對碼的部分函數(shù)依賴

消除決定屬性2NF

集非碼的非平1消除非主屬性對碼的傳遞函數(shù)依賴

凡函數(shù)依賴3NF

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

BCNF

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

4NF

圖6.8規(guī)范化過程

AnIntroductiontoDatabaseSystem

規(guī)范化小結(jié)（續(xù)）

不能說規(guī)范化程度越高的關(guān)系模式就越好

?:?在設(shè)計數(shù)據(jù)庫模式結(jié)構(gòu)時，必須對現(xiàn)實世界的實際情況和

用戶應(yīng)用需求作進一步分析，確定一個合適的、能夠反映

現(xiàn)實世界的模式

上面的規(guī)范化步驟可以在其中任何一步終止

AnIntroductiontoDatabaseSystem

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

6.1問題的提出

6.2規(guī)范化

6.3數(shù)據(jù)依賴的公理系統(tǒng)

*6.4模式的分解

6.5小結(jié)

AnIntroductiontoDatabaseSystem

6.3數(shù)據(jù)依賴的公理系統(tǒng)

?:?邏輯蘊含

定義6.11對于滿足一組函數(shù)依賴戶的關(guān)系模式F>,

其任何一個關(guān)系廣，若函數(shù)依賴X—Y都成立，（即r中任意

兩元組f,s,若fX]=sX],則"]=sY]）,則稱「邏輯

蘊含X-Y

AnIntroductiontoDatabaseSystem

1.Armstrong公理系統(tǒng)

關(guān)系模式R〈U,尸〉來說有以下的推理規(guī)則：

A1.自反律(Reflexivity)：若則X—V為尸所蘊

含。

A2.增廣律(Augmentation)：若X-Y為尸所蘊含，且2=

U,則XZ-YZ為f所蘊含。

A3.傳遞律(Trans讓Mty)：若X-丫及Y-Z為F所蘊含,則

X—Z為尸所蘊含。

AnIntroductiontoDatabaseSystem

定理6.1Armstrong推理規(guī)則是正確的

(D自反律：若y=x=u,則x—Y為尸所蘊含

證：設(shè)u

對Rvu,尸〉的任一關(guān)系r中的任意兩個元組t,s：

若f兇二s兇，由于Y=X,有f[y]=s[y],

所以x—y成立，自反律得證

AnIntroductiontoDatabaseSystem

定理61Armstrong推理規(guī)則是正確的(續(xù))

(2)增廣律:若X—y為尸所蘊含，且Z=U,則XZ—YZ為尸所

蘊含。

證：設(shè)X-Y為尸所蘊含，且Z=U。

設(shè)RvU,尸＞的任一關(guān)系r中任意的兩個元組t,s：

若f[XZ]=s[XZ],則有f兇二s兇和f[Z]=s[Z]；

由x-y,于是有"Y]=s[Y],所以[yz]=s[yz],所以

XZ-YZ為F所蘊含,增廣律得證。

AnIntroductiontoDatabaseSystem

定理6JArmstrong推理規(guī)則是正確的(續(xù))

(3)傳遞律：若X—Y及y—z為F所蘊含，則

x-z為尸所蘊含。

證：設(shè)x-y及y-z為尸所蘊含。

對RVU,尸〉的任一關(guān)系r中的任意兩個元組力s：

若f兇二S兇，由于X—K有f[Y]=s[Y]；

再由Y一乙有f[Z]=s[Z],所以X—Z為尸所蘊含，傳遞

律得證。

AnIntroductiontoDatabaseSystem

2.導(dǎo)出規(guī)則

1.根據(jù)A1,A2,A3這三條推理規(guī)則可以得到下面三

條推理規(guī)則：

合并規(guī)則：由X-Y,X一乙有X—YZ。

(A2,A3)

偽傳遞規(guī)則：由x-y,wy一乙有XW—z。

(A2,A3)

分解規(guī)則：由X-Y及有X-Z。

(A1,A3)

AnIntroductiontoDatabaseSystem

2,根據(jù)合并規(guī)則和分解規(guī)則，可得引理6.1

引理6.1乂一44…4成立的充分必要條件是

X-4成立（/=l,2,.?.，k）

AnIntroductiontoDatabaseSystem

Armstrong公理系統(tǒng)

Armstrong公理系統(tǒng)是有效的、完備的

■有效性：由尸出發(fā)根據(jù)Armstrong公理推導(dǎo)出來

的每一個函數(shù)依賴一定在戶中；

■完備性：戶中的每一個函數(shù)依賴，必定可以由產(chǎn)

出發(fā)根據(jù)Armstrong公理推導(dǎo)出來

AnIntroductiontoDatabaseSystem

3.函數(shù)依賴閉包

定義6.12在關(guān)系模式RvU,尸＞中為「所邏輯蘊含的

函數(shù)依賴的全體叫作尸的閉包，記為戶。

定義6.13設(shè)尸為屬性集U上的一組函數(shù)依賴，XQU,

X，={4|Xf4能由尸根據(jù)Armstrong公理導(dǎo)出},

X,稱為屬性集X關(guān)于函數(shù)依賴集產(chǎn)的閉包

AnIntroductiontoDatabaseSystem

EgsASQseqgea。1uogonponu-u4

……

《

—喇

m鼠叵小爪dNGM44+L?Eg{u<x--<ixorL

個

個

個

(ZAXZAXz>x個ZX.ZAX>xz>zx

個

個

個

下

ZX個ZAXxzx-zx>xz>x

個

個

個

z>個z>xZxzxz>AX-ZXx

個

個

下

"x個xZXAX>x

個

ZAX”xX

個

個

個

個

個

Z個ZAXZ>z>ZZXZ>xz>>zx

個

個

”個

”個

個

>個z>xZz>zx>xz>>x

個

尸個

個

個

個

”個

X個z>xz>XzxX>xZZAxX

個

個

個

個

個

個

s個z>xsz>3zxs>x§Z3>§X

H+L

L

”個

N個>XHL

關(guān)于閉包的引理

引理62

設(shè)戶為屬性集u上的一組函數(shù)依賴，x,Y^U,x—y能

+

由F根據(jù)Armstrong公理導(dǎo)出的充分必要條件是Y^XF

?:?用途

將判定X—Y是否能由尸根據(jù)Armstrong公理導(dǎo)出的問題,

轉(zhuǎn)化為求出X/、判定Y是否為X/的子集的問題

AnIntroductiontoDatabaseSystem

求閉包的算法

算法6.1求屬性集X(X=U)關(guān)于U上的函數(shù)依賴集產(chǎn)的閉包X/

+

輸入：X,F輸出：XF

步驟：

(1)令X(。)=X,/=0

(2)求B,這里8=尸八VqX⑴仞｝;

(3)X(i+1)=8UX⑴

(4)判斷X(i+1)二X⑴嗎？

(5)若相等或X⑴=U,則X⑴就是X/,算法終止。

(6)若否，貝iJ/=/+l,返回第(2)步。

AnIntroductiontoDatabaseSystem

對于算法6.1,令a產(chǎn)|X⑴{aj形成一個步

長大于1的嚴(yán)格遞增的序列，序列的上界是|

U\,因此該算法最多|U|-兇次循環(huán)就

會終止。

AnIntroductiontoDatabaseSystem

函數(shù)依賴閉包

［例1］已知關(guān)系模式R〈U,F>,其中

U={A,B,CD,E}；

F={AB^C,B—D,C—E,EC—B,AC^B}O

+

求CAB)Fo

解設(shè)X

(1)

(^)X=ABi)CD=ABCDo

⑵X(。)*X⑴

X⑵二X⑴UBE=ABCDEO

⑶X⑵二U,算法終止

+

今(AB)F=ABCDEOAnIntroductiontoDatabaseSystem

4.Armstrong公理系統(tǒng)的有效性與完備性

?:?定理6.2Armstrong公理系統(tǒng)是有效的、完

備的

?:?證明：

1.有效性

可由定理6.1得證

2.完備性

只需證明逆否命題:若函數(shù)依賴XVY不能由尸

從Armstrong公理導(dǎo)出，那么它必然不為尸所蘊含

AnIntroductiontoDatabaseSystem

Armstrong公理系統(tǒng)完備性證明

(1)引理：若V—WZ成立，且VqXJ,則I/IZ=XJ

(2)構(gòu)造一張二維表「，它由下列兩個元組構(gòu)成，可以證明「必是R

(U,F)的一個關(guān)系，即戶中的全部函數(shù)依賴在r上成立。

VU-XJ

AA

(\

00……0

11……111……1

⑶若X—Y不能由「從Armstrong公理導(dǎo)出，則Y不是XJ的子集。

AnIntroductiontoDatabaseSystem

5.函數(shù)依賴集等價

定義6.14