數(shù)據(jù)庫實(shí)用教程(第三版)課件

數(shù)據(jù)庫實(shí)用教程（第三版）第五章規(guī)范化設(shè)計(jì)數(shù)據(jù)庫實(shí)用教程（第三版）第五章規(guī)范化設(shè)計(jì)1第五章規(guī)范化設(shè)計(jì)

本章討論如何設(shè)計(jì)關(guān)系數(shù)據(jù)庫的模式問題。關(guān)系數(shù)據(jù)庫規(guī)范化設(shè)計(jì)理論即“模式設(shè)計(jì)理論”數(shù)據(jù)依賴―――研究數(shù)據(jù)之間的聯(lián)系范式―――關(guān)系模式的標(biāo)準(zhǔn)

模式設(shè)計(jì)方法――規(guī)范化的方法第五章規(guī)范化設(shè)計(jì)關(guān)系數(shù)據(jù)庫數(shù)據(jù)依賴―――研究數(shù)據(jù)之2關(guān)系模式的一般形式和關(guān)系模式的冗余和異常問題。數(shù)據(jù)依賴的定義、數(shù)據(jù)依賴與關(guān)鍵碼的聯(lián)系；平凡的FD。關(guān)系模式的范式：1NF，2NF，3NF，BCNF。邏輯蘊(yùn)涵、閉包、數(shù)據(jù)依賴的公理系統(tǒng)和推理規(guī)則；屬性集的閉包；FD集的等價(jià)；最小依賴集。無損分解的定義、性質(zhì)、測(cè)試；保持依賴的分解定義。分解算法：分解成3NF、BCNF模式集的算法。本章重要概念:關(guān)系模式的一般形式和關(guān)系模式的冗余和異常問題。關(guān)系模3一、關(guān)系模式的一般形式:

R<U,D,Dom,F>

§1概述一、關(guān)系模式的一般形式:§1概述4

R<U,D,Dom,F>其中：U：為組成關(guān)系R的全部屬性的集合，即U＝{A1,A2,……An}。D：為域的集合，即屬性的取值范圍的集合。Dom：為U與D之間的映象，即Dom：UD|Dom安全約束集。F：為屬性U上的一組約束，即數(shù)據(jù)依賴集。例如：學(xué)習(xí)關(guān)系SC中存在如下數(shù)據(jù)依賴：（SNO,CNO）GRADE學(xué)生關(guān)系S中存在如下數(shù)據(jù)依賴：SNOSNAME（SNO,SNAME）AGE例如：學(xué)習(xí)關(guān)系SC中存在如下數(shù)據(jù)依賴：5關(guān)系模式一般形式可簡化為：

R<U,F>泛關(guān)系模式

滿足上述制約條件F的關(guān)系用符號(hào)r表示

r

表示的關(guān)系稱為：泛關(guān)系例如:學(xué)習(xí)關(guān)系模式SC<U,F>其中:U={SNO,CNO,GRADE}F={(SNO,CNO)GRADE}

關(guān)系模式一般形式可簡化為：6設(shè)計(jì)關(guān)系數(shù)據(jù)庫的核心問題是關(guān)系模式的設(shè)計(jì)。對(duì)于一個(gè)數(shù)據(jù)庫設(shè)計(jì)，可以有多個(gè)關(guān)系模式的選擇。

按照什么原則來選擇關(guān)系模式？標(biāo)準(zhǔn)是什么？如何實(shí)現(xiàn)？

設(shè)計(jì)關(guān)系數(shù)據(jù)庫的核心問題是關(guān)系模式的設(shè)計(jì)。7二．關(guān)系模式的存儲(chǔ)異常問題在數(shù)據(jù)管理中,數(shù)據(jù)冗余一直是影響系統(tǒng)性能的大問題。數(shù)據(jù)冗余是指同一個(gè)數(shù)據(jù)在系統(tǒng)中多次重復(fù)出現(xiàn)。例：Score(Stu_id,Stu_Name,Cou_id，Cou_Name，tea_Name)屬性分別表示:學(xué)號(hào)、學(xué)生名、課程號(hào)、課程名、教師名vScore的一個(gè)實(shí)例：二．關(guān)系模式的存儲(chǔ)異常問題例：Score(Stu_id8存在的問題：①

數(shù)據(jù)冗余②

修改異常③插入異常④刪除異常存在的問題：9

關(guān)系可定義為笛卡兒積的一個(gè)子集，并不是每個(gè)子集都是有意義的。對(duì)關(guān)系的值要作各種限制，這種限制稱為數(shù)據(jù)完整性約束條件。數(shù)據(jù)完整性約束主要有兩種：1.依賴于值域的限制------------由DBMS完整性子系統(tǒng)實(shí)現(xiàn)；2.只依賴于屬性間取值的相等與否的限制--------------僅取決于兩個(gè)元組的某些分量是否相等--------統(tǒng)稱為數(shù)據(jù)依賴數(shù)據(jù)依賴描述的是屬性與屬性之間的對(duì)應(yīng)關(guān)系?！?函數(shù)依賴關(guān)系可定義為笛卡兒積的一個(gè)子集，并不是每個(gè)10一、函數(shù)依賴定義定義：設(shè)有關(guān)系模式R（A1,A2,……An），X和Y是屬性集（A1,A2,……An）的子集，如果對(duì)于R的任何一個(gè)關(guān)系r中的任兩個(gè)元組u和v，對(duì)應(yīng)于X的屬性分量的值相等，而對(duì)應(yīng)于Y的屬性分量的值也相等，即：只要有u[X]=v[X]，就有u[Y]=v[Y]，稱“X函數(shù)確定Y”或稱“Y函數(shù)依賴于X”,其符號(hào)表示為：XYFD的確切語義：表示了關(guān)系模式集X值與Y值的多對(duì)一聯(lián)系。

(Stu_id)(Stu_Name)……….(Stu_id,Cou_id)(Stu_Name,Cou_Name,Tea_Name)更明確地說：

對(duì)于r中屬性或?qū)傩越MX的每一個(gè)值，r中Y只有一個(gè)值與之對(duì)應(yīng)。一、函數(shù)依賴定義FD的確切語義：表示了關(guān)系模式11二、完全函數(shù)依賴

定義：在關(guān)系模式R（A1,A2,……An）中，已知XY,對(duì)于X中任何真子集X′(X′X)都不能函數(shù)確定Y，稱X

Y是完全函數(shù)依賴,用符號(hào)XY表示。完全依賴也稱為“左部不可約依賴”。f(Stu_id,Cou_id)(Stu_Name)(Stu_id,Cou_id)(Cou_Name)(Stu_id,Cou_id)(Stu_Name,Cou_Name,Tea_Name)二、完全函數(shù)依賴

定義：在關(guān)系模式R（A112三、部分函數(shù)依賴

定義：在關(guān)系模式R（A1,A2,……An）中，已知XY,如果存在一個(gè)真子集X′(X′X)，滿足X′

Y，則稱Y對(duì)X是部分函數(shù)依賴，用符號(hào)XY表示。p(Stu_id,Cou_id)(Stu_Name)(Stu_id,Cou_id)(Cou_Name)三、部分函數(shù)依賴

定義：在關(guān)系模式R（A1,A2,13四、傳遞函數(shù)依賴

定義：在關(guān)系模式R（A1,A2,……An）中，已知XY，Y

Z(YX，ZY不存在Y

X），則稱XZ是傳遞函數(shù)依賴。t(Stu_id,Cou_id)(Cou_Name)(Cou_Name)(Credit)(Stu_id,Cou_id)(Credit)四、傳遞函數(shù)依賴

定義：在關(guān)系模式R（A1,A2,14

定義:如果A是關(guān)系模式R的候選鍵K中屬性，那么稱A是R的主屬性；否則稱A是R的非主屬性。五、函數(shù)依賴和關(guān)鍵碼的聯(lián)系

定義:設(shè)有關(guān)系模式R(A1,A2,……An),K是屬性集(A1,A2,……An)的一個(gè)子集。如果KU（U完全函數(shù)依賴于K）在R上成立，那么稱K是R的一個(gè)候選鍵。f如果X

U(KX)在R上成立,那么稱X是R的一個(gè)超鍵。p五、函數(shù)依賴和關(guān)鍵碼的聯(lián)系f如果XU(KX15§3關(guān)系模式的范式

用什么標(biāo)準(zhǔn)來衡量關(guān)系模式設(shè)計(jì)的好與壞？---------關(guān)系模式的范式(NormalForms,簡記為NF)。一、第一范式（1NF）定義：如果關(guān)系模式R的每個(gè)關(guān)系r的屬性值都是不可分的原子值,那么稱R是第一范式(firstnormalform)的模式。滿足1NF的關(guān)系稱為規(guī)范化的關(guān)系，否則稱為非規(guī)范化的關(guān)系。關(guān)系數(shù)據(jù)庫研究的關(guān)系都是規(guī)范化的關(guān)系。

§3關(guān)系模式的范式一、16

既使關(guān)系模式是1NF，但很可能具有不受歡迎的冗余和異?，F(xiàn)象。

因此需把關(guān)系模式作進(jìn)一步的規(guī)范化。

如果數(shù)據(jù)庫模式中每個(gè)關(guān)系模式都是2NF，則稱數(shù)據(jù)庫模式為2NF的數(shù)據(jù)庫模式?！⒌诙妒剑?NF）定義:如果關(guān)系模式R1NF,并且R中每個(gè)非主屬性都完全函數(shù)依賴于R的候選鍵，稱R是第二范式（2NF）的模式。既使關(guān)系模式是1NF，但很可能具有不受歡迎的冗余和異常現(xiàn)象17三、第三范式（3NF）定義:如果關(guān)系模式R1NF,并且R中每個(gè)非主屬性都不傳遞依賴于R的候選鍵,那么稱R是第三范式（3NF）的模式。

如果數(shù)據(jù)庫模式中每個(gè)關(guān)系模式都是3NF，則稱其為3NF的數(shù)據(jù)庫模式。

在3NF模式中，并未排除主屬性對(duì)候選鍵的傳遞依賴，仍有可能有冗余和異常現(xiàn)象。3NF分解三、第三范式（3NF）如果數(shù)據(jù)庫模式中每個(gè)18四、BCNF模式定義：如果關(guān)系模式R1NF，并且R中每個(gè)屬性都不傳遞依賴于R的候選鍵,那么稱R是BCNF的模式。由BCNF的定義得出如下結(jié)論：

1.非主屬性對(duì)碼完全函數(shù)依賴；2.主屬性對(duì)不包含它的碼也是完全函數(shù)依賴；3.沒有屬性完全依賴非碼的任何屬性組。如果數(shù)據(jù)庫模式中每個(gè)關(guān)系模式都是BCNF，稱其為BCNF的數(shù)據(jù)庫模式。四、BCNF模式由BCNF的定義得出如下結(jié)論19

例如：關(guān)系模式R(C,S,Z)其中

C：城市名稱S：街道名稱Z：郵政編碼假定：F={CSZ,ZC}CSZ:表示地址(城市和街道)決定郵政編碼;

ZC:表示郵政編碼決定城市名稱。R的候選碼為：CS和SZ。例如：關(guān)系模式R(C,S,Z)20

R(C,S,Z)的候選碼為：CS和SZ。

由于F中存在ZC:

主屬性C對(duì)不包含它的碼SZ不是完全函數(shù)依賴，

所以R(C,S,Z)不是BCNF模式，但R(C,S,Z)是3NF，因?yàn)闆]有任何非主屬性對(duì)碼傳遞函數(shù)依賴或部分函數(shù)依賴。

如果把R(C,S,Z)分解為:R1（S，Z）R2（Z,C）

能解決冗余問題，而且R1，R2都是BCNF模式集。

但丟失了CSZ，數(shù)據(jù)語義將會(huì)引起新的矛盾。R(C,S,Z)的候選碼為：CS和SZ21§4數(shù)據(jù)依賴的公理系統(tǒng)一、函數(shù)依賴FD的邏輯蘊(yùn)涵

F邏輯蘊(yùn)涵X→Y，記為：F?X→Y

。定義一：設(shè)F是關(guān)系模式R(A1,A2,……An)上成立的函數(shù)依賴集，

X和Y是屬性集（A1,A2,……An）的子集，X→Y是一個(gè)其他的函數(shù)依賴。如果對(duì)于R的每個(gè)滿足F的關(guān)系r也滿足X→Y（或從F推導(dǎo)出X→Y也在R（U）上成立），那么稱§4數(shù)據(jù)依賴的公理系統(tǒng)F邏輯蘊(yùn)涵22定義二：設(shè)F是關(guān)系模式R（A1,A2,……An）上成立的函數(shù)依賴集，X和Y是屬性集（A1,A2,……An）的子集，

F的所有邏輯蘊(yùn)涵組成的集合稱為函數(shù)依賴集F的閉包,記為F+。F+=｛X→Y|F?X→Y｝即：從給定的函數(shù)依賴集合F推出的所有函數(shù)依賴組成的集合，稱為F的閉包。

記為F+。F+=｛X→Y|F?X→Y23二、FD推理規(guī)則（Armstrong公理）

設(shè)U是關(guān)系模式R的屬性集，F(xiàn)是R上成立的一組函數(shù)依賴集X、Y分別是U上的子集，存在如下規(guī)則：

1、FD公理（函數(shù)依賴公理）：①自反性：若YXU，則X→Y在R上成立。②增廣性：若X→Y在R上成立，且ZU，則

XZ→YZ在R上成立。③傳遞性：若X→Y和Y→Z在R上成立，則

X→Z在R上成立。二、FD推理規(guī)則（Armstrong公理）②增廣性：242、FD推理規(guī)則①并規(guī)則：若X→Y，X→Z，則X→YZ。②偽傳遞規(guī)則：若X→Y，YW→Z，則XW→Z。③分解規(guī)則：若X→Y，ZY，則X→Z。

④復(fù)合規(guī)則：若X→Y，W→Z，則XW→YZ。⑤通用一致性定理：若X→Y，W→Z，則X∪（W－Y）→YZ。

從并規(guī)則和分解規(guī)則可得到下面的定理。定理:如果A1…An是關(guān)系模式R的屬性集，那么X→A1…An成立的充分必要條件是X→Ai（i=1，…，n）成立。2、FD推理規(guī)則④復(fù)合規(guī)則：若X→Y，W→25例:已知關(guān)系模式R(ABC),F=｛A→B，B→C｝,求F+。答：根據(jù)函數(shù)依賴公理系統(tǒng)，可推出F的F+有43個(gè)FD。其中：①據(jù)自反性可得出27個(gè)FD：→A→B→C→AB→

BC→CA→

ABC→A→AB→B

C→CAB→ABC→BCA→A

ABC→A

AB→BBC→CCA→C

ABC→B

AB→ABBC→BCCA→CA

ABC→CABC→ABABC→BCABC→CAABC→ABC例:已知關(guān)系模式R(ABC),F=｛A→B，B→C｝26②據(jù)增廣性可得出7個(gè)FD：A→BB→CAB→C(∵A→B，AB→B,B→C)A→ABB→BCAB→ABCCA→BC(∵CA→A,A→B,B→BC)③據(jù)傳遞性可得出9個(gè)FD：A→C(∵A→B，B→C)CA→B(∵CA→A,A→B)A→CAA→BC(∵A→CA,CA→BC

)AB→BC(∵AB→A,A→BC）CA→AB(∵CA→A,A→AB)CA→AB(∵CA→A,A→AB)AB→CA(∵AB→A,A→CA)A→ABC(∵A→CA,CA→ABC)②據(jù)增廣性可得出7個(gè)FD：③據(jù)傳遞性可得出9個(gè)FD：27在實(shí)際使用中，經(jīng)常要判斷能否從已知的函數(shù)依賴集F推導(dǎo)出函數(shù)依賴X→Y，那么可先求出F的閉包F+，然后再看X→Y是否在F+中。但是從F求F+是一個(gè)復(fù)雜且困難的問題（NP完全問題，指數(shù)級(jí)問題）。下面引入屬性集閉包概念，將使判斷問題化為多項(xiàng)式問題。定義三：對(duì)于函數(shù)依賴X→Y，如果YX，那么稱X→Y是一個(gè)“平凡的FD”；否則稱為“非平凡的FD”。平凡的FD并沒有實(shí)際意義，根據(jù)自反性就可推出。我們感興趣的是非平凡的FD。只有非平凡的FD與完整性約束條件相關(guān)。在實(shí)際使用中，經(jīng)常要判斷能否從已知的函數(shù)依賴集F推導(dǎo)出函數(shù)依28三、屬性集的閉包定義：設(shè)F是屬性集U上的FD集,X是U的子集，那么（相對(duì)于F）屬性集X的閉包用XF+表示，它是一個(gè)從F集使用FD推理規(guī)則推出的所有滿足X→A的屬性A的集合：

XF+=｛A|AU，X→AF+｝從屬性集閉包的定義可得出下面的定理。

定理：X→Y能用FD推理規(guī)則推出的充分必要條件是:

YXF+三、屬性集的閉包XF+=｛A|AU，X→AF29四、屬性集X的閉包的計(jì)算方法輸入：一個(gè)有限的屬性集合U；U上滿足的函數(shù)依賴集合F；U的一個(gè)子集X。輸出：X關(guān)于F的閉包XF+

。四、屬性集X的閉包的計(jì)算方法輸出：X關(guān)于F的30方法：根據(jù)下列規(guī)則計(jì)算屬性集序列X（0），X（1），…。①、置初值X（0）:=X,i=0；②、X(i+1):=X(i)∪{A|Y→Z∈F∧A

Z∧YX(i)}③、判斷X（i）=X（i+1）否？若不等，置X（i）=X（i+1）,i:=i+1轉(zhuǎn)②

若相等，計(jì)算終止，此時(shí)X（i+1）就是所要求的屬性集X關(guān)于F的閉包XF+

。方法：根據(jù)下列規(guī)則計(jì)算屬性集序列X（0），X（1），…。②、31例：設(shè)U＝{A,B,C,D,E,G}，F(xiàn)={AB→C，C→A，BC→D,ACD→B,D→EG,BE→C,CG→BD,CE→AG}求(BD)F+

解：設(shè)X=BD①令：X(0)=BD②計(jì)算X(1):=BD∪EG=BDEG;(D→EG)③計(jì)算X(2):=BDEG∪C=BCDEG;(BE→C)④計(jì)算X(2):=BCDEG

∪A=ABCDEG;

(C→A)

X(3)已包括所有屬性，算法終止。(BD)F+=ABCDEG

例：設(shè)U＝{A,B,C,D,E,G}，F(xiàn)={AB→C，C→32五、函數(shù)依賴集的等價(jià)和最小依賴集定義一:關(guān)系模式R(U)上的兩個(gè)函數(shù)依賴集F和G，如果F+=G+，稱F和G是等價(jià)的；如果F和G等價(jià)，稱F覆蓋G，或G覆蓋F。

定理：F+=G+的充分必要條件是：FG+且GF

+

五、函數(shù)依賴集的等價(jià)和最小依賴集定理：F+=G+33定義二：如果函數(shù)依賴集F滿足下列三個(gè)條件,稱F為最小依賴集：①F中每一個(gè)函數(shù)依賴的右邊都是單屬性;---------右端無冗余屬性

②對(duì)于F中任一函數(shù)依賴X→A，其F－{X→A}與F不等價(jià)；----------F中沒有冗余的函數(shù)依賴③對(duì)于F中任一函數(shù)依賴X→A，其F－{X→A}∪{Z→A}與F不等價(jià)，其中ZX。--------左端無冗余屬性。

定理：任何一個(gè)函數(shù)依賴集F至少存在一個(gè)最小函數(shù)依賴集Fmin。定義二：如果函數(shù)依賴集F滿足下列三個(gè)條件,①F中34例：分析下列函數(shù)依賴集F1，F(xiàn)2，F(xiàn)3是否為最小函數(shù)依賴集。

AD→BC

A→DA→CF1=BE→CF2=B→AF3=AD→BC→HA→CC→DB→DD→A

D→C解析：F1不是最小集，因?yàn)锳D→BC不滿足條件①。

F2不是最小集,因?yàn)镕2－{A→C}等價(jià)于F2，不滿足條件②。F3不是最小集，因?yàn)镕3－{AD→B}∪{D→B}等價(jià)于F3，不滿足條件③。(F3中：D→A，AD→B由偽傳遞得D→B)

例：分析下列函數(shù)依賴集F1，F(xiàn)2，F(xiàn)3是否為最小函數(shù)依35函數(shù)依賴集最小化處理的一般步驟：1、用分解規(guī)則消去函數(shù)依賴右端的冗余屬性。(使F中每一個(gè)函數(shù)依賴的右邊都是單屬性).2、應(yīng)用傳遞性消去函數(shù)依賴集F中冗余的函數(shù)依賴。(對(duì)于F中每一個(gè)函數(shù)依賴X→A,分別檢驗(yàn)F與F－{X→A}不等價(jià))3、應(yīng)用偽傳遞規(guī)則消去函數(shù)依賴左端的冗余屬性。（對(duì)于F中任一函數(shù)依賴X→A，其F－{X→A}∪{Z→A}與F不等價(jià)，ZX）。函數(shù)依賴集最小化處理的一般步驟：2、應(yīng)用傳遞性消去函數(shù)依賴集36例:已知F={A→D，B→D，BD→CA，CD→B}，求Fmin。

第二步：消去函數(shù)依賴左端的冗余屬性(應(yīng)用偽傳遞)由B→D,BD→C,可推出B→C,所以BD→C的左端的D是多余的;由B→D，BD→A,可推出B→A,所以BD→A的左端的D是多余的;

F2={A→D，B→D，B→C，B→A,CD→B}

第三步：去除F中冗余的FD(應(yīng)用傳遞性);由B→A，A→D，，可推出B→D，所以B→D是多余的。

Fmin={A→D，B→C，B→A,CD→B}解:第一步：應(yīng)用分解規(guī)則得：F1={A→D，B→D，BD→C，BD→A,CD→B}例:已知F={A→D，B→D，BD→CA，CD→B}，37

解決的辦法是：對(duì)關(guān)系模式進(jìn)行分解

即：將一個(gè)模式分解為多個(gè)關(guān)系模式。但在分解后又會(huì)出現(xiàn)新的問題，原模式所滿足的特征（如屬性之間的約束）在新模式中是否被保持；即模式的等價(jià)性問題。

關(guān)系模式存在多余的函數(shù)依賴或者說模式不夠規(guī)范，就有可能出現(xiàn)存儲(chǔ)異?，F(xiàn)象?！?關(guān)系模式的分解解決的辦法是：對(duì)關(guān)系模式進(jìn)行分解但在分解后又會(huì)出38

等價(jià)性問題包括:數(shù)據(jù)等價(jià)和依賴等價(jià)兩個(gè)方面:數(shù)據(jù)等價(jià)是指兩個(gè)數(shù)據(jù)庫實(shí)例應(yīng)表示同樣的信息內(nèi)容,用“無損聯(lián)接”來衡量。如果是無損聯(lián)接分解，那么反復(fù)投影和自然聯(lián)接都不會(huì)丟失信息。依賴等價(jià)是指兩個(gè)數(shù)據(jù)庫模式應(yīng)有相同的依賴集閉包。在依賴集閉包相同的情況下，數(shù)據(jù)的語義是不會(huì)出差錯(cuò)的。一個(gè)違反數(shù)據(jù)等價(jià)或依賴等價(jià)的分解很難說是一個(gè)好的模式設(shè)計(jì)。等價(jià)性問題包括:數(shù)據(jù)等價(jià)和依賴等價(jià)兩個(gè)方面:數(shù)據(jù)等39一、模式分解問題定義：設(shè)有關(guān)系模式R（U），R1、…、Rk都是R的子集，

U=R1∪…∪Rk,關(guān)系模式R1、…、Rk的集合用ρ表示，

ρ=｛R1，…，Rk｝,用ρ代替R的過程稱為關(guān)系模式R的分解。

ρ稱為R的一個(gè)分解,ρ也稱為數(shù)據(jù)庫模式。泛關(guān)系模式

數(shù)據(jù)庫模式Rρ={R1，…，Rk}

rσ=＜r1，…，rk＞

泛關(guān)系(元組的集合）數(shù)據(jù)庫實(shí)例（數(shù)據(jù)庫）一、模式分解問題泛關(guān)系模式40

把R分解成ρ的目的:

是為了消除數(shù)據(jù)冗余和操作異?，F(xiàn)象。問題是：σ和r是否表示同一個(gè)數(shù)據(jù)庫。如果兩者表示不同的內(nèi)容，那么這個(gè)分解就沒有什么意義了。把R分解成ρ的目的:41可以從兩個(gè)角度來考慮分解：①

σ和r是否等價(jià):即是否表示同樣的數(shù)據(jù)?用“無損分解”特性表示。②

在模式R上有一個(gè)函數(shù)依賴集F，在ρ的每一個(gè)模式Ri上也有一個(gè)FD集Fi，那么

｛F1，…，F(xiàn)n｝與F是否等價(jià)?

用“保持依賴”特性表示。數(shù)據(jù)庫實(shí)用教程(第三版)課件42二、無損聯(lián)接分解定義：如果R是一個(gè)關(guān)系模式,數(shù)據(jù)庫模式ρ={R1，…，Rk}是R的一個(gè)分解,F是R上成立的一個(gè)函數(shù)依賴集。如果在R中滿足F的每一個(gè)關(guān)系r，都有下式成立：r=πR1（r）?πR2（r）?…?πRk（r）稱分解ρ相對(duì)于F是“無損聯(lián)接分解”，否則稱為“損失分解”。其中：符號(hào)πRi（r）表示：關(guān)系r在模式Ri屬性上的投影。

r的投影聯(lián)接表達(dá)式πR1(r)…?πRk(r)用符號(hào)mρ(r)表示：

K

mρ（r）=?πRi（r）

i=1二、無損聯(lián)接分解r=πR1（r）?πR2（r）43如果R是一個(gè)關(guān)系模式，ρ={R1,R2,…，Rk}是關(guān)系模式R上的一個(gè)分解，r是R上的任一關(guān)系，ri=πRi(r)（1≤i≤k）,則有下列性質(zhì)：

①rmρ(r);

②若s=mρ(r),則πRi(s)=ri;

③mρ(mρ(r))=mρ(r);冪等性。如果R是一個(gè)關(guān)系模式，ρ={R1,R2,…，44三、無損聯(lián)接的測(cè)試算法1：

輸入：關(guān)系模式R（A1,A2,…An）,R上成立的函數(shù)依賴集F，R的一個(gè)分解ρ={R1，R2，…，Rk}。輸出：判斷ρ相對(duì)于F是否具有無損聯(lián)接特性。

具體步驟:①構(gòu)造一張k行n列的表格,每列對(duì)應(yīng)一個(gè)屬性Aj(1≤j≤n)，每行對(duì)應(yīng)一個(gè)模式Ri(1≤i≤k)：

如果Aj在Ri中，那么在表格的第i行第j列處填上符號(hào)aj，否則填上符號(hào)bij。三、無損聯(lián)接的測(cè)試算法1：具體步驟:45②反復(fù)檢查F中的每一個(gè)函數(shù)依賴,并修改表格中的元素,方法是：取F中的一個(gè)函數(shù)依賴X→Y，如果表格中有兩行在X分量上相等,在Y分量上不相等，那么修改Y，使這兩行在Y分量上也相等。原則：a.如果Y的分量中有一個(gè)是aj，那么另一個(gè)也修改成aj；

b.如果沒有aj，那么用其中一個(gè)bij替換另一個(gè)符號(hào)（盡量把下標(biāo)ij改成較小的數(shù)）。一直到表格不能修改為止

（這個(gè)過程稱為Chase過程）。③、若修改到最后,一張表格中有一行是全a，即a1a2…an,那么ρ相對(duì)于F是無損聯(lián)接分解。②反復(fù)檢查F中的每一個(gè)函數(shù)依賴,并修改表格中的元素,方法是：46例：設(shè)有R（ABCDE），F(xiàn)={A→C，B→C，C→D，CE→A，DE→C}，R的一個(gè)分解ρ={AD，AB，BE，CDE，AE}，求ρ的分解無損性。答：①根據(jù)已知條件構(gòu)造一張5行5列的表格如下：

ji

AB

C

DEADa1b12b13a4b15ABa1a2b23b24b25BEb31a2b33b34a5CDEb41b42a3a4a5AEa1b52b53b54a5例：設(shè)有R（ABCDE），F(xiàn)={A→C，B→C，C→D，CE47②根據(jù)A→C，對(duì)表一進(jìn)行處理，將b23，b53改為b13，

ji

AB

C

DEADa1b12b13a4b15ABa1a2b23

b13b24b25BEb31a2b33b34a5CDEb41b42a3a4a5AEa1b52b53

b13b54a5

再考慮B→C，將b33改為b13;

②根據(jù)A→C，對(duì)表一進(jìn)行處理，將b23，b53改為b1348②根據(jù)A→C，對(duì)表一進(jìn)行處理，將b23，b53改為b13，再考慮B→C，將b33改為b13;

ji

AB

C

DEADa1b12b13a4b15ABa1a2b23

b13b24

b25BEb31a2b33

b13b34

a5CDEb41b42a3a4a5AEa1b52b53

b13b54

a5②根據(jù)A→C，對(duì)表一進(jìn)行處理，將b23，b53改為b1349②根據(jù)A→C，對(duì)表一進(jìn)行處理，將b23，b53改為b13，再考慮B→C，將b33改為b13;然后考慮C→D，將b24，b34，b54改為a4。修改后的表格如下：

ji

AB

C

DEADa1b12b13a4b15ABa1a2b23

b13b24

a4b25BEb31a2b33

b13b34

a4a5CDEb41b42a3a4a5AEa1b52b53

b13b54

a4a5②根據(jù)A→C，對(duì)表一進(jìn)行處理，將b23，b53改為b1350在上表的基礎(chǔ)上，考慮DE→C，將b13改為a3;考慮CE→A，將b31,b41改為a1。

③由于第三行為全a,所以ρ是無損聯(lián)接。

AB

C

DEADa1b12b13

a4b15ABa1a2b13a4b25BEb31a1a2b13a3a4a5CDEb41a1b42a3a4a5AEa1b52b13a3a4a5在上表的基礎(chǔ)上，考慮DE→C，將b13改為a3;③51

2、無損聯(lián)接的測(cè)試算法2：如果R的一個(gè)分解為ρ={R1,R2}，F(xiàn)為R所滿足的函數(shù)依賴集合，分解ρ相對(duì)于F是無損分解的充要條件是：

R1∩R2→R1-R2或R1∩R2→R2-R1

2、無損聯(lián)接的測(cè)試算法2：52

例：試分析下列分解是否具有無損聯(lián)接性：①設(shè)R（ABC），F(xiàn)={A→B}在R上成立，ρ1={AB，AC}。

52頁答：ρ1相對(duì)于F具有無損聯(lián)接性。

∵R1∩R2=AB∩AC=A；R1-R2=AB-AC=B；滿足A→B；

∴模式ρ1={AB，AC}具有無損聯(lián)接性。例：試分析下列分解是否具有無損聯(lián)接性：52頁答：ρ1相53②設(shè)R(ABC),F={A→B}在R上成立，ρ2={AB，BC}。

答：ρ2相對(duì)于F3是有損分解：

∵R1∩R2=AB∩BC=B；R1-R2=AB-BC=A； 不滿足A→B；

∴模式ρ2={AB，BC}是有損分解。②設(shè)R(ABC),F={A→B}在R上成立，ρ2={AB54③設(shè)R(Sno,Sname,Cno,Cname),F={Sno→Sname,Cno→Cname}在R上成立，ρ3={SnoSnameCno，CnoCname}。答：ρ3相對(duì)于F3是無損分解：

∵R1∩R2=SnoSnameCno∩CnoCname=Cno；

R1-R2=SnoSnameCno-CnoCname=SnoSname；

R2-R1=CnoCname-SnoSnameCno=Cname； 滿足Cno→Cname；

∴模式ρ3={SnoSnameCno,CnoCname}是無損分解。③設(shè)R(Sno,Sname,Cno,Cname),F={55四、保持函數(shù)依賴的分解

如果關(guān)系模式在分解后不能保持函數(shù)依賴，那么在數(shù)據(jù)庫中就會(huì)出現(xiàn)異常現(xiàn)象。所以，關(guān)系模式R到ρ={R1，R2，…，Rk}的分解，應(yīng)使函數(shù)依賴集F被F在這些Ri上的投影所邏輯蘊(yùn)涵。

這就是保持函數(shù)依賴問題。

四、保持函數(shù)依賴的分解56定義一:設(shè)F是屬性集U上的函數(shù)依賴集,Z是U上的一個(gè)子集,F在Z上的一個(gè)投影用πZ（F）表示：

πZ（F）={X→Y|X→YF+∧X,YZ}定義二:設(shè)ρ={R1,R2,

…，Rk}是關(guān)系模式R的一個(gè)分解，F(xiàn)是R上的函數(shù)依賴集，如果

k∪πRi（F）?Fi=1

稱分解ρ保持函數(shù)集F。

定義一:設(shè)F是屬性集U上的函數(shù)依賴集,Z是U上的一個(gè)子57

k

k從定義一可知F?∪πRi（F），從定義二可知∪πRi（F）?F，

i=1

k

i=1

因此，在分解ρ保持函數(shù)依賴情況下有（∪πRi（F））+=F+。

i=1根據(jù)定義二，測(cè)試一個(gè)分解是否保持FD，比較可行的方法是

k

逐步驗(yàn)證F中每個(gè)FD是否被

∪πRi（F）邏輯蘊(yùn)涵。

i=1如果F的投影不蘊(yùn)涵F，而我們又用ρ=｛R1，…，Rk｝表達(dá)R，很可能會(huì)找到一個(gè)數(shù)據(jù)庫實(shí)例σ滿足投影后的依賴，但不滿足F。對(duì)σ的更新也有可能使r違反FD。下面的例子說明了這種情況。k58例：試分析下列分解是否具有無損聯(lián)接性和保持函數(shù)依賴性：設(shè)R（ABC），F(xiàn)={A→C，B→C}在R上成立，ρ={AB，AC}。又∵已知F={A→C，B→C}∵A+=ACB+=BC（AB）+=ABC∴πAB（F）={φ}；πAC（F）={A→C}；

而πAB（F）∪πAC（F）={A→C}，B→C在該分解中丟失了。

∴模式ρ不具有保持函數(shù)依賴性。解：ρ相對(duì)于F是無損聯(lián)接分解但不保持函數(shù)依賴性?！逺1∩R2=AB∩AC=A；R2-R1=AC-AB=C；滿足A→C；∴模式ρ={AB，AC}具有無損聯(lián)接性。例：試分析下列分解是否具有無損聯(lián)接性和保持函數(shù)依賴性：59一、分解成3NF模式集算法1：結(jié)果為3NF并保持函數(shù)依賴性的分解。輸入：關(guān)系模式R的屬性集合U和R上成立的最小函數(shù)依賴集Fmin。輸出：R的一個(gè)分解ρ={R1，R2，…，Rk}，滿足每一個(gè)Ri相對(duì)

πRi（F）是3NF，且ρ保持F?！?模式分解的方法一、分解成3NF模式集§6模式分解的方法60方法：①如果R中某些屬性在F的所有依賴的左端或右端都不出現(xiàn)，那么這些屬性可以從R中分解出去，單獨(dú)構(gòu)成一個(gè)模式。②如果F中存在一個(gè)依賴X→A，而且{X，A}=U，則ρ:={R}，停止。如果不為①②，則進(jìn)行如下分解：

對(duì)F中的每一個(gè)依賴X→A，構(gòu)成一個(gè)關(guān)系模式XA。如果F中有X→A1，X→A2…，An，則可以用模式XA1A2…An代替XA1，

XA2，

…，XAn。分解結(jié)束，輸出ρ。方法：②如果F中存在一個(gè)依賴X→A，而且{61例：關(guān)系模式W（CTHSRG），最小函數(shù)依賴集Fmin=（C→T，HR→C，HT→R，CS→G，HS→R）根據(jù)算法，生成的分解為：ρ=（CT，HRC，HTR，CSG，HSR）

這樣的分解，顯然將原有的函數(shù)依賴都保持下來，而且每個(gè)分解模式均為3NF模式。例：關(guān)系模式W（CTHSRG），62算法2：轉(zhuǎn)換為3NF即具有無損連接性又保持函數(shù)依賴的分解。輸入:關(guān)系模式R的屬性集合U和R上成立的最小函數(shù)依賴集Fmin。輸出:即保持函數(shù)依賴又具有無損聯(lián)接地分解τ，而且τ中所有關(guān)系模式都是3NF。方法：①設(shè)ρ={R1，R2，…，Rn}是由算法1得到的一個(gè)3NF保持函數(shù)依賴的分解；②構(gòu)造τ=ρ{X},其中X是R的一個(gè)侯選鍵。例：ρ=（CT，HRC，HTR，CSG，HSR）∵HS+=CTHSRGτ=ρ{X}=(CT，HRC，HTR，CSG，HSR)算法2：轉(zhuǎn)換為3NF即具有無損連接性又保持函數(shù)依賴的分解。63四、無損聯(lián)接地分解成BCNF模式集

定理：設(shè)F是模式R的FD集，ρ={R1，R2，…，Rk}是相對(duì)于F的一個(gè)無損聯(lián)接分解，則有下面的結(jié)論成立：①對(duì)某個(gè)i，設(shè)Fi=πRi（F）,且ρ1={S1，S2，…，Sm}是相對(duì)于Fi的Ri一個(gè)無損聯(lián)接分解。那么R分解成：{R1…，Ri-1，S1，S2，…Sm，Ri+1，…，Rk}是相對(duì)于F的一個(gè)無損聯(lián)接分解。②設(shè)ρ2={R1…，Rk，Rk+1，…，Rn}是R的一個(gè)分解，那么ρ2相對(duì)于F也是一個(gè)無損聯(lián)接分解，四、無損聯(lián)接地分解成BCNF模式集①對(duì)某個(gè)i，設(shè)Fi64算法3：無損聯(lián)接地分解成BCNF模式集輸入：關(guān)系模式R的屬性集合U和R上成立的函數(shù)依賴集F。輸出：R的一個(gè)無損分解ρ={R1，R2，…，Rk}，滿足每個(gè)Ri相對(duì)πRi（F）是BCNF模式集。方法：反復(fù)使用上述定理，逐步分解關(guān)系模式R，使每次分解具有無損聯(lián)接特征，并且分解出來的模式滿足BCNF。算法3：無損聯(lián)接地分解成BCNF模式集方法：反復(fù)使用上述65方法：反復(fù)使用上述定理，逐步分解關(guān)系模式R，使每次分解具有無損聯(lián)接特征，并且分解出來的模式滿足BCNF。①置初值：ρ={R}；②如果ρ中所有模式都是BCNF，則轉(zhuǎn)④；③如果ρ中有一個(gè)關(guān)系模式S不是BCNF，則

S中必能找到一個(gè)函數(shù)依賴X→A有X不是S的碼,且AX，設(shè)S1=XA，S2=S—A，用分解{S1，S2}代替S，轉(zhuǎn)②;④分解結(jié)束，輸出ρ。方法：反復(fù)使用上述定理，逐步分解關(guān)系模式R，使每次分解66舉例1：試分析下列分解是否保持函數(shù)依賴性：設(shè)R（ABCD），F(xiàn)={A→B，B→C,C→D，D→A},ρ={AB,BC,CD}請(qǐng)運(yùn)用保持函數(shù)依賴集的測(cè)試算法驗(yàn)證ρ是否保持函數(shù)依賴性。解：算法的第一步是計(jì)算F在每一個(gè)關(guān)系模式Ri上的投影：∵A+=ABCD，B+=ABCD，C+=ABCD，D+=ABCD∴πAB(F)={A→B，B→A}

πBC(F)={B→C，C→B}

πCD(F)={C→D，D→C}k算法的第二步是逐步驗(yàn)證F中每個(gè)FD是否被∪πRi(F)邏輯蘊(yùn)涵。ki=1∵∪πRi(F)={A→B,B→A,B→C,C→B,C→D,D→C}只要判斷其是否i=1邏輯蘊(yùn)涵D→A?

由D→C,C→B,B→A可推出D→A，∴ρ={AB,BC,CD}保持FD。舉例1：試分析下列分解是否保持函數(shù)依賴性：解：算法的第一步67解：反例r可以用測(cè)試時(shí)的初始表格:即滿足F的泛關(guān)系r如下所示r

ABC

πAB（r）

AB

πBC（r）

BC

AB a1a2 b13 a1a2a2b13

BC b21a2 a3

b21a2a2a3πAB（r）?πBC（r）有四個(gè)元組：

A B C

a1 a2

b13∴mρ（r）≠r a1 a2 a3 b21 a2

b13 b21 a2 a3

舉例2：設(shè)關(guān)系模式R（ABC）分解成ρ=｛AB，BC｝，如果R上的FD集F=｛A→B｝，那么這個(gè)分解是損失分解。試舉出R的一個(gè)關(guān)系r，不滿足mρ（r）=r。舉例2：設(shè)關(guān)系模式R（ABC）分解成ρ=｛AB，BC｝，68解：反例r可以用測(cè)試時(shí)的初始表格:即滿足F的泛關(guān)系r如下所示rABCπAB(r)ABπBC(r)BC

AB a1a2b13a1a2a2b13

BC b21a2a3

b21a2a2a3πAB（r）?πBC（r）有四個(gè)元組：

A B C

a1 a2

b13∴

mρ（r）≠r a1 a2 a3 b21 a2

b13 b21 a2 a3

解：反例r可以用測(cè)試時(shí)的初始表格:即滿足F的泛關(guān)系r如69

舉例3：設(shè)有關(guān)系模式R（職工編號(hào)，日期，日營業(yè)額，部門名，部門經(jīng)理），該模式統(tǒng)計(jì)商店里每個(gè)職工的日營業(yè)額，以及職工所在的部門和經(jīng)理信息。

如果規(guī)定：每個(gè)職工每天只有一個(gè)營業(yè)額；每個(gè)職工只在一個(gè)部門工作；每個(gè)部門只有一個(gè)經(jīng)理。試回答下列問題：（1）根據(jù)上述規(guī)定，寫出模式R的基本FD和關(guān)鍵碼；（2）說明R不是2NF的理由，并把R分解成2NF模式集；（3）進(jìn)而分解成3NF模式集。舉例3：設(shè)有關(guān)系模式R（職工編號(hào)，日期，日營業(yè)額，部門名，70解:（1）據(jù):每個(gè)職工每天只有一個(gè)營業(yè)額,每個(gè)職工只在一個(gè)部門工作,每個(gè)部門只有一個(gè)經(jīng)理。

得到基本的函數(shù)依賴有三個(gè)：（職工編號(hào)，日期）→日營業(yè)額

職工編號(hào)→部門名,部門名→部門經(jīng)理R的關(guān)鍵碼為（職工編號(hào)，日期）（2）R中有兩個(gè)這樣的FD： （職工編號(hào)，日期）→（部門名，部門經(jīng)理）

職工編號(hào)→（部門名，部門經(jīng)理）由于前一個(gè)函數(shù)依賴是部分函數(shù)依賴，所以R不是2NF模式。

R應(yīng)分解成

R1（職工編號(hào)，部門名，部門經(jīng)理） R2（職工編號(hào)，日期，日營業(yè)額） 此時(shí)，R1和R2都是2NF模式。解:（1）據(jù):每個(gè)職工每天只有一個(gè)營業(yè)額,（271

R1（職工編號(hào)，部門名，部門經(jīng)理）R2（職工編號(hào)，日期，日營業(yè)額）（3）R2已是3NF模式。

但在R1中存在傳遞依賴：職工編號(hào)→部門經(jīng)理∵職工編號(hào)→部門名,部門名→部門經(jīng)理∴

R1不是3NF模式。

將R1分解為：

R11（職工編號(hào)，部門名）

R12（部門名，部門經(jīng)理）這樣，ρ={R11，R12，R2}是一個(gè)3NF模式集。R1（職工編號(hào)，部門名，部門經(jīng)72①

ρ是BCNF模式集，或3NF模式集；②

無損分解，即對(duì)于R上任何滿足F的泛關(guān)系r應(yīng)滿足

K

r=?πRi（r）

i=1K

③

保持函數(shù)依賴集F，即（∪πRi（F））?Fi=1五、模式設(shè)計(jì)方法的原則

關(guān)系模式R<U,F>分解成數(shù)據(jù)庫模式:

ρ=｛R1，…，Rk｝，一般應(yīng)具有三個(gè)特性：①

ρ是BCNF模式集，或3NF模式集；五、模式設(shè)計(jì)方法73關(guān)系模式設(shè)計(jì)方法的原則：模式設(shè)計(jì)方法應(yīng)符合三條原則：表達(dá)性,分離性,最小冗余性。

表達(dá)性涉及兩個(gè)數(shù)據(jù)庫模式的數(shù)據(jù)等價(jià)和依賴等價(jià)問題,分別用無損聯(lián)接和保持函數(shù)依賴來衡量。分離性是指屬性間的間接聯(lián)系應(yīng)該用不同的模式表達(dá)，分離的基準(zhǔn)是一系列范式。

最小冗余性要求分解后的模式個(gè)數(shù)和模式中屬性總數(shù)應(yīng)最少。關(guān)系模式設(shè)計(jì)方法的原則：74函數(shù)依賴有效地表達(dá)了屬性值之間的多對(duì)一聯(lián)系;

多值依賴和聯(lián)系依賴能刻劃一部分一對(duì)多聯(lián)系。一、多值依賴（multivalueddependency，簡記為MVD）定義一:設(shè)U是關(guān)系模式R的屬性集，X、Y是U的子集。如果滿足R的任一關(guān)系r，對(duì)于X的某一個(gè)確定值，都存在Y的一組值與之對(duì)應(yīng),，且Y的這組值又與Z=U―X―Y中的屬性值不相關(guān)，此時(shí)稱Y多值依賴于X，或稱X多值決定Y，記為:X→→Y?！?多值依賴和第四范式函數(shù)依賴有效地表達(dá)了屬性值之間的多對(duì)一聯(lián)系;一、75例:模式R(DNAME，TNAME，TSEX,SNAME，SSEX)：

模式R的關(guān)鍵碼是（TNAME，SNAME）DNAME

TNAMETSEXSNAME

SSEX

計(jì)算機(jī) 馬亮男吳康男

計(jì)算機(jī) 馬亮

男

劉紅

女計(jì)算機(jī) 李燕女吳康

男

計(jì)算機(jī) 李燕女

……劉紅

女……

……

……

……通訊汪宏偉

男李志鳴

男

通訊

錢紅

女

李志鳴

男其中有函數(shù)依賴：

TNAME→TSEX,SNAM→SSEX。還有多值依賴：DNAME→→（TNAME，TSEX）DNAME→→（SNAME，SSEX）這個(gè)例子也說明了多值依賴具有互補(bǔ)性：X→→Y成立

就一定有X→→Z成立（Z=U―X―Y）。例:模式R(DNAME，TNAME，TSEX,SNAME，76例:模式R(DNAME，TNAME，TSEX,SNAME，SSEX)：

模式R的關(guān)鍵碼是（TNAME，SNAME）DNAME

TNAMETSEXSNAME

SSEX

計(jì)算機(jī) 馬亮

男吳康男

計(jì)算機(jī) 馬亮

男

劉紅

女計(jì)算機(jī) 李燕女吳康

男

計(jì)算機(jī) 李燕女

……劉紅

女……

……

……

……通訊汪宏偉

男李志鳴

男

通訊

錢紅

女

李志鳴

男例:模式R(DNAME，TNAME，TSEX,SNAME，77其中有函數(shù)依賴：TNAME→

TSEX,SNAME→SSEX還有多值依賴：DNAME→→（TNAME，TSEX）DNAME→→（SNAME，SSEX）這個(gè)例子也說明了:

多值依賴具有互補(bǔ)性：如果X→→Y成立，就一定有X→→Z成立（Z=U―X―Y）。81頁其中有函數(shù)依賴：TNAME→TSEX,SNAME78顯然，這里存在著數(shù)據(jù)冗余和操作異?，F(xiàn)象。產(chǎn)生問題的原因是:教師和學(xué)生沒有直接的聯(lián)系。教師與系有直接的聯(lián)系，學(xué)生與系有直接的聯(lián)系，而教師與學(xué)生之間的聯(lián)系是一種間接的聯(lián)系。

把有間接聯(lián)系的屬性放在一個(gè)模式中就會(huì)產(chǎn)生冗余和異?，F(xiàn)象。在模式R中，一個(gè)系有很多教師（一對(duì)多聯(lián)系），一個(gè)系有很多學(xué)生（一對(duì)多聯(lián)系），教師與學(xué)生間沒有直接聯(lián)系。這種屬性間的一對(duì)多聯(lián)系稱為多值依賴。顯然，這里存在著數(shù)據(jù)冗余和操作異?，F(xiàn)象。把有間接聯(lián)79

顯然關(guān)系模式R中至少有三個(gè)屬性，才