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

12:221問(wèn)題的提出規(guī)范化數(shù)據(jù)依賴的公理系統(tǒng)模式的分解第六章關(guān)系數(shù)據(jù)理論31.關(guān)系數(shù)據(jù)庫(kù)有關(guān)概念回顧關(guān)系：關(guān)系是由行和列組成的表。元組：關(guān)系表中的每一行稱為元組。屬性：關(guān)系表中每一個(gè)帶名稱的列。碼 ：唯一可以確定一個(gè)元組的某個(gè)屬性（集）稱為本關(guān)系的碼（也稱鍵）。域：域是一個(gè)或多個(gè)屬性的取值集合。6.1

問(wèn)題的提出分量：元組中的一個(gè)屬性值稱為該元組的分量。維：關(guān)系所包含的屬性個(gè)數(shù)?；鶖?shù)：關(guān)系中元組的個(gè)數(shù)稱為關(guān)系的基數(shù)。關(guān)系數(shù)據(jù)庫(kù)：是具有不同關(guān)系名的規(guī)范化關(guān)系的一個(gè)集合。關(guān)系模型關(guān)系數(shù)據(jù)庫(kù)標(biāo)準(zhǔn)語(yǔ)言SQL1.關(guān)系數(shù)據(jù)庫(kù)有關(guān)概念回顧（續(xù)）6.1

問(wèn)題的提出6.1

問(wèn)題的提出2.關(guān)系數(shù)據(jù)庫(kù)的邏輯設(shè)計(jì)問(wèn)題應(yīng)該如何構(gòu)造關(guān)系模式？每個(gè)關(guān)系應(yīng)由哪些屬性組成？針對(duì)具體問(wèn)題、具體應(yīng)用，如何構(gòu)造與其相適應(yīng)的關(guān)系模式？6.1

問(wèn)題的提出3.關(guān)系模式——關(guān)系的描述表示為：R（U，D，dom，F(xiàn)）其中:R——是關(guān)系名

U——是屬性組D——是屬性組U中屬性所來(lái)自的域的集合

dom——為屬性向域的映射F——為屬性間數(shù)據(jù)的依賴關(guān)系的集合通常簡(jiǎn)記為：R（U）或：R（A1，A2，…，An）

其中：A1，A2，…，An為屬性名6.1

問(wèn)題的提出3.關(guān)系模式——關(guān)系的描述(續(xù))在關(guān)系數(shù)據(jù)庫(kù)的邏輯設(shè)計(jì)時(shí)，我們主要考慮屬性及其屬性間數(shù)據(jù)的依賴關(guān)系。R（U，F(xiàn)）可以描述為：當(dāng)且僅當(dāng)在U上的一個(gè)關(guān)系r滿足F時(shí)，稱r為關(guān)系模式R（U，F(xiàn)）的一個(gè)關(guān)系。6.1

問(wèn)題的提出4.關(guān)系數(shù)據(jù)庫(kù)的邏輯設(shè)計(jì)時(shí)可能會(huì)出現(xiàn)的問(wèn)題例6.1設(shè)關(guān)系模式Staffbranch如下:B0002

石家莊

石家莊市北

050003馬路90號(hào)B0002

石家莊

石家莊市北

050003馬路90號(hào)B0002

石家莊

石家莊市北

050003馬路90號(hào)SG401

吳德海

男 經(jīng)理

5500.

B0004

廣州

廣州市沙河

510501路40號(hào)Staffbranch

(

Staff

No，name，sex，position，salary，branch

No，city，address，postcod存e在)

數(shù)StaffNo

name

sexpositionsalaryBranch

Nocityaddress據(jù)冗余postcodeSB101

趙海洋

男經(jīng)理8000.B0001北京北京海淀區(qū)青龍橋18號(hào)100091SS201

錢(qián)光明

男會(huì)產(chǎn)生數(shù)經(jīng)理6000.B0002石家莊石家莊市北馬路90號(hào)050003SS2據(jù)12的孫更佩霞新女異常SS223

李萬(wàn)章

男經(jīng)理助理業(yè)務(wù)員5000.3000.B0002石家莊石家莊市北馬路90號(hào)050003B0002石家莊石家莊市北馬路90號(hào)050003SB112

周

全

男經(jīng)理助理6000.B0001北京北京海淀區(qū)青龍橋18號(hào)100091SG401吳德海男經(jīng)理5500.B0004廣州廣州市沙河路40號(hào)5105016.1

問(wèn)題的提出5.冗余數(shù)據(jù)和更新異常問(wèn)題的解決方法為解決關(guān)系staffbranch中存在的冗余數(shù)據(jù)和更新異常問(wèn)題?？蓪⒃撽P(guān)系進(jìn)行分解，形成2個(gè)新的關(guān)系來(lái)避免上述異常。分解如下：Staff(StaffNo，name，sex，position，salary，branch

No)branch(branchNo，city，address，postcode)6.1

問(wèn)題的提出Branch

NocityaddresspostcodeB0001北京北京海淀區(qū)青龍橋18號(hào)100091B0002石家莊石家莊市北馬路90號(hào)050003B0003大連大連市中山區(qū)解放路10號(hào)116002B0004廣州廣州市沙河路40號(hào)510501B0005長(zhǎng)沙長(zhǎng)沙市韶山北路168號(hào)410003branchstaffStaff

NonamesexpositionsalaryBranch

NoSB101趙海洋男經(jīng)理8000.B0001SS201錢(qián)光明男經(jīng)理6000.B0002SS212孫佩霞女經(jīng)理助理5000.B0002SS223李萬(wàn)章男業(yè)務(wù)員3000.B0002SB112周全男經(jīng)理助理6000.B0001SG401吳德海男經(jīng)理5500.B00046.1

問(wèn)題的提出6.規(guī)范化問(wèn)題的提出將一個(gè)關(guān)系分解成多個(gè)較小的關(guān)系時(shí)要考慮兩個(gè)問(wèn)題：無(wú)損連接：確保初始關(guān)系的任一實(shí)例都可以通過(guò)分解后的關(guān)系中相應(yīng)實(shí)例獲得。保持函數(shù)依賴特性。如何來(lái)構(gòu)造結(jié)構(gòu)良好的關(guān)系？—規(guī)范化規(guī)范化是用來(lái)生成既有所期望的特性，又滿足用戶的數(shù)據(jù)需求的一組關(guān)系的技術(shù)。6.2

規(guī)范化函數(shù)依賴碼（鍵）多值依賴和范式6.2.1

函數(shù)依賴1.函數(shù)依賴的定義定定義義66.1.1另一設(shè)R種（描U）述是屬性集U上的關(guān)系模式，X、Y所是謂U函的數(shù)子依集賴。是若描對(duì)述于一R個(gè)（關(guān)U）系的中任屬意性一之個(gè)間可的聯(lián)能系的。關(guān)假系設(shè)Xr，和rY中均不為可關(guān)能系存R在的兩屬個(gè)性元，組如在果X上的的每屬個(gè)性值值都相是等與，而Y中在惟Y上一的一屬個(gè)性值值對(duì)不應(yīng)等，，就則稱稱YX函函數(shù)數(shù)依確賴定于YX或（Y表函示數(shù)為依

賴X→于YX），。記X為和XY→可Y能。是由一個(gè)或多個(gè)屬性組成。2.常用術(shù)語(yǔ)及記號(hào)6.2.

1

函數(shù)依賴X→Y，但YX→Y，但YX

則稱X→Y是平凡依賴。X

則稱X→Y是非平凡依賴。X→Y，但X∩Y=?

則稱X→Y是完全非平凡依賴。X→Y

，Y→X

，則記為X?Y。若Y不函數(shù)依賴于X，則記為X→Y。若X

→Y

，則X叫做決定因素或決定方。例6.2函數(shù)依賴舉例——staffStaff

Nonamesexpositionsalarybranch

NoSB101趙海洋男經(jīng)理8000.B0001SS201錢(qián)光明男經(jīng)理6000.B0002SS212孫佩霞女經(jīng)理助理5000.B0002SS223李萬(wàn)章男業(yè)務(wù)員3000.B0002SB112周全男經(jīng)理助理6000.B0001SG401吳德海男經(jīng)理5500.B0004例如：?jiǎn)T工的編號(hào)與員工的姓名存在：staff

No→namename函數(shù)依賴于staffNostaff

No

name6.2.

1

函數(shù)依賴?yán)?.2函數(shù)依賴舉例——staffStaff

Nonamesexpositionsalarybranch

NoSB101趙海洋男經(jīng)理8000.B0001SS201錢(qián)光明男經(jīng)理6000.B0002SS212孫佩霞女經(jīng)理助理5000.B0002SS223李萬(wàn)章男業(yè)務(wù)員3000.B0002SB112周全男經(jīng)理助理6000.B0001SG401吳德海男經(jīng)理5500.B00046.2.

1

函數(shù)依賴屬性

staff

No

與屬性

sex有：staff

No→sex反過(guò)來(lái)，對(duì)屬性sex的每個(gè)值屬性staffNo有多個(gè)值與其相對(duì)應(yīng)。我們說(shuō)屬性staffNo不函數(shù)依賴于屬性sex。記為：sex

→staff

No6.2.

1

函數(shù)依賴?yán)?.3函數(shù)依賴舉例2例6.3

為例6.1定義的關(guān)系staffbranch確定一組有用的函數(shù)依賴。Staff

branch

(Staff

No，name，sex，position，salary，branch

No，city，address，postcode)基于對(duì)上述屬性的理解我們可知：對(duì)給定的員工編號(hào)可以確定該員工的信息（包括姓

名、性別、職務(wù)、工資、所屬分支、工作地址等）。分支編號(hào)可以確定分支地址。分支地址也可以確定分支編號(hào)。分支編號(hào)和職務(wù)可以決定工資。分支地址和職務(wù)也可以確定工資。6.2.1

函數(shù)依賴Staff

No

→

nameStaff

No

→

sexStaff

No

→

positionStaff

No

→

salarybranch

No

→

city，address，postcodecity，address，postcode

→ branch

Nobranch

No，position

→

salarycity，address，postcode，position

→

salaryStaff

No

→ branch

NoStaff

No

→

cityStaff

No

→

addressStaff

No

→

postcode例6.3函數(shù)依賴舉例2(續(xù))Staff

branch

(Staff

No，name，sex，position，salary，branch

No，city，address，postcode)據(jù)此可得到一組函數(shù)依賴：3.完全函數(shù)依賴6.2.

1

函數(shù)依賴定義6.2在R（U）中，如果X

→Y，并且對(duì)于X的任何一個(gè)真子集X′，都有X′→Y，則稱Y對(duì)X完全函數(shù)依賴。記為：X

→F

Y若X→Y，但Y不完全函數(shù)依賴于X，則稱Y對(duì)X部分函數(shù)依賴。記作：

X

→P

Y6.2.

1

函數(shù)依賴——完全函數(shù)依賴定義6.2 的另一種定義——語(yǔ)言描述完全函數(shù)依賴假設(shè)X和Y是關(guān)系R的屬性組，如果Y函數(shù)依賴于

X，但不函數(shù)依賴于X的任一真子集時(shí)，我們就說(shuō)Y完全函數(shù)依賴于X。部分函數(shù)依賴假設(shè)X和Y是關(guān)系R的屬性組，Y函數(shù)依賴于X，如果移除X中的某些屬性，這種依賴仍然存在，我們就說(shuō)Y部分函數(shù)依賴于X。4.傳遞函數(shù)依賴6.2.1

函數(shù)依賴定義6.3

在R（U）中，如果X

→Y，Y X，Y→X，Y→Z，則稱Z對(duì)X傳遞函數(shù)依賴。記為：X→Z6.2.2 碼（鍵）設(shè)K為R（U）中的屬性或?qū)貴定義6.4性組，如果K U，則稱K為R的候選碼（候選鍵）。若候選碼（候選鍵）多于一個(gè)，則選定其中的一個(gè)為主碼（主鍵）。簡(jiǎn)單情況：關(guān)系中只有一個(gè)屬性，則單個(gè)屬性是碼。極端情況：關(guān)系中的所有屬性都是碼，則稱為全碼。6.2

.2

碼（鍵）Staff

No

→

nameStaff

No

→

sexStaff

No

→

positionStaff

No

→

salaryStaff

No

→ branch

NoStaff

No

→

cityStaff

No

→

addressStaff

No

→

postcode碼（鍵）舉例關(guān)系模式：Staff

branch

(Staff

No，name，sex，position，salary，branch

No，city，address，postcode)branch

No

→

city，address，postcodecity，address，postcode

→ branch

Nobranch

No，position

→

salarycity，address，postcode，position

→

salary只有屬性StaffNo是唯一的候選碼，StaffNo也就成為關(guān)系staffbranch的主碼（主鍵），其屬性StaffNo稱為主屬性。6.2.

2

碼（鍵）例6.4 著作關(guān)系模式著作關(guān)系模式為:Author

(name，city，street，title)姓名

name住址

city

，street作品

titleAuthor關(guān)系模式實(shí)例：著者姓名：瓊瑤住址二處：臺(tái)北市長(zhǎng)沙市忠孝西路365號(hào)湘春路25號(hào)作品三部：還珠格格月朦朧，鳥(niǎo)朦朧碧云天namecitystreettitel瓊

瑤臺(tái)北市忠孝西路365號(hào)還珠格格瓊

瑤長(zhǎng)沙市湘春路25號(hào)還珠格格瓊

瑤臺(tái)北市忠孝西路365號(hào)月朦朧，鳥(niǎo)朦朧瓊

瑤長(zhǎng)沙市湘春路25號(hào)月朦朧，鳥(niǎo)朦朧瓊

瑤臺(tái)北市忠孝西路365號(hào)碧云天瓊

瑤長(zhǎng)沙市湘春路25號(hào)碧云天例6.4 著作關(guān)系模式實(shí)例6.2.

2

碼（鍵）如何確定碼（鍵）？①單獨(dú)某一個(gè)屬性不能確定唯一的元組。②任意兩個(gè)屬性也不能確定唯一的元組。③任意三個(gè)屬性也不能確定唯一的元組。④只有四個(gè)屬性一起才能確定唯一的元組。所以關(guān)系A(chǔ)uthor的碼（鍵）是：（name，city，street，title）（全碼關(guān)系）外部碼定義6.2.

2

碼（鍵）定義6.5

關(guān)系模式R中屬性或?qū)傩越MX不是R的碼，但X是另一個(gè)關(guān)系模式的碼，則稱X是R的外部碼，也稱外碼。例：關(guān)系模式staff和關(guān)系模式branchstaff

(Staff

No,

name,

sex,

position,

salary,

branchNo)branch

(branchNo，city，address，postcode)關(guān)系模式staff中的屬性branchNo不是staff的碼。而關(guān)系模式branch的主碼為branch

No

。我們就稱branch

No為關(guān)系模式staff的外碼。主碼的確定6.2.

2

碼（鍵）根據(jù)函數(shù)依賴確定決定方（因素）考察決定方找出候選碼確定主碼（主鍵）6.2.3

多值依賴和范式范式的概念范式是關(guān)系模式的規(guī)范形式。規(guī)范化是用來(lái)生成既有所期望的特性，又滿足用戶的數(shù)據(jù)需求的一組關(guān)系的技術(shù)。換句話說(shuō)：把一個(gè)給定的關(guān)系模式轉(zhuǎn)換成某種范式的過(guò)程稱為關(guān)系模式的規(guī)范化過(guò)程，簡(jiǎn)稱規(guī)范化。5NF

4NF

BCNF

3NF

2NF

1NF各種范式之間的關(guān)系1NF2NF3NFBCNF4NF5NF更高級(jí)關(guān)系數(shù)據(jù)庫(kù)中的關(guān)系是要滿足一定要求的，滿足不同程度要求的為不同的范式。滿足最低要求的為第一范式，簡(jiǎn)稱1NF。在滿足第一范式基礎(chǔ)上滿足進(jìn)一步要求的是第二范式，即2NF。依此類推。6.2.3

多值依賴和范式6.2.3

多值依賴和范式一、第一范式設(shè)R是一個(gè)關(guān)系模式，如果R的每個(gè)屬性的值域都是不可分割的簡(jiǎn)單數(shù)據(jù)項(xiàng)的集合，則稱這個(gè)關(guān)系模式為第一范式關(guān)系模式?？捎洖椋?/p>

R∈1NF換個(gè)說(shuō)法：如果關(guān)系模式R中的所有屬性值都是不可再分割的原子值，那么就稱R是第一范式的關(guān)系模式。二、第二范式6.2.3

多值依賴和范式定義6.6若R∈1NF，且每一個(gè)非主屬性完全依賴于碼，則R∈2NF

。另一種表述：第二范式是符合第一范式的關(guān)系，并且每個(gè)非主關(guān)鍵屬性都完全依賴于主關(guān)鍵屬性。6.2.3

多值依賴和范式——第二范式第二范式——實(shí)例關(guān)系：Staff

branch

(staffNo，name，sex，position，salary，branchNo，city，address，postCode)staffbranch∈1NF它的主關(guān)鍵屬性是staffNo且只有一個(gè)，其它屬性都是非主關(guān)鍵屬性且都完全依賴于

staffNo。因此有：staffbranch

∈2NF只有一個(gè)主碼（鍵）的關(guān)系是2NF的關(guān)系。6.2.3

多值依賴和范式—第二范式例6.5 教材P175

例4關(guān)系模式（學(xué)生—住處—課程關(guān)系）如下：S-L-C（SNO，SDEPT，SLOC，

CNO，

G）學(xué)號(hào)

系別

住所

課程號(hào)

成績(jī)從關(guān)系中我們可知：由學(xué)號(hào)和課程號(hào)我們可確定成績(jī)。也就是說(shuō)成績(jī)是完全依賴于學(xué)號(hào)和課程號(hào)的。因此：（SNO，CNO）→F

G由學(xué)號(hào)和課程號(hào)可以確定系別，學(xué)號(hào)也可以確定系別。SNO

→

SDEPT

，（SNO，CNO）→P

SDEPT6.2.3

多值依賴和范式—第二范式例6.5 教材P175

例4（續(xù)）由學(xué)號(hào)和課程號(hào)可以確定學(xué)生住處，學(xué)號(hào)也可以確定學(xué)生住處，系別也可以確定學(xué)生的住處。PSNO

→

SLOC

，（SNO，CNO）→

SLOC，SDEPT

→

SLOC綜上所述：學(xué)生的成績(jī)是完全依賴于學(xué)號(hào)和課程號(hào)的，而學(xué)生的系別和住處是部分依賴于學(xué)號(hào)和課程號(hào)。唯一能標(biāo)識(shí)一個(gè)元組的只有屬性組(SNO，CNO)。因而，在關(guān)系S-L-C屬于第一范式，主碼由SNO

和CON兩個(gè)屬性組成。但每個(gè)非主關(guān)鍵屬性并不都完全依賴于主關(guān)鍵屬性（如SLOC、SDEPT），所以它不是第二范式的。例6.5 教材P175

例4（續(xù)）6.2.3

多值依賴和范式—第二范式解決的辦法：分解關(guān)系S-L-C。唯一能標(biāo)識(shí)一個(gè)元組的只有屬性組(SNO，CNO)。關(guān)系模式：學(xué)號(hào)

系別

住所

課程號(hào)S-L-C（SNO，SDEPT，SLOC，

CNO，

G）成績(jī)存在更新異常的問(wèn)題！問(wèn)題的所在之一是關(guān)系中有兩種非主屬性：一種是對(duì)碼完全依賴的非主屬性，另一種是對(duì)碼部分依賴的非主屬性。6.2.3

多值依賴和范式—第二范式例6.5

關(guān)系分解的方法①先把部分依賴的屬性移到一個(gè)新表。即把屬性SDEPT，SLOC移到新表SL中。②再把這些屬性的決定方復(fù)制到新表SL中。形成新表：SL（SNO，SDEPT，SLOC）得到兩個(gè)新的關(guān)系：SC（SNO，CNO，G）SL（SNO，SDEPT，SLOC）關(guān)系SC

的主碼是（SNO，CNO）并有：F（SNO，CNO）→

G關(guān)系SL主碼是SNO

并有：SNO

F

SDEPT

和SNO

F

SLOC）→

→6.2.3

多值依賴和范式三、第三范式定義6.7關(guān)系模式R（U，F(xiàn)）中若不存在這樣的碼X、屬性組Y及非主屬性組Z(Z

Y)使得：X→Y，Y→Z，（Y→X）成立。則稱：

R（U）∈

3NF另一種描述：關(guān)系R（U）滿足2NF，在關(guān)系R中的所有非主關(guān)鍵屬性都不是傳遞依賴于主關(guān)鍵屬性的，則關(guān)系R是3NF的。由滿足第二范式的關(guān)系變換成滿足第三范式的關(guān)系就是要消除關(guān)系中存在的依賴于主關(guān)鍵屬性的傳遞依賴。Why?存在更新異常！6.2.3

多值依賴和范式——第三范式例：SC（SNO，CNO，G）SL（SNO，SDEPT，SLOC）在關(guān)系SL中存在傳遞依賴：SNO

→

SDEPTSDEPT→SLOC（系別可以決定住處）當(dāng)某個(gè)系的學(xué)生調(diào)整住處時(shí)，關(guān)系中所有與該系相關(guān)的學(xué)生記錄都必須一一修改，若有一處遺漏就會(huì)造成不一致。如果學(xué)校對(duì)所有學(xué)生住處進(jìn)行調(diào)整，則所有記錄都要改變。Why?存在更新異常！——再例6.2.3

多值依賴和范式——第三范式再如：Staffbranch

(staffNo，name，sex，position，salary，branchNo，city，address，postCode)函數(shù)依賴：staffNo

→

name，sex，position，salary，branchNo，city，address，postCodebranchNo

→

city，address，postCodecity，address，postCode

→

branchNo在關(guān)系中存在傳遞依賴：staffNo

→

branchNobranchNo

→

city，address，postCode12:22Why?存在更新異常！Staff

branchStaff

NonamesexpositionsalaryBranchNocityaddresspostcodeSB101趙海洋男經(jīng)理8000.B0001北京北京海淀區(qū)青龍橋18號(hào)100091SS201錢(qián)光明男經(jīng)理6000.B0002石家莊石家莊市北馬路90號(hào)050003SS212孫佩霞女經(jīng)理助理5000.B0002石家莊石家莊市北馬路90號(hào)050003SS223李萬(wàn)章男業(yè)務(wù)員3000.B0002石家莊石家莊市北馬路90號(hào)050003SB112周全男經(jīng)理助理6000.B0001北京北京海淀區(qū)青龍橋18號(hào)100091SG401吳德海男經(jīng)理5500.B0004廣州廣州市沙河路40號(hào)510501刪除“吳德?！边@一記錄，會(huì)造成分支機(jī)構(gòu)信息的丟失。因?yàn)椋摲种C(jī)構(gòu)目前只有一個(gè)工作人員的記錄。6.2.3

多值依賴和范式——第三范式6.2.3

多值依賴和范式——第三范式如何消除傳遞依賴？①將傳遞依賴的屬性移到一個(gè)新的關(guān)系表中。②再將這些屬性的決定方復(fù)制到新建的關(guān)系表中。例如：將屬性city，address，postCode移到一個(gè)新的關(guān)系表branch中。再將這些屬性的決定方branchNo復(fù)制到新建的關(guān)系表branch中。這樣形成兩個(gè)新的關(guān)系：Branch

(branchNo，city，address，postCode)Staff(staffNo，name，sex，position，salary，branchNo)6.2.3

多值依賴和范式——第三范式如何消除傳遞依賴？再例如：SL（SNO，SDEPT，SLOC）在關(guān)系SL中存在傳遞依賴：SNO

→

SDEPTSDEPT

→

SLOC將屬性SLOC移到一個(gè)新的關(guān)系表DL中。再將這些屬性的決定方SDEPT復(fù)制到新建的關(guān)系表DL中。這樣形成兩個(gè)新的關(guān)系：

SD（SNO，SDEPT）DL（SDEPT，SLOC）6.2.3

多值依賴和范式四、BCNF（Boyce

Codd Normal

Form

）范式BCNF范式是Boyce和Codd在1974年提出的。經(jīng)過(guò)2NF和3NF

的規(guī)范消除了存在在主碼（主關(guān)鍵字）上的部分依賴和傳遞依賴，這樣就可以消除更新異常。但并不是說(shuō)符合3NF的關(guān)系就不存在更新異常。但是，經(jīng)過(guò)2NF和3NF

的規(guī)范并沒(méi)有考慮關(guān)系中其他候選碼（候選關(guān)鍵字）

（如果關(guān)系中還存在其他候選碼<候選關(guān)鍵字>的話）。因此，BCNF范式是第三范式的修正或擴(kuò)充。6.2.3

多值依賴和范式四、BCNF（Boyce

Codd Normal

Form

）范式定義6.8

關(guān)系模式R（U，F(xiàn)）∈1NF。若X→Y且Y

X時(shí)X必含有碼，則R（U，F(xiàn)）∈BCNF

。另一種描述：一個(gè)關(guān)系是符合BCNF的，當(dāng)且僅當(dāng)每

個(gè)函數(shù)依賴的決定方都是碼（候選關(guān)鍵字）。6.2.3

多值依賴和范式—BCNF范式BCNF范式——實(shí)例我們考察下面的關(guān)系：SD（SNO，SDEPT）SNO

→

SDEPTDL（SDEPT，SLOC）SDEPT

→

SLOC關(guān)系SD決定方SNO是碼，所以SD∈BCNF關(guān)系DL

的決定方SDEPT是碼，所以DL∈BCNF。6.2.3

多值依賴和范式—BCNF范式例6.6

BCNF范式實(shí)例2（教材P177的例7

）關(guān)系模式

SJP（

S

，

J

，

P

）學(xué)生課程名次

假設(shè)沒(méi)有并列名次，現(xiàn)在我們分析：名次P不可能單獨(dú)由課程來(lái)決定

名次P也不可能單獨(dú)由學(xué)生來(lái)決定名次P可以由學(xué)生和課程共同來(lái)決定因此有

（S，J）→P

是一個(gè)完全函數(shù)依賴6.2.3

多值依賴和范式—BCNF范式例6.6

（續(xù)）關(guān)系模式

SJP（

S

，

J

，

P

）學(xué)生課程名次學(xué)生S

不可能單獨(dú)由課程來(lái)決定學(xué)生S

也不可能單獨(dú)由排名來(lái)決定學(xué)生S

可以由課程和排名來(lái)共同決定因此有

（J，P）→S

也是一個(gè)完全函數(shù)依賴這樣，（

S，J）和（J，P）都可以作為關(guān)系SJP的候選碼，每個(gè)碼都由兩個(gè)屬性組成。因?yàn)殛P(guān)系SJP

沒(méi)有部分依賴，也沒(méi)有對(duì)碼的傳遞依賴，所以SJP∈3NF。同時(shí)，兩個(gè)函數(shù)依賴的決定方都是碼，所以SJP∈BCNF

。6.2.3

多值依賴和范式—BCNF范式例6.7

再分析教材P177的例8關(guān)系模式

STJ（

S

，T

，J

）學(xué)生教師課程每個(gè)教師只教一門(mén)課，每門(mén)課有若干教師，學(xué)生選定某門(mén)課就對(duì)應(yīng)一個(gè)教師。函數(shù)依賴如下：（S，T）→J

；（S，J）→T

；T→J其中

（S，T）和（S，J）是候選碼從函數(shù)依賴關(guān)系式我們可知沒(méi)有任何非主屬性對(duì)碼傳遞依賴或部分依賴。STJ∈3NF但STJ

ˇ

BCNF

，因?yàn)門(mén)是決定方，但T不是碼。6.2.3

多值依賴和范式—BCNF范式什么情況下會(huì)違反BCNF關(guān)系？一般的情形是：關(guān)系中包含兩個(gè)（或更多的）復(fù)合候選碼。候選碼關(guān)鍵字重疊，通常至少有一個(gè)重疊的屬性。關(guān)系STJ就屬于這種情形。這種情形的關(guān)系也存在更新異常：如：刪除一個(gè)學(xué)生記錄時(shí)，連同教師及該教師所教課程的信息都刪除了。如果，記載教師所教課程的信息只有這一個(gè)記錄了，則丟失了該教師所教課程的信息，產(chǎn)生異常。6.2.3

多值依賴和范式課程C教師T參考書(shū)B(niǎo)物理李勇王軍普通物理學(xué)光學(xué)原理

物理習(xí)題集數(shù)學(xué)李勇張平數(shù)學(xué)分析微分方程高等代數(shù)………一門(mén)課程多個(gè)教師，選用多本參考書(shū)。一本書(shū)可供多門(mén)課程采用作為參考書(shū)。五、多值依賴1.

多值依賴的成因關(guān)系是一個(gè)表，第一范式要求關(guān)系的每個(gè)屬性的值域都是不可分割的簡(jiǎn)單數(shù)據(jù)項(xiàng)的集合。也就是說(shuō)，第一范式不允許一個(gè)元組的某個(gè)屬性含有多個(gè)值。例如：用符合1NF的關(guān)系表表示：6.2.3

多值依賴和范式—多值依賴課程C教師T參考書(shū)B(niǎo)物理李勇普通物理學(xué)物理李勇光學(xué)原理物理李勇物理習(xí)題集物理王軍普通物理學(xué)物理王軍光學(xué)原理物理王軍物理習(xí)題集數(shù)學(xué)李勇數(shù)學(xué)分析數(shù)學(xué)李勇微分方程數(shù)學(xué)李勇高等代數(shù)數(shù)學(xué)張平數(shù)學(xué)分析數(shù)學(xué)張平微分方程數(shù)學(xué)張平高等代數(shù)………對(duì)這個(gè)關(guān)系的更新操作很不方便。存在數(shù)據(jù)冗余。原因：存在多值依賴。如：C→→TC

→→

B定義6.92.多值依賴的定義設(shè)R（U）是屬性集U上的一個(gè)關(guān)系6.2.3

多值依賴和范式—多值依賴模式。X、Y、Z

是U的子集，并且Z=U–X–Y

。關(guān)系模式R（U）中多值依賴X→→Y

成立，當(dāng)且僅當(dāng)對(duì)R（U）的任一關(guān)系r，給定的一對(duì)（x，z）值，有一組Y的值，這組值僅僅決定于x值而與z值無(wú)關(guān)。我們用另一種描述來(lái)定義多值依賴：表示關(guān)系中屬性（如A、B和C）之間的依賴。對(duì)于A的每個(gè)值都存在一個(gè)B或C的值的集合，而且，B和C的值集合是相互獨(dú)立的。平凡多值依賴對(duì)于關(guān)系R（U）中的一個(gè)多值依賴：A

→→B如果：

a)

B是A的子集，或者：

b)

A∪B

=

U

。那么多值依賴A→→B就是平凡多值依賴。否則，多值依賴A→→B就是非平凡多值依賴。6.2.3

多值依賴和范式—多值依賴6.2.3

多值依賴和范式—多值依賴多值依賴——實(shí)例對(duì)“課程—教師—參考書(shū)”（C-T-B）的關(guān)系給定一對(duì)值（數(shù)學(xué)，數(shù)學(xué)分析）有一組值

（李勇，張平）同樣給定一對(duì)值（數(shù)學(xué)，李勇）有一組值

（數(shù)學(xué)分析，微分方程，高等代數(shù)）這兩組值一組是姓名的集合，一組是書(shū)名的集合。二者是相互獨(dú)立的。表示為：

C

→→

T C

→→

BC→→T和C→→B都是非平凡的多值依賴。3.多值依賴的性質(zhì)6.2.3

多值依賴和范式—多值依賴①對(duì)稱律若X→→Y，則X→→Z，其中Z=U–X–Y。②傳遞律若X→→Y，Y→→Z，則X

→→Z–Y。③替代律函數(shù)依賴是多值依賴的特殊情況。即：若X→Y，則X→→Y。④

合并律若X→→Y，X→→Z，則X→→Y∪Z

。⑤

分解律若X→→Y，X→→Z，則：X→→Y∩Z

，X→→Y–Z，X→→Z–Y

。6.2.3

多值依賴和范式這就將非平凡多值依賴X→→Y（Y

?

X）約束成了實(shí)際上的函數(shù)依賴X→Y（Y

?

X）。六、第四范式定義6.10

關(guān)系模式R（U，F(xiàn)）∈1NF，如果對(duì)于R的每個(gè)非平凡多值依賴：X

→→

Y（Y

?

X）X都含有碼，則稱R（U，F(xiàn)）∈4NF。X→→Y（Y

?

X），X是碼，則必有X→Y。這是因?yàn)閅依賴于碼，根據(jù)碼的定義，碼X能唯一確定一個(gè)Y的值。我們換一種表述：在關(guān)系R中，如果X→→Y（Y?

X）是非平凡的多值依賴，且X是（超鍵）碼，那么就有R∈4NF。6.2.3

多值依賴和范式——第四范式titlenamecitystreettitle瓊瑤臺(tái)北市忠孝西路365號(hào)還珠格格瓊瑤長(zhǎng)沙市湘春路25號(hào)還珠格格瓊瑤臺(tái)北市忠孝西路365號(hào)月朦朧，鳥(niǎo)朦朧瓊瑤長(zhǎng)沙市湘春路25號(hào)月朦朧，鳥(niǎo)朦朧瓊瑤臺(tái)北市忠孝西路365號(hào)碧云天瓊瑤長(zhǎng)沙市湘春路25號(hào)碧云天六、第四范式——實(shí)例著作關(guān)系模式Author

(name，city，street，title)姓名

name

住址

city

，street

作品Author關(guān)系模式中存在多值依賴：name→→city，street即：對(duì)每一個(gè)著者姓名，其地址集伴隨著著者的每一部作品出現(xiàn)。6.2.3

多值依賴和范式——第四范式titlenamecitystreettitle瓊瑤臺(tái)北市忠孝西路365號(hào)還珠格格瓊瑤長(zhǎng)沙市湘春路25號(hào)還珠格格瓊瑤臺(tái)北市忠孝西路365號(hào)月朦朧，鳥(niǎo)朦朧瓊瑤長(zhǎng)沙市湘春路25號(hào)月朦朧，鳥(niǎo)朦朧瓊瑤臺(tái)北市忠孝西路365號(hào)碧云天瓊瑤長(zhǎng)沙市湘春路25號(hào)碧云天六、第四范式——實(shí)例著作關(guān)系模式Author

(name，city，street，title)姓名

name

住址

city

，street

作品Author關(guān)系模式中存在多值依賴：name→→city，street即：對(duì)每一個(gè)著者姓名，其地址集伴隨著著者的每一部作品出現(xiàn)。6.2.3

多值依賴和范式——第四范式如何消除多值依賴，把一個(gè)關(guān)系分解成符合4NF的多個(gè)關(guān)系？①確定一個(gè)多值依賴（如：A→→B）。（name

→→

city，street）②分解后的第一個(gè)關(guān)系模式中包含A和B的屬性。(name，city，street)③分解后的第二個(gè)關(guān)系模式中包含A的屬性以及既不屬于A也不屬于B的R中的所有其他屬性。(name，title)④為這兩個(gè)新關(guān)系命名。Author-address

(name，city，street)Author-title

(name，title)namecitystreet瓊瑤臺(tái)北市忠孝西路365號(hào)瓊瑤長(zhǎng)沙市湘春路25號(hào)碼(鍵)為：(name，city，street)多值依賴nametitle瓊瑤還珠格格瓊瑤月朦朧，鳥(niǎo)朦朧瓊瑤碧云天碼(鍵)為：(name，title)多值依賴name

→→titlename

→→

city，streetAuthor-title分解后關(guān)系A(chǔ)uthor的實(shí)例如下：Author-address不存在非平凡依賴6.2.3

多值依賴和范式——第四范式6.2.3

多值依賴和范式——第四范式根據(jù)平凡多值依賴的定義對(duì)于關(guān)系R（U）中的一個(gè)多值依賴A

→→B，如果：a)

B是A的子集，或者b) A∪B

=

U

；那么，多值依賴A→→B就是平凡多值依賴?？梢?jiàn)

name→→

city，streetname→→

title都是平凡多值依賴。因此Author-address?

4NFAuthor-title?

4NF626.3

數(shù)據(jù)依賴的公理系統(tǒng)數(shù)據(jù)依賴的公理系統(tǒng)是模式分解的理論基礎(chǔ)。利用它可以有效地進(jìn)行模式分解。一、公理系統(tǒng)定義6.11（邏輯蘊(yùn)含）對(duì)于滿足一組函數(shù)依賴F

的關(guān)系模式R(U,F)，其任何一個(gè)關(guān)系r，若函數(shù)依賴X→Y都成立（即r中任意兩元組t、s，若t[X]=s[X]，則有t[Y]=s[Y]），則稱F邏輯蘊(yùn)含X→Y。設(shè)U為屬性集總體，F(xiàn)是U上的一組函數(shù)依賴，于是有關(guān)系模式R（U，F(xiàn)）。對(duì)R（U，F(xiàn)）來(lái)說(shuō)有以下的推理規(guī)則：A1

自反律：若Y

X U，則X→Y為F所蘊(yùn)含。A2

增廣律：若X→Y為F所蘊(yùn)含，且Z

U，則

XZ→YZ

為F所蘊(yùn)含。A3

傳遞律：若X→Y及Y→Z為F所蘊(yùn)含，則X→Z為F所蘊(yùn)含。Armstrong公理系統(tǒng)6.3

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

推理規(guī)則是正確的。6.3 數(shù)據(jù)依賴的公理系統(tǒng)—Armstrong公理系統(tǒng)證明：①自反律在關(guān)系R中的任一關(guān)系r

任取兩個(gè)元組t，s，X，必有t[Y]=s[Y]，若t[X]=s[X]，由于Y∴

X→Y為F所蘊(yùn)含。②增廣律在關(guān)系R中的任一關(guān)系r

任取兩個(gè)元組t，s，若t[XZ]=s[XZ]，則有t[X]=s[X]，t[Z]=s[Z]，由于X→Y為F所蘊(yùn)含，必有t[Y]=s[Y]，∴

t[YZ]=s[YZ]∴

XZ→YZ為F所蘊(yùn)含。定理6.1

證明（續(xù)）6.3 數(shù)據(jù)依賴的公理系統(tǒng)—Armstrong公理系統(tǒng)證明：③傳遞律在關(guān)系R中的任一關(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)含。證畢。自反律、增廣律和傳遞律稱為Armstrong公理系統(tǒng)。其他推理規(guī)則6.3 數(shù)據(jù)依賴的公理系統(tǒng)—Armstrong公理系統(tǒng)A4

合并規(guī)則：由X→Y，X→Z，有X→YZ。根據(jù)A2（增廣律）有XZ→YZ∴X→YZ

成立，證明：∵X→Y又∵X→Z證畢。A5

偽傳遞規(guī)則：由X→Y，WY→Z，有XW→Z。證明：∵X→Y

根據(jù)A2（增廣律）

有XW→WY

又∵WY→Z

，根據(jù)A3（傳遞律）有XW→Z，證畢。6.3 數(shù)據(jù)依賴的公理系統(tǒng)—Armstrong公理系統(tǒng)其他推理規(guī)則（續(xù)）A6

分解規(guī)則：由X→Y及Z Y，有X→Z。證明：∵Z

Y

根據(jù)A1（自反律）有Y→Z又∵X→Y，Y→Z

，根據(jù)A3（傳遞律）有X→Z，證畢。6.3

數(shù)據(jù)依賴的公理系統(tǒng)二、屬性集的閉包引理6.1

X→

A1A2

…Ak成立的充要條件是X

→

Ai

成立（i

=1，2，…，k）。定義6.12（閉包的定義）在關(guān)系模式R（U，F(xiàn)）中，為F所邏輯蘊(yùn)含的函數(shù)依賴的全體叫做F的閉包。記為：F+6.3

數(shù)據(jù)依賴的公理系統(tǒng)—屬性集的閉包定義6.13定義6.13設(shè)F為屬性集U上的一組函數(shù)依賴，

X

U，F(xiàn)FX+={A｜X→A能由F根據(jù)Armstrong

公理導(dǎo)出}，X+稱為屬性集X關(guān)于函數(shù)依賴集F的閉包。F是一組函數(shù)依賴Ai

是屬性，Ai

U

(i=1，2，…）由Armstrong

公理可由F中的函數(shù)依賴導(dǎo)出X→AiF1

2X+

=

{A

，A

，…}

(i=1，2，…)6.3

數(shù)據(jù)依賴的公理系統(tǒng)—屬性集的閉包定義6.13的另一種描述:定義6.13（另一種描述）設(shè)F為屬性集U上的函數(shù)依賴集，X是U的子集，那么相對(duì)于F來(lái)說(shuō)屬性集X的閉包用F

FArmstrong

公理推出的所有滿足X→A的屬性A組成的集合。X+來(lái)表示；X

+是由從函數(shù)依賴集F使用6.3

數(shù)據(jù)依賴的公理系統(tǒng)—屬性集的閉包引理6.2引理6.2設(shè)F為屬性集U上的一組函數(shù)依賴，X、Y U，X→Y

能由F根據(jù)Armstrong

公理導(dǎo)出的充分必要條件是YF。X

+FX

→Ai

（i=1，2，…，n）因此有：X→A1A2…An，即X→Y

。證明（充分性）：+設(shè)Y=A1A2…An

，且Y XF

。根據(jù)X

+的定義可知：證明：（必要性）設(shè)X→Y

能由F根據(jù)Armstrong公理導(dǎo)出，Y=A1A2…An

；根據(jù)引理6.1

可知：X→Ai

（i=1，2，…，n）成立；F∴

YF證畢。∴

Ai

X

+（i=1，2，…，n），X

+X→Y

能否由F根據(jù)Armstrong公理導(dǎo)出？？6.3

數(shù)據(jù)依賴的公理系統(tǒng)—屬性集的閉包Y

XF

？？？+F求X+如何求出屬性集X關(guān)于函數(shù)依賴集F的閉包呢？6.3

數(shù)據(jù)依賴的公理系統(tǒng)—屬性集的閉包我們給出這樣的算法（教材P184算法6.1的語(yǔ)言表述）：從給定的屬性集出發(fā)，如果發(fā)現(xiàn)包含了某個(gè)函數(shù)依賴左邊的屬性，就把其右邊的屬性增加到屬性集中，不斷擴(kuò)充該集合。最終，當(dāng)該集合再也無(wú)法擴(kuò)展時(shí)，得到的結(jié)果就是閉包。12:22

74R(U，F(xiàn))屬性間的對(duì)應(yīng)關(guān)系—對(duì)一多對(duì)多—對(duì)多范式閉

包函數(shù)依賴集的閉包屬性集的閉包最小覆蓋依賴關(guān)系平凡依賴非平凡依賴完全函數(shù)依賴部分函數(shù)依賴傳遞依賴平凡多值依賴非平凡多值依賴公理系統(tǒng)1NF2NF3NFBCNF4NF5NF模式分解無(wú)損連接等價(jià)函數(shù)依賴等價(jià)既保持無(wú)損連接又具有函數(shù)依賴的等價(jià)6.3

數(shù)據(jù)依賴的公理系統(tǒng)—屬性集的閉包求屬性集的閉包舉例例：已知關(guān)系模式R（U，F(xiàn)），其中U={A，B，C，D，E}；F={

AB→C，B→D，C→E，EC→B，AC→B

}

，F(xiàn)求(AB)+。給定/增加后的屬性集左邊含有給定屬性集中某個(gè)屬性的函數(shù)依賴{AB}AB→C，B→D{ABCD}C→E{ABCDE}

}

=UF∴

(AB)

+

=

{ABCDE}6.3

數(shù)據(jù)依賴的公理系統(tǒng)—屬性集的閉包求屬性集的閉包舉例例：已知關(guān)系模式R（U，F(xiàn)），其中U={A，B，C，D，E}；F={

AB→C，B→D，C→E，EC→B，AC→B

}

，F(xiàn)求(C)+。給定/增加后的屬性集左邊含有給定屬性集中某個(gè)屬性的函數(shù)依賴{C}C→E{CE}EC→B{BCE}B→D{BCDE}F∴

(C)

+

=

{BCDE}定理6.26.3

數(shù)據(jù)依賴的公理系統(tǒng)—屬性集的閉包定理6.2

Armstrong公理系統(tǒng)是正確的（有效的）、完備的。正確性： 詳見(jiàn)定理6.1的證明。Armstrong公理的完備性：F中的每一個(gè)函數(shù)依賴，一定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來(lái)。為了證明完備性，我們用逆否證法：即若函數(shù)依賴X→Y不能由F從Armstrong公理導(dǎo)出，那么它必然不為F所蘊(yùn)含。6.3

數(shù)據(jù)依賴的公理系統(tǒng)三、最小覆蓋定義6.14設(shè)G和F是兩個(gè)函數(shù)依賴集，如果G+=F+則稱函數(shù)依賴集F與函數(shù)依賴集G等價(jià)（或者說(shuō)函數(shù)依賴集G和F相互覆蓋）。G+和G

F+。6.3

數(shù)據(jù)依賴的公理系統(tǒng)——最小覆蓋充分性：

設(shè)F G+

且GF+對(duì)于每個(gè)X→Y∈F+，X→Y由F出發(fā)使用Armstrong公理導(dǎo)出。（根據(jù)閉包的定義）∵

FG+∴

X→Y由G+出發(fā)使用Armstrong公理導(dǎo)出即：X→Y∈G+F+因此對(duì)于每個(gè)X→Y∈F+都有X→Y∈G+

G+。同理可證G+

F+

。∴

G+=F+

證畢。引理6.3

G+=F+的充分必要條件是F證明：必要性：設(shè)G+=F+，F(xiàn)+∵

F

又

∵

G+=F+

∴我們有F

G+。同理可證

G

F+。

必要性證畢。6.3

數(shù)據(jù)依賴的公理系統(tǒng)——最小覆蓋定義6.15定義6.15如果函數(shù)依賴集F滿足下列條件，則稱F為一個(gè)極小函數(shù)依賴集。（也稱最小依賴集或最小覆蓋或稱正則覆蓋）。①F中任一函數(shù)依賴的右邊僅含有一個(gè)屬性。②F中不存在這樣的函數(shù)依賴X→A，使得F與F-{X→A}等價(jià)。③F中不存在這樣的函數(shù)依賴X→A，X有真子集

Z使得F與F-{X→A}∪{Z→A}等價(jià)。條件⑴很清楚，就是每個(gè)函數(shù)依賴的右邊都只有一個(gè)屬性。

條件⑵是說(shuō)從F中移出任何依賴都無(wú)法再得到和原來(lái)的F等價(jià)的一組依賴。條件⑶是說(shuō)F中的任何依賴X→A，不存在X的真子集Z，使得用Z-A代替X-A后得到和原來(lái)的F等價(jià)的一組依賴。定理6.36.3

數(shù)據(jù)依賴的公理系統(tǒng)——最小覆蓋定理6.3每一個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)極小函數(shù)依賴集Fm。此Fm稱為F的最小依賴集。關(guān)于定理6.3教材P186有證明過(guò)程的概述，其實(shí)質(zhì)就是利用最小依賴集所具備的三個(gè)條件來(lái)逐一處理。在此我們就不詳細(xì)解釋?，F(xiàn)在我們介紹一些等價(jià)的處理方法，這些方法在教材中沒(méi)有詳細(xì)介紹，在實(shí)際中比較有效。6.3

數(shù)據(jù)依賴的公理系統(tǒng)——最小覆蓋方法一：利用Armstrong公理系統(tǒng)的傳遞律直接處理。例：已知關(guān)系模式R（U，F(xiàn)），其中U={A，B，C}；F={A→B，B→A，B→C，A→C，C→A}求Fm解：∵A→B，B→C

由傳遞律可以推出A→C∴F中的A→C是冗余的。F1={A→B，B→A，B→C，C→A}又∵B→C，C→A

由傳遞律可以推出B→A∴F中的B→A是冗余的。F2={A→B，B→C，C→A}Fm=

F2={A→B，B→C，C→A}6.3

數(shù)據(jù)依賴的公理系統(tǒng)——最小覆蓋方法二：利用合并規(guī)則分析處理。步驟1

把函數(shù)依賴集F中的形如X1→Y1和X1→Y2的函數(shù)依賴替換為：X1→Y1Y2。步驟2

找出在Y1或Y2中含無(wú)關(guān)屬性的函數(shù)依賴Y1→Y2

或Y2→Y1。步驟3

如果發(fā)現(xiàn)無(wú)關(guān)屬性，把它刪除。步驟4

重復(fù)上面的步驟，直到F不再改變。方法二實(shí)例6.3

數(shù)據(jù)依賴的公理系統(tǒng)——最小覆蓋例：已知關(guān)系模式R（U，F(xiàn)），其中U={A，B，C}；F={A→B，B→A，B→C，A→C，C→A}，求Fm

。解一：F={A→B，B→A，B→C，A→C，C→A}由A→B

和A→C

得A→BCF1={A→BC，B→A，B→C，C→A}∵A→BC

和B→C知A→BC中的C是無(wú)關(guān)屬性去掉C。得F2={A→B，B→A，B→C，C→A}由B→A，和B→C得B→ACF3={A→B，B→AC，C→A}∵B→AC

和C→A知B→AC中的A是無(wú)關(guān)屬性去掉A。F4={A→B，B→C，C→A}Fm=F4={A→B，B→C，C→A}6.3

數(shù)據(jù)依賴的公理系統(tǒng)——最小覆蓋方法二實(shí)例(續(xù))例：已知關(guān)系模式R（U，F(xiàn)），其中U={A，B，C}；F={A→B，B→A，B→C，A→C，C→A}，求Fm

。解二：F={A→B，B→A，B→C，A→C，C→A}由B→A，和B→C得B→ACF1={A→B，B→AC，A→C，C→A}∵B→AC和A→C知B→AC中的C是無(wú)關(guān)屬性去掉C。F2={A→B，B→A，A→C，C→A}由A→B

和A→C

得A→BCF3={A→BC，B→A，C→A}在F3中找不出這樣的函數(shù)依賴：B→C或C→B故F2就是F的一個(gè)最小函數(shù)依賴集。Uj

(1≤i，6.4

模式的分解什么是模式分解？定義6.16

關(guān)系模式R（U，F(xiàn)）的一個(gè)分解是指:ρ={R1(U1，F(xiàn)1)，R2(U2，F(xiàn)2)，…，Rn(Un，F(xiàn)n)}其中：U=∪Ui

（

1≤i≤n

），并且沒(méi)有Uij≤n；i≠j)，F(xiàn)i是F在Ui上的投影。什么是函數(shù)依賴集合的投影集？定義6.17

函數(shù)依賴集合:{X→Y|X→Y∈F+∧XY

Ui

}的一個(gè)覆蓋Fi叫作F在屬性Ui上的投影6.4.1

模式分解的定義對(duì)一個(gè)模式的分解是多種多樣的，但分解后產(chǎn)生的模式應(yīng)與原模式等價(jià)。有三種不同的“等價(jià)”概念：無(wú)損連接等價(jià)保持函數(shù)依賴等價(jià)既保持函數(shù)依賴性，又具有無(wú)損連接性的等價(jià)1.

無(wú)損連接等價(jià)無(wú)損連接是一種分解的特性，它確保當(dāng)關(guān)系通過(guò)自然連接運(yùn)算重新組合起來(lái)時(shí)，不會(huì)產(chǎn)生謬誤的元組。從中我們可以知道無(wú)損連接強(qiáng)調(diào)信息的不丟失要求，以使分解后的數(shù)據(jù)庫(kù)能夠通過(guò)自然連接恢復(fù)到原來(lái)的情況。無(wú)損連接等價(jià)是關(guān)系模式分解的基本要求。6.4.1

模式分解的定義6.4.1

模式分解的定義——無(wú)損連接等價(jià)通過(guò)分解后的關(guān)系R1和R2中的屬性“員工姓名”把它們自然連接起來(lái)，使之恢復(fù)到關(guān)系R原來(lái)的情況。①僅具有無(wú)損連接等價(jià)的關(guān)系有可能存在更新異常問(wèn)題例如：關(guān)系模式R（U，F(xiàn)）U={員工編號(hào)，員工姓名，分支機(jī)構(gòu)編號(hào)，分支機(jī)構(gòu)負(fù)責(zé)人}F={員工編號(hào)→員工姓名，分支機(jī)構(gòu)編號(hào)→分支機(jī)構(gòu)負(fù)責(zé)人，員工姓名→分支機(jī)構(gòu)編號(hào)}我們把關(guān)系模式R（U，F(xiàn)）分解為：ρ={R1（{員工編號(hào)，員工姓名，分支機(jī)構(gòu)編號(hào)}，{員工編號(hào)→員工姓名，員工姓名→分支機(jī)構(gòu)編號(hào)}），R2（{員工姓名，分支機(jī)構(gòu)負(fù)責(zé)人}，{員工姓名→分支機(jī)構(gòu)負(fù)責(zé)人}）

}但存在更新異常。如：在關(guān)系R1中增加一名新員工，有員工編號(hào)、姓名和分支機(jī)構(gòu)編號(hào)，但確定不了分支機(jī)構(gòu)負(fù)責(zé)人。②為什么會(huì)產(chǎn)生更新異常呢?簡(jiǎn)單地說(shuō)就是分解的不合理。其實(shí)質(zhì)是沒(méi)有做到函數(shù)依賴等價(jià)。分解前：F={員工編號(hào)→員工姓名，員工姓名→分支機(jī)構(gòu)編號(hào),分支機(jī)構(gòu)編號(hào)→分支機(jī)構(gòu)負(fù)責(zé)人}分解后：{員工編號(hào)→員工姓名，員工姓名→分支機(jī)構(gòu)編號(hào)}{員工姓名→分支機(jī)構(gòu)負(fù)責(zé)人}6.4.1

模式分解的定義——無(wú)損連接等價(jià)6.4.1

模式分解的定義2.保持函數(shù)依賴等價(jià)例：設(shè)關(guān)系模式R（U，F(xiàn)），其中：U={學(xué)號(hào)，學(xué)生姓名，教師工號(hào)，教師姓名}F={學(xué)號(hào)→學(xué)生姓名，教師工號(hào)→教師姓名}將關(guān)系模式R（U，F(xiàn)）分解為：ρ={R1（

{學(xué)號(hào)，學(xué)生姓名}，{學(xué)號(hào)→學(xué)生姓名}），R2({教師工號(hào)，教師姓名}，{教師工號(hào)→教師姓名})}顯而易見(jiàn)，關(guān)系模式R1和R2與原來(lái)的關(guān)系模式R保持了函數(shù)依賴等價(jià)。但它們并不具有無(wú)損連接等價(jià)。6.4.1

模式分解的定義3.既保持函數(shù)依賴性，又具有無(wú)損連接性的等價(jià)例如：關(guān)系模式R（U，F(xiàn)）U={員工編號(hào)，員工姓名，分支機(jī)構(gòu)編號(hào)，分支機(jī)構(gòu)負(fù)責(zé)人}F={員工編號(hào)→員工姓名，分支機(jī)構(gòu)編號(hào)→分支機(jī)構(gòu)負(fù)責(zé)人，員工姓名→分支機(jī)構(gòu)編號(hào)}將關(guān)系模式R（U，F(xiàn)）分解為：ρ={R1（{員工編號(hào)，員工姓名，分支機(jī)構(gòu)編號(hào)}，{員工編號(hào)→員工姓名，員工姓名→分支機(jī)構(gòu)編號(hào)}），R2（{分支機(jī)構(gòu)編號(hào)，分支機(jī)構(gòu)負(fù)責(zé)人}，{分支機(jī)構(gòu)編號(hào)→分支機(jī)構(gòu)負(fù)責(zé)人}）

}關(guān)系R1和R2與原來(lái)的關(guān)系模式R保持了函數(shù)依賴等價(jià)。屬性“分支機(jī)構(gòu)編號(hào)”把它們自然連接起來(lái)，使之恢復(fù)到

關(guān)系R原來(lái)的情況。分解后的關(guān)系模式R1和R2不存在更新異常問(wèn)題。給出三個(gè)模式分解等價(jià)的定義其意義就在于：我們所追求的等價(jià)是既具有無(wú)損連接性，又保持函數(shù)依賴性的等價(jià)。結(jié)論6.4.1

模式分解的定義定義一個(gè)記號(hào)mρ(r)：設(shè)ρ={R1（U1，F(xiàn)1），…，Rk（Uk，F(xiàn)k）}是R（U，F(xiàn)）上的一個(gè)分解，r是R（U，F(xiàn)）上的一個(gè)關(guān)系。定義:6.4.2分解的無(wú)損連接性和保持函數(shù)依賴性kmρ(r)

=

??

πRi(r)i=1其中：πRi(r)={

t.Ui｜t

∈r}即：mρ(r)是r在ρ中各關(guān)系模式上投影的連接。引理6.4

：設(shè)R（U，F(xiàn)）是一個(gè)關(guān)系模式，ρ={R1（U1，F(xiàn)1），…，Rk（Uk，F(xiàn)k）}是R的一個(gè)分解，r是R的一個(gè)關(guān)系，ri

=πRi(r)，則:⑴

r

mρ(r)⑵若s=mρ(r)，則πRi(s)=ri⑶

mρ(

mρ(r)

)

=

mρ(r)引理6.46.4.2分解的無(wú)損連接性和保持函數(shù)依賴性定義6.18——無(wú)損分解定義6.18設(shè)ρ={R1（U1，F(xiàn)1），…，Rk（Uk，F(xiàn)k）}是R(U，F(xiàn))上的一個(gè)分解，若對(duì)R(U，F(xiàn))的任何一個(gè)關(guān)系r均有r=mρ(r)成立，則稱分解ρ具有無(wú)損連接性，簡(jiǎn)稱ρ為無(wú)損分解。6.4.2分解的無(wú)損連接性和保持函數(shù)依賴性一個(gè)分解的無(wú)損連接性的判斷方法6.4.2分解的無(wú)損連接性和保持函數(shù)依賴性輸入：關(guān)系模式R（A1，A2，…，An）R上的函數(shù)依賴集FR上的分解ρ={R1，R2，…，Rk}輸出：判斷ρ的無(wú)損連接性方法： ①

建立一個(gè)n列k行的表。n

關(guān)系模式R中的屬性個(gè)數(shù)k

R上的分解ρ中的關(guān)系模式個(gè)數(shù)②對(duì)每一個(gè)關(guān)系模式Ri

，按下面的規(guī)則填表：ij

j

i若A

ˇ

Ua

j

若Aj

?

Ui表中第i

行第j列元素=b6.4.2分解的無(wú)損連接性和保持函數(shù)依賴性一個(gè)分解的無(wú)損連接性的判斷方法（續(xù)1）③對(duì)于R上的函數(shù)依賴集F中的每一個(gè)函數(shù)依賴X→Y做下列操作：檢查X中屬性所對(duì)應(yīng)的列，找出相等的那些行。如果存在兩行或兩行以上相等，則把對(duì)應(yīng)行中的屬性Y的符號(hào)改為一致。改為一致是指：如其中一個(gè)符號(hào)為aj（j為屬性Y所在的列號(hào)），則其他也改為aj；否則改為bmj(m為相同行中行號(hào)最小的行號(hào))。對(duì)R上的F中每個(gè)函數(shù)依賴逐一進(jìn)行如此處理，稱為對(duì)F的一次掃描。在某次掃描中若出現(xiàn)有一行為：a1，a2，…，an，算法終止。6.4.2分解的無(wú)損連接性和保持函數(shù)依賴性一個(gè)分解的無(wú)損連接性的判斷方法（續(xù)2）④比兩次掃描間表中的變化，表中沒(méi)有變化，算法終止。若表中變化，則返回③處理。若表中出現(xiàn)有一行為：a1，a2，…，an，表明ρ具有無(wú)損連接性。6.4.2分解的無(wú)損連接性和保持函數(shù)依賴性分解的無(wú)損連接判別——實(shí)例例：設(shè)有關(guān)系模式R（ABCDE），ρ={R1（AD），R2（AB），R3（BE），R4（CDE），R5（AE）}是R的一個(gè)分解。在R上函數(shù)依賴有：{

A→C，B→C，C→D，DE→C，CE→A}請(qǐng)判斷ρ是否為無(wú)損分解。6.4.2分解的無(wú)損連接性和保持函數(shù)依賴性R1（AD）R2（AB）R3（BE）R4（CDE）R5（AE）分解的無(wú)損連接判別——實(shí)例（續(xù)1）解：首先構(gòu)造一個(gè)表格（五行五列），并填上初始記號(hào)。AAA

BBB

CCC

DDD

EEEABCDEa1b12b13a4b15a1a2b23b24b25b31a2b33b34a5b41b42a3a4a5a1b52b53b54a56.4.2分解的無(wú)損連接性和保持函數(shù)依賴性分解的無(wú)損連接判別——實(shí)例（續(xù)2）開(kāi)始掃描：按A→C，B→C，C→D，DE→C，CE→A的次序。A→C：存在第1、2、5行屬性A上的符號(hào)相同（均是a1）操作：將屬性C列上的第1、2、5行均改為b13。R1（AD）R2（AB）R3（BE）R4（CDE）R5（AE）A

B

C

D

Ea1

b12b13a4

b15a1

a2b23b24

b25b31

a2

b33

b34

a5b41

b42

a3

a4

a5a1

b52b53b54

a5ABCDEa1b12b13a4b15a1a2b13b24b25b31a2b33b34a5b41b42a3a4a5a1b52b13b54a56.4.2分解的無(wú)損連接性和保持函數(shù)依賴性分解的無(wú)損連接判別——實(shí)例（續(xù)3）開(kāi)始掃描：按