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

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

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

3、令令G=F - XA, 若若A XG , 則置 則置F G。 因：由因：由A XG 可得 可得XA， 故故F中的中的XA多余多余。 (3) 刪除刪除F中每個(gè)中每個(gè)FD左部的左部的多余屬性多余屬性。 對(duì)每個(gè)對(duì)每個(gè)XA F, 設(shè)設(shè)X=B1B2Bm (m2),逐個(gè)逐個(gè)考查考查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,

4、CA, ACD, CBBE 的的最小覆蓋最小覆蓋 (1) 用用分解規(guī)則分解規(guī)則將將F中的每個(gè)中的每個(gè)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=

5、ACA, CB, BA, CD, CA, ACD, CBBE 的的最小覆蓋最小覆蓋 (1) 用用分解規(guī)則分解規(guī)則將將F中的每個(gè)中的每個(gè)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中的每個(gè)中的每個(gè)FD右部右部分解為

6、分解為單屬性單屬性。 (2) 刪除刪除F中中多余的多余的FD。 函數(shù)依賴集的函數(shù)依賴集的最小覆蓋最小覆蓋 例例: 求求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中的每個(gè)中的每個(gè)FD右部右部分解為分解為單屬性單屬性。 (2) 刪除刪除F中中多余的多余的FD。 函數(shù)依賴集的函數(shù)依賴集的最小覆蓋最小覆蓋 例例: 求求F= ACA

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

8、B, BA, CBB, CBE (AC)G+= ，F(xiàn)不變不變 。, B, ED (AC)G+ ， (1) 用用分解規(guī)則分解規(guī)則將將F中的每個(gè)中的每個(gè)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中的每個(gè)中的每個(gè)FD右部右部分解為分解

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

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

11、A, ACD, CBE (1) 用用分解規(guī)則分解規(guī)則將將F中的每個(gè)中的每個(gè)FD右部右部分解為分解為單屬性單屬性。 (2) 刪除刪除F中中多余的多余的FD。 CD, BF+= ，BC不是不是多余多余屬性，保留。屬性，保留。, AE BF+， (3) 刪除刪除F中每個(gè)中每個(gè)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中的每個(gè)中的每個(gè)FD右部右部分解為分

12、解為單屬性單屬性。 (2) 刪除刪除F中中多余的多余的FD。 CD, (3) 刪除刪除F中每個(gè)中每個(gè)FD左部的左部的多余屬性多余屬性。 CF+= ，CB是是多余多余屬性，刪去。屬性，刪去。, B, AE CF+，, D, E CE F的的規(guī)范覆蓋規(guī)范覆蓋為：為：Fc= 最后得到最后得到F的的最小覆蓋最小覆蓋為：為：Fm= CB, BA, CD, CE , BACBDE 多值依賴多值依賴 在在函數(shù)依賴函數(shù)依賴范疇內(nèi)，范疇內(nèi)，BCNF已經(jīng)非常完美已經(jīng)非常完美。但是屬于但是屬于 BCNF的關(guān)系模式仍可能存在問(wèn)題。的關(guān)系模式仍可能存在問(wèn)題。 例例如：如： 假設(shè)假設(shè)多個(gè)教師上同一門(mén)課程，使用同一套參考書(shū)

13、：多個(gè)教師上同一門(mén)課程，使用同一套參考書(shū)： 注意：注意： TC不成立，因?yàn)橐粋€(gè)教師可以上多門(mén)課。不成立，因?yàn)橐粋€(gè)教師可以上多門(mén)課。 BC不成立，因?yàn)閰⒖紩?shū)可以跨課程交叉使用。不成立，因?yàn)閰⒖紩?shū)可以跨課程交叉使用。 數(shù)學(xué)分析數(shù)學(xué)分析 高等代數(shù)高等代數(shù) 微分方程微分方程 數(shù)學(xué)數(shù)學(xué) 鄧軍鄧軍 陳斯陳斯 物理物理 李平李平 王強(qiáng)王強(qiáng) 鄧軍鄧軍 普通物理普通物理 微分方程微分方程 用關(guān)系模式用關(guān)系模式Teach( C, T, B ) 表示。表示。 課程課程 教師教師 參考書(shū)參考書(shū) F = ， 候選碼為候選碼為CTB, 即全碼，所以即全碼，所以TeachBCNF 否則：否則：候選碼是候選碼是TBTeach

14、2NF TBC是是部分依賴部分依賴 Teach關(guān)系存在以下關(guān)系存在以下4個(gè)問(wèn)題：個(gè)問(wèn)題： Teach( C, T, B ) 存在的問(wèn)題存在的問(wèn)題 (1)數(shù)據(jù)冗余大數(shù)據(jù)冗余大：有多少教師上同一門(mén)：有多少教師上同一門(mén) 課，參考書(shū)就重復(fù)多少次課，參考書(shū)就重復(fù)多少次; (2)更新異常更新異常：改某一門(mén)課的參考書(shū)需：改某一門(mén)課的參考書(shū)需 要修改該課的所有記錄要修改該課的所有記錄; (3)插入異常插入異常: : 某門(mén)課增加一個(gè)教師，某門(mén)課增加一個(gè)教師， 該課有多少參考書(shū)就需要插入多少該課有多少參考書(shū)就需要插入多少 個(gè)元組個(gè)元組; (4)刪除異常刪除異常: 刪除某門(mén)課的一本參考刪除某門(mén)課的一本參考 書(shū)，該課

15、程有多少教師就要?jiǎng)h除多書(shū)，該課程有多少教師就要?jiǎng)h除多 少元組。少元組。 原因：原因： 對(duì)于每一門(mén)課，對(duì)于每一門(mén)課，Teach表中都表中都 存儲(chǔ)了存儲(chǔ)了T和和B的笛卡爾積的笛卡爾積, 即下列條即下列條 件對(duì)每門(mén)課件對(duì)每門(mén)課x都成立：都成立： Teach CTB 數(shù)學(xué)數(shù)學(xué) 數(shù)學(xué)數(shù)學(xué) 數(shù)學(xué)數(shù)學(xué) 數(shù)學(xué)數(shù)學(xué) 數(shù)學(xué)數(shù)學(xué) 數(shù)學(xué)數(shù)學(xué) 物理物理 物理物理 物理物理 物理物理 物理物理 物理物理 鄧軍鄧軍 鄧軍鄧軍 鄧軍鄧軍 陳斯陳斯 陳斯陳斯 陳斯陳斯 李平李平 李平李平 王強(qiáng)王強(qiáng) 王強(qiáng)王強(qiáng) 鄧軍鄧軍 鄧軍鄧軍 數(shù)學(xué)分析數(shù)學(xué)分析 高等代數(shù)高等代數(shù) 微分方程微分方程 數(shù)學(xué)分析數(shù)學(xué)分析 高等代數(shù)高等代數(shù) 微分方程微

16、分方程 普通物理普通物理 微分方程微分方程 普通物理普通物理 微分方程微分方程 普通物理普通物理 微分方程微分方程 P PT, B( ( s sC=x(Teach) ) = P PT ( ( s sC=x(Teach) )P PB( ( s sC=x(Teach) ) 由此引出由此引出多值依賴多值依賴的定義：的定義： R(U) U XY Z rXYZ 設(shè)設(shè)R(U)是是U上的關(guān)系模式，上的關(guān)系模式， 定義定義( (多值依賴多值依賴) )： X,Y,Z U, 且且Z= =U-X-Y, , 若對(duì)若對(duì)R(U)的的任意關(guān)系任意關(guān)系r， 都有：都有： 以及以及r在在X屬性組上的任意值屬性組上的任意值x,

17、, 成立，成立，P PY, Z( ( s sX=x(r) ) = P PY ( ( s sX=x(r) )P PZ( ( s sX=x(r) ) x x 說(shuō)明：說(shuō)明： 則稱則稱X多值確定多值確定Y或或Y多值依賴于多值依賴于X，記作記作X Y。 條件必須對(duì)條件必須對(duì)R(U)的的所有可能所有可能 關(guān)系關(guān)系在在X屬性組上的屬性組上的所有可所有可 能值能值都成立都成立, ,只要在只要在某個(gè)可某個(gè)可 能值能值上上條件條件不成立，則不成立，則: X Y不成立。不成立。 R(U) U XY Z rXYZ 設(shè)設(shè)R(U)是是U上的關(guān)系模式，上的關(guān)系模式， 多值依賴多值依賴的另一個(gè)定義：的另一個(gè)定義： X,Y,Z

18、 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的元組的元組, , 說(shuō)明：說(shuō)明： 則稱則稱多值依賴多值依賴X Y在在R(U)上成立上成立。 兩種定義是等價(jià)的兩種定義是等價(jià)的： x y1 z1 x y2 z2 x y2 z1 x y1 z2 y1 z1 y2 z2 y2 z1 y1 z2 y1 y2 z1 z2 = 多值依賴的性質(zhì)多值依賴的性質(zhì) (1)對(duì)稱性對(duì)稱性： 若若X Y，則則X U-X-Y (即即Z) 證明證明: : P PY

19、, 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 x y y z1 zk X Y: 若若X上的上的 分量相等分量相等 ，則，則Y上上 的分量相的分量相 等。等。

20、 P PY, Z(. (.)P PY (. (.)P PZ(. (.) y z1 y zk y z1 zk = = 證明證明： 所以所以X Y 多值依賴的性質(zhì)多值依賴的性質(zhì) (1)對(duì)稱性對(duì)稱性： 若若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

21、 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)平凡多值依賴平凡多值依賴：對(duì)：對(duì)U上的多值依賴上的多值依賴XY, 若若Y X, 或或 XY=U，則稱則稱XY為為平凡多值依賴平凡多值依賴。這是因?yàn)椋?。這是因?yàn)椋?Y XXYXY (3) XX (3) XXXU-X (1) XY-X XY=U XXY XY (4) XY XYY-X Teach(C, T, B )存在問(wèn)題的原因：存在問(wèn)題的原因： 存在非平凡多值依賴存在非平凡多值依賴CT, 且且C不含候選碼不含候選碼CTB 。 解決辦法：解決辦法： 分解分解關(guān)系模式關(guān)系模式, 消除消除