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

(1)F中每個FD的右部只含一個屬性。函數(shù)依賴集的最小覆蓋定義

:設(shè)F

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

B→A,C→D,A→E,B→D},將最小覆蓋中左部相同的FD合并成一個后得到的FD集稱為規(guī)范覆蓋。C→BD,B→AD,A→E函數(shù)依賴集的最小覆蓋(1)

用分解規(guī)則將F中的每個FD右部分解為單屬性。如何計算FD集F的最小覆蓋？分三步：F(F-{XY})∪{XAi|i=1,2,…,k

}。對每個XYF,若Y=A1A2…Ak(k≥2),則置：(2)

刪除F中多余的FD。對每個XAF,令G=F-{XA},若AXG＋,則置FG。因：由AXG＋可得XA，故F中的XA多余。(3)

刪除F中每個FD左部的多余屬性。對每個XAF,設(shè)X=B1B2…Bm(m≥2),逐個考查Bi(i=1..m):若A(X-Bi)F＋,因：由A(X-Bi)F＋可得(X-Bi)A，故XA中Bi是多余屬性。則置F(F-{XA})∪{(X-Bi)A}。F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→B,CB→E}例:

求F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→BE}的最小覆蓋(1)用分解規(guī)則將F中的每個FD右部分解為單屬性。(2)刪除F中多余的FD。G={

C→B,

B→A,C→D,C→A,AC→D,CB→B,CB→E}(AC)G+={A,C,…}，∵A(AC)G＋，∴置FG

。函數(shù)依賴集的最小覆蓋函數(shù)依賴集的最小覆蓋F={

C→B,

B→A,C→D,C→A,AC→D,CB→B,CB→E}G={

B→A,C→D,C→A,AC→D,CB→B,CB→E}CG+={}，∴F不變

。,DC,A∵BCG＋，例:

求F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→BE}的最小覆蓋(1)用分解規(guī)則將F中的每個FD右部分解為單屬性。(2)刪除F中多余的FD。函數(shù)依賴集的最小覆蓋F={

C→B,

B→A,C→D,C→A,AC→D,CB→B,CB→E}例:

求F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→BE}的最小覆蓋BG+={B}，∴F不變

?！逜BG＋，G={

C→B,C→D,C→A,AC→D,CB→B,CB→E}(1)用分解規(guī)則將F中的每個FD右部分解為單屬性。(2)刪除F中多余的FD。函數(shù)依賴集的最小覆蓋例:

求F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→BE}的最小覆蓋F={

C→B,

B→A,C→D,C→A,AC→D,CB→B,CB→E}G={

C→B,B→A,C→A,AC→D,CB→B,CB→E}CG+={}，∴置FG

。,BC,A∵DCG＋，,D,E(1)用分解規(guī)則將F中的每個FD右部分解為單屬性。(2)刪除F中多余的FD。函數(shù)依賴集的最小覆蓋例:

求F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→BE}的最小覆蓋F={

C→B,

B→A,C→A,AC→D,CB→B,CB→E}G={

C→B,B→A,AC→D,CB→B,CB→E}CG+={}，∴置FG

。,BC,A∵ACG＋，,D,E(1)用分解規(guī)則將F中的每個FD右部分解為單屬性。(2)刪除F中多余的FD。函數(shù)依賴集的最小覆蓋例:

求F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→BE}的最小覆蓋A,CF={

C→B,

B→A,AC→D,CB→B,CB→E}G={

C→B,B→A,

CB→B,CB→E}(AC)G+={}，∴F不變

。,B,E∵D(AC)G+

，(1)用分解規(guī)則將F中的每個FD右部分解為單屬性。(2)刪除F中多余的FD。函數(shù)依賴集的最小覆蓋例:

求F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→BE}的最小覆蓋(CB)G+={}，C,B,…F={

C→B,

B→A,AC→D,CB→B,CB→E}G={

C→B,B→A,AC→D,CB→E}∴置FG

?！連(CB)G+，(1)用分解規(guī)則將F中的每個FD右部分解為單屬性。(2)刪除F中多余的FD。函數(shù)依賴集的最小覆蓋例:

求F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→BE}的最小覆蓋(CB)G+={}，C,BF={

C→B,

B→A,AC→D,

CB→E}G={

C→B,B→A,AC→D

}∴F不變

。,A,D∵E(CB)G+，(1)用分解規(guī)則將F中的每個FD右部分解為單屬性。(2)刪除F中多余的FD。函數(shù)依賴集的最小覆蓋例:

求F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→BE}的最小覆蓋F={

C→B,

B→A,AC→D,

CB→E}(3)刪除F中每個FD左部的多余屬性。F={

C→B,

B→A,AC→D,

CB→E

}CF+={}，C∴A是多余屬性，刪去。,B,A∵DCF+，,D,E

C→D,(1)用分解規(guī)則將F中的每個FD右部分解為單屬性。(2)刪除F中多余的FD。函數(shù)依賴集的最小覆蓋例:

求F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→BE}的最小覆蓋F={

C→B,

B→A,AC→D,

CB→E}F={

C→B,

B→A,AC→D,

CB→E

}(1)用分解規(guī)則將F中的每個FD右部分解為單屬性。(2)刪除F中多余的FD。

C→D,BF+={}，B∴C不是多余屬性，保留。,A∵EBF+，(3)刪除F中每個FD左部的多余屬性。函數(shù)依賴集的最小覆蓋例:

求F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→BE}的最小覆蓋F={

C→B,

B→A,AC→D,

CB→E}F={

C→B,

B→A,AC→D,

CB→E

}(1)用分解規(guī)則將F中的每個FD右部分解為單屬性。(2)刪除F中多余的FD。

C→D,(3)刪除F中每個FD左部的多余屬性。CF+={}，C∴B是多余屬性，刪去。,B,A∵ECF+，,D,EC→EF的規(guī)范覆蓋為：Fc={}最后得到F的最小覆蓋為：Fm={C→B,

B→A,C→D,C→E},B→AC→BDE多值依賴在函數(shù)依賴范疇內(nèi)，BCNF已經(jīng)非常完美。但是屬于BCNF的關(guān)系模式仍可能存在問題。例如：假設(shè)多個教師上同一門課程，使用同一套參考書：注意：

TC不成立，因為一個教師可以上多門課。

BC不成立，因為參考書可以跨課程交叉使用。數(shù)學(xué)分析高等代數(shù)微分方程數(shù)學(xué)鄧軍陳斯物理李平王強(qiáng)鄧軍普通物理微分方程用關(guān)系模式Teach(C,T,B)表示。課程教師參考書F={}，候選碼為CTB,即全碼，所以Teach∈BCNF否則：候選碼是TBTeach∈2NF

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

某門課增加一個教師，該課有多少參考書就需要插入多少個元組;(4)刪除異常:刪除某門課的一本參考書，該課程有多少教師就要刪除多少元組。原因：對于每一門課，Teach表中都存儲了T和B的笛卡爾積,即下列條件對每門課x都成立：TeachCTB數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)物理物理物理物理物理物理…鄧軍鄧軍鄧軍陳斯陳斯陳斯李平李平王強(qiáng)王強(qiáng)鄧軍鄧軍…數(shù)學(xué)分析高等代數(shù)微分方程數(shù)學(xué)分析高等代數(shù)微分方程普通物理微分方程普通物理微分方程普通物理微分方程…PT,B(sC=x(Teach))=PT

(sC=x(Teach))×PB(sC=x(Teach))由此引出多值依賴的定義：R(U)UXYZrXYZ………………………設(shè)R(U)是U上的關(guān)系模式，定義(多值依賴)：X,Y,ZU,且Z=U-X-Y,若對R(U)的任意關(guān)系r，都有：以及r在X屬性組上的任意值x,成立，PY,Z(sX=x(r))=PY

(sX=x(r))×PZ(sX=x(r))xx說明：則稱X多值確定Y或Y多值依賴于X，記作XY。條件必須對R(U)的所有可能關(guān)系在X屬性組上的所有可能值都成立,只要在某個可能值上條件不成立，則:XY不成立。R(U)UXYZrXYZ………………………………設(shè)R(U)是U上的關(guān)系模式，多值依賴的另一個定義：X,Y,ZU,且Z=U-X-Y,若R的任意關(guān)系r滿足:那么(x,y2,z1)和(x,y1,z2)也是r的元組，只要(x,y1,z1)和(x,y2,z2)是r的元組,說明：則稱多值依賴XY在R(U)上成立。兩種定義是等價的：xy1

z1xy2

z2xy2

z1xy1

z2y1

z1y2

z2y2

z1y1

z2y1y2z1z2=×多值依賴的性質(zhì)(1)對稱性：若XY，則XU-X-Y(即Z)證明:PY,Z(sX=x(r))=PY

(sX=x(r))×PZ(sX=x(r))成立，必有PZ,Y(sX=x(r))=PZ

(sX=x(r))×PY(sX=x(r))成立。(2)傳遞性：若XY，YZ,則XZ-Y證明非常復(fù)雜，大大超出了本課程的范圍。(3)復(fù)制性：若XY,則XY。rXYZ………x…xy…yz1…zk………XY:若X上的分量相等，則Y上的分量相等。PY,Z(.)PY

(.)PZ(.)yz1…yzkyz1…zk×=×=證明：所以XY多值依賴的性質(zhì)(1)對稱性：若XY，則XU-X-Y(即Z)證明:PY,Z(sX=x(r))=PY

(sX=x(r))×PZ(sX=x(r))成立，必有PZ,Y(sX=x(r))=PZ

(sX=x(r))×PY(sX=x(r))成立。(2)傳遞性：若XY，YZ,則XZ-Y證明非常復(fù)雜，大大超出了本課程的范圍。(3)復(fù)制性：若XY,則XY。(4)并規(guī)則：若XY,XZ,則XYZ。(5)交規(guī)則：若XY,XZ,則XY∩Z。(6)差規(guī)則：若XY,XZ,