第三章数据依赖

第三章数据依赖内容摘要：

D]= 0 COUNT[AB→E]= 1 RESULT=ADE UPDATE=ED 其余不变。 (3) COUNT[E→C]= 0 RESULT=ACDE UPDATE=CD 其余不变。 最后返回结果为 ACDEI。 29 定理 1： LINCLOSURE算法对输入长度 n而言，具有时间复杂度 O(n)。 证明： (1) 初始化阶段计算 COUNT[W→Z] 所用时间和 |W|成正比。 计算 COUNT的全部初始化值为 O(n)次。 (2) 填写 LIST表花费 O(n)， RESULT和 UPDATE能用 O(n)时间进行初始化。 (3) 计算阶段， F中的属性加入到 UPDATE至多一次。 减COUNT所花费的时间为 O(n)。 算法中涉及 ADD的计算与 │ Z│成正比，是 O(n)的。 30 算法 判定 F是否蕴涵 X→Y 的成员测试算法 输入：函数依赖集 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 函数依赖的等价和覆盖 函数依赖的等价和覆盖 定义 (等价和覆盖 ) 在模式 R上的 FDs F和 G， 若 F+=G+， 则 F和 G等价。 记作 FG。 若 FG， 称 F是 G的一个 覆盖 ，也称 G是 F的一个覆盖。 32 定理 4 已知模式 R上的函数依赖集 F和 G。 当且仅当 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 } *一个函数依赖集的无冗余覆盖不是唯一的 . 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 设 F和 G是模式 R上的两个等价的、无冗余的 FDs。 令 X→Y 是 F上的一个 FD。 则在 G中存在一个 FD V→W 使得 XV。 定义 (属性集等价 ) 设 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) ， 则根据属性闭包的概念， 有： G|=X→S。 又因 FG， F|= S→Z. 则该函数依赖有一个基于 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 例：设无冗余的等价的函数依赖集 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。 设EF(X)是 F中左部等价于 X的函数依赖集，即： EF(X)={Z→W  Z→W F且 XZ} 令 EF 为 F上所有左部等价的函数依赖的集合，即： EF ={ EF(X)  X  R且 EF (X)  φ} *F上左部等价的依赖集的集合 EF 是 F的一个划分。 设无冗余的等价的函数依赖集 F和 G： |EF| = | EG| 40 例： 设 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 ，。