第三章數(shù)據(jù)依賴-在線瀏覽
2024-12-20 12:45本頁(yè)面
【正文】 設(shè) F是關(guān)系 r(R)上的 FDs， F所蘊(yùn)含的所有 FD的集合稱為 F的閉包，記作 F +。 F+ 為： F+ = {A→A, AB→A, AC→A, ABC→A, B→B, AB→B, BC→B ， ABC→B ， C→C ， AC→C ， BC→C,ABC→C ， AB→AB， ABC→AB ， AC→AC ， ABC→AC ， BC→BC, ABC→BC, ABC→ABC, AB→C, AB→AC, AB→BC, AB→ABC ， C→B, C→BC ， AC→B ， AC→AB} 19 定義 (屬性集的閉包 X + ) 設(shè)關(guān)系模式 R(U, F)， X ? U, 所有用公理推出的 X→A i中 Ai的屬性集合稱 X對(duì)于 F的閉包，記作： X + X +={ Ai | 用公理推出的 X→A i 且 Ai ? U} 20 定理 2 Armstrong公理是完備的。為此，構(gòu)造一個(gè)關(guān)系 r(R)。 21 設(shè) R=A1A2 … A n， 關(guān)系 r中僅有二個(gè)元組 t 和 t39。 元組 t39。(Ai ) = bi 若 Ai ? X+ X+ U X+ A1 A2 ... Ak Ak+1 ... An t a1 a2 ... ak ak+1 ... an t39。 根據(jù)屬性閉包定義，有 X→W ， 又因 W→Z， 根據(jù)公理 A3有 X→Z 。 (b) W ? X+。 由 (a)和 (b)得： r(R)滿足 F。即 X?X+而 Y?X+， 由 r的構(gòu)造知， X→Y 在 r上不成立，即 X→Y 不被 F所蘊(yùn)涵。 for every FD W→Z in F do if W?RESULT then RESULT:=RESULT∪Z end。 RESULT:=X。 如 list[A]， 將存放左部含 A的 FD； 2. 構(gòu)造一個(gè)計(jì)數(shù)器 COUNT， 計(jì)數(shù) FD的左部屬性數(shù)。 3. 變量 UPDATE記錄未考察的屬性，使每個(gè)屬性僅 考察一次， RESULT放中間和最后結(jié)果。 for each attribute A in W do add W→Z to list[A] end。 UPDATE:=X. 27 Ⅱ. 計(jì)算 While UPDATE?φ do begin Choose an A in UPDATE。 for each FD W→Z in LIST[A] do begin COUNT[W→Z]:=COUNT[W→Z] 1。 RESULT:=RESULT∪ADD UPDATE:=UPDATE∪ADD end end end. Ⅲ. return(RESULT). 28 例 : 設(shè) F={A→D ， AB→E ， BI→E ， CD→I ， E→C} 計(jì)算： LINCLOSURE(AE,F)。 (3) COUNT[E→C]= 0 RESULT=ACDE UPDATE=CD 其余不變 。 29 定理 1： LINCLOSURE算法對(duì)輸入長(zhǎng)度 n而言，具有時(shí)間復(fù)雜度 O(n)。計(jì)算 COUNT的全部初始化值為 O(n)次。 (3) 計(jì)算階段， F中的屬性加入到 UPDATE至多一次。 算法中涉及 ADD的計(jì)算與 │ Z│成正比，是 O(n)的。 輸出：若 F蘊(yùn)涵 X→Y 輸出為 true， 否則為 false MEMBER(F, X→Y) begin if Y? LINCLOSURE(X,F) then return(true) eles return(false) end. 31 函數(shù)依賴的等價(jià)和覆蓋 函數(shù)依賴的等價(jià)和覆蓋 定義 (等價(jià)和覆蓋 ) 在模式 R上的 FDs F和 G， 若 F+=G+， 則 F和 G等價(jià) 。 若 F?G， 稱 F是 G的一個(gè) 覆蓋 ，也稱 G是 F的一個(gè)覆蓋。 當(dāng)且僅當(dāng) F|=G 且 G|=F ，則 F ? G。 同理，如果 G|=F， 有 F + ?G +。 反之， 若 F?G， 則 F|=G和 G|=F是顯然的。 例 : 證明 F={A→BC, A→D, CD→E} 和 G={A→BCE, A→ABD, CD→E} 等價(jià) 33 無(wú)冗余覆蓋 定義 (無(wú)冗余覆蓋 ) 如果 FDs F不存在真子集 F?使 F?? F成立，則 F是無(wú)冗余的。 例 : 求 F={A→B, B→A, B→C, AB→C } 的一個(gè)無(wú)冗余覆蓋。 for each FD X→Y in F do if MEMBER(G－ {X→Y}, X→Y) then G: =G－ {X→Y}。 令 X→Y 是 F上的一個(gè) FD。 定義 (屬性集等價(jià) ) 設(shè) X、 Y?R， 若 F|=X→Y ，且 F|=Y→X ， 則 X和 Y在 F上等價(jià)。 36 證明：若 X→Y ?F， 因 F?G， G|=X→Y. 則對(duì) X→Y 有一個(gè)基于 G的推理序列，其使用集為 U(G,X→Y) 。 又因 F?G， F|= S→Z. 則該函數(shù)依賴有一個(gè)基于 F的推理序列。 因 F?G， V→W 有一個(gè)基于 F的推理序列且 X→Y ? U(F,V→W) , 則有 G|= V→X 。 這樣，由 F和 G等價(jià)可推出： F?{X→Y} |= U(G,X→Y) ， 則 X→Y 在 F中是冗余的 ，這與 F 是 無(wú) 冗 余 的 相 矛 盾 。 由以上證明可知 ， G|=X→V ， 則 F|=X→V ， 又 F|=V→X 。 證畢 。 39 等價(jià)類： 對(duì)于模式 R上的 FDs集 F和屬性集 X ? R。 設(shè)無(wú)冗余的等價(jià)的函數(shù)依賴集 F和 G： |EF| = | EG| 40 例： 設(shè) F={A→BC ， B→A ， AD→E} ， G={A→B ， B→A ， B→C ， BD→E} ， F和 G是無(wú)冗余的且 F?G 求： F和 G中左部等價(jià)的依賴集。 若模式 R中的屬性 A滿足下列條件，則稱屬性 A在 X→Y中是 外部屬性 。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1