第12讲函数依赖的理论.ppt

函数依赖集等价和最小函数依赖集 Armstrong公理 【例】设F={A→BC,B→AC,C→A},求Fm。 1)函数依赖右边属性单一化 F={A→B, A→C, B→A, B→C,C→A} 2)去掉冗余的函数依赖 判断A→B是否冗余： G1= {A→C, B→A, B→C,C→A} AＧ1 ＋= AC, B不属于AＧ1 ＋，A→B不冗余； 判断A→C是否冗余： G2= {A→B, B→A, B→C,C→A} AＧ2 ＋= ABC，C∈AＧ2 ＋，A→C冗余 F={A→B, B→A, B→C,C→A}； 函数依赖集等价和最小函数依赖集 Armstrong公理 【例】设F={A→BC,B→AC,C→A},求Fm。 判断B→A是否冗余： G3= {A→B, B→C,C→A} BＧ3 ＋= ABC， A∈BＧ3 ＋，B→A冗余 F={A→B, B→C,C→A}； 判断B→C是否冗余： G4= {A→B,C→A} BＧ4 ＋= B，C不属于BＧ4 ＋，B→C不冗余； 判断C→A是否冗余： G5= {A→B,B→C} CＧ5 ＋= C，A不属于CＧ5 ＋，C→A不冗余。 函数依赖集等价和最小函数依赖集 Armstrong公理 【例】设F={A→BC,B→AC,C→A},求Fm。 3)由于例中函数依赖的决定因素均为单属性，因而不需要第三步检查，上述结果就是最小函数依赖集。 Fm＝{A→B, B→C, C→A} 函数依赖集等价和最小函数依赖集 Armstrong公理 【例】 函数依赖集F={AB→C,A→B,B→A}，求Fm。 解： 1）所有的函数依赖右部均为单属性，此步完成。 2）去掉冗余的函数依赖，按前例方法，经过检验，函数依赖集仍为F； 3）去掉各函数依赖左部冗余的属性。 本题只需考虑AB→C。 函数依赖集等价和最小函数依赖集 Armstrong公理 【例】 函数依赖集F={AB→C,A→B,B→A}，求Fm。 解： 方法1：在决定因素中去掉B,若C ∈A F+,则以A→C代替AB→C。 求得A F+＝ABC, ∵ C ∈A F+, ∴ Fm＝{A→C, A→B,B→A}; 方法2：在决定因素中去掉A,若C∈ B F+,则以B→C代替AB→C。 求得B F+＝ABC, ∵ C ∈ B F+ ∴ Fm＝{B→C, A→B,B→A}; 最小函数依赖集 不是唯一的 主要内容 Armstrong公理 逻辑蕴含 函数依赖集F 的闭包F+ Armstrong公理推理规则 属性集闭包 函数依赖集等价和最小函数依赖集 候选键及其求解方法 函数依赖的理论 候选键的概念 在关系模式R（U，F）中，如果属性集K满足K U，K为关系模式R的候选键。 候选键及其求解方法 如何判断？ 候选键的求解方法 方法一： 在关系模式R（U，F）中，K ? U，利用Armstrong公理中的推导规则，从已知的函数依赖集F中推导得到如下的函数依赖关系，则K为候选键。 K→U，且不存在K的真子集K’ →U 候选键及其求解方法 【例1】R (A, B, C, D)，F= { B→D, AB→C }，求解R的候选键。 候选码及其求解方法 解：由B→D 利用增广规则可得： AB→AD ………….(1) ?? 由(1), AB→C 及合并规则可得: AB→ACD …………(2) ?? 由(2) 利用增广规则可得： AB→ABCD 由于不存在A→ABCD和B→ABCD， 则AB为候选键。 AB是否是唯一的候选键？ 候选键的求解方法 方法二： 在关系模式R（U，F）中，K? U，根据候选键的定义及属性集闭包的概念，如果K满足下面两个条件，则K为候选键： KF+ = U 对于K 的任意一个