函数依赖理论第二讲PPT学习课件.ppt

函数依赖理论与范式 郑子仪 1 主要内容 无关属性 正则覆盖 无损连接分解 有损连接分解第一范式 1NF 第二范式 2NF Boyce Codd范式 BCNF 第三范式 3NF 2 无关属性 给定函数依赖集F及 F 如果去除 或 的一个属性不会改变F 则称该属性是无关的 给定函数依赖集F及 F 若A 且F逻辑蕴涵 F A 则属性A在 中是无关的 左无关 给定函数依赖集F及 F 若A 且 F A 逻辑蕴涵F 则属性A在 中是无关的 右无关 3 无关属性检测算法 设r R 为关系模式 F是函数依赖集 则检测 上的属性A左无关或右无关的算法分别如图 a 或 b 所示 4 无关属性检测举例 设F AB CD A E E C 证明C在AB CD中为无关属性 证明 由于C是AB CD中的右边属性 依图 b 的算法 计算F F AB D A E E C 计算F 下 AB AB ABCDE 判断C是否属于 AB C ABCDE 因此 C是AB CD中的无关属性 证毕 5 正则覆盖定义和计算方法 正则覆盖 canonicalcover Fc是一个依赖集 使得F逻辑蕴涵Fc中的所有依赖 Fc逻辑蕴涵F中的所有依赖 而且必须具有下列特性 Fc中的任何函数依赖都不包含无关属性 Fc中函数依赖的左半部都是唯一的 即Fc中不存在两个依赖 1 1和 2 2 且 1 2 根据上述性质 计算F的正则覆盖Fc分为两个步骤 合并函数依赖 将F中所有形如 1 1 1 2的函数依赖合并为 1 1 2 得到新函数依赖集F 去除无关属性 对F 中的每个函数依赖 依次判断是否包含无关属性 若发现无关属性 则用去除无关属性后的函数依赖代替F 中的原函数依赖 6 计算正则覆盖举例 考虑关系模式r R r A B C 和函数依赖集F A BC B C A B AB C 计算F的正则覆盖Fc 第1步 合并函数依赖 将A BC和A B合并为A BC F A BC B C AB C 第2步 去除无关属性 对于AB C 根据图5 9 a 的算法可检测A是无关的 因此 去除无关属性A后 AB C变为B C 而B C已在F 中存在 则F B C A BC 对于B C 由于其左右两边都为单属性 故不存在无关属性 对于A BC 根据图5 9 b 的算法可检测C是无关的 因此 去除无关属性C后 A BC变为A B 则F B C A B F 中的函数依赖左半部都是唯一的 且都不存在无关属性 因此Fc B C A B 7 无损连接分解 给定关系模式r R 及函数依赖集F 若r R 的任意一个满足函数依赖集F的关系实例r都有 r 其中r1 R1 r2 R2 分别为分解后的子模式 则称该分解对于F是无损连接的 无损连接分解能够根据分解后的关系通过连接来还原原来的关系实例 如何判定一分解是否是无损的 8 无损连接分解判断方法 给定关系模式r R 及函数依赖集F 则将r R 分解成r1 R1 r2 R2 的分解是无损连接分解 当且仅当F 包含函数依赖R1 R2 R1或R1 R2 R2 因此 当一个关系模式分解为两个关系模式时 该分解为无损连接分解的充要条件是两分解关系的公共属性包含r1 R1 的码或r2 R2 的码 9 无损连接分解判断举例 假设关系模式r R r A B C D E F A BC CD E B D E A 则可将r R 进行两种不同的分解 分解1 r1 R1 r1 A B C r2 R2 r2 A D E 分解2 r1 R1 r1 A B C r2 R2 r2 C D E 对于分解1 R1 R2 A 且A R1 故此分解是无损连接分解 而对于分解2 R1 R2 C 且C R1 C R2 故此分解不是无损连接分解 10 保持依赖分解 关系数据库模式分解的另一个目标是保持依赖 给定关系模式r R 及函数依赖集F r1 R1 r2 R2 rn Rn 为r R 的分解 F在Ri的投影为闭包F 中所有只包含Ri属性的函数依赖的集合 记为Fi 即如果 在Fi中 则 和 的所有属性均在Ri中 称具有函数依赖集F的关系模式r R 的分解r1 R1 r2 R2 rn Rn 为保持依赖分解 当且仅当 F1 F2 Fn F 11 保持依赖分解判断举例 设关系模式r R r A B C F A B B C 有两种分解 r1 R1 r1 A B r2 R2 r2 B C r1 R1 r1 A B r2 R2 r2 A C 显然 前一种分解是保持依赖分解 而后一种分解不是保持依赖分解 因为分解后 函数依赖B C既不能从F在R1的投影F1中推导出来 也不能从F在R2的投影F2中推导出来 12 范式概述 基于函数依赖理论 关系模式可分成第一范式 1NF 第二范式 2NF 第三范式 3NF Boyce Codd范式 BCNF 这几种范式的要求一个比一个严格 它们之间的联系为BCNF 3NF 2NF 1NF 即满足BCNF范式的关系一定满足3NF范式 满足3NF范式的关系一定满足2NF范式 满足2NF范式的关系一定满足1NF范式 13 第一范式 1NF 如果一关系模式r R 的每个属性对应的域值都是不可分的 即原子的 则称r R 属于第一范式 记为r R 1NF 第一范式的目标是 将基本数据划分成称为实体集或表的逻辑单元 当设计好每个实体后 需要为其指定主码 14 第二范式 2NF 第二范式的目标是 将只部分依赖于主码 即依赖于主码的部分属性 的数据移到其他表中 也就是说 在满足第一范式的实体中 如果有复合主码 即多个属性共同构成主码 那么所有非主属性必须依赖于全部的主码 而不能只是依赖于部分的主码属性 违背了2NF的模式 即存在非主属性对候选码的部分依赖 则可能导致例5 1所述的数据冗余及异常问题 15 对于非2NF范式的关系模式 可通过分解进行规范化 以消除部分依赖 如将关系模式SCE分解为关系模式S C和E 这样在每个关系模式中 所有非主属性对候选码都是完全函数依赖 因此都属于2NF范式 2NF范式虽然消除了由于非主属性对主码的部分依赖所引起的冗余及各种异常 但并没有排除传递依赖 因此 还需要对其进一步规范化 16 Boyce Codd范式 BCNF 给定关系模式r R 及函数依赖集F 若F 中的所有函数依赖 R R 至少满足下列条件之一 是平凡函数依赖 即 是r R 的一个超码 即 包含R的全部属性 即起决定作用的属性必须是超码 则称r R 属于Boyce Codd范式 记为r R BCNF 换句话说 在关系模式r R 中 如果F 中的每一个非平凡函数依赖的决定属性集 都包含候选码 则r R BCNF 特别说明 为确定r R 是否满足BCNF范式 必须考虑F 而不是F中的每个依赖 17 从函数依赖角度可得出 一个满足BCNF的关系模式必然满足下列结论 所有非主属性都完全函数依赖于每个候选码 所有主属性都完全函数依赖于每个不包含它的候选码 没有任何属性完全函数依赖于非候选码的任何一组属性 BCNF范式排除了 任何属性 包括主属性和非主属性 对候选码的部分依赖和传递依赖 主属性之间的传递依赖 18 Boyce Codd范式判断举例 例1r R r A B C F A B B C r R 的候选码为A r R BCNF 因为函数依赖B C中的决定属性B不是超码 例2r R r A B C F AB C C A r R 的候选码为AB或BC r R BCNF 因为C A的决定属性C不是超码 例3r R r A B C F AB C BC A r R 的候选码为AB或BC r R BCNF 因为两个函数依赖中的决定属性AB或BC都是r R 的候选码 19 Boyce Codd范式存在问题 对于非BCNF范式的关系模式 可通过分解进行规范化 以消除部分依赖和传递依赖 将例5 13中的r R 分解为r1 R1 r1 A B r2 R2 r2 B C 或r1 R1 r1 A B r2 R2 r2 A C 显然 这两种分解得到的r1 R1 和r2 R2 都属于BCNF范式 但是 后一种分解不是保持依赖分解 例5 12已分析 因此 满足BCNF范式要求的模式分解 可能不是保持依赖分解 20 第三范式 3NF 给定关系模式r R 及函数依赖集F 若对F 中的所有函数依赖 R R 至少满足下列条件之一 是平凡函数依赖 即 是r R 的一个超码 即 包含R的全部属性 中的每个属性是r R 的候选码的一部分 则称r R 属于第三范式 记为r R 3NF 3NF与BCNF范式的区别在于第3个条件 21 放松之处 允许存在主属性对候选码的传递依赖和部分依赖 注意 3NF的第3个条件不要求 中的每个属性必须包含在r R 的一个候选码中 即 中的每个属性可以包含在r R 的不同候选码中 22 第三范式的目标是 去掉表中不依赖于主码的数据 也就是说 在满足第二范式的实体中 非主属性不能依赖于另一个非主属性 即所有的非主属性应该直接依赖于全部的主属性 即必须完全依赖 这是2NF的要求 并且彼此之间无相互依赖关系 即不能存在部分依赖 这是3NF的要求 换一句话说 非主属性不能包括它们自己的属性 如果属性不包括属性 则它们就是真正的实体 23 3NF范式判断举例 例1r R r A B C F A B B C r R 的候选码为A r R 3NF 且r R BCNF 例2r R r A B C F AB C C A r R 的候选码为AB或BC r R 3NF 但r R BCNF 例3r R r A B C F AB C BC A r R 的候选码为AB或BC r R 3NF 且r