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

第六章關(guān)系數(shù)據(jù)庫理論回顧6.2.3范式1NF6.2.42NF6.2.53NF6.2.6BCNF6.2.42NF2NF定義6.6若R1NF，且每個非主屬性完全函數(shù)依賴于碼，則稱R2NF消除非主屬性對碼的部分函數(shù)依賴6.2.53NF定義6.7關(guān)系模式R<U，F(xiàn)>

中若不存在這樣的碼X、屬性組Y及非主屬性Z(ZY),使得X→Y,(Y→X),Y→Z成立，則稱R<U，F(xiàn)>∈3NF。6.2.6BC范式（BCNF）定義6.8設(shè)關(guān)系模式R<U，F(xiàn)>∈1NF，若X→Y

且YX時X必含有候選碼,則R∈BCNF

設(shè)關(guān)系模式R<U，F(xiàn)>∈1NF，如果對于R的每個函數(shù)依賴X→Y，若Y不屬于X，則X必含有候選碼，那么R∈BCNF。也就是說，關(guān)系模式R<U，F(xiàn)>中，若每一個決定因素都包含碼，則R<U，F(xiàn)>∈BCNF。

6.2.6BC范式(續(xù))例：在關(guān)系模式STJ（S，T，J）中，S表示學(xué)生，T表示教師，J表示課程。每一教師只教一門課。每門課由若干教師教，某一學(xué)生選定某門課，就確定了一個固定的教師。某個學(xué)生選修某個教師的課就確定了所選課的名稱：

(S，J)→T，(S，T)→J，T→J

6.2.6BC范式(續(xù))

SJTSTJSTJ

6.2.6BC范式(續(xù))STJ∈3NF

(S，J)和(S，T)都可以作為候選碼

S、T、J都是主屬性STJ∈BCNFT→J，T是決定屬性集，T不是候選碼

6.2.6BC范式(續(xù))若R∈BCNFR中的所有非主屬性對每一個碼都是完全函數(shù)依賴R中的所有主屬性對每一個不包含它的碼，也是完全函數(shù)依賴沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性R∈3NF（證明）若R∈3NF則R不一定∈BCNF

6.2.6BC范式(續(xù))

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

SJ(S，J)∈BCNF，TJ(T，J)∈BCNF

沒有任何屬性對碼的部分函數(shù)依賴和傳遞函數(shù)依賴SJSTTJTJ

6.2.6BC范式(續(xù))3NF與BCNF的關(guān)系如果關(guān)系模式R∈BCNF，必定有R∈3NF。如果R∈3NF，且R只有一個候選碼，則R必屬于BCNF。6.2.7多值依賴?yán)?每個宿舍住著多個學(xué)生；每個學(xué)生可選修多門課程；為了生活學(xué)習(xí)方便，同一宿舍的學(xué)生約好選修相同的課程。 關(guān)系模式

SSC(SSH,SNAME,CNO)

宿舍號(SSH)、學(xué)生姓名(SNAME)和選修課程(CNAME)6.2.7多值依賴6.2.7多值依賴?yán)?每個classroom有多個教師給多個班上課；每個教師在多個classroom給多個班上課；每個班在多個classroom聽多個教師講課。6.2.7多值依賴?yán)?學(xué)校中某一門課程由多個教師講授，他們使用相同的一套參考書。每個教員可以講授多門課程，每種參考書可以供多門課程使用 關(guān)系模式Teaching(C,T,B)

課程C、教師T和參考書B6.2.7多值依賴6.2.7多值依賴（續(xù)）課程C教員T參考書B

物理

數(shù)學(xué)

計(jì)算數(shù)學(xué)李勇王軍

李勇張平

張平周峰

普通物理學(xué)光學(xué)原理物理習(xí)題集

數(shù)學(xué)分析微分方程高等代數(shù)

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

6.2.7多值依賴（續(xù)）普通物理學(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課程C6.2.7多值依賴（續(xù)）Teaching∈BCNF:Teaching具有唯一候選碼(C，T，B)，即全碼Teaching模式中存在的問題

(1)數(shù)據(jù)冗余度大：有多少名任課教師，參考書就要存儲多少次6.2.7多值依賴（續(xù)）(2)插入操作復(fù)雜：當(dāng)某一課程增加一名任課教師時，該課程有多少本參照書，就必須插入多少個元組例如物理課增加一名教師劉關(guān)，需要插入兩個元組：

（物理，劉關(guān)，普通物理學(xué)）（物理，劉關(guān)，光學(xué)原理）6.2.7多值依賴（續(xù)）(3)刪除操作復(fù)雜：某一門課要去掉一本參考書，該課程有多少名教師，就必須刪除多少個元組(4)修改操作復(fù)雜：某一門課要修改一本參考書，該課程有多少名教師，就必須修改多少個元組6.2.7多值依賴（續(xù)）產(chǎn)生原因 存在多值依賴6.2.7多值依賴（續(xù)）對于關(guān)系模式R及其屬性子集X,Y來說，如果給定一個X屬性值,就有一組Y屬性值(可以包括零個在內(nèi)的有限多個)與之對應(yīng),而與其他的屬性Z(Z=R-X-Y)無關(guān),則稱X多值決定Y,或Y多值依賴于X,并記為X→→Y.6.2.7多值依賴（續(xù)）定義6.10

設(shè)R(U)是一個屬性集U上的一個關(guān)系模式，X、Y和Z是U的子集，并且Z＝U－X－Y，多值依賴X→→Y成立當(dāng)且僅當(dāng)對R的任一關(guān)系r，r在（X，Z）上的每個值對應(yīng)一組Y的值，這組值僅僅決定于X值而與Z值無關(guān)

6.2.7多值依賴（續(xù)）例Teaching（C,T,B）

對于C的每一個值，T有一組值與之對應(yīng)，而不論B取何值6.2.7多值依賴（續(xù)）多值依賴形式化定義:在R（U）的任一關(guān)系r中，如果存在元組t，s使得t[X]=s[X]，那么就必然存在元組w，vr，（w，v可以與s，t相同），使得(1)w[X]=v[X]=t[X]=s[X](2)w[Y]=t[Y]且w[Z]=s[Z](3)v[Y]=s[Y]且v[Z]=t[Z]（即交換s，t元組的Y值所得的兩個新元組必在r中），則Y多值依賴于X，記為X→→Y。6.2.7多值依賴（續(xù)）平凡多值依賴和非平凡的多值依賴

若X→→Y，而Z＝φ，則稱

X→→Y為平凡的多值依賴 否則稱X→→Y為非平凡的多值依賴6.2.7多值依賴（續(xù)）（1）多值依賴具有對稱性若X→→Y，則X→→Z，其中Z＝U－X－Y

多值依賴的對稱性可以用完全二分圖直觀地表示出來。（2）多值依賴具有傳遞性若X→→Y，Y→→Z，則X→→Z-Y6.2.7多值依賴（續(xù)）XiZi1Zi2…ZimYi1Yi2…Yin多值依賴的對稱性6.2.7多值依賴（續(xù)）物理普通物理學(xué)光學(xué)原理物理習(xí)題集李勇王軍6.2.7多值依賴（續(xù)）（3）函數(shù)依賴是多值依賴的特殊情況。 若X→Y，則X→→Y。（4）若X→→Y，X→→Z，則X→→YZ。（5）若X→→Y，X→→Z，則X→→Y∩Z。（6）若X→→Y，X→→Z，則X→→Y-Z， X→→Z-Y。6.2.7多值依賴（續(xù)）多值依賴與函數(shù)依賴的區(qū)別(1)有效性多值依賴的有效性與屬性集的范圍有關(guān)若X→→Y在U上成立，則在W（XYWU）上一定成立；反之則不然，即X→→Y在W（WU）上成立，在U上并不一定成立6.2.7多值依賴（續(xù)）多值依賴的定義中不僅涉及屬性組X和Y，而且涉及U中其余屬性Z。一般地，在R（U）上若有X→→Y在W（WU）上成立，則稱X→→Y為R（U）的嵌入型多值依賴6.2.7多值依賴（續(xù)）(2)

若函數(shù)依賴X→Y在R（U）上成立，則對于任何Y'Y均有X→Y'成立多值依賴X→→Y若在R(U)上成立，不能斷言對于任何Y'Y有X→→Y'成立6.2.84NF定義6.10關(guān)系模式R<U，F(xiàn)>∈1NF，如果對于R的每個非平凡多值依賴X→→Y（YX），X都含有候選碼，則R∈4NF。如果R∈4NF，則R∈BCNF4NF就是限制關(guān)系模式的屬性之間不允許有非平凡且非函數(shù)依賴的多值依賴

允許的只是函數(shù)依賴(非平凡的多值依賴)6.2.84NF(續(xù))例：Teaching(C,T,B)∈4NF

存在非平凡的多值依賴C→→T，且C不是候選碼用投影分解法把Teach分解為如下兩個關(guān)系模式：

CT(C,T)∈4NF CB(C,B)∈4NF

C→→T，C→→B是平凡多值依賴6.2.9規(guī)范化小結(jié)關(guān)系數(shù)據(jù)庫的規(guī)范化理論是數(shù)據(jù)庫邏輯設(shè)計(jì)的工具。一個關(guān)系只要其分量都是不可分的數(shù)據(jù)項(xiàng)，它就是規(guī)范化的關(guān)系，但這只是最基本的規(guī)范化。規(guī)范化程度可以有多個不同的級別6.2.9規(guī)范化小結(jié)(續(xù))規(guī)范化程度過低的關(guān)系不一定能夠很好地描述現(xiàn)實(shí)世界，可能會存在插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問題一個低一級范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換為若干個高一級范式的關(guān)系模式集合，這種過程就叫關(guān)系模式的規(guī)范化6.2.9規(guī)范化小結(jié)(續(xù))關(guān)系模式規(guī)范化的思想消除不合適的數(shù)據(jù)依賴的各關(guān)系模式達(dá)到某種程度的“分離”采用“一事一地”的模式設(shè)計(jì)原則讓一個關(guān)系描述一個概念、一個實(shí)體或者實(shí)體間的一種聯(lián)系。若多于一個概念就把它“分離”出去所謂規(guī)范化實(shí)質(zhì)上是概念的單一化.6.2.9規(guī)范化小結(jié)(續(xù))不能說規(guī)范化程度越高的關(guān)系模式就越好在設(shè)計(jì)數(shù)據(jù)庫模式結(jié)構(gòu)時，必須對現(xiàn)實(shí)世界的實(shí)際情況和用戶應(yīng)用需求作進(jìn)一步分析，確定一個合適的、能夠反映現(xiàn)實(shí)世界的模式.關(guān)系規(guī)范化在現(xiàn)實(shí)應(yīng)用中可在任一步終止。6.2.9規(guī)范化小結(jié)(續(xù))2NF4NF1NF3NF消除非主屬性對碼的部分函數(shù)依賴消除非主屬性對碼的傳遞函數(shù)依賴消除主屬性對碼的傳遞函數(shù)依賴消除非平凡且非函數(shù)的多值依賴BCNF第六章關(guān)系數(shù)據(jù)理論6.1數(shù)據(jù)依賴6.2規(guī)范化6.3數(shù)據(jù)依賴的公理系統(tǒng)6.4模式的分解6.3數(shù)據(jù)依賴的公理系統(tǒng)邏輯蘊(yùn)含 定義6.11對于滿足一組函數(shù)依賴F的關(guān)系模式R<U，F(xiàn)>，其任何一個關(guān)系r，若函數(shù)依賴X→Y都成立(X→Y∈F),則稱F邏輯蘊(yùn)含X→Y6.3數(shù)據(jù)依賴的公理系統(tǒng)定義6.11`設(shè)F的關(guān)系模式R<U，F(xiàn)>的一個函數(shù)依賴集，X,Y是R的屬性子集,如果從F中的函數(shù)依賴能夠推導(dǎo)出X→Y,則稱F邏輯蘊(yùn)含X→Y或X→Y是F的邏輯蘊(yùn)含(涵).閉包(Closure)所有被F邏輯蘊(yùn)含的函數(shù)依賴集稱為F的閉包(Closure)記為F+6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))Armstrong公理系統(tǒng)一套推理規(guī)則，是模式分解算法的理論基礎(chǔ)用途求給定關(guān)系模式的碼從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))關(guān)系模式R<U，F(xiàn)>來說有以下的推理規(guī)則：Al.自反律（Reflexivity）：若Y

X

U，則X→Y為F所蘊(yùn)含。A2.增廣律（Augmentation）：若X→Y為F所蘊(yùn)含，且Z

U，則XZ→YZ為F所蘊(yùn)含。A3.傳遞律（Transitivity）：若X→Y及Y→Z為F所蘊(yùn)含，則X→Z為F所蘊(yùn)含。6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))注意：由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴，自反律的使用并不依賴于F定理6.lArmstrong推理規(guī)則是正確的6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))（l）自反律(Reflexivity):

若Y

X

U，則X→Y為F所邏輯蘊(yùn)含證:設(shè)Y

X

U

對R<U，F(xiàn)>

的任一關(guān)系r中的任意兩個元組t，s：若t[X]=s[X]，由于Y

X，有t[Y]=s[Y]，所以X→Y成立.自反律得證6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))(2)增廣律(Augmentation):若X→Y為F所蘊(yùn)含，且Z

U，則XZ→YZ為F所蘊(yùn)含。證：設(shè)X→Y為F所蘊(yùn)含，且Z

U。設(shè)R<U，F(xiàn)>

的任一關(guān)系r中任意的兩個元組t，s；若t[XZ]=s[XZ]，則有t[X]=s[X]和t[Z]=s[Z]；由X→Y，于是有t[Y]=s[Y]，所以t[YZ]=s[YZ]，所以XZ→YZ為F所蘊(yùn)含.增廣律得證。6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))(3)傳遞律(Transitivity)：若X→Y及Y→Z為F所蘊(yùn)含，則X→Z為F所蘊(yùn)含。證：設(shè)X→Y及Y→Z為F所蘊(yùn)含。對R<U，F(xiàn)>

的任一關(guān)系r中的任意兩個元組t,s.若t[X]=s[X]，由于X→Y，有t[Y]=s[Y]；再由Y→Z，有t[Z]=s[Z]，所以X→Z為F所蘊(yùn)含.傳遞律得證。6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))由Armstrong公理導(dǎo)出的推理規(guī)則合并律(unionrule)若XY，XZ，則XYZ}XY增廣律}XXY}XZ增廣律XYYZ傳遞律XYZ6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))由Armstrong公理導(dǎo)出的推理規(guī)則分解律(decompositionrule)若XY，及ZY則

XZ}ZY自反律}YZXY傳遞律XZ若XYZ，則XY,XZ6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))由Armstrong公理導(dǎo)出的推理規(guī)則偽傳遞律(pseudotransitivityrule)若XY，WYZ，則WXZ}XY增廣律}WXWYWYZ傳遞律WXZ6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))示例練習(xí)

R<U,F>,U=(A,B,C,G,H,I),F={AB,AC,CGH,CGI,BH},AH？CGHI？AGI？6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理6.1

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

F={X→Y,Y→Z},F+計(jì)算是NP完全問題，

F+={X→φ,Y→φ,Z→φ,XY→φ,XZ→φ,YZ→φ,XYZ→φ,X→X,Y→Y,Z→Z,XY→X,XZ→X,YZ→Y,XYZ→X,X→Y,Y→Z,XY→Y,XZ→Y,YZ→Z,XYZ→Y,X→Z,Y→YZ,XY→Z,XZ→Z,YZ→YZ,XYZ→Z,X→XY,XY→XY,XZ→XY,XYZ→XY,X→XZ,XY→YZ,XZ→XZ,XYZ→YZX→YZ,XY→XZ,XZ→XY,XYZ→XZ,X→ZYZ,XY→XYZ,XZ→XYZ,XYZ→XYZ}6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))定義6.13屬性集的閉包:設(shè)F為屬性集U上的一組函數(shù)依賴，X

U，

XF+={A|X→A能由F根據(jù)Armstrong公理導(dǎo)出}，XF+稱為屬性集X關(guān)于函數(shù)依賴集F的閉包6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))引理6.2

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

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

XF+6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))問題：有沒有一般性的算法判定XY是否能由F根據(jù)Armstrong公理導(dǎo)出？如果計(jì)算出F+，再判斷XY是否屬于F+，則由于F+的計(jì)算非常復(fù)雜，實(shí)際上是不可行的。由引理2，將判定X→Y是否能由F根據(jù)Armstrong公理導(dǎo)出的問題，就轉(zhuǎn)化為求出XF+

，判定Y是否為XF+的子集的問題6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))求屬性集閉包的算法算法6.l求屬性集X（X

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

輸入：X，F(xiàn)輸出：XF+6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))步驟：（1）令X（0）=X，i=0（2）求B，這里B={A|(

V)(

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

W)}；（3）X（i+1）=B∪X（i）（4）判斷X（i+1）=X

（i）嗎?6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))（5）若相等或X（i）=U,則X（i）就是XF+,

算法終止。（6）若否，則i=i+l，返回第（2）步。對于算法6.l，令ai=|X（i）|，{ai

}形成一個步長大于1的嚴(yán)格遞增的序列，序列的上界是|U|，因此該算法最多|U|-|X|次循環(huán)就會終止。6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))DefineXF+=closureofX=setofattributesfunctionallydeterminedbyXBasis:XF+:=XInduction:IfYXF+,andY→AisagivenFD,thenaddAtoXF+EndwhenXF+cannotbechanged.yX+NewX+A6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))Example

U={A,B,C,D};F={A→B,BC→D};A+=AB.C+=C.(AC)+=ABCD.ACB6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))U={A,B,C,D};F={A→B,BC→D};(AC)+=ABCD.ACDB6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))[例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+

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

AB→C，B→D。于是X（1）=AB∪CD=ABCD。6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))(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。6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))Armstrong公理系統(tǒng)的有效性與完備性建立公理系統(tǒng)體系目的：從已知的

f

推導(dǎo)出未知的f明確：1.公理系統(tǒng)推導(dǎo)出來的f正確？2.F+中的每一個f都能推導(dǎo)出來？

f不能由F導(dǎo)出,f

∈

F+6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))Armstrong公理是有效的、完備的。有效性：由F出發(fā)，根據(jù)Armstrong公理推導(dǎo)出來的每一個函數(shù)依賴一定在F+中。完備性：F+中的每一個函數(shù)依賴，必定可以由F出發(fā)，根據(jù)Armstrong公理推導(dǎo)出來。6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))要證明完備性，就首先要解決如何判定一個函數(shù)依賴是否屬于由F根據(jù)Armstrong公理推導(dǎo)出來的函數(shù)依賴的集合。當(dāng)然，如果能求出這個集合，問題就解決了。但不幸的是，這是一個NP完全問題。比如從F＝{X→A1,…,X→An}出發(fā)，至少可以推導(dǎo)出2n個不同的函數(shù)依賴。6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))證明：

1.有效性可由定理6.l得證2.完備性 只需證明逆否命題:

若函數(shù)依賴X→Y不能由F從Armstrong公理導(dǎo)出，那么它必然不為F所蘊(yùn)含分三步證明：6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))(1)引理:若V→W成立，且V

XF+，則W

XF+

證因?yàn)閂

XF+，所以有X→V成立；因?yàn)閄→V，V→W，于是X→W成立所以W

XF+(2)/*若

f不能用Armstrong公理推導(dǎo)出來，

f∈F+/*若存在r，F(xiàn)+中的全部函數(shù)依賴在r上成立。

/*而不能用Armstrong公理推導(dǎo)出來的f,在r上不成立。構(gòu)造一張二維表r，它由下列兩個元組構(gòu)成，可以證明r必是R（U，F(xiàn)）的一個關(guān)系，即F+中的全部函數(shù)依賴在r上成立。6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))

XF+

U-XF+

11......100......0

11......111......1

若r不是R<U，F(xiàn)>的關(guān)系，則必由于F中有函數(shù)依賴V→W在r上不成立所致。由r的構(gòu)成可知，V必定是XF+的子集，而W不是XF+的子集，可是由第（1）步，W

XF+，矛盾。所以r必是R<U，F(xiàn)>的一個關(guān)系。6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))Armstrong公理的完備性及有效性說明:“蘊(yùn)含”==“導(dǎo)出”等價的概念

F+==由F出發(fā)借助Armstrong公理導(dǎo)出的函數(shù)依賴的集合6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))函數(shù)依賴集等價 定義6.14如果G+=F+，就說函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價。6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))函數(shù)依賴集等價的充要條件引理6.3F+=G+的充分必要條件是

F

G+，和G

F+證:必要性顯然，只證充分性。（1）若FG+，則XF+

XG++。（2）任取X→YF+則有Y

XF+

XG++。 所以X→Y(G+）+=G+。即F+

G+。（3）同理可證G+

F+，所以F+=G+。6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))最小依賴集定義6.15如果函數(shù)依賴集F滿足下列條件，則稱F為一個極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。(1)F中任一函數(shù)依賴的右部僅含有一個屬性。(2)F中不存在這樣的函數(shù)依賴X→A，使得F與

F-{X→A}等價。(3)F中不存在這樣的函數(shù)依賴X→A，X有真子集Z使得F-{X→A}∪{Z→A}與F等價。6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))[例2]對于6.l節(jié)中的關(guān)系模式S<U，F(xiàn)>，其中：

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}6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))F是最小覆蓋，而F’不是。因?yàn)椋篎’-{SNO→MN}與F’等價

F’-{(SNO，SDEPT)→SDEPT}也與F’等價

F’-{(SNO，SDEPT)→SDEPT}∪{SNO→SDEPT}也與F’等價6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))定理6.3每一個函數(shù)依賴集F均等價于一個極小函數(shù)依賴集Fm。此Fm稱為F的最小依賴集6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))證:構(gòu)造性證明，依據(jù)定義分三步對F進(jìn)行“極小化處理”，找出F的一個最小依賴集。(1)逐一檢查F中各函數(shù)依賴FDi：X→Y，若Y=A1A2…Ak，k>2，則用{X→Aj

|j=1，2，…，k}來取代X→Y。

引理6.1保證了F變換前后的等價性。6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))(2)逐一檢查F中各函數(shù)依賴FDi：X→A，令G=F-{X→A}，若AXG+，則從F中去掉此函數(shù)依賴。由于F與G=F-{X→A}等價的充要條件是AXG+

因此F變換前后是等價的。6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))(3)逐一取出F中各函數(shù)依賴FDi：X→A，設(shè)X=B1B2…Bm，逐一考查Bi

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

）F+，則以X-Bi

取代X。由于F與F-{X→A}∪{Z→A}等價的充要條件是AZF+，其中Z=X-Bi

因此F變換前后是等價的。6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù)) 由定義，最后剩下的F就一定是極小依賴集。因?yàn)閷的每一次“改造”都保證了改造前后的兩個函數(shù)依賴集等價，因此剩下的F與原來的F等價。證畢定理6.3的證明過程也是求F極小依賴集的過程6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))例6.3將下列函數(shù)依賴集F化為最小依賴集F=AB→CD→EGC→ABE→CBC→DCG→BDACD→BCE→AG6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))解:按最小依賴集的定義分別考慮三個條件(1)用分解規(guī)則將所有依賴變?yōu)橛疫叾际菃螌傩缘囊蕾?即:AB→CD→ED→GC→ABE→CBC→DCG→BCG→DACD→BCE→ACE→G6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))(2)去掉F中多余的依賴,其具體做法是:從第一個依賴開始,從F中去掉它(假設(shè)該依賴是X→Y);然后在剩下的依賴中求X+,看X+是否包含Y,若是,則去掉X→Y;若不包含Y,則不能去掉X→Y.這樣一次做下去,則可符合條件(2).6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))注:按不同的次序考慮可能得到不同的結(jié)果.為什么?6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))(3)去掉各依賴左邊多余屬性.其方法是一個一個地檢查F中左邊是非單屬性的依賴.例如XY→A,現(xiàn)在要判斷Y是否為多余的,只要在F中求出X+,若X+

包含A,則Y是多余屬性;否則Y不是多余屬性.依次判斷其他屬性即可消除各依賴左邊的多余屬性6.3數(shù)據(jù)依賴的公理系統(tǒng)(續(xù))

F1`=F2`=AB→CC→ABC→DCD→BD→ED→GBE→CCG→DCE→GCG→B

ACD→B

CE→AAB→CC→ABC→DD→ED→GBE→CCG→BCE→G6.4模式的分解分解的基本代數(shù)運(yùn)算投影自然連接分解的目標(biāo)無損連接分解保持函數(shù)依賴保持函數(shù)依賴且無損連接分解達(dá)到更高級范式6.4模式的分解把低一級的關(guān)系模式分解為若干個高一級的關(guān)系模式的方法并不是唯一的只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價，分解方法才有意義6.4模式的分解(續(xù))三種模式分解的等價定義⒈分解具有無損連接性⒉分解要保持函數(shù)依賴⒊分解既要保持函數(shù)依賴，又要具有無損連接性6.4模式的分解(續(xù))定義6.16關(guān)系模式R<U,F>的一個分解：ρ={R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>}U=U1∪U2∪…∪Un，且不存在Ui

Uj，F(xiàn)i

為F在Ui

上的投影定義6.17

函數(shù)依賴集合{X→Y|X→Y

F+∧XY

Ui}的一個覆蓋

Fi

叫作F在屬性Ui

上的投影6.4模式的分解(續(xù))例:SL（Sno，Sdept，Sloc）

F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}SL∈2NF存在插入異常、刪除異常、冗余度大和修改復(fù)雜等問題分解方法可以有多種6.4模式的分解(續(xù))SL──────────────────

Sno

Sdept

Sloc

──────────────────95001CSA95002ISB95003MAC95004ISB95005 PH B──────────────────6.4模式的分解(續(xù))1.SL分解為下面三個關(guān)系模式：

SN(Sno)

SD(Sdept)

SO(Sloc)6.4模式的分解(續(xù))分解后的關(guān)系為：SN

SDSOSno

9500195002950039500495005SdeptCSISMAPHSlocABC6.4模式的分解(續(xù))分解后的數(shù)據(jù)庫丟失了許多信息例如無法查詢95001學(xué)生所在系或所在宿舍。如果分解后的關(guān)系可以通過自然連接恢復(fù)為原來的關(guān)系，那么這種分解就沒有丟失信息6.4模式的分解(續(xù))2.SL分解為下面二個關(guān)系模式：

NL(Sno,Sloc)

DL(Sdept,Sloc)分解后的關(guān)系為：

NL────────────DL────────────

Sno

Sloc

Sdept

Sloc

────────────────────────95001A CSA95002B ISB95003C MAC95004B PHB95005B──────────────────────6.4模式的分解(續(xù))NLDL─────────────

Sno

Sloc

Sdept

─────────────95001ACS95002BIS95002BPH95003CMA95004BIS95004BPH95005BIS95005BPH6.4模式的分解(續(xù))

NLDL比原來的SL關(guān)系多了3個元組

無法知道95002、95004、95005

究竟是哪個系的學(xué)生

元組增加了，信息丟失了6.4模式的分解(續(xù))第三種分解方法3.將SL分解為下面二個關(guān)系模式：

ND(Sno,Sdept)

NL(Sno,Sloc)

分解后的關(guān)系為：

6.4模式的分解(續(xù))ND────────────NL──────────

Sno

Sdept

Sno

Sloc

──────────────────────95001CS95001A95002IS95002B95003MA95003C95004IS95004B95005PH95005B

───────────────────────6.4模式的分解(續(xù))

NDNL──────────────

Sno

Sdept

Sloc──────────────

95001CSA95002ISB95003MAC95004CSA95005PHB──────────────與SL關(guān)系一樣，因此沒有丟失信息6.4模式的分解(續(xù))具有無損連接性的模式分解關(guān)系模式R<U,F>的一個分解ρ={R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>}若R與R1、R2、…、Rn自然連接的結(jié)果相等，則稱關(guān)系模式R的這個分解ρ具有無損連接性（Losslessjoin）6.4模式的分解(續(xù))具有無損連接性的分解保證不丟失信息無損連接性不一定能解決插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問題6.4模式的分解(續(xù))

第三種分解方法具有無損連接性

問題:

這種分解方法沒有保持原關(guān)系中的函數(shù)依賴

SL中的函數(shù)依賴Sdept→Sloc

沒有投影到關(guān)系模式ND、NL上6.4模式的分解(續(xù))保持函數(shù)依賴的模式分解設(shè)關(guān)系模式R<U,F>被分解為若干個關(guān)系模式

R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>（其中U=U1∪U2∪…∪Un，且不存在Ui

Uj，F(xiàn)i為F在Ui上的投影），若F所邏輯蘊(yùn)含的函數(shù)依賴一定也由分解得到的某個關(guān)系模式中的函數(shù)依賴Fi所邏輯蘊(yùn)含，則稱關(guān)系模式R的這個分解是保持函數(shù)依賴的（Preservedependency）。6.4模式的分解(續(xù))第四種分解方法將SL分解為下面二個關(guān)系模式：

ND(Sno,Sdept)

DL(Sdept,Sloc)

這種分解方法就保持了函數(shù)依賴。6.4模式的分解(續(xù))如果一個分解具有無損連接性，則它能夠保證不丟失信息。如果一個分解保持了函數(shù)依賴，則它可以減輕或解決各種異常情況。分解具有無損連接性和分解保持函數(shù)依賴是兩個互相獨(dú)立的標(biāo)準(zhǔn)。具有無損連接性的分解不一定能夠保持函數(shù)依賴。同樣，保持函數(shù)依賴的分解也不一定具有無損連接性。6.4模式的分解(續(xù))第一種分解方法既不具有無損連接性，也未保持函數(shù)依賴，它不是原關(guān)系模式的一個等價分解第二種分解方法保持了函數(shù)依賴，但不具有無損連接性第三種分解方法具有無損連接性，但未保持函數(shù)依賴第四種分解方法既具有無損連接性，又保持了函數(shù)依賴6.4模式的分解(續(xù))分解算法算法6.2判別一個分解的無損連接性方法：(1)建立矩陣S,列j對應(yīng)屬性Aj,行i對應(yīng)Ri;(2)FORi=1TOkDOFORj=1TOnDOIFRi

包含屬性AjTHEN

S[i,j]:=aj;ELSE

S[i,j]:=bij;ENDFOR;ENDFOR;6.4模式的分解(續(xù))示例第1,2步U={A,B,C,D,E},F={ABC,CD,DE} ={(A,B,C),(C,D),(D,E)}ABCDEABCa1a2a3b14b15CDb21b22a3a4b25DEb31b32b33a4a56.4模式的分解(續(xù))(3)DOUNTILS無變化

FOR每個XYDOFORS中所有在X對應(yīng)的列上具有相同符號的行

i1,i2,…ikDO

按照下列規(guī)則修改Y所對應(yīng)列的符號：

a.FOR每個具有“a”類符號的Y對應(yīng)列DO

把該列i1,i2,…ik行的符號改為相同的a類符號；