數(shù)據(jù)庫 規(guī)范覆蓋的計算、多值依賴

1、(1) F中每個中每個FD的的右部右部只含一個屬性。只含一個屬性。函數(shù)依賴集的函數(shù)依賴集的最小覆蓋最小覆蓋定義定義 : 設(shè)設(shè)F 是是R(U)上的上的FD集，集， 如果如果F滿足以下滿足以下三個條件三個條件：(2) F中無中無多余多余FD。 即不存在即不存在XA, 滿足滿足F與與FXA等價。等價。(3) F中每個中每個FD的的左部左部都不含都不含多余屬性多余屬性。即不存在即不存在XA，X有真子集有真子集Z，滿足：滿足：F與與(FXA)ZA等價。等價。則稱則稱F為為最小依賴集最小依賴集或或最小覆蓋最小覆蓋。則對應(yīng)的則對應(yīng)的規(guī)范覆蓋規(guī)范覆蓋為：為： Fc= 。例：例：設(shè)設(shè)最小覆蓋最小覆蓋為：為：Fm

2、=CB, BA, CD, AE, BD,將將最小覆蓋最小覆蓋中左部相同的中左部相同的FD合并合并成一個后得到的成一個后得到的FD集集稱為稱為規(guī)范覆蓋規(guī)范覆蓋。CBD, BAD, AE函數(shù)依賴集的函數(shù)依賴集的最小覆蓋最小覆蓋(1) 用用分解規(guī)則分解規(guī)則將將F中的每個中的每個FD右部右部分解為分解為單屬性單屬性。如何計算如何計算FD集集F的的最小覆蓋最小覆蓋？分三步：分三步：F (F - XY )X Ai | i=1,2,k 。對每個對每個XY F, 若若Y=A1A2Ak (k2), 則置：則置：(2) 刪除刪除F中中多余的多余的FD。對每個對每個XA F, 令令G=F - XA, 若若A XG,

3、 則置則置F G。因：由因：由A XG可得可得XA， 故故F中的中的XA多余多余。(3) 刪除刪除F中每個中每個FD左部的左部的多余屬性多余屬性。對每個對每個XA F, 設(shè)設(shè)X=B1B2Bm (m2),逐個逐個考查考查Bi (i=1.m):若若A (X- Bi)F,因：由因：由A (X-Bi)F可得可得(X-Bi)A，故故XA中中Bi是是多余屬性多余屬性。則置則置F (F - XA )(X- Bi)A。F= ACA, CB, BA, CD, CA, ACD, CBB, CBE 例例: 求求F= ACA, CB, BA, CD, CA, ACD, CBBE 的最小覆蓋的最小覆蓋(1) 用用分解規(guī)

4、則分解規(guī)則將將F中的每個中的每個FD右部右部分解為分解為單屬性單屬性。(2) 刪除刪除F中中多余的多余的FD。G= CB, BA, CD, CA, ACD, CBB, CBE (AC)G+= A,C,， A (AC)G ， 置置F G 。函數(shù)依賴集的函數(shù)依賴集的最小覆蓋最小覆蓋函數(shù)依賴集的函數(shù)依賴集的最小覆蓋最小覆蓋F= CB, BA, CD, CA, ACD, CBB, CBE G= BA, CD, CA, ACD, CBB, CBE CG+= ，F(xiàn)不變不變 。, DC, AB CG ，例例: 求求F= ACA, CB, BA, CD, CA, ACD, CBBE 的最小覆蓋的最小覆蓋(1)

5、 用用分解規(guī)則分解規(guī)則將將F中的每個中的每個FD右部右部分解為分解為單屬性單屬性。(2) 刪除刪除F中中多余的多余的FD。函數(shù)依賴集的函數(shù)依賴集的最小覆蓋最小覆蓋F= CB, BA, CD, CA, ACD, CBB, CBE 例例: 求求F= ACA, CB, BA, CD, CA, ACD, CBBE 的最小覆蓋的最小覆蓋BG+= B ，F(xiàn)不變不變 。A BG ，G= CB, CD, CA, ACD, CBB, CBE (1) 用用分解規(guī)則分解規(guī)則將將F中的每個中的每個FD右部右部分解為分解為單屬性單屬性。(2) 刪除刪除F中中多余的多余的FD。函數(shù)依賴集的函數(shù)依賴集的最小覆蓋最小覆蓋例例

6、: 求求F= ACA, CB, BA, CD, CA, ACD, CBBE 的最小覆蓋的最小覆蓋F= CB, BA, CD, CA, ACD, CBB, CBE G= CB, BA, CA, ACD, CBB, CBE CG+= ，置置F G 。, BC, AD CG ，, D, E(1) 用用分解規(guī)則分解規(guī)則將將F中的每個中的每個FD右部右部分解為分解為單屬性單屬性。(2) 刪除刪除F中中多余的多余的FD。函數(shù)依賴集的函數(shù)依賴集的最小覆蓋最小覆蓋例例: 求求F= ACA, CB, BA, CD, CA, ACD, CBBE 的最小覆蓋的最小覆蓋F= CB, BA, CA, ACD, CBB,

7、 CBE G= CB, BA, ACD, CBB, CBE CG+= ，置置F G 。, BC, AA CG ，, D, E(1) 用用分解規(guī)則分解規(guī)則將將F中的每個中的每個FD右部右部分解為分解為單屬性單屬性。(2) 刪除刪除F中中多余的多余的FD。函數(shù)依賴集的函數(shù)依賴集的最小覆蓋最小覆蓋例例: 求求F= ACA, CB, BA, CD, CA, ACD, CBBE 的最小覆蓋的最小覆蓋A, CF= CB, BA, ACD, CBB, CBE G= CB, BA, CBB, CBE (AC)G+= ，F(xiàn)不變不變 。, B, ED (AC)G+ ，(1) 用用分解規(guī)則分解規(guī)則將將F中的每個中的

8、每個FD右部右部分解為分解為單屬性單屬性。(2) 刪除刪除F中中多余的多余的FD。函數(shù)依賴集的函數(shù)依賴集的最小覆蓋最小覆蓋例例: 求求F= ACA, CB, BA, CD, CA, ACD, CBBE 的最小覆蓋的最小覆蓋(CB)G+= ，C, B,F= CB, BA, ACD, CBB, CBE G= CB, BA, ACD, CBE 置置F G 。B (CB)G+，(1) 用用分解規(guī)則分解規(guī)則將將F中的每個中的每個FD右部右部分解為分解為單屬性單屬性。(2) 刪除刪除F中中多余的多余的FD。函數(shù)依賴集的函數(shù)依賴集的最小覆蓋最小覆蓋例例: 求求F= ACA, CB, BA, CD, CA,

9、ACD, CBBE 的最小覆蓋的最小覆蓋(CB)G+= ，C, BF= CB, BA, ACD, CBE G= CB, BA, ACD F不變不變 。, A, DE (CB)G+，(1) 用用分解規(guī)則分解規(guī)則將將F中的每個中的每個FD右部右部分解為分解為單屬性單屬性。(2) 刪除刪除F中中多余的多余的FD。函數(shù)依賴集的函數(shù)依賴集的最小覆蓋最小覆蓋例例: 求求F= ACA, CB, BA, CD, CA, ACD, CBBE 的最小覆蓋的最小覆蓋F= CB, BA, ACD, CBE (3) 刪除刪除F中每個中每個FD左部的左部的多余屬性多余屬性。F= CB, BA, ACD, CBE CF+=

10、 ，CA是是多余多余屬性，刪去。屬性，刪去。, B, AD CF+，, D, E CD,(1) 用用分解規(guī)則分解規(guī)則將將F中的每個中的每個FD右部右部分解為分解為單屬性單屬性。(2) 刪除刪除F中中多余的多余的FD。函數(shù)依賴集的函數(shù)依賴集的最小覆蓋最小覆蓋例例: 求求F= ACA, CB, BA, CD, CA, ACD, CBBE 的最小覆蓋的最小覆蓋F= CB, BA, ACD, CBE F= CB, BA, ACD, CBE (1) 用用分解規(guī)則分解規(guī)則將將F中的每個中的每個FD右部右部分解為分解為單屬性單屬性。(2) 刪除刪除F中中多余的多余的FD。 CD,BF+= ，BC不是不是多余

11、多余屬性，保留。屬性，保留。, AE BF+，(3) 刪除刪除F中每個中每個FD左部的左部的多余屬性多余屬性。函數(shù)依賴集的函數(shù)依賴集的最小覆蓋最小覆蓋例例: 求求F= ACA, CB, BA, CD, CA, ACD, CBBE 的最小覆蓋的最小覆蓋F= CB, BA, ACD, CBE F= CB, BA, ACD, CBE (1) 用用分解規(guī)則分解規(guī)則將將F中的每個中的每個FD右部右部分解為分解為單屬性單屬性。(2) 刪除刪除F中中多余的多余的FD。 CD,(3) 刪除刪除F中每個中每個FD左部的左部的多余屬性多余屬性。CF+= ，CB是是多余多余屬性，刪去。屬性，刪去。, B, AE C

12、F+，, D, ECEF的的規(guī)范覆蓋規(guī)范覆蓋為：為：Fc= 最后得到最后得到F的的最小覆蓋最小覆蓋為：為：Fm= CB, BA, CD, CE , BACBDE多值依賴多值依賴 在在函數(shù)依賴函數(shù)依賴范疇內(nèi)，范疇內(nèi)，BCNF已經(jīng)非常完美已經(jīng)非常完美。但是屬于但是屬于BCNF的關(guān)系模式仍可能存在問題。的關(guān)系模式仍可能存在問題。例例如：如： 假設(shè)假設(shè)多個教師上同一門課程，使用同一套參考書：多個教師上同一門課程，使用同一套參考書：注意：注意： TC不成立，因為一個教師可以上多門課。不成立，因為一個教師可以上多門課。 BC不成立，因為參考書可以跨課程交叉使用。不成立，因為參考書可以跨課程交叉使用。數(shù)學(xué)分

13、析數(shù)學(xué)分析高等代數(shù)高等代數(shù)微分方程微分方程數(shù)學(xué)數(shù)學(xué)鄧軍鄧軍陳斯陳斯物理物理李平李平王強王強鄧軍鄧軍普通物理普通物理微分方程微分方程用關(guān)系模式用關(guān)系模式Teach( C, T, B ) 表示。表示。 課程課程 教師教師 參考書參考書F = ， 候選碼為候選碼為CTB, 即全碼，所以即全碼，所以TeachBCNF否則：否則：候選碼是候選碼是TBTeach2NF TBC是是部分依賴部分依賴Teach關(guān)系存在以下關(guān)系存在以下4個問題：個問題：Teach( C, T, B ) 存在的問題存在的問題數(shù)據(jù)冗余大數(shù)據(jù)冗余大：有多少教師上同一門：有多少教師上同一門課，參考書就重復(fù)多少次課，參考書就重復(fù)多少次;(

14、2)更新異常更新異常：改某一門課的參考：改某一門課的參考書需要修改該課的所有記錄書需要修改該課的所有記錄;(3)插入異常插入異常: : 某門課增加一個教師，某門課增加一個教師，該課有多少參考書就需要插入多少該課有多少參考書就需要插入多少個元組個元組; (4)刪除異常刪除異常: 刪除某門課的一本參考刪除某門課的一本參考書，該課程有多少教師就要刪除多書，該課程有多少教師就要刪除多少元組。少元組。原因：原因： 對于每一門課，對于每一門課，Teach表中都表中都存儲了存儲了T和和B的笛卡爾積的笛卡爾積, 即下列條即下列條件對每門課件對每門課x都成立：都成立：TeachCTB數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)

15、數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)物理物理物理物理物理物理物理物理物理物理物理物理鄧軍鄧軍鄧軍鄧軍鄧軍鄧軍陳斯陳斯陳斯陳斯陳斯陳斯李平李平李平李平王強王強王強王強鄧軍鄧軍鄧軍鄧軍數(shù)學(xué)分析數(shù)學(xué)分析高等代數(shù)高等代數(shù)微分方程微分方程數(shù)學(xué)分析數(shù)學(xué)分析高等代數(shù)高等代數(shù)微分方程微分方程普通物理普通物理微分方程微分方程普通物理普通物理微分方程微分方程普通物理普通物理微分方程微分方程P PT, B( s( sC=x(Teach) ) = P PT ( s( sC=x(Teach) )P PB( s( sC=x(Teach) )由此引出由此引出多值依賴多值依賴的定義：的定義：R(U)UXY ZrXYZ設(shè)設(shè)R(U)是是U上的關(guān)

16、系模式，上的關(guān)系模式，定義定義( (多值依賴多值依賴) )：X,Y,Z U, 且且Z= =U-X-Y, ,若對若對R(U)的的任意關(guān)系任意關(guān)系r， 都有：都有：以及以及r在在X屬性組上的任意值屬性組上的任意值x, ,成立，成立，P PY, Z( s( sX=x(r) ) = P PY ( s( sX=x(r) )P PZ( s( sX=x(r) )xx說明：說明：則稱則稱X多值確定多值確定Y或或Y多值依賴于多值依賴于X，記作記作X Y。條件必須對條件必須對R(U)的的所有可能所有可能關(guān)系關(guān)系在在X屬性組上的屬性組上的所有可所有可能值能值都成立都成立, ,只要在只要在某個可某個可能值能值上上條件

17、條件不成立，則不成立，則:X Y不成立。不成立。R(U)UXY ZrXYZ設(shè)設(shè)R(U)是是U上的關(guān)系模式，上的關(guān)系模式，多值依賴多值依賴的另一個定義：的另一個定義：X,Y,Z U, 且且Z= =U-X-Y, ,若若R的的任意關(guān)系任意關(guān)系r滿足滿足: :那么那么(x,y2,z1)和和(x,y1,z2)也是也是r的元組，的元組，只要只要(x,y1,z1)和和(x,y2,z2)是是r的元組的元組, ,說明：說明：則稱則稱多值依賴多值依賴X Y在在R(U)上成立上成立。兩種定義是等價的：兩種定義是等價的：x y1 z1x y2 z2x y2 z1x y1 z2y1 z1y2 z2y2 z1y1 z2y

18、1y2z1z2=多值依賴的性質(zhì)多值依賴的性質(zhì)(1)對稱性對稱性： 若若X Y，則則X U-X-Y (即即Z)證明證明: : P PY, Z( s( sX=x(r) ) = P PY ( s( sX=x(r) )P PZ( s( sX=x(r) )成立，成立，必有必有P PZ, Y( s( sX=x(r) ) = P PZ ( s( sX=x(r) )P PY( s( sX=x(r) )成立。成立。(2)傳遞性傳遞性： 若若X Y，Y Z , 則則X Z -Y 證明非常復(fù)雜，大大超出了本課程的范圍。證明非常復(fù)雜，大大超出了本課程的范圍。(3)復(fù)制性復(fù)制性： 若若X Y, 則則X Y。rXYZ x

19、xyyz1zk X Y:若若X上的上的分量相等分量相等，則，則Y上上的分量相的分量相等。等。P PY, Z(. (.)P PY (. (.)P PZ(. (.)y z1y zkyz1zk=證明證明：所以所以X Y多值依賴的性質(zhì)多值依賴的性質(zhì)(1)對稱性對稱性： 若若X Y，則則X U-X-Y (即即Z)證明證明: : P PY, Z( s( sX=x(r) ) = P PY ( s( sX=x(r) )P PZ( s( sX=x(r) )成立，成立，必有必有P PZ, Y( s( sX=x(r) ) = P PZ ( s( sX=x(r) )P PY( s( sX=x(r) )成立。成立。(2

20、)傳遞性傳遞性： 若若X Y，Y Z , 則則X Z -Y 證明非常復(fù)雜，大大超出了本課程的范圍。證明非常復(fù)雜，大大超出了本課程的范圍。(3)復(fù)制性復(fù)制性： 若若X Y, 則則X Y。(4)并規(guī)則并規(guī)則： 若若XY, X Z, 則則X YZ。(5)交規(guī)則交規(guī)則：若：若XY, X Z, 則則X YZ。(6)差規(guī)則差規(guī)則：若：若XY, XZ, 則則XY-Z, XZ-Y。(7)平凡多值依賴平凡多值依賴：對：對U上的多值依賴上的多值依賴XY, 若若Y X, 或或XY=U，則稱則稱XY為為平凡多值依賴平凡多值依賴。這是因為：。這是因為：Y XXYXY(3)XX(3)XXXU-X(1)XY-XXY=UXXYXY(4)XYXYY-XTeach(C, T, B )存在問題的原因：存在問題的原因： 存在非平凡多值依賴存在非平凡多值依賴CT, 且且C不含候選碼不含候選碼CTB 。解決辦法：解決辦法： 分解分解關(guān)系模式關(guān)系模式, 消