数据库原与理-5 关系数据理论 .ppt

2、子集有效性不同： 若函数依赖X →Y在R（U）上成立，则对于任何Y’属于Y，都有 X →Y’成立。 而多值依赖X →→ Y在R（U）上成立，却不能断言对于任何Y’属于Y，有X →→Y’成立。 5.2.8 4NF 定义5.10 若关系模式R（U，F）∈1NF，如果对于R的每个非平凡多值依赖X →→ Y（Y不包含于X），X都含有码，则称R（U，F）∈4NF。 实质上4NF消除了多值依赖。为什么？ 一个关系模式到了BCNF可能还有不合适的性质 WSC（仓库、管理员、物品）中，仓库的管理员与物品无关，存放的物品也与管理员无关； 每一管理员随物品增加而重复被存储，类似地，每一物品也随管理员增加而重复被存储，存在过度冗余； 三类异常同样存在。 可以通过分解方法将其分解为一组4NF 的关系模式 WSC分解为WS和WC两个关系模式即可使之达到4NF，解决上述问题 5.2.9 规范化小结 1NF：每个分量是不可分的数据项。 ∪ 2NF：非主属性完全函数依赖于码。 ∪ 3NF：非主属性即不部分依赖于码也不传递依赖于码。 ∪ BCNF：所有属性都不部分依赖于码也不传递依赖于码。所有决定因素(属性集)都包含码。 ∪ 4NF：所有非平凡的多值依赖都是函数依赖。 5.3 数据依赖的公理系统 逻辑蕴含： 定义5.11 对于关系模式RU，F，其任何一个关系r，若函数依赖X → Y都成立（即r中任意两元组s，t，若t[X]=s[X]，则t[Y]=s[Y]），则称函数依赖集F逻辑蕴含X→Y。 为了求得给定关系模式的码，为了从一组函数依赖求得蕴含的函数依赖，例如已知函数依赖集F，要问X→Y是否为F所蕴含，就需要一套推理规则，这组推理规则是1974年首先由Armstrong提出来的。它是关系模式分解算法的理论基础。 要求得给定关系模式的所有候选码对于关系模式的范式级别判定具有决定作用： 范式级别的判定需要知道关系模式的所有候选码； 有的范式级别还需确定主属性和非主属性，也需要知道所有候选码。 Armstrong 公理系统 A1 自反律 若Y ? X ? U，则X － Y为F所蕴含(给出平凡的函数依赖)。 A2 增广律 若X → Y为F所蕴含，且Z ? U，则XZ →YZ为F所蕴含。 A3 传递律 如X → Y及Y → Z为F 所蕴含，则X → Z为F所蕴含。 Armstrong公理的推论： 合并规则：若X → Y，X → Z，有X →YZ。 分解规则：由X →Y及Z包含于Y，有X → Z。 伪传递规则：若X → Y，WY → Z，有XW → Z。 根据合并规则和分解规则，得到一个重要事实： X → A1A2…AK成立的充分必要条件是X → Ai成立（i=1,2,…,k)。 F的闭包： 在关系模式R（U，F）中为F所逻辑蕴含的函数依赖的全体叫做F的闭包，记作F + 。 Armstrong公理是有效的，完备的： 有效性：由F出发根据Armstrong公理推导出来的每个函数依赖一定在F +中 。 有效性的证明书上定理5.1“Armstrong推理规则是正确的”可直接得证。 完备性： F + 中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来。 经典证明 定义5.13 XF +的定义 设F是属性集U上的一组函数依赖集，X ? U， XF + ＝ {A|X－A能由F根据Armstrong公理导出}。 引理5.2 设F为属性集U上的一组函数依赖，X，Y ? U，X－Y能否由F根据Armstrong公理导出的充分必要条件是Y ? XF + 算法5.1 求XF +的方法。 非常重要。 例1.P185 增加要求 求(AC) F + 令X(0)＝AC 计算X(1)=ACEB=ABCE 计算X(2)＝ABCDE 即得结果。 定义5.13,引理5.2和算法5.1非常重要，可用于求码。 如K F +=U, 而K’F + ！=U，即求得K为一候选码。 求码方法要点(自己的总结) 找出不出现在非平凡函数依赖右部的属性组X，它们一定包含于所有候选码。 求XF +，判断＝U？成立结束，否则转3。 (自底向上)扩展X的X’，求X’F +，判断＝U？直到所有情况找完为止。 应用举例，对书上P185例1，求所有候选码 要点： 不出现在任何函数依赖右部的只有A； 求AF+＝A； 扩展 AB，ABF+＝U； AC，ACF+＝U； AD，ADF+ ！＝U；（需再扩展） AE， AEF+ ！＝U；（需再扩展） 再扩展 ADE，ADEF+ ！＝U 要证明它首先解决如何判定一个函数依赖是否属于由F根据Armstrong公理推导出来的函数依赖的集合。如果能求出这个集合就很容易判断，但是求这样的集合是一个NP完全问题。所以