第三章數(shù)據(jù)依賴(編輯修改稿)
2024-11-22 12:45 本頁面
【文章內(nèi)容簡介】 D]= 0 COUNT[AB→E]= 1 RESULT=ADE UPDATE=ED 其余不變 。 (3) COUNT[E→C]= 0 RESULT=ACDE UPDATE=CD 其余不變 。 最后返回結(jié)果為 ACDEI。 29 定理 1： LINCLOSURE算法對輸入長度 n而言，具有時間復(fù)雜度 O(n)。 證明： (1) 初始化階段計算 COUNT[W→Z] 所用時間和 |W|成正比。計算 COUNT的全部初始化值為 O(n)次。 (2) 填寫 LIST表花費 O(n)， RESULT和 UPDATE能用 O(n)時間進(jìn)行初始化。 (3) 計算階段， F中的屬性加入到 UPDATE至多一次。減COUNT所花費的時間為 O(n)。 算法中涉及 ADD的計算與 │ Z│成正比，是 O(n)的。 30 算法 判定 F是否蘊涵 X→Y 的成員測試算法 輸入：函數(shù)依賴集 F和 FD X→Y 。 輸出：若 F蘊涵 X→Y 輸出為 true， 否則為 false MEMBER(F, X→Y) begin if Y? LINCLOSURE(X,F) then return(true) eles return(false) end. 31 函數(shù)依賴的等價和覆蓋 函數(shù)依賴的等價和覆蓋 定義 (等價和覆蓋 ) 在模式 R上的 FDs F和 G， 若 F+=G+， 則 F和 G等價 。 記作 F?G。 若 F?G， 稱 F是 G的一個 覆蓋 ，也稱 G是 F的一個覆蓋。 32 定理 4 已知模式 R上的函數(shù)依賴集 F和 G。 當(dāng)且僅當(dāng) F|=G 且 G|=F ，則 F ? G。 證明：如果 F|=G， 若有 X→Y∈G ， 則 F|=X→Y ， 即 X→Y∈F +， 有 G?F +， (G)+?(F+)+ = F + 。 同理，如果 G|=F， 有 F + ?G +。 因此， F +=G +， 則 F?G。 反之， 若 F?G， 則 F|=G和 G|=F是顯然的。證畢。 例 : 證明 F={A→BC, A→D, CD→E} 和 G={A→BCE, A→ABD, CD→E} 等價 33 無冗余覆蓋 定義 (無冗余覆蓋 ) 如果 FDs F不存在真子集 F?使 F?? F成立，則 F是無冗余的。如果 F是 G的一個覆蓋且 F是無冗余的，則 F是 G的一個無冗余覆蓋。 例 : 求 F={A→B, B→A, B→C, AB→C } 的一個無冗余覆蓋。 {A→B, B→A, B→C , AB→C } *一個函數(shù)依賴集的無冗余覆蓋不是唯一的 . 34 算法 計算無冗余覆蓋 NONREDUN(F) begin G: =F 。 for each FD X→Y in F do if MEMBER(G－ {X→Y}, X→Y) then G: =G－ {X→Y}。 return(G) end. 35 定理 5 設(shè) F和 G是模式 R上的兩個等價的、無冗余的 FDs。 令 X→Y 是 F上的一個 FD。 則在 G中存在一個 FD V→W 使得 X?V。 定義 (屬性集等價 ) 設(shè) X、 Y?R， 若 F|=X→Y ，且 F|=Y→X ， 則 X和 Y在 F上等價。記作 X?Y。 36 證明：若 X→Y ?F， 因 F?G， G|=X→Y. 則對 X→Y 有一個基于 G的推理序列，其使用集為 U(G,X→Y) 。 對任一 FD S→Z ?U(G,X→Y) ， 則根據(jù)屬性閉包的概念， 有： G|=X→S 。 又因 F?G， F|= S→Z. 則該函數(shù)依賴有一個基于 F的推理序列。 要證明： X?V 在 G中一定有一個 FD V→W ? U(G,X→Y) ， 則有 X→V 。 因 F?G， V→W 有一個基于 F的推理序列且 X→Y ? U(F,V→W) , 則有 G|= V→X 。 接下頁 37 否則 ,若 X→Y ?U(F,V→W) ， 則 FD V→W 的使用集可寫為：U(F?{X→Y} ， V→W) 。 這樣，由 F和 G等價可推出： F?{X→Y} |= U(G,X→Y) ， 則 X→Y 在 F中是冗余的 ，這與 F 是 無 冗 余 的 相 矛 盾 。 因此 ， 必 定 有 X→Y ?U(F,V→W) ， 則 F|=V→X 。 由以上證明可知 ， G|=X→V ， 則 F|=X→V ， 又 F|=V→X 。 因此 ， 在 F中有 X?V， 同理 ， 在 G中亦有X?V。 證畢 。 示例 38 例：設(shè)無冗余的等價的函數(shù)依賴集 F?G F ={A→BC ， B→A ， AD→E} G={A→ABC ， B→A ， BD→E} F和 G中左部等價的屬性集為： A?A， B?B， AD?BD AD→E 是 F中的 FD， 在 G中有 BD→E 使得 AD?BD： 在 G中， U（ G， AD→E ） ={A→ABC ， BD→E} 在 F中， U（ F， A→ABC ） ={A→BC} U（ F， BD→E ） ={B→A ， AD→E} 因此，在 F和 G中有 AD?BD。 39 等價類： 對于模式 R上的 FDs集 F和屬性集 X ? R。 設(shè)EF(X)是 F中左部等價于 X的函數(shù)依賴集，即： EF(X)={Z→W ? Z→W ?F且 X?Z} 令 ?EF 為 F上所有左部等價的函數(shù)依賴的集合，即： ?EF ={ EF(X) ? X ? R且 EF (X) ? φ} *F上左部等價的依賴集的集合 ?EF 是 F的一個劃分。 設(shè)無冗余的等價的函數(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是無冗余的且 F?G 求： F和 G中左部等價的依賴集。 解： ?EF 為： EF (A)={A→BC ， B→A} ， EF (AD)={AD→E} ?EG 為： EG (A)={A→B ， B→A ，
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1