第三章數(shù)據(jù)依賴-資料下載頁
2024-10-17 12:45本頁面
【導(dǎo)讀】函數(shù)依賴的概念及函數(shù)依賴公理。函數(shù)依賴集的等價(jià)和覆蓋。是通過一個(gè)關(guān)系中屬性間值的相等與否體現(xiàn)出來。是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象。是數(shù)據(jù)內(nèi)在的性質(zhì)。r,如果t1[X]=t2[X]有t1[Y]=t2[Y]，稱X. 元組，則有X→Y。都不成立，則稱X→Y是完全函數(shù)依賴；若對(duì)X的真子集X?→Y成立，則稱FDX→Y是部分函數(shù)依賴，即Y函。數(shù)依賴于X的一部分。⒉一個(gè)系只有一名主任；⒋每個(gè)學(xué)生所學(xué)的每門課程都有一個(gè)成績(jī)。X→Y邏輯蘊(yùn)涵于F。證明：A1.自反律:若Y?證明：A2.增廣律:若X→Y且Z?ΠY至多有一個(gè)元組，r必滿足XZ→Y。推論1若X→Y，X→Z，則X→YZ。推論3若X→Y，YZ→W，則XZ→W。An成立的充要條件是：。依賴組成的序列稱F上的一個(gè)推理序列。的閉包，記作F+。，ABC→AB，AC→AC，ABC→AC，BC→BC,ABC→BC,X+={Ai|用公理推出的X→Ai且Ai?定理2Armstrong公理是完備的。為此，構(gòu)造一個(gè)關(guān)系r。An，關(guān)系r中僅有二個(gè)元組t和t'。F，W在r中有兩種情況:
【正文】 →G ， C→BJ ， E→IK} 有： AB→CE ， CE →JK 則： AB → JK 54 定理 8 設(shè) F是一個(gè)無冗余的 FDs集。若 F中某個(gè) FD的左部 X和屬性 Y有 X?Y， 則在 eF(X)中存在一 個(gè) Z， 滿足 Y → Z 。 證明： (1) 若 Y?eF(X)， 則 Z=Y， 有 Y → Y。 (2) 若 Y? eF(X)。 對(duì) eF(X)中任一屬性集 W因 X?Y,有 F|=Y→W 。 假設(shè) Z?eF(X)使得 U(F, Y→Z) 具有最少函數(shù)依賴數(shù)， Y → Z。 若 Y→ Z不成立，則有 V→T ? U(F,Y→Z) 且 V?eF(X)，而 U(F, Y→Z) ∩E G(X)≠ φ 。 如果這樣的 V→T 存在，則U(F, Y→V) 比 U(F, Y→Z) 具有更少的函數(shù)依賴數(shù)，與假設(shè)矛盾。因此， Z?eF(X)且 Y → Z。 55 例： F={A→DE ， DE→A ， AC→BI ， I→D} 有： AC ? CDE， CDE→AC 56 定理 9 設(shè) F為最小函數(shù)依賴集，在任一個(gè) EF(X)中不存在不同的 Y→U 和 Z→V 能使 Y → Z 成立。 證明： 假設(shè)在 EF(X)中存在不同的 Y→U 和 Z→V 能使 Y → Z成立。即： U (F, Y→Z) ∩E F(X)=φ 也就是有： Y→U ? EF(X) 而 Y→U ? U (F, Y→Z) 因 Y?Z， 則用 Z→UV 代替 Y→U 和 Z→V ， 結(jié)果為 F?， 且 F? F? 即 F? |= Y→U 和 F? |= Z→V 。 但 F? 有更少的函數(shù)依賴數(shù)，因而與 F是最小函數(shù)依賴集矛盾。 57 定理 10 若 F和 G是等價(jià)的最小函數(shù)依賴集，則對(duì)任一 X， |EF(X)|＝ |EG(X)| 。 證明：假設(shè) |EF(X)| ? |EG(X)| ， EF(X)和 EG(X)分別由以下 FDs 組成，且 m ? n。 |EF(X)| = { Xi → X i | 1 i m} |EG(X)| ={ Yj→Y j | 1 j n} X1 → X 1 Y1→Y 1 X2 →X 2 Y2→Y 2 … … Xm →X m Ym→ Y m … Yn→Y n ? ? ? ? ? ? ? ? ? eF(X)={X1,X2,… ,Xm} eG(X)={Y1,Y2, … , Yn} 58 在 EG(X)中，對(duì)所有的 Yj其中有些與 Xi是相同的。有些不同，即 Yj?Xi。 對(duì)于這些 Yj?Xi， 因 Yj ?Xi， 根據(jù)定理 8，一定有某個(gè) Xi能使得 Yj→ Xi。 因此，在 G中用 Xi → ?Yj 代替 Yj→ ?Yj 不會(huì)改變 G的閉包，也不會(huì)改變 G的最小性。 找尋所有這樣的 Yj → Xi， 之后都用對(duì)應(yīng)的 Xi → ?Yj 代替 Yj→ ?Yj。 代替后對(duì) EG(X)中的函數(shù)依賴重新排序。 因 m n， 在 EG(X)中一定有某個(gè) Xi → ?Yi 和 Xj → ?Yj其左部相等。合并這二個(gè) FD為： Xi → ?Yi?Yj， 使 EG(X)中的函數(shù)依賴數(shù)減少，這與 G是最小依賴集矛盾。 因此，應(yīng)有 m = n。 59 例 : 設(shè) F={A→BC ， B→A ， I→BDEJ ， BDE→IJ} ， G={A→B, B→AC, I→ACDE, ADE→IJ} 。 F和 G都是最小覆蓋且 F?G。 在 F和 G中有： A → A ， B → B ， I → I ， BDE → ADE ， ADE → BDE 。 *** 二個(gè)等價(jià)的最小依賴集 F和 G其等價(jià)類中的FD間存在著對(duì)應(yīng)關(guān)系： Xi → Yj ， Yj → Xi 。 若 Yj → Xi， 在 G中用 Xi代替 Yj不改變 G的閉包。 60 定理 11 若 G是無冗余的但不是最小依賴集，則存在某個(gè) EG(X)含有不同的 FD Y→U 和 Z→V ， 使得 Y → Z 。 證明：設(shè) F是 G的一個(gè)最小覆蓋。因 G不是最小的，必存在某一 X使得 |EF(X)| |EG(X)|。 根據(jù)定理 9，因 |EF(X)||EG(X)|， 必有 X→W ?EF(X)， Y→U 、 Z→V ?EG(X)， 且 Y→X 和 Z→X ， Y?Z。 同樣 有 X→Y 或 X→Z 。 假定有 X→Z ， 則根據(jù)定理 7， 得 Y→Z 。 61 算法 求最小覆蓋 輸入：函數(shù)依賴集 G 輸出： G的最小覆蓋 MINIMIZE(G) begin F:=NONREDUN(G)。 find the set of ?EF 。 for each EF(X) in ?EF do for each Y→U in E F(X) do for each Z→V ?Y→U in E F(X) do if MEMBER(F? EF(X)， Y→Z) then replace Y→U and Z→V by Z→UV in F return(F)。 end. 62 (3)考察每個(gè) EF(X)， EF(AD)中 EC → AD 用 AD→EGH 代替 AD→E, EC→GH 得最小依賴集為： F={A→BC, C→A, AD→EGH, E→D} 例 : 設(shè) F={A→BC, C→A, AD→E, EC→GH, AE→H, E→D} 求： F的最小覆蓋 解： (1)計(jì)算 F的無冗余覆蓋?？疾?F得 FD AE→H 是冗余的，去掉冗余 FD， 則： F={A→BC, C→A, AD→E, EC→GH, E→D} 。 (2) 找出 F中 FD左部的等價(jià)類如下： EF(A)={A→BC,C→A} EF(AD)={AD→E, EC→GH} EF(E)={E→D}
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1