數(shù)據(jù)庫(kù)原理第15講

數(shù)據(jù)庫(kù)系統(tǒng)概論AnIntroductiontoDatabaseSystem第六章關(guān)系數(shù)據(jù)理論.6.2.5多值依賴與第四范式（4NF）例:學(xué)校中某一門課程由多個(gè)教師講授，他們使用相同的一套參考書。 關(guān)系模式Teaching(C,T,B)

課程C、教師T和參考書B.………課程C教員T參考書B

物理

數(shù)學(xué)

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

李勇張平

張平周峰

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

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

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

表6.1.普通物理學(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課程C用二維表表示Teaching

.多值依賴與第四范式（續(xù)）Teaching∈BCNF:Teach具有唯一候選碼(C，T，B)，即全碼Teaching模式中存在的問(wèn)題

(1)數(shù)據(jù)冗余度大：有多少名任課教師，參考書就要存儲(chǔ)多少次

.多值依賴與第四范式（續(xù)）

(2)插入操作復(fù)雜：當(dāng)某一課程增加一名任課教師時(shí)，該課程有多少本參照書，就必須插入多少個(gè)元組例如物理課增加一名教師劉關(guān)，需要插入兩個(gè)元組：

（物理，劉關(guān)，普通物理學(xué)）（物理，劉關(guān)，光學(xué)原理）.多值依賴與第四范式（續(xù)）(3)刪除操作復(fù)雜：某一門課要去掉一本參考書，該課程有多少名教師，就必須刪除多少個(gè)元組(4)修改操作復(fù)雜：某一門課要修改一本參考書，該課程有多少名教師，就必須修改多少個(gè)元組產(chǎn)生原因 存在多值依賴.一、多值依賴定義6.10

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

對(duì)于C的每一個(gè)值，T有一組值與之對(duì)應(yīng)，而不論B取何值.多值依賴（續(xù)）平凡多值依賴和非平凡的多值依賴

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

X→→Y為平凡的多值依賴 否則稱X→→Y為非平凡的多值依賴.二、第四范式（4NF）定義6.10關(guān)系模式R<U，F(xiàn)>∈1NF，如果對(duì)于R的每個(gè)非平凡多值依賴X→→Y（YX），X都含有候選碼，則R∈4NF。（X→Y）如果R∈4NF，則R∈BCNF

不允許有非平凡且非函數(shù)依賴的多值依賴

允許的是函數(shù)依賴（是非平凡多值依賴）.第四范式（續(xù)）例：Teach(C,T,B)∈4NF

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

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

C→→T，C→→B是平凡多值依賴

.6.2規(guī)范化6.2.1第一范式（1NF）6.2.2第二范式（2NF）6.2.3第三范式（3NF）6.2.4BC范式（BCNF）6.2.5多值依賴與第四范式（4NF）6.2.6規(guī)范化.6.2.6規(guī)范化關(guān)系數(shù)據(jù)庫(kù)的規(guī)范化理論是數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)的工具。一個(gè)關(guān)系只要其分量都是不可分的數(shù)據(jù)項(xiàng)，它就是規(guī)范化的關(guān)系，但這只是最基本的規(guī)范化。規(guī)范化程度可以有多個(gè)不同的級(jí)別.規(guī)范化（續(xù)）規(guī)范化程度過(guò)低的關(guān)系不一定能夠很好地描述現(xiàn)實(shí)世界，可能會(huì)存在插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問(wèn)題一個(gè)低一級(jí)范式的關(guān)系模式，通過(guò)模式分解可以轉(zhuǎn)換為若干個(gè)高一級(jí)范式的關(guān)系模式集合，這種過(guò)程就叫關(guān)系模式的規(guī)范化.規(guī)范化（續(xù)）關(guān)系模式規(guī)范化的基本步驟

1NF ↓消除非主屬性對(duì)碼的部分函數(shù)依賴消除決定屬性2NF集非碼的非平↓消除非主屬性對(duì)碼的傳遞函數(shù)依賴凡函數(shù)依賴3NF ↓消除主屬性對(duì)碼的部分和傳遞函數(shù)依 賴

BCNF ↓消除非平凡且非函數(shù)依賴的多值依賴

4NF.規(guī)范化數(shù)據(jù)庫(kù)中數(shù)據(jù)規(guī)范化的優(yōu)點(diǎn)是減少了數(shù)據(jù)冗余，節(jié)約了存儲(chǔ)空間，相應(yīng)邏輯和物理的I/O次數(shù)減少，同時(shí)加快了增、刪、改的速度。但是一個(gè)完全規(guī)范化的設(shè)計(jì)并不總能生成最優(yōu)的性能，因?yàn)閷?duì)數(shù)據(jù)庫(kù)查詢通常需要更多的連接操作，從而影響到查詢的速度。.反規(guī)范化是否規(guī)范化的程度越高越好呢？在表格中有意識(shí)的引入一定的數(shù)據(jù)冗余以改進(jìn)性能被稱為反規(guī)范化。反規(guī)范化是查詢效率與數(shù)據(jù)冗余的折中。.6.3數(shù)據(jù)依賴的公理系統(tǒng)邏輯蘊(yùn)含 定義6.11對(duì)于滿足一組函數(shù)依賴F的關(guān)系模式R<U，F(xiàn)>，其任何一個(gè)關(guān)系r，若函數(shù)依賴X→Y都成立,則稱

F邏輯蘊(yùn)含X→Y.Armstrong公理系統(tǒng)一套推理規(guī)則，是模式分解算法的理論基礎(chǔ)用途求給定關(guān)系模式的碼從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴.1.Armstrong公理系統(tǒng)

關(guān)系模式R<U，F(xiàn)>來(lái)說(shuō)有以下的推理規(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)含。

注意：由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴，自反律的使用并不依賴于F.定理6.lArmstrong推理規(guī)則是正確的（l）自反律:若Y

X

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

X

U

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

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

X，有t[y]=s[y]，所以X→Y成立.自反律得證.定理6.l(2)增廣律:若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中任意的兩個(gè)元組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.l(3)傳遞律：若X→Y及Y→Z為F所蘊(yùn)含，則

X→Z為F所蘊(yùn)含。證：設(shè)X→Y及Y→Z為F所蘊(yùn)含。對(duì)R<U，F(xiàn)>

的任一關(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)含.傳遞律得證。.2.導(dǎo)出規(guī)則1.根據(jù)A1，A2，A3這三條推理規(guī)則可以得到下面三條推理規(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）.導(dǎo)出規(guī)則2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理6.1

引理6.lX→A1A2…Ak成立的充分必要條件是X→Ai成立（i=l，2，…，k）。.函數(shù)依賴與屬性關(guān)系屬性之間有三種關(guān)系，但并不是每一種關(guān)系中都存在函數(shù)依賴。設(shè)有屬性集X、Y及關(guān)系模式R：如果X和Y之間是1:1的關(guān)系，則存在函數(shù)依賴：X→Y和Y→X。如果X和Y之間是m:1的關(guān)系，則存在函數(shù)依賴：X→Y。如果X和Y之間是m:n的關(guān)系，則X和Y之間不存在函數(shù)依賴。.3.函數(shù)依賴閉包定義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的閉包.F的閉包F={XY,YZ},F+計(jì)算是NP完全問(wèn)題，XA1A2...An

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}.求閉包的算法算法6.l求屬性集X（X

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

輸入：X，F(xiàn)輸出：XF+步驟：（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）

.算法6.l（4）判斷X（i+1）=X

（i）嗎?（5）若相等或X（i）=U,則X（i）就是XF+,

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

}形成一個(gè)步長(zhǎng)大于1的嚴(yán)格遞增的序列，序列的上界是|U|，因此該算法最多|U|-|X|次循環(huán)就會(huì)終止。.DefineXF+=closureofX=setofattributesfunctionallydeterminedbyXBasis:XF+:=XInduction:IfYXF+,andYAisagivenFD,thenaddAtoXF+EndwhenXF+cannotbechanged.AlgorithmyX+NewX+A.

U={A,B,C,D};F={AB,BCD};A+=AB.C+=C.(AC)+=ABCD.ExampleACB.

ExampleACDBU={A,B,C,D};AB,BCD.(AC)+=ABCD..函數(shù)依賴閉包[例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。.函數(shù)依賴閉包(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。.4.Armstrong公理系統(tǒng)的有效性與完備性建立公理系統(tǒng)體系目的：從已知的

f

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

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

FF+f.4.Armstrong公理系統(tǒng)的有效性與完備性有效性：由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來(lái)的每一個(gè)函數(shù)依賴一定在F+中

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

/*Armstrong公理夠用，完全完備性：所有不能用Armstrong公理推導(dǎo)出來(lái)f,都不為真

若

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

f∈F+.有效性與完備性的證明證明： 1.有效性可由定理6.l得證2.完備性 只需證明逆否命題:

若函數(shù)依賴X→Y不能由F從Armstrong公理導(dǎo)出，那么它必然不為F所蘊(yùn)含分三步證明：.6.函數(shù)依賴集等價(jià)

定義6.14如果G+=F+，就說(shuō)函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價(jià)。.6.最小依賴集

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

(1)F中任一函數(shù)依賴的右部?jī)H含有一個(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à)。.最小依賴集[例2]對(duì)于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}F是最小覆蓋，而F’不是。因?yàn)椋篎’-{SNO→MN}與F’等價(jià)

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

F’-{(SNO，SDEPT)→SDEPT}∪{SNO→SDEPT}也與F’等價(jià).7.極小化過(guò)程定理6.3每一個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)極小函數(shù)依賴集Fm。此Fm稱為F的最小依賴集證:構(gòu)造性證明，依據(jù)定義分三步對(duì)F進(jìn)行“極小化處理”，找出F的一個(gè)最小依賴集。(1)逐一檢查F中各函數(shù)依賴FDi：X→Y，若Y=A1A2

…Ak，k>2，則用{X→Aj

|j=1，2，…，k}來(lái)取代X→Y。

引理6.1保證了F變換前后的等價(jià)性。.極小化過(guò)程(2)逐一檢查F中各函數(shù)依賴FDi：X→A，令G=F-{X→A}，若AX