第4章 關(guān)系規(guī)范化理論

1971E.F.Codd

提出

1NF2NF3NFBCNF4NF5NF

第四章關(guān)系規(guī)范化理論規(guī)范化函數(shù)依賴模式分解14.1問題的提出關(guān)系模式

R(U，D，dom，I，F(xiàn))

數(shù)據(jù)依賴：關(guān)系中屬性間互相依存、互相制約的關(guān)系。

[函數(shù)依賴、多值依賴、連接依賴、分層依賴和相互依賴]2例：U={學(xué)號，系部，系主任，課程名稱，成績}F={學(xué)號→系部，系部→系主任,(學(xué)號，課程名稱)→成績}系部系主任成績

學(xué)號課程名稱3缺點1、冗余太大2、操作異常

1）插入異常

2）刪除異常

3）修改異常

學(xué)號系部系主任

課程名稱成績02101CSXAAA02101CSXBBB02101CSXCCA02102MAMAAB02102MAMDDA02103MAMEEC02104ISJEEB02105ISJBBA4通過適當(dāng)?shù)剡M(jìn)行模式分解可以避免上述問題：1、冗余太大2、操作異常

1）插入異常

2）刪除異常

3）修改異常學(xué)生（學(xué)號，系部）系部（系部，系主任）選課（學(xué)號，課程名稱，成績）原模式分解為三個子模式5適當(dāng)?shù)剡M(jìn)行模式分解關(guān)系規(guī)范化理論即適當(dāng)?shù)剡M(jìn)行模式分解的理論，包括：

4.2函數(shù)依賴和范式理論

4.3ArmStrong公理系統(tǒng)

4.4模式分解的方法64.2函數(shù)依賴和范式理論范式理論的目的和內(nèi)容：1）定義范式級別：衡量模式的規(guī)范化程度，即模式的數(shù)據(jù)冗余和操作異常程度。2）范式的判定：通過分析模式中的數(shù)據(jù)依賴關(guān)系，判斷關(guān)系模式的范式級別。3）函數(shù)依賴：是最基本的數(shù)據(jù)依賴關(guān)系，是屬性或者屬性組間存在的依賴。7定義和判定范式級別

——利用函數(shù)依賴一、定義函數(shù)依賴的概念二、基于函數(shù)依賴來重新定義候選碼三、幾種級別的范式及其判定8一、定義函數(shù)依賴函數(shù)依賴：類比于數(shù)學(xué)函數(shù)f:X→Y定義4.1：設(shè)R(U)是屬性集U上的關(guān)系模式。X，Y是U的子集。若對于R(U)的任意一個可能的關(guān)系r，當(dāng)且僅當(dāng)r中任意一個給定的X的值，r中存在唯一的Y值與之對應(yīng)。則稱Y函數(shù)依賴與X，或者X函數(shù)確定Y，記作X→Y?；貞洠河成洌瑔紊?、滿射、雙射、函數(shù)9定義4.3：R（U）的屬性子集X，Y之間的函數(shù)依賴用X→Y表示，它在構(gòu)成關(guān)系R的任意元組r上指定了一個約束。這個約束是：如果對于r中的任何兩個元組t1和t2有t1[X]＝t2[X]，則必須也有t1[Y]＝t2[Y]。

定義4.2：設(shè)R(U)是屬性集U上的關(guān)系模式，X，Y是U的子集。若對于R(U)的任意一個可能的關(guān)系r，r中不可能存在兩個元組在X上的屬性值相等，而在Y上的屬性值不等，則稱X函數(shù)確定Y或Y函數(shù)依賴于X，記作X→Y。一、定義函數(shù)依賴10例如：U={學(xué)號，系部，系主任，課程名稱，成績}F={學(xué)號→系部，系部→系主任,(學(xué)號，課程名稱)→成績}注意：函數(shù)依賴，不是指關(guān)系模式R的某個或某些關(guān)系滿足的條件，而是指R的一切關(guān)系均要滿足的約束條件11由函數(shù)依賴導(dǎo)出的概念：

1.決定因素：若X→Y，則X叫做決定因素

2.互相依賴：若X→Y，Y→X，則記作X←→Y。

3.若Y不函數(shù)依賴于X，則記作XY?！弧⒍x函數(shù)依賴12

定義4.4：平凡（非平凡）函數(shù)依賴 在R(U)中，一個函數(shù)依賴X→Y，如果滿足YX，則稱此函數(shù)依賴是非平凡函數(shù)依賴，否則稱為平凡函數(shù)依賴。

一、定義函數(shù)依賴幾種類型的函數(shù)依賴：13

定義4.5

：完全函數(shù)依賴在R(U)中，如果X→Y，并且對于X的任何一個真子集X’，都有X’→Y，則稱Y對X完全函數(shù)依賴。記作：FXY

定義4.6：部分函數(shù)依賴

在R(U)中，如果X→Y，存在真子集X’，有X’→Y成立，則稱Y對X部分函數(shù)依賴。記作：PXY幾種類型的函數(shù)依賴：14定義4.7：傳遞函數(shù)依賴

在R(U)中，如果對于非平凡函數(shù)依賴X→Y，有Y→X，且Y→Z，則稱：Z對X傳遞函數(shù)依賴。幾種類型的函數(shù)依賴：15完全函數(shù)依賴傳遞函數(shù)依賴部分函數(shù)依賴系部系主任成績

學(xué)號課程名稱幾種類型的函數(shù)依賴：16二、利用函數(shù)依賴定義候選碼定義4.8：設(shè)K為R(U，F(xiàn))中的屬性或?qū)傩越M，若，則K為R的候選碼。FKU主碼主屬性：包含在任何碼中的屬性。非主屬性：不包含在任何碼中的屬性。全碼外碼主碼與外碼提供了一個表示關(guān)系間聯(lián)系的手段17三、幾種級別的范式第一范式(1NF)定義4.9：滿足關(guān)系的每一個分量都是不可分的數(shù)據(jù)項的關(guān)系模式就屬于第一范式(1NF)。缺點： 插入異常、刪除異常、冗余太大、修改復(fù)雜18

學(xué)號系部系主任

課程名稱成績99101CSXAAA99101CSXBBB99101CSXCCA99102MAMAAB99102MAMDDA99103MAMEEC99104ISJEEB99105ISJBBA第一范式(1NF)關(guān)系的每一個分量都是不可分的數(shù)據(jù)項缺點： 插入異常 刪除異常 冗余太大 修改復(fù)雜19第二范式(2NF)定義4.10：若R∈1NF，且每一個非主屬性完全函數(shù)依賴于碼，則R∈2NF。系部系主任成績

學(xué)號課程名稱存在部分函數(shù)依賴20成績系部系主任

R1（學(xué)號，系部，系主任）

學(xué)號

學(xué)號課程名稱

R2（學(xué)號，課程名稱，成績）模式分解，消除部分函數(shù)依賴模式分解后的子模式：21第三范式(3NF)定義4.11：關(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∈2NF，且每一個非主屬性不傳遞依賴于碼，則R∈3NF。系部系主任

學(xué)號22編號成員負(fù)責(zé)人項目名稱任務(wù)情況職務(wù)例如：項目(編號，項目名稱，負(fù)責(zé)人，職務(wù)，成員，任務(wù)情況)(假設(shè):負(fù)責(zé)人無重名情況）23任務(wù)（編號，成員，任務(wù)情況）項目（編號，項目名稱，負(fù)責(zé)人，職務(wù)）根據(jù)2NF要求編號成員任務(wù)情況編號負(fù)責(zé)人項目名稱職務(wù)任務(wù)項目24編號成員任務(wù)情況任務(wù)編號負(fù)責(zé)人項目名稱項目負(fù)責(zé)人職務(wù)負(fù)責(zé)人職務(wù)根據(jù)3NF要求25例如：分析以下關(guān)系屬第幾范式學(xué)生學(xué)習(xí)情況：

R(學(xué)號，姓名，班級，年齡，宿舍，系部，系主任，課程號，課程名，先修課程，成績)26學(xué)號課程號學(xué)號課程號姓名成績先修課程課程名系主任系部宿舍年齡班級分析函數(shù)依賴關(guān)系：判斷：屬于1NF分析：關(guān)鍵字：27成績學(xué)號+課程號姓名系部宿舍年齡班級學(xué)號系主任系部先修課程課程名課程號3NF分解：28問題：設(shè)有關(guān)系模式R（A，B，C，D），其數(shù)據(jù)依賴集：F＝{（A，B）→C，C→D}，則關(guān)系模式R的規(guī)范化程度最高達(dá)到（）。

29BCNF(擴充的3NF)定義：關(guān)系模式R(U，F(xiàn))∈1NF。若X→Y且YX時X必含有碼，則R(U，F(xiàn))∈BCNF。即：關(guān)系模式R(U，F(xiàn))中，若每一個決定因素都包含碼，則R(U，F(xiàn))∈BCNF。三、幾種級別的范式30所有非主屬性對每一個碼都是完全函數(shù)依賴。所有主屬性對每一個不包含它的碼也是完全函數(shù)依賴。沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性。滿足BCNF的關(guān)系模式的性質(zhì)：31例如：關(guān)系模式SJP(S,J,P)S：學(xué)生[學(xué)生選修課程有一定的名次]J：課程[每門課程中每一名次只有一個學(xué)生]P：名次（名次沒有并列）函數(shù)依賴：(S，J)→P(J，P)→S

分析得知：SJP∈3NFSJP∈BCNF32例如：關(guān)系模式STJ(S，T，J)S：學(xué)生[某一學(xué)生選定某門課，就對應(yīng)一個固定教師]T：教師[每個教師只教一門課]J：課程

[每門課有若干教師]

函數(shù)依賴：(S，J)→T(S，T)→J分析得知：STJ∈3NF但是STJ∈BCNF，因為

T→JSTJ可以分解為：ST(S，T)和TJ(T，J)33消除非主屬性對碼的部分函數(shù)依賴消除非主屬性對碼的傳遞函數(shù)依賴消除主屬性對碼的部分和傳遞函數(shù)依賴1NF2NF3NFBCNF消除決定因素非碼的非平凡函數(shù)依賴小結(jié)：34小測驗指出下列關(guān)系模式屬第幾范式，并說明理由。(1)R（X,Y,Z）F＝{XY→Z}(2)R（X,Y,Z）F＝{Y→Z,XZ→Y}(3)R（X,Y,Z）F＝{Y→Z,Y→X,X→YZ}35假設(shè)某旅館業(yè)務(wù)規(guī)定，每個賬單對應(yīng)一個顧客，賬單的發(fā)票號是惟一的，賬單中包含一個顧客姓名、到達(dá)日期和顧客每日的消費明細(xì)，賬單的格式如圖所示:試回答下列問題：

(1)找出R的候選鍵。

(2)判斷R最高可達(dá)到第幾范式，為什么?36配件管理模式WPE（WNO，PNO，ENO，QNT）分別表示倉庫號，配件號，職工號，數(shù)量。有以下條件a.一個倉庫有多個職工。b.一個職工僅在一個倉庫工作。c.每個倉庫里一種型號的配件由專人負(fù)責(zé)，但一個人可以管理幾種配件。d.同一種型號的配件可以分放在幾個倉庫中。1.ENO→WNO2.WNO,PNO→ENO3.WNO,PNO→QNT候選碼1.(WNO，PNO)為候選碼2.因為ENO，PNO→WNO

所以(ENO，PNO)為候選碼37內(nèi)容回顧規(guī)范化的提出函數(shù)依賴碼（候選碼、主碼、外碼、

主屬性、非主屬性）范式（1NF～BCNF）一個事實：函數(shù)依賴存在冗余，一個函數(shù)依賴或許可以從其他依賴導(dǎo)出。38一個事實：函數(shù)依賴存在冗余，一個函數(shù)依賴或許可以從其他依賴導(dǎo)出。例如：關(guān)系模式R(U，F(xiàn))其中U(A，B，C，D，E，F(xiàn)，G)F(A→B，C→D，AB→E，F(xiàn)→G)則函數(shù)依賴A→E可以從F中導(dǎo)出4.3Armstrong公理系統(tǒng)39定義4.15

邏輯蘊含

對于R(U,F)，如果X→Y不在F中，但是對于其任何一個關(guān)系r，X→Y都成立，則稱F邏輯蘊含X→Y。

[或者說：X→Y可以由F導(dǎo)出]例：關(guān)系模式R(U，F(xiàn))其中U(A，B，C，D，E，F(xiàn)，G)F(A→B，C→D，AB→E，F(xiàn)→G)問：F是否邏輯蘊含A→E40函數(shù)依賴間的蘊含關(guān)系的推理規(guī)則的理論系統(tǒng)，包括：1）三個基本公理2）三個擴展的推理規(guī)則4.3.1Armstrong公理系統(tǒng)41對于關(guān)系模式R(U，F(xiàn))，有公理1：自反律(Reflexivity)

若YXU，則X→Y為F所蘊含。公理2：增廣律(Augmenttation)

若X→Y為F所蘊含，且ZU，則XZ→YZ為F所蘊含。公理3：傳遞律(Transitivity)

若X→Y，Y→Z為F所蘊含，則X→Z為F所蘊含。三條基本公理：自反律、增廣律、傳遞律42公理4：合并規(guī)則由X→Y，X→Z，有X→YZ。公理5：偽傳遞規(guī)則由X→Y，WY→Z，有XW→Z公理6：分解規(guī)則由X→Y及ZY，有X→Z。由基本公理導(dǎo)出的三條推理規(guī)則：43例：關(guān)系模式R(U，F(xiàn))其中U(A，B，C，D，E，F(xiàn)，G)F(A→B，C→D，AB→E，F(xiàn)→G)問：F是否邏輯蘊含A→E解：

∵

A→B（已知）

∴

A→AB（增廣率）∵

AB→E（已知）∴

A→E（傳遞率）44定義4.16

函數(shù)依賴集F的閉包 在關(guān)系模式R(U，F(xiàn))中，函數(shù)依賴集F及F所邏輯蘊含的函數(shù)依賴的全體叫做F的閉包，記為F+。4.3.2函數(shù)依賴集和屬性集的閉包F+={X→Y|F及能由F根據(jù)Armstrong公理導(dǎo)出}45 設(shè)R(U,F)，F(xiàn)為屬性集U上的一組函數(shù)依賴，屬性集XU，則X關(guān)于F的閉包定義為XF+

：

XF+={A|X→A能由F根據(jù)

Armstrong公理導(dǎo)出}

。定義4.17：X關(guān)于F的閉包46【例如】設(shè)關(guān)系模式R（A、B、C）的函數(shù)依賴集為F={A→B,B→C}，分別求A、B、C的閉包。若X=A，∵A→B，B→C（已知）∴A→C（傳遞律）∵A→A（自反律）∴XF+={A，B，C}若X=B，∵B→B

B→C∴XF+={B，C}若X=C，∵C→C∴XF+={C}47定理4.2：設(shè)F為屬性集U上的一組函數(shù)依賴關(guān)系，X，YU，X→Y能由F根據(jù)Armstrong公理導(dǎo)出的充分必要條件是YXF＋。利用XF+可以判定： 函數(shù)依賴X→Y是否為F所蘊含如何求得XF+呢？48求XF+的算法：輸入：X，F(xiàn)輸出：XF+(1)令X(0)=X，i=0(2)求B,B={A|(V)(W) (V→W∈FVX(i)

A∈W)}(3)X(i+1)=B∪X(i)(4)判斷X(i+1)=X(i)嗎？(5)若相等或X(i)=U則X(i)就是XF+

，算法終止。(6)若否，則i=i+1，返回第(2)步。算法4.1：49例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+。解：1：X(0)=AB2：計算X(1)=X(0)∪C∪D=ABCD3：求X(2)=X(1)∪E∪B=ABCDE4：由于X(2)

已經(jīng)等于全部屬性集合，所以(AB)F+=ABCDE找出左部為A，B或AB的函數(shù)依賴50例2：已知關(guān)系模式R(U，F(xiàn))，其中U={A，B，C，D，E，F(xiàn)，G，H}；F={A→D，AB→E，BH→E，CD→H，E→C}令X=AE，求X+。解：1：X(0)=AE2：X(1)=X(0)∪D∪C=ACDE3：X(2)=X(1)∪D∪H∪C=ACDEH4：X(3)=ACDEH不變，即X(3)=X(2)

所以X+=(AE)+=ACDEH51對于屬性閉包算法的終止條件，下列四種方法是等價的：

1X(i+1)=X(i)2當(dāng)發(fā)現(xiàn)X(i)

包含了全部屬性時；

3在F中的函數(shù)依賴的右部屬性中，再也找不到X(i)

中未出現(xiàn)過的屬性。

4在F中未用過的函數(shù)依賴的左部屬性中已沒有X(i)

的子集。52定理：Armstrong公理系統(tǒng)是有效的(正確性）、完備的。正確性：指公理1、2、3是正確的。有效性：指由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來的每一個函數(shù)依賴一定在F+。完備性：指F+中的每一個函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來。534.3.3函數(shù)依賴集的等價和

最小函數(shù)依賴集定義4.18

如果G+=F+，則稱F與G等價，記為F=G。F+=G+的充分必要條件是FG+且GF+54例：R(U)U=ABCF={A→B，B→C，A→C，AB→C,A→BC}可以寫成：G={A→B，B→C}證明：1：A→B，B→C傳遞規(guī)則A→C2：A→B，擴展AB→BB即AB→B再由B→C所以AB→C3：A→B，B→C擴展B→BC所以A→BCF與G等價55定義4.19：最小依賴集定義：如果函數(shù)依賴集F滿足下列條件，則稱F為一個極小函數(shù)依賴集，也稱最小依賴集或最小覆蓋。1)F中任一函數(shù)依賴的右部僅含有一個屬性。2)F中不存在這樣的函數(shù)依賴X→A，使得

F與F-{X→A}等價。[不存在冗余FD]3)F中不存在這樣的函數(shù)依賴X→A，X有真子集Z使得F-{X→A}∪{Z→A}與F等價。[決定因素不存在冗余]56例：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}結(jié)論：

F與F’等價

F是最小覆蓋，F(xiàn)’不是。57算法4.2求Fm（F的最小依賴集）的算法(1)將X→A1A2…Ak(k>2)轉(zhuǎn)換為X→Ai(i=1,2,…,k)

[將右部屬性分解為單個屬性](2)逐個檢查函數(shù)依賴X→A，令G=F-{X→A}，若A∈(X)G+，則從F中去掉X→A。[逐個檢查F中的每一項，看是否F-{X→A}與F等價](3)逐個檢查函數(shù)依賴X→A，若X=B1B2…Bm，逐個考查Bi(i=1,2,…,m)，若A∈(X-Bi)F+，則以X-Bi取代X。[判每個函數(shù)依賴左部是否有冗余屬性]58例：將下列函數(shù)依賴集F劃為最小函數(shù)依賴集。F={A→B，B→A，B→C，A→C，C→A}解：1：分解為單個屬性F1=F2：消去F中冗余的函數(shù)依賴考察A→B：令X=A求X+=？X(0)=AX(1)=AC=X+

因為B不屬于X+

所以A→B不冗余。考察B→A：令X=B求X+=？

X(0)=BX(1)=BCX(2)=ABC=X+

因為A屬于X+

所以B→A冗余?？疾霣→C：令X=B求X+=？

X(0)=BX(1)=B=X+

因為C不屬于X+

所以B→C不冗余。59考察A→C：令X=A求X+=？

X(0)=AX(1)=ABX(2)=ABC=X+

因為C屬于X+

所以A→C冗余?？疾霤→A：令X=C求X+=？

因為A不屬于X+

所以C→A不冗余。因此3：判每個函數(shù)依賴左部是否有冗余屬性F={A→B，B→A，B→C，A→C，C→A}Fm={A→B，B→A，A→C，C→A}思考F2={A→B，B→C，C→A}60設(shè)有關(guān)系模式R（A，B，C，D），其上的函數(shù)依賴集為：F＝{A→C,C→A，B→AC，D→AC}，求F的最小覆蓋。

61假定我們要構(gòu)造一個數(shù)據(jù)庫，屬性集為｛A,B,C,D,E,F,G｝，給定的函數(shù)依賴集F如下：

F=｛BCD→A，BC→E，A→F，F(xiàn)→G，C→D，A→G｝.

找出這個函數(shù)依賴集的最小覆蓋G624.4關(guān)系模式的分解

模式分解等價性的三個判定準(zhǔn)則分解的無損連接性和函數(shù)依賴保持性模式分解的算法63T#TDDHT#TDDHT1T2T3T4D1D1D2D3AAAABBCC設(shè)一關(guān)系模式R(T#，TD，DH)，其中T#表示教師編號，TD表示教師所屬系部，DH表示系主任名。假定每位教師只能在一個系任教，每個系只有一位系主任。64分解1：

ρ1={R1(T#)，R2(TD)，R3(DH)}分解2：

ρ2={R1(T#，TD)，R2(T#，DH)}分解3：

ρ3={R1(T#，TD)，R2(TD，DH)}分析：這三種分解那一個最好？65分解1：T#T1T2T3T4R1R2TDD1D2D3R3DHAABBCC問題：T1是哪一個系的教師？無法回答。R1，R2，R3也無法恢復(fù)到原來的R。66分解2：T#T1T2T3T4R1TDD1D1D2D3T#T1T2T3T4R2DHAAAABBCC此時，R1，R2的分解是可恢復(fù)的，但仍然存在操作異常。原因：TD→DH在R1，R2中沒有體現(xiàn)。67分解3：T#T1T2T3T4R1TDD1D1D2D3TDR2DHD1D2D3AABBCC此時，R1，R2的分解是可恢復(fù)的，并且消除了操作異常。68

關(guān)系模式R被分解為兩個投影R1和R2是獨立的，當(dāng)且僅當(dāng)：

1.R中的每個函數(shù)依賴都可由R1和R2的函數(shù)依賴導(dǎo)出。

2.R1和R2中的公共屬性至少是R1和R2

中某個關(guān)系的侯選碼。獨立投影法則694.4.1無損連接和函數(shù)依賴保持一、分解的無損連接性：

如果一個關(guān)系模式分解后，可以通過自然連接恢復(fù)原模式的信息，這一特性稱為分解的無損連接性。70分解的無損連接性：設(shè)R是關(guān)系模式，F(xiàn)是R上的函數(shù)依賴集，則R的分解δ={R1,…,Rk}是無損連接的，如果R中每個滿足F的關(guān)系r都有下式成立：??…?71Tij=aj，如果Aj∈Ribij，如果Aj∈Ri1)構(gòu)造一個k行n列的二維表T：每列對應(yīng)一個屬性Aj

每行對應(yīng)一個模式Ri

ρ={R1(U1,F1),…,Rk(Uk,Fk)}是R(U,F)的一個分解，U={A1,…,An}，F(xiàn)={FD1,FD2,…,FDp}。算法4.3

判定分解的無損連接性722)根據(jù)F中函數(shù)依賴修改表T的內(nèi)容。修改規(guī)則：逐個考察F中的每個函數(shù)依賴FD：X→Y，找到表格中在X屬性上取值相等的行，將在這些行上的Y屬性取值改為相等，具體如下：

（1）如果其中有一個符號為aj，則把其它符號也改為aj，否則改為bmj，其中m是這些行的最小行號。（2）特別注意：修改過程中若某個bij被改動，則它所在列的所有bij都要做相應(yīng)改動733)如果發(fā)現(xiàn)表中有一行已變成a1a2…ak，則表示該分解具有無損連接性，否則分解不是無損連接的。例：已知R(U，F(xiàn))U={A，B，C，D，E，F(xiàn)}，F(xiàn)={AB→C,C→D，A→F，D→E，D→F}

R的一個分解為：

ρ={R1(A，B，C)，R2(C，D)，R3(D，E，F(xiàn))}

判斷ρ是否具有無損連接性。74ABCDEFa1b21b31a2b22b32a3a3b33b14a4a4b15b25a5b16b26a6第一步：建Tρ={R1(A，B，C)R2(C，D)R3(D，E，F(xiàn))}Tij=aj，如果Aj∈Ribij，如果Aj∈Ri75

第二步：逐個考察函數(shù)依賴，并修改表。(1)AB→C,(2)C→D,(3)A→F,(4)D→E,(5)D→F因此，該分解具有無損連接性。a4a5a5ABCDEFa1b21b31a2b22b32a3a3b33a4a4a5a6b14b16b15b25b26a6a6由于沒有相同的分量，所以表不改變76

ρ1={R1(T#)，R2(TD)，R3(DH)}ρ2={R1(T#，TD)，R2(T#，DH)}ρ3={R1(T#，TD)，R2(TD，DH)}ρ1T#TDDHa1b12b13

b21a2b23

b31b32a3具有無損連接性ρ2T#TDDHa1a2b13

a1b22a3

ρ3T#TDDHa1a2b13

b21a2a3具有無損連接性77練習(xí)設(shè)關(guān)系模式R為R(H,I,J,K,L)，R上的一個函數(shù)依賴集為F={H→J,J→K,I→J,JL→H}，判斷如下哪個分解是無損連接的。

p={HK，HI，IJ，JKL，HL}p={HIL，IKL，IJL}p={HJ，IK，HL}p={HI，JK，HL}78HIJKLHKa1b12b13a4b15HIa1a2b23b24b25IJb31a2a3b34b35JKLb41b42a3a4a5HLa1b52b53b54a5A.p={HK，HI，IJ，JKL，HL}建表：79HIJKLHKa1b12b13a4b15HIa1a2b13b24b25IJb31a2a3b34b35JKLb41b42a3a4a5HLa1b52b13b54a5F={H→J,J→K,I→J,JL→H}修改表：80HIJKLHKa1b12b13a4b15HIa1a2b13a4b25IJb31a2a3a4b35JKLb41b42a3a4a5HLa1b52b13a4a5F={H→J,J→K,I→J,JL→H}修改表：81HIJKLHKa1b12a3a4b15HIa1a2a3a4b25IJb31a2a3a4b35JKLb41b42a3a4a5HLa1b52a3a4a5F={H→J,J→K,I→J,JL→H}修改表：82HIJKLHKa1b12a3a4b15HIa1a2a3a4b25IJb31a2a3a4b35JKLa1b42a3a4a5HLa1b52a3a4a5F={H→J,J→K,I→J,JL→H}修改表：83HIJKLHKa1b12a3a4b15HIa1a2a3a4b25IJb31a2a3a4b35JKLa1b42a3a4a5HLa1b52a3a4a5F={H→J,J→K,I→J,JL→H}修改表：陷入循環(huán)，結(jié)束非無損84HIJKLHILa1b12b13a4b15IKLa1a2b23b24b25IJLb31a2a3b34b35B.p={HIL，IKL，IJL}F={H→J,J→K,I→J,JL→H}建表：85HIJKLHILa1a2a3b14a5IKLa1a2a3a4a5IJLa1a2a3b34a5B.p={HIL，IKL，IJL}F={H→J,J→K,I→J,JL→H}修改表：無損連接分解。86設(shè)ρ={R1，R2}是關(guān)系模式R的一個分解，F(xiàn)是R的一個函數(shù)依賴集，則對于F，ρ具有連接不失真性的充分必要條件是：

R1∩R2→R1-R2∈F+

或R1∩R2→R2-R1∈F+。定理4.4:

R1和R2中的公共屬性至少是R1和R2中某個關(guān)系的侯選碼。87二、分解的函數(shù)依賴保持性：

若關(guān)系R(U,F)的一個分解ρ={R1(U1,F1),…,Rk(Uk,Fk)}的所有函數(shù)依賴的并集邏輯蘊涵了F中所有函數(shù)依賴，即=F+，

則稱分解ρ具有函數(shù)依賴保持性。i=1k(∪Fi)i=1k(∪Fi)+88二、分解的函數(shù)依賴保持性問題：給定關(guān)系R(U,F)，及其分解：ρ={R1(U1,F1),…,Rk(Uk,Fk)}如何計算Fi：稱為F在Ui上的投影

Fi={X→Y|X→Y∈F+∧XY?Ui}；或與其等價的依賴集89例：關(guān)系模式R(U，F(xiàn))U={A，B，C，D}F={A→B，B→C，C→D，D→A}分解ρ={R1(A，B)，R2(B，C)，R3(C，D)}是否具有函數(shù)依賴保持性？其中：

F1＝πU1(F)=(A→B,B→A)F2＝πU2(F)=(B→C,C→B)F3＝πU3(F)=(C→D,D→C)判斷分解是否具有函數(shù)依賴保持性的方法90

F1∪F2∪F3={A→B,B→A,B→C,C→B,C→D,D→C}F={A→B，B→C，C→D，D→A}因為(F1∪F2∪F3)+=F+

所以分解ρ具有函數(shù)依賴保持性。判斷分解是否具有函數(shù)依賴保持性的方法91練習(xí)設(shè)有R（U，F(xiàn)），其中，U={A，B，C，D，F(xiàn)}，F(xiàn)={A→C，B→C，C→D，DF→C，CF→A}，R的一個分解為：R1=AB，R2=AD，R3=AF，R4=BF，R5=CDF，判斷該分解是否具有函數(shù)依賴保持性。

92算法4.5：

結(jié)果為3NF的依賴保持分解算法4.4.2模式分解算法⑴如果R中有某些屬性與F的最小覆蓋F′中的每個依賴的左邊和右邊都無關(guān)，原則上可由這些屬性構(gòu)成一個關(guān)系模式，并從R中將它們消除；否則，⑵如果F′中有一個依賴涉及到R的所有屬性，則輸出R；否則，⑶輸出一個分解ρ，它由模式XA組成，其中X→A∈F′

。但當(dāng)X→A1，X→A2，…，X→An均屬于F′時，則用模式XA1A2…An代替XAi（i=1，2，…，n）。93假定我們要夠造一個數(shù)據(jù)庫，屬性集為｛A,B,C,D,E,F,G｝，給定的函數(shù)依賴集F如下：

F=｛BCD→A，BC→E，A→F，F(xiàn)→G，C→D，A→G｝.

求R的一個滿足3NF的函數(shù)依賴保持分解舉例94舉例

1求F的最小覆蓋

Fm＝{BC→AE,A→F,F→G，C→D}

2條件（1）不滿足

3條件（2）不滿足

4根據(jù)條件（3）輸出ρ

ρ={BCAE,AF,FG,CD}95算法4.6：

結(jié)果為3NF的依賴保持和連接不失真分解

設(shè)δ是由“結(jié)果為3NF的依賴保持分解算法”得到的3NF分解，X為R的一個候選關(guān)鍵字，則：τ=δ∪{X}是R的一個分解，且其中的所有關(guān)系模式均滿足3NF，同時，既具有連接不失真性，又具有依賴保持性。問題：如何找到候選碼？——碼值理論96對于給定的關(guān)系R（A1，A2，……，An）和函數(shù)依賴集F，可將其屬性分為4類：

L類僅出現(xiàn)在F的函數(shù)依賴左部的屬性

R類僅出現(xiàn)在F的函數(shù)依賴右部的屬性

N類在F的函數(shù)依賴左右兩邊均未出現(xiàn)的屬性

LR類在F的函數(shù)依賴左右兩邊均出現(xiàn)的屬性碼值理論97定理1

對于給定的關(guān)系模式R及其函數(shù)依賴集F，若X（X∈R）是L類屬性，則X必是R的候選碼的成員。定理3

對于給定的關(guān)系模式R及其函數(shù)依賴集F，若X（X∈R）是R類屬性，則X不在任何候選碼中。定理2

對于給定的關(guān)系模式R及其函數(shù)依賴集F，若X（X∈R）是N類屬性，