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

第6章關(guān)系數(shù)據(jù)理論6.1問題的提出6.2規(guī)范化6.3數(shù)據(jù)依賴的公理系統(tǒng)*6.4模式的分解(要求)6.5小結(jié)問題的提出關(guān)系數(shù)據(jù)庫邏輯設(shè)計(jì)針對(duì)具體問題，如何構(gòu)造一個(gè)適合于它的數(shù)據(jù)模式數(shù)據(jù)庫邏輯設(shè)計(jì)的工具──關(guān)系數(shù)據(jù)庫的規(guī)范化理論關(guān)系模式的形式化定義關(guān)系模式由五部分組成，即它是一個(gè)五元組：

R(U,D,DOM,F)R：關(guān)系名U：組成該關(guān)系的屬性名集合D：屬性組U中屬性所來自的域DOM：屬性向域的映象集合F：屬性間數(shù)據(jù)的依賴關(guān)系集合關(guān)系模式的簡化表示關(guān)系模式R（U,D,DOM,F）簡化為一個(gè)三元組：

R（U,F）當(dāng)且僅當(dāng)U上的一個(gè)關(guān)系r滿足F時(shí)，r稱為關(guān)系模式R（U,F）的一個(gè)關(guān)系數(shù)據(jù)依賴定義屬性值間的相互關(guān)連,是數(shù)據(jù)庫模式設(shè)計(jì)的關(guān)鍵一個(gè)關(guān)系內(nèi)部屬性與屬性之間的約束關(guān)系現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象數(shù)據(jù)內(nèi)在的性質(zhì)語義的體現(xiàn)數(shù)據(jù)依賴的類型函數(shù)依賴（FunctionalDependency，簡記為FD）多值依賴（MultivaluedDependency，簡記為MVD）其他數(shù)據(jù)依賴對(duì)關(guān)系模式的影響[例1]建立一個(gè)描述學(xué)校教務(wù)的數(shù)據(jù)庫： 學(xué)生的學(xué)號(hào)（Sno）、所在系（Sdept） 系主任姓名（Mname）、課程名（Cname） 成績（Grade）單一的關(guān)系模式：Student<U、F>U＝｛Sno,Sdept,Mname,Cname,Grade｝關(guān)系模式Student<U,F>中存在的問題1.數(shù)據(jù)冗余太大2.更新異常（UpdateAnomalies）3.插入異常（InsertionAnomalies）4.刪除異常（DeletionAnomalies）U＝｛Sno,Sdept,Mname,Cname,Grade｝結(jié)論：Student關(guān)系模式不是一個(gè)好的模式。“好”的模式：不會(huì)發(fā)生插入異常、刪除異常、更新異常，數(shù)據(jù)冗余應(yīng)盡可能少不好原因：由存在于模式中的某些數(shù)據(jù)依賴引起解決方法：通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴規(guī)范化基本概念

1,函數(shù)依賴

定義:設(shè)R(U)是屬性集U上的關(guān)系模式X,Y是U的子集。若對(duì)于R(U)的任意一個(gè)可能的關(guān)系r，r中不可能存在兩個(gè)元組在X上的屬性值相等,而在Y上的屬性值不等,則稱X函數(shù)確定Y或Y函數(shù)依賴于X，記作X→Y。

{R<U,F>X→YR中屬性（組）X的每一個(gè)值，R

中的Y只有一個(gè)值與之對(duì)應(yīng)}2、非平凡函數(shù)依賴

（X→Y；Y￠X）

X→Y，Y不包含于X，X→Y非平凡的函數(shù)依賴3、決定因素

X→Y，X為決定因素

4、完全函數(shù)依賴

X→Y：X→Y，X’為X的任一真子集

X’/Y5、部分函數(shù)依賴

X→Y：X→YX’為X的任一真子集存在X’Y例如SCI（SNO，CNO，G，CRE）（SNO，CNO）→G（SNO，CNO）→CRE又CNO→CRE

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

X→Y，Y不包含于X，Y→X，Y→Z則稱Z對(duì)X傳遞函數(shù)依賴

7、碼侯選碼：K為R<U，F(xiàn)>的屬性或?qū)傩越M合，若K完全函數(shù)確定U(強(qiáng)調(diào)不存在K的真子集能函數(shù)確定U)，K為R的候選碼。若候選碼多于一個(gè)，則選定其中的一個(gè)為主碼主屬性：包含在任何一個(gè)候選碼中的屬性非主屬性：不包含在任何侯選碼中的屬性全碼：整個(gè)屬性組是碼外碼：范式

第一范式：1NF要求：關(guān)系模式R<U,F>中每個(gè)分量必須是不可分的數(shù)據(jù)項(xiàng)。滿足1NF則滿足了關(guān)系模式中的基本要求。例：SC1（SNO，CNO，G，CRE）SC1∈1NF

例：SC1（SNO，CNO，G，CRE）SC1∈1NF

分析步驟：1）寫出關(guān)系模式的函數(shù)依賴集FD(或畫函數(shù)依賴圖)(SNO,CNO)→G,(SNO，CNO)→CRE,CNO→CRE2）確定關(guān)系模式的候選碼：(SNO，CNO)3）分析存在的問題：

冗余，插入異常，刪除異常，更新復(fù)雜4）找出存在問題的原因：

存在非主屬性CRE部分函數(shù)依賴于碼（SNO,CNO）5）問題的解決：

分解關(guān)系模式SC1為兩個(gè)關(guān)系模式：

SC11<（SNO，CNO，G），(SNO，CNO)→G>SC12<（CNO，CRE）,CNO→CRE

>由此，消除了非主屬性對(duì)碼的部分函數(shù)依賴,所有非主屬性對(duì)碼是完全函數(shù)依賴．第二范式：2NF要求：R∈1NF且每一個(gè)非主屬性完全函數(shù)依賴于碼,

則R∈2NF例：S-L-C（SNO，SD，SL，CNO，G）

FD：（SNO，CNO）→GSNO→SD,SD不屬于SNOSDSNO,SD→SLSL傳遞依賴SNOGSNOCNOSDSL

∵碼（SNO，CNO）主屬性SNO，CNO

非主屬性SD，SL，G∴存在非主屬性部分依賴于碼并非每個(gè)非主屬性完全函數(shù)依賴于碼∴S-L-C∈2NF問題：冗余，插入異常，刪除異常，更新復(fù)雜解決：模式分解分解S-L-C為:SC和SL2個(gè)關(guān)系模式

SC<（SNO，CNO，G）,（SNO，CNO）→G>∈2NF

SL<（SNO，SD，SL）,SNO→SD,SD→SL>∈2NF每個(gè)非主屬性完全函數(shù)依賴于碼,不存在非主屬性對(duì)碼的部分函數(shù)依賴.R∈2NFSL仍然存在問題：冗余,存儲(chǔ)異常,更新復(fù)雜

顯然是存在非主屬性對(duì)碼的傳遞函數(shù)依賴

第三范式：3NF要求：如果關(guān)系模式R<U,F>中的所有非主屬性對(duì)任何碼（侯選碼）都不存在傳遞依賴，則關(guān)系R是第三范式.R∈3NF可以證明：若R∈3NF則每一個(gè)非主屬性即不部分依賴于碼也不傳遞依賴于碼∴R∈3NF必然R∈2NFS-L-C（SNO，SD，SL，CNO，G）分解為如3個(gè)關(guān)系模式:SC<（SNO,CNO,G）,（SNO，CNO）→G>SD<（SNO，SD）,SNO→SD>DL<（SD，DL）,SD→SL

>SC,SD,SL均屬于第三范式如圖給出的關(guān)系R為第幾范式?是否存在操作異常?若存在，則將其分解為高一級(jí)范式。分解完成的高級(jí)范式中是否可以避免分解前關(guān)系中存在的操作異常?(確定R<U,F>)工程號(hào)材料號(hào)數(shù)量開工日期完工日期價(jià)格

P1I1498059902250P1I2698059902300P1I31598059902180P2I1698119912250P2I41898119912350

完工日期

工程號(hào)開工日期數(shù)量

材料號(hào)價(jià)格R1(工程號(hào),材料號(hào),數(shù)量)R2(材料號(hào),價(jià)格)R3(工程號(hào),開工日期,完工日期)例:R(SNO,SNA,CNO,G,CNA,TNA,TAGE)(學(xué)號(hào),姓名,課程號(hào),成績,課程名稱,教師姓名,教師年齡)

一名教師可以講授多門課程,一門課程僅由一位教師講授,其它語意略分析R并將其轉(zhuǎn)換為高級(jí)范式FD:SNOSNA;(SNO,CNO)G;CNOCAN;CNOTNA;TNATAGER1(SNO,SNA),R2(SNO,CNO,G)R3(CNO,CAN,TNA,TAGE)例：設(shè)有關(guān)系模式,

倉庫保管WPE（W＃，P＃，E＃，QNT）倉庫號(hào)，器件號(hào)，職工號(hào)，數(shù)量函數(shù)依賴：（W#，P#）QNT

（E#，P#）QNT

（W#，P#）E#E#W#W#問題：關(guān)系模式WPE（W＃，P＃，E＃，QNT）達(dá)到？NFE#P#QNT分析：關(guān)系模式WPE有兩個(gè)侯選碼（W#，P#）、（E#，P#）主屬性：W#，P#，E#非主屬性：QNT∴WPE∈3NF存在問題(設(shè)確定（E#，P#）為主碼)某新職工分配來倉庫，處于學(xué)習(xí)階段，但沒有獨(dú)立承但任務(wù)，即有E＃但無P＃，缺少碼的組成部分，無法插入到該關(guān)系——插入異常原因：主屬性W＃對(duì)另一個(gè)侯選碼（E#，P#）的部分函數(shù)依賴解決方法：分解關(guān)系模式WPE為保管EP（E＃，P＃，QNT）碼（E＃，P＃）工作EW（E＃，W＃）碼E＃*分解后的關(guān)系可以通過自然連接恢復(fù)原關(guān)系*分解后將失去某些函數(shù)依賴：（P#，W#）E#

（P#，W#）QNT意味著失去某些語義，從而不符合語義的數(shù)據(jù)可以被數(shù)據(jù)庫接受。(如果原關(guān)系模式確定(P#，W#)為主碼上述函數(shù)依賴可以保證)對(duì)應(yīng)上述丟失的函數(shù)依賴，失去語義要求：*每個(gè)倉庫一種器件由專人負(fù)責(zé)，新關(guān)系模式接受如下情況（P1W1）E1

（P1W1）E2*某倉庫的某種器件有其數(shù)量所以：分解后的關(guān)系模式降低了部分的完整性約束。實(shí)際工程應(yīng)綜合考慮整體代價(jià)。

BC范式：BCNF要求：R〈U，F(xiàn)〉∈1NF，若X→Y且Y￠X時(shí),X必含有碼，則R〈U，F(xiàn)〉∈BCNF。意味著：R〈U，F(xiàn)〉中，若每個(gè)決定因素都包含碼，則R〈U，F(xiàn)〉∈BCNF上例中存在E#W#E#中沒有包含碼∴WPE∈BCNF可以證明：R∈BCNF則R∈3NFR∈3NF，仍可能存在的問題，原因在于主屬性對(duì)碼的部分依賴和傳遞依賴。例：判斷以下關(guān)系模式是否∈BCNF1、SJP（S，J，P）學(xué)生,課程,名次(唯一)

2、STJ（S，T，J）學(xué)生,教師,課程(一名教師僅講授一門課程)例：判斷以下關(guān)系模式是否∈BCNF1、SJP（S，J，P）學(xué)生,課程,名次(唯一)FD:(S,J)P(J,P)S2、STJ（S，T，J）學(xué)生,教師,課程(一名教師僅講授一門課程)FD:(S,J)T(S,T)JTJ小結(jié)：1NF（每個(gè)分量必須不可分）消除非屬性對(duì)碼的部分函數(shù)依賴2NF（每個(gè)非屬性完全函數(shù)依賴于碼）消除非屬性對(duì)碼的傳遞函數(shù)依賴3NF(所有非屬性對(duì)任何碼都不存在傳遞函數(shù)依賴）消除主屬性對(duì)碼的部分和傳遞函數(shù)依賴BCNF（每個(gè)決定因素都包含碼）

多值依賴定義6.9設(shè)R(U)是屬性集U上的一個(gè)關(guān)系模式。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值無關(guān)。若X→→Y，Z為空，則稱X→→Y為平凡的多值依賴。例如:Teaching(課程,教師,參考書)普通物理學(xué)光學(xué)原理物理習(xí)題集普通物理學(xué)光學(xué)原理物理習(xí)題集數(shù)學(xué)分析微分方程高等代數(shù)數(shù)學(xué)分析微分方程高等代數(shù)…李勇李勇李勇王軍王軍王軍李勇李勇李勇張平張平張平

…物理物理物理物理物理物理數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)…

參考書B教員T課程CTeaching∈BCNFTeaching具有唯一候選碼(C，T，B)，即全碼Teaching

4NF

定義:關(guān)系模式R〈U,F〉∈lNF,如果對(duì)于R的每個(gè)非平凡多值依賴X→→Y(YX)，

X都含有碼,則稱R〈U,F〉∈4NF。

4NF就是限制關(guān)系模式的屬性之間不允許有非平凡且非函數(shù)依賴的多值依賴存在。因?yàn)楦鶕?jù)定義，對(duì)于每一個(gè)非平凡的多值依賴X→→Y，

X都含有候選碼，于是就有X→Y，所以4NF所允許的非平凡的多值依賴實(shí)際上是函數(shù)依賴。關(guān)系模式WSC（W，S，C）

W表示倉庫，S表示保管員，C表示商品假設(shè)每個(gè)倉庫有若干個(gè)保管員，有若干種商品每個(gè)保管員保管所在的倉庫的所有商品每種商品被所有保管員保管

WSCW1S1C1W1S1C2W1S1C3W1S2C1W1S2C2W1S2C3W2S3C4W2S3C5W2S4C4W2S4C5W→→S且W→→C用下圖表示這種對(duì)應(yīng)

第四范式：4NFR<U,F>∈1NF,如果對(duì)于R的每個(gè)非平凡多值依賴X→→Y（Y￠X），X都含有碼，則R〈U，F(xiàn)〉∈4NF例中:教員T多值依賴,課程C:C→→T是非平凡多值依賴,但C不含有碼,所以Teaching,WSC都不屬于4NF解決:模式分解消除非平凡且非函數(shù)依賴的多值依賴.(R1(C,T),R2(C,B))

應(yīng)為平凡的多值依賴或函數(shù)依賴,既為4NF即：要么是平凡的多值依賴，要么是函數(shù)依賴。本例分解屬于前者。小結(jié)：1NF（每個(gè)分量必須不可分）消除非屬性對(duì)碼的部分函數(shù)依賴2NF（每個(gè)非屬性完全函數(shù)依賴于碼）消除非屬性對(duì)碼的傳遞函數(shù)依賴3NF(所有非屬性對(duì)任何碼都不存在傳遞函數(shù)依賴）消除主屬性對(duì)碼的部分和傳遞函數(shù)依賴BCNF（每個(gè)決定因素都包含碼）消除非平凡且非函數(shù)依賴的多值依賴4NF(平凡的多值依賴或函數(shù)依賴)

對(duì)于各種范式之間的聯(lián)系有

5NF

4NFBCNF

3NF

2NF

lNF成立。

一個(gè)低一級(jí)范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換為若干個(gè)高一級(jí)范式的關(guān)系模式的集合,這種過程就叫規(guī)范化。理論上高級(jí)范式規(guī)范程度高,關(guān)系模式好.實(shí)際工程中要結(jié)合具體情況進(jìn)行分析,確定數(shù)據(jù)庫中的關(guān)系模式,例如P22例中R3保持在2NF更好

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

定義6.11對(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。

Armstrong公理系統(tǒng)

對(duì)R〈U,F〉來說有以下的推理規(guī)則：Al.自反律(Reflexivity):若YXU,則X→Y為F所蘊(yùn)含。A2.增廣律(Augmentation):若X→Y為F所蘊(yùn)含,且ZU,則XZ→YZ為F所蘊(yùn)含A3.傳遞律(Transitivity):若X→Y及Y→Z為F所蘊(yùn)含,則X→Z為F所蘊(yùn)含。根據(jù)Armstrong公理系統(tǒng)

的A1，A2，A3這三條推理規(guī)則進(jìn)一步可以得到下面三條推理規(guī)則：

合并規(guī)則：由X→Y，X→Z，有X→YZ。（A2，A3）

偽傳遞規(guī)則：由X→Y，WY→Z，有XW→Z。（A2，A3）

分解規(guī)則：由X→Y及ZY，有X→Z。（A1，A3）根據(jù)合并規(guī)則和分解規(guī)則，可得引理6.1

引理6.l

X→A1A2…Ak成立的充分必要條件是X→Ai成立（i=l，2，…，k）定義6.l2在關(guān)系模式R<U，F(xiàn)>中為F所邏輯蘊(yùn)含的函數(shù)依賴的全體叫作F的閉包，記為F+。

F={XY,YZ},F+計(jì)算是NP完全問題，

F+={Xφ,Yφ,Zφ,XYφ,XZφ,YZφ,XYZφ,XX,YY,ZZ,XYX,XZX,YZY,XYZX,XY,YZ,XYY,XZY,YZZ,XYZY,XZ,YYZ,XYZ,XZZ,YZYZ,XYZZ,XXY,XYXY,XZXY,XYZXY,XXZ,XYYZ,XZXZ,XYZYZXYZ,XYXZ,XZXY,XYZXZ,XZYZ,XYXYZ,XZXYZ,XYZXYZ}F={XA1,……,XAn}的閉包F+計(jì)算是一個(gè)NP完全問題

定義6.l2在關(guān)系模式R<U，F(xiàn)>中為F所邏輯蘊(yùn)含的函數(shù)依賴的全體叫作F的閉包，記為F+。定義6.13設(shè)F為屬性集U上的一組函數(shù)依賴，X

U，XF+={A|X→A能由F根據(jù)Armstrong公理導(dǎo)出}，

XF+稱為屬性集X關(guān)于函數(shù)依賴集F的閉包(左部為X的全體右部的集合,或出發(fā)點(diǎn)為X的全體右部的集合)引理6.2

設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y

U，X→Y能由F根據(jù)Armstrong公理導(dǎo)出的充分必要條件是Y

XF+用途將判定X→Y是否能由F根據(jù)Armstrong公理導(dǎo)出的問題，就轉(zhuǎn)化為求出XF+

，判定Y是否為XF+的子集的問題算法6.1

求屬性集X（X

U）關(guān)于U上的函數(shù)依賴集F的閉包XF+

輸入：X，F(xiàn) 輸出：XF+步驟：1）令X（0）=X，i=02）求B，這里B={A|(

V)(

W)(V→WF∧VX（i）∧A

W)}(左部為X（i）子集的那些右部并入XF+)3）X（i+1）=B∪X（i）

4）判斷X（i+1）=X

（i）嗎?5）若相等或X（i）=U,則X（i）就是XF+,算法終止。6）若否，則i=i+l，返回第（2）步。[例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+

。解設(shè)X（0）=AB；(1)計(jì)算X（1）:逐一的掃描F集合中各個(gè)函數(shù)依賴，找左部為A，B或AB的函數(shù)依賴。得到兩個(gè)：

AB→C，B→D。于是X（1）=AB∪CD=ABCD。

(2)因?yàn)閄（0）≠X（1），所以再找出左部為ABCD子集的那些函數(shù)依賴，又得到AB→C，B→D，C→E，AC→B，于是X（2）=X（1）∪BCDE=ABCDE。(3)因?yàn)閄（2）=U，算法終止所以（AB）F+=ABCDE。A,B之間無函數(shù)依賴關(guān)系,所以AB為一個(gè)候選碼.例:求（AC）F+

Armstrong公理有效性：由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來的每一個(gè)函數(shù)依賴一定在F+中完備性：F+中的每一個(gè)函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來

定義6.14如果G+=F+，就說函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價(jià)。引理6.3F+=G+

的充分必要條件是

F

G+，和G

F+

定義6.15

如果函數(shù)依賴集F滿足下列條件，則稱F為一個(gè)極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。

1.F中任一函數(shù)依賴的右部僅含有一個(gè)屬性。

2.F中不存在這樣的函數(shù)依賴X→A，使得F與

F-{X→A}等價(jià)。

3.F中不存在這樣的函數(shù)依賴X→A,X有真子集Z使得（F-{X→A}）∪{Z→A}與F等價(jià)。[例]關(guān)系模式R<U，F(xiàn)>，其中：

U={Sno，Sdept，Mname，Cno，Grade}，

F={Sno→Sdept，Sdept→Mname，(Sno，Cno)→Grade}

設(shè)F’={Sno→Sdept，Sno→Mname，Sdept→Mname，(Sno，Cno)→Grade，

(Sno，Sdept)→Sdept}F是最小覆蓋，而F’不是。因?yàn)椋篎’

-{Sno→Mname}與F’等價(jià)

F’

-{(Sno，Sdept)→Sdept}也與F’等價(jià)

定理6.3每一個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)極小函數(shù)依賴集Fm。此Fm稱為F的最小依賴集。證明:構(gòu)造性證明，找出F的一個(gè)最小依賴集。

(1)逐一檢查F中各函數(shù)依賴FDi：X→Y，若Y=A1A2

…Ak，

k>2，則用{X→Aj

|j=1，2，…，k}來取代X→Y。(2)逐一檢查F中各函數(shù)依賴FDi：X→A，令G=F-{X→A}，若AXG+，則從F中去掉此函數(shù)依賴。(3)逐一取出F中各函數(shù)依賴FDi：X→A，設(shè)X=B1B2…Bm，逐一考查Bi

（i=l，2，…，m），若A（X-Bi

）F+，則以X-Bi

取代X。例1：R<U,F>

U={A,B,C,D}F={A→B,B→A,B→C,A→C,C→A}

求Fm例2:R<U,F>U={A,B,C,D}F={A

→

C,C→

A,B→

AC,D→

AC,BD→

A}求Fm答見word把低一級(jí)的關(guān)系模式分解為若干個(gè)高一級(jí)的關(guān)系模式的方法不是唯一的只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價(jià)，分解方法才有意義關(guān)系模式分解的標(biāo)準(zhǔn)三種模式分解等價(jià)的定義：⒈分解具有無損連接性⒉分解要保持函數(shù)依賴⒊分解既要保持函數(shù)依賴，又要具有無損連接性定義6.16關(guān)系模式R<U,F>的一個(gè)分解：ρ={R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>}U=∪Ui，且不存在Ui

Uj，F(xiàn)i為F在Ui上的投影定義6.17函數(shù)依賴集合{X→Y|X→Y

F+∧XY

Ui}的一個(gè)覆蓋Fi叫作F在屬性Ui上的投影i=1n關(guān)系模式R<U,F>的一個(gè)分解ρ={R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>}

若R與R1、R2、…、Rn自然連接的結(jié)果相等，則稱關(guān)系模式R的這個(gè)分解ρ具有無損連接性（Losslessjoin）具有無損連接性的分解保證不丟失信息無損連接性不一定能解決插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問題例：S-L（Sno，Sdept，Sloc）

F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}S-L∈2NF分解方法可以有多種：1.S-L分解為三個(gè)關(guān)系模式：SN(Sno) SD(Sdept) SO(Sloc)2.SL分解為下面二個(gè)關(guān)系模式：NL(Sno,Sloc) DL(Sdept,Sloc)3.將SL分解為下面二個(gè)關(guān)系模式：

ND(Sno,Sdept) NL(Sno,Sloc)

第3種分解方法具有無損連接性S-L（Sno，Sdept，Sloc）

F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}S-L∈2NF模式分解：ND<(Sno,Sdept),Sno→Sdept>NL<(Sno,Sloc),Sno→Sloc>

問題:這種分解方法沒有保持原關(guān)系中的函數(shù)依賴S-L中的函數(shù)依賴Sdept→Sloc沒有投影到關(guān)系模式ND、NL上這樣，現(xiàn)實(shí)中Sdept確定，辦公地點(diǎn)Sloc確定的語義丟失，即：函數(shù)依賴Sdept→Sloc沒有保持。

設(shè)關(guān)系模式R<U,F>被分解為若干個(gè)關(guān)系模式R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>（其中U=U1∪U2∪…∪Un，且不存在UiUj，F(xiàn)i為F在Ui上的投影），若F所邏輯蘊(yùn)含的函數(shù)依賴一定也由分解得到的某個(gè)關(guān)系模式中的函數(shù)依賴Fi所邏輯蘊(yùn)含，則稱關(guān)系模式R的這個(gè)分解是保持函數(shù)依賴的（Preservedependency）4.將SL分解為下面二個(gè)關(guān)系模式：

ND(Sno,Sdept)DL(Sdept,Sloc)

這種分解方法就保持了函數(shù)依賴第1種分解方法既不具有無損連接性，也未保持函數(shù)依賴，它不是原關(guān)系模式的一個(gè)等價(jià)分解第2種分解方法不保持函數(shù)依賴，不具有無損連接性第3種分解方法具有無損連接性，但未持函數(shù)依賴第4種分解方法既具有無損連接性，又保持了函數(shù)依賴三種模式分解的等價(jià)定義⒈分解具有無損連接性⒉分解要保持函數(shù)依賴⒊分解既要保持函數(shù)依賴，又要具有無損連接性如果一個(gè)分解具有無損連接性，則它能夠保證不丟失信息。如果一個(gè)分解保持函數(shù)依賴，

則它可以減輕或解決各種異常情況。分解具有無損連接性和分解保持函數(shù)依賴是兩個(gè)互相獨(dú)立的標(biāo)準(zhǔn)。具有無損連接性的分解不一定能夠保持函數(shù)依賴。同樣，保持函數(shù)依賴的分解也不一定具有無損連接性。以下分別討論模式分解的無損連接和保持函數(shù)依賴[1]如果R只分解為兩個(gè)關(guān)系模式定理6.5對(duì)于R<U,F>的一個(gè)分解{<R1<U1,F1>,R2<U2,F2>}，如果：

U1∩U2→U1-U2∈F+U1∩U2→U2-U1∈F+則該分解具有無損連接性例WPE(W#,P#,E#,QNT)分解為:EP(E#,P#,QNT)EW(E#,W#)此分解是否具有無損連接性?答:因?yàn)镋#→W#∈F+

所以,此分解是否具有無損連接性[2]R分解為多個(gè)(>2個(gè))關(guān)系模式算法6.2判別一個(gè)分解的無損連接性;定理6.4p190例5例:R(A,B,C,D,E)F:{A→D,E→D,D→B,BC→D,DC→A}分解為:R1(A,B)R2(A,E)R3(C,E)R4(B,C,D)R5(A,C)判斷其無損連接性(是)ABCDER1(A,B)a1a2b13b14b15R2(A,E)a1b22b23b24a5R3(C,E)b31b32a3b34a5R4(B,C,D)b41a2a3a4b45R5(A,C)a1b52a3b54b55A→D,E→D,D→B,BC→D,DC→AABCDER1(A,B)a1a2b13b14b15R2(A,E)a1b22b23b14a5R3(C,E)b31b32a3b34a5R4(B,C,D)b41a2a3a4b45R5(A,C)a1b52a3b14b55R1(A,B);R2(A,E);R3(C,E);R4(B,C,D);R5(A,C)ABCDER1(A,B)a1a2b13b14b15R2(A,E)a1b22b23b14a5R3(C,E)b31b32a3b14a5R4(B,C,D)b41a2a3a4b45R5(A,C)a1b52a3b14b55ABCDER1(A,B)a1a2b13b14b15R2(A,E)a1a2b23b14a5R3(C,E)b31a2a3b14a5R4(B,C,D)b41a2a3a4b45R5(A,C)a1a2a3b14b55A→D,E→D,D→B,BC→D,DC→A

ABCDER1(A,B)a1a2b13b14b15R2(A,E)a1a2b23b14a5R3(C,E)b31a2a3a4a5R4(B,C,D)b41a2a3a4b45R5(A,C)a1a2a3a4b55ABCDER1(A,B)a1a2b13b14b15R2(A,E)a1a2b23b14a5R3(C,E)a1a2a3a4a5R4(B,C,D)a1a2a3a4b45R5(A,C)a1a2a3a4b55A→D,E→D,D→B,BC→D,DC→A例:R(A,B,C,D,E)F:{A→C,B→D,C→D,DE→C,CE→A}分解ρ={AD,AB,BE,CDE,AE}是否為R的無損連接分解?是定義6.16關(guān)系模式R<U,F>的一個(gè)分解：ρ={R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>}U=∪Ui，且不存在Ui

Uj，F(xiàn)i為F在Ui上的投影定義6.17函數(shù)依賴集合{X→Y|X→Y

F+∧XY

Ui}的一個(gè)覆蓋Fi叫作F在屬性Ui上的投影i=1n定義6.19若F+=

,則R<U,F>的分解ρ={<R1<U1,F1>,…,Rk<Uk,Fk>}保持函數(shù)依賴引理6.3F+=G+的充分必要條件FG+,和GF+

要判定FG+,只需逐一對(duì)F中的函數(shù)依賴,X→Y

考察Y是否屬于XG++

定義6.19,引理6.3判別R的分解是否保持函數(shù)依賴R<U,F>U={A,B,C,D}F＝{A→B,B→C,C→D,D→A}判斷關(guān)系模式R的分解ρ={AB,BC,CD}是否具有保持依賴性解:ΠAB(F)={A→B,B→A}(定義6.１７)

ΠBC(F)={B→C,C→B}ΠCD(F)={C→D,D→C}ΠAB(F)∪ΠBC(F)∪ΠCD(F)=G={A→B,B→A,B→C,C→B,C→D,D→C}又DG+=ABCD,D→A也被保持(定義6.19,引理6.3)

所以,該分解具有依賴保持性

求所有的候選碼給定一個(gè)關(guān)系模式R<U，F(xiàn)>

U={A1，A2，…An}F中的函數(shù)依賴關(guān)系可以將屬性分為如下四類：

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

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

LR：在函數(shù)依賴集F左右部都出現(xiàn)的屬性

NLR：在函數(shù)依賴集F左右部都未出現(xiàn)的屬性

問題:?有可能是候選碼的屬性

?肯定不是候選碼的屬性算法：1)把R的所有屬性分為L、R、NLR和LR四類

并令X代表L、NLR類,Y代表LR類。2)求XF+

(簡記為X+),如果X+包含了R的全部屬性,則X為R的唯一候選碼,轉(zhuǎn)(5);否則,轉(zhuǎn)(3)。3)在Y中取一個(gè)屬性A,求(XA)+,如果它包含了R的全部屬性,則轉(zhuǎn)(4);否則,調(diào)換一個(gè)屬性反復(fù)進(jìn)行這一過程,直到試完所有Y中的屬性。4)如果已經(jīng)找到所有的候選碼,則轉(zhuǎn)(5);否則在Y中依次取兩個(gè)、三個(gè)……求它們的屬性閉包,直到其閉包包含R的所有屬性。5)停止,輸出結(jié)果。有如下結(jié)論：ZWYXF={W→Y,Y→W,X→W,X→Y,Z→Y,Z→W,XZ→W

}L類:{Z,X}又:(ZX)F+={X,Z,Y,W}所以:ZX是唯一候選碼極小函數(shù)依賴集:F’={W→Y,Y→W,X→Y,Z→W

}SDIBOQIBOQSD已知分解,判別無損連接性和保持函數(shù)依賴的依據(jù):算法6.2判別一個(gè)分解的無損連接性(定理6.4)定理6.5R分解為R1,R2具有無損連接性的充要條件定義6.19,引理6.3判別R的分解是否保持函數(shù)依賴未知分解.將低級(jí)關(guān)系模式分解為滿足相應(yīng)范式要求的關(guān)系模式:算法6.3（合成法）轉(zhuǎn)換為3NF的保持函數(shù)依賴的分解。算法6.4轉(zhuǎn)換為3NF既有無損連接性又保持函數(shù)依賴的分解算法6.5轉(zhuǎn)換為BCNF的無損連接分解（分解法）R<U,F>U={A,B,C,D}F={A→C,C→A,B→AC,D→AC,BD→A}對(duì)關(guān)系模式R進(jìn)行范式分析:1)求最小函數(shù)依賴集：Fm={A→C,C→A,B→C,D→C}2)候選碼:(BD)3)R屬于1NF4)轉(zhuǎn)換為高級(jí)范式,例如3NF如何進(jìn)行?R<U,F>U={A,B,C,D}F={A→C,C→A,B→AC,D→AC,BD→A}對(duì)關(guān)系模式R進(jìn)行范式分析:求得：Fm={A→C,C→A,B→C,D→C}唯一候選碼：

（BD）轉(zhuǎn)換為3NF保持函數(shù)依賴的分解為:

ρ={AC,BC,DC}(算法6.3)轉(zhuǎn)換為3NF既無損鏈接又保持函數(shù)依賴的分解為：ρ={AC,BC,DC,BD}(算法6.4)例１:R(A,B,C,D,E)F＝{A→Ｄ,Ｅ→D,Ｄ→Ｂ,ＢＣ→Ｄ,CＤ→

A}１）求Ｒ的侯選碼２）將Ｒ分解為３ＮＦ且保持函數(shù)依賴

１）Ｒ的侯選碼CE因?yàn)椋簝H在左部出現(xiàn)的屬性(ＣＥ)+=ABCDE２）ρ={ＤＥ，ＢＣＤ，ＡＣＤ}因?yàn)?Fm={A→Ｄ,Ｅ→D,D→Ｂ,ＢＣ→D,CD→A}將R分解為3NF:

ρ={AD,DE,BD,BCD,ACD}除去包含關(guān)系,化簡為:ρ={DE,BCD,ACD}

例２：R(Ｆ，Ｇ，Ｈ，Ｉ，Ｊ)F={Ｆ→Ｉ,Ｊ→Ｉ,Ｉ→Ｇ,ＧＨ→Ｉ,ＩＨ→Ｆ}

１）求Ｒ的侯選碼２）判斷ρ={FG,FJ,JH,IGH,FH}是否為無損分解．３）將Ｒ分解為３ＮＦ，具有無損連接并保持函數(shù)依賴

１）Ｒ的侯選碼JH

因?yàn)椋簝H在左部出現(xiàn)的屬性(JH)+=FGIJH２）由判斷表ρ具有無損分解

3）Fm={Ｆ→Ｉ,Ｊ→Ｉ,Ｉ→Ｇ,ＧＨ→Ｉ,ＩＨ→Ｆ}則滿足3NF具有保持依賴的分解為

ρ={JI,IGH,IHF}

經(jīng)判斷ρ不具有無損連接性令ρ=ρ∪{JH}

ρ={JI,IGH,IHF,JH}即為所求.例３：R(Ａ，Ｂ，Ｃ，Ｄ，Ｅ)F＝{Ａ→Ｃ,Ｃ→Ｄ,Ｂ→Ｃ,ＤＥ→Ｃ,ＣＥ→Ａ}１）求Ｒ的侯選碼２）判斷ρ={AD,AB,BC,CDE,AE}是否為無損分解．３）將Ｒ分解為BCNF，具有無損連接性．１）Ｒ的侯選碼BE

因?yàn)椋簝H在左部出現(xiàn)的屬性(BE)+=ABCDE２）由判斷表ρ不具有無損分解F＝{Ａ→Ｃ,Ｃ→Ｄ,Ｂ→Ｃ,ＤＥ→Ｃ,ＣＥ→Ａ}

3）R不屬于BCNF(并非決定因素都包含碼)首先考慮A→C,A非碼,將U分解為:U1={AC},F1={Ａ→Ｃ},R1是BCNF；U2={ABDE}，由F可推出F2

必包括：B→D

因?yàn)锽E為碼，所以R2不是BCNF(并非決定因素都包含碼)對(duì)于R2,考慮B→D,B非碼,將U2進(jìn)一步分解為

{BD},{ABE}均屬于BCNF

所以ρ={AC,BD,ABE}即為所求

設(shè)關(guān)系模式R(ABCD),在R上有五個(gè)相應(yīng)的FD集及分解。①F={B→C,D→A},ρ={BC,AD}②F={AB→C,C→A,C→D},ρ={ACD,BC}③