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

。

AnIntroductiontoDatabaseSystem

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

AnIntroductiontoDatabaseSystem

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

6.1問(wèn)題的提出

6.2規(guī)范化

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

*6,4模式的分解

6.5小結(jié)

AnIntroductiontoDatabaseSystem

6.1問(wèn)題的提出

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

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

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

AnIntroductiontoDatabaseSystem

問(wèn)題的提出

一、概念回顧

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

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

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

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

AnIntroductiontoDatabaseSystem

'、概念回顧

?:?關(guān)系

關(guān)系模式

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

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

AnIntroductiontoDatabaseSystem

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

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

R(U,D,DOM,F)

R：關(guān)系名

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

D：屬性組U中屬性所來(lái)自的域

DOM：屬性向域的映象集合

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

AnIntroductiontoDatabaseSystem

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

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

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

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

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

AnIntroductiontoDatabaseSystem

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

2.數(shù)據(jù)依賴(lài)

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

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

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

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

AnIntroductiontoDatabaseSystem

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

3.數(shù)據(jù)依賴(lài)的類(lèi)型

?:?函數(shù)依賴(lài)（FunctionalDependency,簡(jiǎn)記為FD）

?:?多值依賴(lài)（MultivaluedDependency,簡(jiǎn)記為MVD）

其他

AnIntroductiontoDatabaseSystem

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

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

簡(jiǎn)化為一個(gè)三元組：

R(U,F)

當(dāng)且僅當(dāng)U上的一個(gè)關(guān)系門(mén)黃足F時(shí)，r稱(chēng)為關(guān)系模式R(U,

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

AnIntroductiontoDatabaseSystem

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

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

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

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

成績(jī)（Grade）

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

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

AnIntroductiontoDatabaseSystem

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

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

F={Sno—Sdept,Sdept-Mname,

(Sno,Cname)一Grade}

AnIntroductiontoDatabaseSystem

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

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

2.更新異常(UpdateAnomalies)

3.插入異常(InsertionAnomalies)

4.刪除異常(DeletionAnomalies)

AnIntroductiontoDatabaseSystem

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

結(jié)論：

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

■“好”的模式：

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

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

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

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

的數(shù)據(jù)依賴(lài)

AnIntroductiontoDatabaseSystem

分解關(guān)系模式

?:?把這個(gè)單一模式分成3個(gè)關(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問(wèn)題的提出

6.2規(guī)范化

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

*6,4模式的分解

6.5小結(jié)

AnIntroductiontoDatabaseSystem

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

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

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

AnIntroductiontoDatabaseSystem

規(guī)范化

6.2.1函數(shù)依賴(lài)

6.2.2碼

6.2.3范式

6.2.42NF

6.2.53NF

6.2.6BCNF

6.2.7多值依賴(lài)

6.2.84NF

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

AnIntroductiontoDatabaseSystem

6.2.1函數(shù)依賴(lài)

函數(shù)依賴(lài)

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

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

傳遞函數(shù)依賴(lài)

AnIntroductiontoDatabaseSystem

、函數(shù)依賴(lài)

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

子集。

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

組在X上的屬性值相等，而在Y上的屬性值不等，則稱(chēng)“X

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

AnIntroductiontoDatabaseSystem

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

2.語(yǔ)義范疇的概念

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

AnIntroductiontoDatabaseSystem

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

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

如果X—Y,但Y又X,則稱(chēng)X—Y是非平凡的函數(shù)依賴(lài)

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

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

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

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

(Sno,Cno)-Cno

AnIntroductiontoDatabaseSystem

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

若X—Y,則X稱(chēng)為這個(gè)函數(shù)依賴(lài)的決定屬性組，也

稱(chēng)為決定因素(Determinant)。

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

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

AnIntroductiontoDatabaseSystem

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

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

子集X、都有X，、Y,則稱(chēng)丫對(duì)*完全函數(shù)依賴(lài)，記作

X-^Yo

若X—丫，但丫不完全函數(shù)依賴(lài)于X,則稱(chēng)丫對(duì)X部分函數(shù)

依賴(lài)，記作XqY。

AnIntroductiontoDatabaseSystem

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

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

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

因?yàn)镾no—Sdept成立，且Sno是（Sno,Cno）

的真子集

AnIntroductiontoDatabaseSystem

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

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

則稱(chēng)Z對(duì)X傳遞函數(shù)依賴(lài)。

記為：X雪Z

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

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

Sno—Sdept,Sdept—Mname

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

AnIntroductiontoDatabaseSystem

規(guī)范化

6.2.1函數(shù)依賴(lài)

6.2.2碼

6.2.3范式

6.2.42NF

6.2.53NF

6.2.6BCNF

6.2.7多值依賴(lài)

6.2.84NF

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

AnIntroductiontoDatabaseSystem

6.2.2碼

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

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

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

(PrimaryKey)。

AnIntroductiontoDatabaseSystem

碼(續(xù))

主屬性與非主屬性

包含在任何一個(gè)候選碼中的屬性，稱(chēng)為主屬性(Prime

attribute)

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

或非碼屬性(Non-keyattribute)

?全碼

整個(gè)屬性組是碼，稱(chēng)為全碼(All-key)

AnIntroductiontoDatabaseSystem

碼(續(xù))

[例2]

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

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

[例3]

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

P：演奏者W：作品A：聽(tīng)眾

一個(gè)演奏者可以演奏多個(gè)作品

某一作品可被多個(gè)演奏者演奏

聽(tīng)眾可以欣賞不同演奏者的不同作品

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

AnIntroductiontoDatabaseSystem

碼(續(xù))

[例2]

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

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

[例3]

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

P：演奏者W：作品A：聽(tīng)眾

一個(gè)演奏者可以演奏多個(gè)作品

某一作品可被多個(gè)演奏者演奏

聽(tīng)眾可以欣賞不同演奏者的不同作品

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

AnIntroductiontoDatabaseSystem

規(guī)范化

6.2.1函數(shù)依賴(lài)

6.2.2碼

6.2.3范式

6.2.42NF

6.2.53NF

6.2.6BCNF

6.2.7多值依賴(lài)

6.2.84NF

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

AnIntroductiontoDatabaseSystem

6.2.3范式

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

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

要求的為不同范式

*范式的種類(lèi)：

〃第一范式(1NF)

第二范式(2NF)

J第三范式(3NF)

]BC范式(BCNF)

第四范式(4NF)

t第五范式(5NF)

AnIntroductiontoDatabaseSystem

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

INFo2NFo3NFoBCNFo4NFn5NF

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

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

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

AnIntroductiontoDatabaseSystem

規(guī)范化

6.2.1函數(shù)依賴(lài)

6.2.2碼

6.2.3范式

6.2.42NF

6.2.53NF

6.2.6BCNF

6.2.7多值依賴(lài)

6.2.84NF

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

AnIntroductiontoDatabaseSystem

6.2.42NF

?1NF的定義

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

則R&1NF

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

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

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

式

AnIntroductiontoDatabaseSystem

2NF(續(xù))

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

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

函數(shù)依賴(lài)包括：

(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滿(mǎn)足第一范式。

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

AnIntroductiontoDatabaseSystem

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

(1)插入異常

(2)刪除異常

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

(4)修改復(fù)雜

AnIntroductiontoDatabaseSystem

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

原因

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

解決方法

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

SC(Sno,Cno,Grade)

S-L(Sno,Sdept,Sloe)

AnIntroductiontoDatabaseSystem

2NF（續(xù)）

函數(shù)依賴(lài)圖:

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

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

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

AnIntroductiontoDatabaseSystem

2NF(續(xù))

2NF的定義

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

碼，則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ù)）

?：?采用投影分解法將一個(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

規(guī)范化

6.2.1函數(shù)依賴(lài)

6.2.2碼

6.2.3范式

6.2.42NF

6.2.53NF

6.2.6BCNF

6.2.7多值依賴(lài)

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,則稱(chēng)RvU,F>e3NF。

■若R￡3NF,則每一個(gè)非主屬性既不部分依賴(lài)于碼也不

傳遞依賴(lài)于碼。

AnIntroductiontoDatabaseSystem

3NF（續(xù)）

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

函數(shù)依賴(lài)：

Sno—Sdept

SdeptVSno

Sdept一Sloe

可得：

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

賴(lài)，S-L&3NF

AnIntroductiontoDatabaseSystem

3NF（續(xù)）

函數(shù)依賴(lài)圖:

AnIntroductiontoDatabaseSystem

3NF（續(xù)）

?：?解決方法

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

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

S-D(Sno,Sdept)

D-L(Sdept,Sloe)

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

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

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ù)）

?采用投影分解法將一個(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

規(guī)范化

6.2.1函數(shù)依賴(lài)

6.2.2碼

6.2.3范式

6.2.42NF

6.2.53NF

6.2.6BCNF

6.2.7多值依賴(lài)

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時(shí)X必含有碼，則RvU,F>eBCNFo

?:?等價(jià)于：每一個(gè)決定屬性因素都包含碼

AnIntroductiontoDatabaseSystem

BCNF（續(xù)）

?:?若R&BCNF

所有非主屬性對(duì)每一個(gè)碼都是完全函數(shù)依賴(lài)

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

依賴(lài)

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

充分

OR￡BCNF1tRE3NF

不必要

AnIntroductiontoDatabaseSystem

BCNF(續(xù))

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

Ce3NF

CeBCNF

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

假定S有兩個(gè)碼Sno,Sname

Se3NFo

S￡BCNF

AnIntroductiontoDatabaseSystem

BCNF(續(xù))

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

函數(shù)依賴(lài)：(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ù)依賴(lài)：

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

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

AnIntroductiontoDatabaseSystem

BCNF（續(xù)）

STJ中的函數(shù)依賴(lài)

AnIntroductiontoDatabaseSystem

BCNF（續(xù)）

STJe3NF

沒(méi)有任何非主屬性對(duì)碼傳遞依賴(lài)或部分依賴(lài)

STJ專(zhuān)BCNF

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

AnIntroductiontoDatabaseSystem

BCNF（續(xù)）

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

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

H0H—2

STTJ

沒(méi)有任何屬性對(duì)碼的部分函數(shù)依賴(lài)和傳遞函數(shù)依賴(lài)

AnIntroductiontoDatabaseSystem

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

?ReBCNF；Re3NF

要

?:?如果RW3NF,且R只有一個(gè)候選碼

充分

ReBCNF^=!：Re3NF

必要

AnIntroductiontoDatabaseSystem

規(guī)范化

6.2.1函數(shù)依賴(lài)

6.2.2碼

6.2.3范式

6.2.42NF

6.2.53NF

6.2.6BCNF

6.2.7多值依賴(lài)

6.2.84NF

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

AnIntroductiontoDatabaseSystem

6.2.7多值依賴(lài)

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

同的一套參考書(shū)。每個(gè)教員可以講授多門(mén)課程，每

種參考書(shū)可以供多門(mén)課程使用。

AnIntroductiontoDatabaseSystem

多值依賴(lài)（續(xù)）

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

教員T參考書(shū)B(niǎo)

課程c

［李勇，

普通物理學(xué)

物理<>

王軍光學(xué)原理

伊理習(xí)題青

［李勇A

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

張平微分方程

［高等代到

張平A

【周峰1J

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

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

?*?

*???

AnIntroductiontoDatabaseSystem

多值依賴(lài)（續(xù)）

用二維表表示Teaching

課程c教員T參考書(shū)B(niǎo)

普通物理學(xué)

光學(xué)原理

物理習(xí)題集

普通物理學(xué)

光學(xué)原理

物理習(xí)題集

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

微分方程

高等代數(shù)

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

微分方程

高等代數(shù)

AnIntroductiontoDatabaseSystem

多值依賴(lài)(續(xù))

TeachingeBCNF

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

AnIntroductiontoDatabaseSystem

多值依賴(lài)(續(xù))

Teaching模式中存在的問(wèn)題

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

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

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

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

AnIntroductiontoDatabaseSystem

多值依賴(lài)(續(xù))

?定義6.9

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

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

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

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

。例Teaching(C,T,B)

AnIntroductiontoDatabaseSystem

多值依賴(lài)（續(xù)）

?:?多值依賴(lài)的另一個(gè)等價(jià)的形式化的定義：

在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元組的丫值所得的兩個(gè)新元組必在r中），

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

Z=U-X-Yo

AnIntroductiontoDatabaseSystem

多值依賴(lài)（續(xù)）

?:?平凡多值依賴(lài)和非平凡的多值依賴(lài)

若X一一丫，而Z=（p,則稱(chēng)

X——Y為平凡的多值依賴(lài)

否則稱(chēng)X--丫為非平凡的多值依賴(lài)

AnIntroductiontoDatabaseSystem

多值依賴(lài)(續(xù))

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

w表示倉(cāng)庫(kù)，s表示保管員，c表示商品

■假設(shè)每個(gè)倉(cāng)庫(kù)有若干個(gè)保管員，有若干種商品

■每個(gè)保管員保管所在的倉(cāng)庫(kù)的所有商品

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

AnIntroductiontoDatabaseSystem

多值依賴(lài)

wsC

W1SICl

W1SIC2

W1SIC3

W1S2Cl

W1S2C2

W1S2C3

W2S3C4

W2S3C5

W2S4C4

W2S4C5

AnIntroductiontoDatabaseSystem

多值依賴(lài)（續(xù)）

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

AnIntroductiontoDatabaseSystem

多值依賴(lài)的性質(zhì)

(1)多值依賴(lài)具有對(duì)稱(chēng)性

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

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

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

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

若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

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

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

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

Y'uY均有X—Y，成立

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

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

AnIntroductiontoDatabaseSystem

規(guī)范化

6.2.1函數(shù)依賴(lài)

6.2.2碼

6.2.3范式

6.2.42NF

6.2.53NF

6.2.6BCNF

6.2.7多值依賴(lài)

6.2.84NF

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

AnIntroductiontoDatabaseSystem

6.2.84NF

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

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

Re4NFo

?如果Re4NF,則ReBCNF

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

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

AnIntroductiontoDatabaseSystem

4NF（續(xù)）

例：Teachings,T,B)^4NF

存在非平凡的多值依賴(lài)C一一T,且C不是碼

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

CT(C,T)e4NF

CB(C,B)e4NF

C一一T,C一一B是平凡多值依賴(lài)

AnIntroductiontoDatabaseSystem

規(guī)范化

6.2.1函數(shù)依賴(lài)

6.2.2碼

6.2.3范式

6.2.42NF

6.2.53NF

6.2.6BCNF

6.2.7多值依賴(lài)

6.2.84NF

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

AnIntroductiontoDatabaseSystem

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

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

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

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

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

AnIntroductiontoDatabaseSystem

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

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

1NF

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

消除決定屬性2NF

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

凡函數(shù)依賴(lài)3NF

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

BCNF

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

4NF

圖6.8規(guī)范化過(guò)程

AnIntroductiontoDatabaseSystem

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

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

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

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

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

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

AnIntroductiontoDatabaseSystem

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

6.1問(wèn)題的提出

6.2規(guī)范化

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

*6.4模式的分解

6.5小結(jié)

AnIntroductiontoDatabaseSystem

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

?:?邏輯蘊(yùn)含

定義6.11對(duì)于滿(mǎn)足一組函數(shù)依賴(lài)戶(hù)的關(guān)系模式F>,

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

兩元組f,s,若fX]=sX],則"]=sY]）,則稱(chēng)「邏輯

蘊(yùn)含X-Y

AnIntroductiontoDatabaseSystem

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

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

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

含。

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

U,則XZ-YZ為f所蘊(yùn)含。

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

X—Z為尸所蘊(yùn)含。

AnIntroductiontoDatabaseSystem

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

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

證：設(shè)u

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

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

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

AnIntroductiontoDatabaseSystem

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

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

蘊(yùn)含。

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

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

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

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

XZ-YZ為F所蘊(yùn)含,增廣律得證。

AnIntroductiontoDatabaseSystem

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

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

x-z為尸所蘊(yùn)含。

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

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

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

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

律得證。

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)出來(lái)

的每一個(gè)函數(shù)依賴(lài)一定在戶(hù)中；

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

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

AnIntroductiontoDatabaseSystem

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

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

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

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

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

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

AnIntroductiontoDatabaseSystem

EgsASQseqgea。1uogonponu-u4

……

《

—喇

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

個(gè)

個(gè)

個(gè)

(ZAXZAXz>x個(gè)ZX.ZAX>xz>zx

個(gè)

個(gè)

個(gè)

下

ZX個(gè)ZAXxzx-zx>xz>x

個(gè)

個(gè)

個(gè)

z>個(gè)z>xZxzxz>AX-ZXx

個(gè)

個(gè)

下

"x個(gè)xZXAX>x

個(gè)

ZAX”xX

個(gè)

個(gè)

個(gè)

個(gè)

個(gè)

Z個(gè)ZAXZ>z>ZZXZ>xz>>zx

個(gè)

個(gè)

”個(gè)

”個(gè)

個(gè)

>個(gè)z>xZz>zx>xz>>x

個(gè)

尸個(gè)

個(gè)

個(gè)

個(gè)

”個(gè)

X個(gè)z>xz>XzxX>xZZAxX

個(gè)

個(gè)

個(gè)

個(gè)

個(gè)

個(gè)

s個(gè)z>xsz>3zxs>x§Z3>§X

H+L

L

”個(gè)

N個(gè)>XHL

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

引理62

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

+

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

?:?用途

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

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

AnIntroductiontoDatabaseSystem

求閉包的算法

算法6.1求屬性集X(X=U)關(guān)于U上的函數(shù)依賴(lài)集產(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

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

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

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

會(huì)終止。

AnIntroductiontoDatabaseSystem

函數(shù)依賴(lài)閉包

［例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ù)依賴(lài)XVY不能由尸

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

AnIntroductiontoDatabaseSystem

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

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

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

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

VU-XJ

AA

(\

00……0

11……111……1

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

AnIntroductiontoDatabaseSystem

5.函數(shù)依賴(lài)集等價(jià)

定義6.14