数据库 规范覆盖的计算、多值依赖.ppt

* (1) F中每个FD的右部只含一个属性。 函数依赖集的最小覆盖 定义 : 设F 是R(U)上的FD集， 如果F满足以下三个条件： (2) F中无多余FD。 即不存在X?A, 满足F与F－{X?A}等价。 (3) F中每个FD的左部都不含多余属性。 即不存在X?A，X有真子集Z， 满足： F与(F－{X?A})∪{Z?A}等价。 则称F为最小依赖集或最小覆盖。 则对应的规范覆盖为： Fc={ }。 例：设最小覆盖为：Fm={C→B, B→A, C→D, A→E, B→D}, 将最小覆盖中左部相同的FD合并成一个后得到的FD集称为规范覆盖。 C→BD , B→AD , A→E 函数依赖集的最小覆盖 (1) 用分解规则将F中的每个FD右部分解为单属性。 如何计算FD集F的最小覆盖？ 分三步： F ? (F - { X?Y } )∪{X? Ai | i=1,2,…,k } 。 对每个X?Y?F, 若Y=A1A2…Ak (k≥2), 则置： (2) 删除F中多余的FD。 对每个X?A?F, 令G=F - {X?A}, 若A?XG＋, 则置F ?G。 因：由A?XG＋可得X?A， 故F中的X?A多余。 (3) 删除F中每个FD左部的多余属性。 对每个X?A?F, 设X=B1B2…Bm (m≥2), 逐个考查Bi (i=1..m): 若A?(X- Bi)F＋, 因：由A?(X-Bi)F＋可得(X-Bi)?A， 故X?A中Bi是多余属性。 则置F ? (F - { X?A } )∪{(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) 用分解规则将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＋ ， ∴置F ?G 。 函数依赖集的最小覆盖 函数依赖集的最小覆盖 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不变 。 , D C , A ∵B?CG＋ ， 例: 求F={ AC→A, C→B, B→A, C→D, C→A, AC→D, CB→BE }的最小覆盖 (1) 用分解规则将F中的每个FD右部分解为单属性。 (2) 删除F中多余的FD。 函数依赖集的最小覆盖 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不变 。 ∵A?BG＋ ， G={ C→B, C→D, C→A, AC→D, CB→B, CB→E } (1) 用分解规则将F中的每个FD右部分解为单属性。 (2) 删除F中多余的FD。 函数依赖集的最小覆盖 例: 求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+={ }， ∴置F ?G 。 , B C , A ∵D?CG＋ ， , D , E (1) 用分解规则将F中的每个FD右部分解为单属性。 (2) 删除F中多余的FD。 函数依赖集的最小覆盖 例: 求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+={ }， ∴置F ?G