數(shù)據(jù)庫數(shù)電課件第6章2database

AnIntroductiontoDatabaseSystem

上課了。。。請肅靜數(shù)據(jù)庫，，，，AnIntroductiontoDatabaseSystem6.3數(shù)據(jù)依賴的公理系統(tǒng)邏輯蘊含 定義6.11對于滿足一組函數(shù)依賴

F的關(guān)系模式R<U，F(xiàn)>，其任何一個關(guān)系r，若函數(shù)依賴X→Y都成立,則稱

F邏輯蘊含X→YAnIntroductiontoDatabaseSystem1.函數(shù)依賴閉包定義6.13設(shè)F為屬性集U上的一組函數(shù)依賴，X

U，

XF+={A|X→A能由F導(dǎo)出}，XF+稱為屬性集X關(guān)于函數(shù)依賴集F的閉包AnIntroductiontoDatabaseSystem求閉包的算法算法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）

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

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

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

}形成一個步長大于1的嚴格遞增的序列，序列的上界是|U|，因此該算法最多|U|-|X|次循環(huán)就會終止。AnIntroductiontoDatabaseSystem函數(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)計算X（1）:逐一的掃描F集合中各個函數(shù)依賴，找左部為A，B或AB的函數(shù)依賴。得到兩個：

AB→C，B→D。于是X（1）=AB∪CD=ABCD。AnIntroductiontoDatabaseSystem函數(shù)依賴閉包(2)因為X（0）≠X（1），所以再找出左部為ABCD子集的那些函數(shù)依賴，又得到AB→C，B→D，C→E，AC→B，于是X（2）=X（1）∪BCDE=ABCDE。(3)因為X（2）=U，算法終止所以（AB）F+=ABCDE。AnIntroductiontoDatabaseSystem2.最小依賴集

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

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

(2)F中不存在這樣的函數(shù)依賴X→A，使得F與 F-{X→A}等價。沒有多余的函數(shù)依賴

(3)F中不存在這樣的函數(shù)依賴X→A，X有真子集Z使得F-{X→A}∪{Z→A}與F等價。去掉左部多余的屬性AnIntroductiontoDatabaseSystem最小依賴集[例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}F是最小覆蓋，而F’不是。因為：F’-{SNO→MN}與F’等價

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

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

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

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

AnIntroductiontoDatabaseSystem極小化過程(2)逐一取出F中各函數(shù)依賴FDi：X→A，設(shè)X=B1B2…Bm，逐一考查Bi

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

）F+，則以X-Bi

取代X。

AnIntroductiontoDatabaseSystem極小化過程(3)逐一檢查F中各函數(shù)依賴FDi：X→A，令G=F-{X→A}，若AXG+，則從F中去掉此函數(shù)依賴。

AnIntroductiontoDatabaseSystem極小化過程例：設(shè)有關(guān)系模式R<U,F>，其中U={EFGH}F={E→G，G→E，F(xiàn)→EGH→EG，F(xiàn)H→E}求F的最小依賴集。將F中右側(cè)屬性單一化F1={E→G，G→E，F(xiàn)→E，F(xiàn)→G，H→E，H→G，F(xiàn)H→E}去掉左側(cè)多余的屬性，對于FH→E，去掉F，H+=GE，E∈H+，所以F可以去掉F2={E→G，G→E，F(xiàn)→E，F(xiàn)→G，H→E，H→G}AnIntroductiontoDatabaseSystem極小化過程F2={E→G，G→E，F(xiàn)→E，F(xiàn)→G，H→E，H→G}去掉多余的函數(shù)依賴E→G，G→E二個沒有E+和G+F→E，F(xiàn)+=GE，E∈GE，可去掉F→G，沒有F+，注意F→E已刪除了H→E，H+=GE，E∈GE，可去掉H→G，沒有H+，注意H→E已刪除了注：結(jié)果不唯一，F(xiàn)→E，F(xiàn)→G可去掉任何一個，H→E，H→G也可去掉任何一個。AnIntroductiontoDatabaseSystem極小化過程[例3]F={A→B，B→A，B→C，

A→C，C→A}Fm1、Fm2都是F的最小依賴集：

Fm1={A→B，B→C，C→A}

Fm2={A→B，B→A，A→C，C→A}F的最小依賴集Fm不一定是唯一的它與對各函數(shù)依賴FDi

及X→A中X各屬性的處置順序有關(guān)AnIntroductiontoDatabaseSystem極小化過程若改造后的F與原來的F相同，說明F本身就是一個最小依賴集AnIntroductiontoDatabaseSystem6.4模式分解有時候為了控制由于冗余帶來的問題以及插入和刪除等問題要求關(guān)系模式滿足一定的范型，可以通過模式分解來達到，這一過程稱之為規(guī)范化(Normalization)有時候考慮到查詢的效率，需要將滿足較高范型的關(guān)系模式進行合并，這一過程稱之為DenormalizationAnIntroductiontoDatabaseSystem

模式的分解把低一級的關(guān)系模式分解為若干個高一級的關(guān)系模式的方法并不是唯一的只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價，分解方法才有意義AnIntroductiontoDatabaseSystem關(guān)系模式分解的標準三種模式分解的等價定義⒈分解具有無損連接性⒉分解要保持函數(shù)依賴⒊分解既要保持函數(shù)依賴，又要具有無損連接性AnIntroductiontoDatabaseSystem模式的分解（續(xù)）例:SL（Sno，Sdept，Sloc）

F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}SL∈2NF存在插入異常、刪除異常、冗余度大和修改復(fù)雜等問題分解方法可以有多種AnIntroductiontoDatabaseSystem模式的分解（續(xù)）SL──────────────────Sno Sdept Sloc──────────────────95001CSA95002ISB95003MAC95004ISB95005 PH B──────────────────AnIntroductiontoDatabaseSystem模式的分解（續(xù)）1.SL分解為下面三個關(guān)系模式：

SN(Sno)SD(Sdept)SO(Sloc)AnIntroductiontoDatabaseSystem分解后的關(guān)系為：

SN──────SD──────SO──────SnoSdeptSloc

──────────────────95001CSA95002ISB95003MAC95004PH─────95005────────────AnIntroductiontoDatabaseSystem模式的分解（續(xù)）

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

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

NL────────────DL────────────SnoSlocSdeptSloc

────────────────────────95001A CSA95002B ISB95003C MAC95004B PHB95005B──────────────────────AnIntroductiontoDatabaseSystem模式的分解（續(xù)）NLDL─────────────SnoSlocSdept─────────────95001ACS95002BIS95002BPH95003CMA95004BIS95004BPH95005BIS95005BPHAnIntroductiontoDatabaseSystem模式的分解（續(xù)） NLDL比原來的SL關(guān)系多了3個元組

無法知道95002、95004、95005

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

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

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

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

AnIntroductiontoDatabaseSystem模式的分解（續(xù)）ND────────────NL──────────SnoSdeptSnoSloc

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

───────────────────────AnIntroductiontoDatabaseSystem模式的分解（續(xù)）NDNL──────────────SnoSdeptSloc──────────────

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

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

問題:

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

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

沒有投影到關(guān)系模式ND、NL上

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

將SL分解為下面二個關(guān)系模式：

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

這種分解方法就保持了函數(shù)依賴。AnIntroductiontoDatabaseSystem模式的分解（續(xù)）如果一個分解具有無損連接性，則它能夠保證不丟失信息。如果一個分解保持了函數(shù)依賴，則它可以減輕或解決各種異常情況。分解具有無損連接性和分解保持函數(shù)依賴是兩個互相獨立的標準。具有無損連接性的分解不一定能夠保持函數(shù)依賴。同樣，保持函數(shù)依賴的分解也不一定具有無損連接性。AnIntroductiontoDatabaseSystem模式的分解（續(xù)）第一種分解方法既不具有無損連接性，也未保持函數(shù)依賴，它不是原關(guān)系模式的一個等價分解第二種分解方法保持了函數(shù)依賴，但不具有無損連接性第三種分解方法具有無損連接性，但未持函數(shù)依賴第四種分解方法既具有無損連接性，又保持了函數(shù)依賴AnIntroductiontoDatabaseSystem分解算法算法6.2判別一個分解的無損連接性算法6.3（合成法）轉(zhuǎn)換為3NF的保持函數(shù)依賴的分解。算法6.4轉(zhuǎn)換為3NF既有無損連接性又保持函數(shù)依賴的分解AnIntroductiontoDatabaseSystem分解算法若要求分解保持函數(shù)依賴，那么模式分解一定能夠達到3NF，但不一定能夠達到BCNF。若要求分解既具有無損連接性，又保持函數(shù)依賴，則模式分解一定能夠達到3NF，但不一定能夠達到BCNF。AnIntroductiontoDatabaseSystem算法6.3（合成法）轉(zhuǎn)換為3NF的保持函數(shù)依賴的分解對R(U,F)中的函數(shù)依賴集F進行極小化找出不在F中出現(xiàn)的屬性，把這樣的屬性構(gòu)成一個關(guān)系模式，把這些屬性從U中去掉，剩余的屬性仍記為U若有X→A∈F，且XA=U，則ρ={R}否則對F按具有相同左部的原則分組，每一組函數(shù)依賴Fi’所涉及全部屬性形成一個屬性集Ui,若Ui

Uj(i≠J)就去掉UiAnIntroductiontoDatabaseSystem算法6.3例：設(shè)有關(guān)系模式R<U,F>，其中U={CTHSRG}，F(xiàn)={CS→G，C→T，TH→R，HR→C，HS→R}，將其保持依賴性分解為3NF。Fmin=F沒有不在Ｆ中出現(xiàn)的屬性沒有哪個依賴X→A∈F，且XA=U沒有相同的左部，所以每個依賴自成一組Ｒ1=CSG,R2=CT,R3=THR,R4=HRC,R5=HSRρ={CSG,CT,THR,HRC,HSR}AnIntroductiontoDatabaseSystem算法6.3例：設(shè)有關(guān)系模式R（ABCDE），R的依賴集F={A→D，E→D，D→B，BC→D，CD→A}，將R分解為3NFAnIntroductiontoDatabaseSystem算法6.3例：設(shè)有關(guān)系模式R（ABCDE），R的依賴集F={A→D，E→D，D→B，BC→D，CD→A}，將R分解為3NFFmin=F沒有不在Ｆ中出現(xiàn)的屬性沒有哪個依賴X→A∈F，且XA=U沒有相同的左部，所以每個依賴自成一組AD，DE，BD，BCD，ACD，因ADACDBDBCD，所以ρ={DE，BCD，ACD}AnIntroductiontoDatabaseSystem算法6.4

轉(zhuǎn)換為3NF既有無損連接性又保持函數(shù)依賴的分解。根據(jù)算法6.3求出保持依賴性分解ρ＝｛Ｒ1,Ｒ2……Ｒk｝設(shè)Ｘ是Ｒ的碼，若Ｘ某個Ｒi，則τ＝ρ，否則τ＝ρ

∪｛Ｘ｝τ就是所求的分解

AnIntroductiontoDatabaseSystem算法6.4（續(xù)）例：設(shè)有關(guān)系模式R（EGHIJ），R的函數(shù)依賴集為F={E→I，J→I，I→G，GH→I，IH→E}，求R的候選碼，將R分解為3NF，并具有無損連接性和依賴保持性。解：去掉在函數(shù)依賴集右側(cè)出現(xiàn)的，剩下JH（JH）+=EGHIJ，所以候選碼只有JH求出最小依賴集Fm=F沒有不在Ｆ中出現(xiàn)的屬性沒有哪個依賴X→A∈F，且XA=U沒有相同的左部，所以每個依賴自成一組ρ={EI,JI,IG,GHI,IHE}τ=ρ

∪｛JH｝τ={EI,JI,IG,GHI,IHE,JH}訂單號DDH姓名XM地址DZ書號SH書名SM單價DJ數(shù)量SL98010張三

沈陽102001020510201高數(shù)線代概率8.007.509.0012012012098011李四

大連220201020530502數(shù)據(jù)庫線代匯編8.507.506.0080804098204王五北京0530230502制圖匯編5.806.008090例：設(shè)某新華書店，訂書單匯總表如下：規(guī)范到3NF，要求分解即具有無損性連接，又要保持函數(shù)依賴。解：R（DDH，XM，DZ，SH，SM，DJ，SL）（1）求最小函數(shù)依賴集F={DDH→XM，DDH→DZ，SH→SM，SH→DJ，（DDH，SH）→SL}（2）找R中不在F中出現(xiàn)的屬性——沒有；（3）找每一個函數(shù)依賴中的屬性集是否與R中屬性集相同即不存在若X→A，則X∪A=U（4）按左部相同的原則分組

R1（DDH，XM，DZ）

R2（SH，SM，DJ）

R3（DDH，SH，SL）達到了把R分解成3NF，且保持函數(shù)依賴。繼續(xù)做無損性連接分解。由于關(guān)系模式R中的關(guān)鍵字是（DDH，SH）而R3中的屬性集包含此關(guān)鍵字所以R1，R2，R3即為所求。即：關(guān)系模式R模式分解為R1，R2，R3，規(guī)范化到了3NF，并且保持了函數(shù)依賴和無損性連接。AnIntroductiontoDatabaseSystem學(xué)校興趣小組表如下規(guī)范到3NF，要求分解即具有無損性連接，又要保持函數(shù)依賴。學(xué)號姓名興趣小組時間地點05001趙一計算機周一563-10105001趙一舞蹈周二783-10205002錢二計算機周一563-101AnIntroductiontoDatabaseSystem綜合例：設(shè)有如下所示的關(guān)系Ｒ它為第幾范式，為什么？是否存在刪除異常，如存在，什么情況下發(fā)生將它分解為高一級的范式，分解后的關(guān)系如何解決分解前的刪除異常。AnIntroductiontoDatabaseSystem綜合它為2NF，因為R的候選碼為課程名，而課程名→教師名，教師名→課程名不成立，教師名→教師地址，所以課程名T

教師地址，存在非主屬性對碼的傳遞函數(shù)依賴，所以它不是3NF，又因為不存在非主屬性對碼的部分依賴，所以它是2NF。存在刪除異常，當(dāng)刪除某門課程時會刪除教師的信息將它分解為R1（課程名，教師名）R2（教師名，教師地址），當(dāng)刪除課程時，僅對R1操作AnIntroductiontoDatabaseSystem例：設(shè)有關(guān)系模式R（運動員編號、比賽項目、成績、比賽類別、比賽主管）存儲運動員比賽成績及比賽類別、主管等信息。如果規(guī)定：每個運動員每參加一個比賽項目，只有一個成績；每個比賽項目只屬于一個比賽類別；每個比賽類別只有一個比賽主管。試回答下列問題：根據(jù)上述規(guī)定，寫出關(guān)系模式R的基本函數(shù)依賴找出R的候選碼找出函數(shù)依賴來說明R不是2NF的理由，并把R分解成2NF模式集。進而分解成3NF模式集。AnIntroductiontoDatabaseSystem基本的FD有三個：（運動員編號，比賽項目）→成績比賽項目→比賽類別比賽類別→比賽主管R的關(guān)鍵碼為：（運動員編號，比賽項目）R中有二個這樣的FD

（運動員編號，比賽項目）→（比賽類別，比賽主管）比賽項目→（比賽類別，比賽主管）可見前一個是局部依賴，所以R不是2NF。AnIntroductiontoDatabaseSystemR分解為R1（比賽項目，比賽類別，比賽主管）

R2（運動員編號，比賽項目，成績）

R1和R2都是2NFR2是3NF，在R1中比賽項目→比賽類別，比賽類別→比賽主管，因此比賽項目