数字剪影

关系的分解

7 min read

Armstrong 公理系统

逻辑蕴涵

定义 / 解释

比如 A→B B→C 在关系模型 R<U,F> 中成立，可以得到 A→C 字 R 中也成立，所以称 F 逻辑蕴含 A→C。

闭包

定义 / 解释

在关系模型 R 中，F 所逻辑蕴涵的所有函数依赖叫做 F 的闭包，记为 。

某个属性集关于依赖集的闭包

定义 / 解释

即已有 X 这个属性集作为左部，通过依赖集 F 的所有函数依赖，可以推导出的所有函数依赖，称为 X 关于 F 的闭包，记为

例题

已知关系模型 R<U,F>，其中 U={A,B,C,D,E} F={AB→C,B→D,C→E,EC→B,AC→B}，求 。

算法：把 AB 作为左部，然后从 F 中找到左部是完全属于 AB 的，把对应的右部并到 AB 里，作为新的左部，重复直到不能再增加左部或者已经等于全集。

结果：=ABCDE

最小依赖集

例题

F={abd→e,ab→g,b→f,c→j,cj→i,g→h}

算法：

  1. 将右部有多个的拆开，比如 ab→cd 变成 ab→c,ab→d
  2. 尝试删除左侧的冗余函数依赖，具体操作是对于每个函数依赖 X→A，假设将该依赖删除，然后求 X 在剩下的依赖集中的闭包 ，如果 A 属于这个闭包，那么就可以删除。
  3. 尝试删除左侧的冗余属性，具体操作是对于剩下的每个有多个属性的函数依赖 X→A，对于每个属性，假设将该属性删除，然后求剩下的属性集在 F 中的闭包 ，如果 A 属于这个闭包，则可以删除。

结果：F={abd→e,ab→g,b→f,c→j,c→i,g→h}

求候选码

例题

已知关系模型 R<U,F>，其中 U=(A,B,C,D,E,G)，F={AB⇒C,CD⇒E,E⇒A.A⇒G}，求 R 的候选码。

算法：

  • 找出只在函数依赖左部出现的属性集 X，X 肯定是任意一个候选码的成员，因为只在左边出现，所以少了它肯定推不出全集 U。
  • 只在右部出现，肯定不属于任何一个候选码。
  • 其他的情况尝试组合求闭包，如果闭包是全集 U，那么就是候选码。

结果：

只在左边出现的是 B 和 D，所以确定了 BD，只在右边出现的是 G，所以排除 G，剩下 A，C，E。

先考虑一个的组合，ABD，BCD 和 BDE，三个的闭包都是全集 U，所以三个都是候选码，算法结束。

模式分解

判断是否无损连接

算法

  • 对于一个分解，有 k 个子集，n 个属性，建立一张 k 行 n 列的初始表，对于每一行也就是分解的每个子集，把该分解子集出现的属性对应的列写上 ，否则写上
  • 对于每一个依赖，找到左部属性对应的列，根据行的值分组，对于行的值相同的这些行，查看对应右部属性的列，如果这些格子里有 a 值，那把所有这些格子改成 a 值，如果没有，改成行最小的 b 值。如果某个 b 值改成 a 值，那么其他行 (不属于当前操作的行) 的相同 b 值也要改成 a 值。
  • 如果不变则停止，如果出现有一行为 a1 a2 … an，那么说明该连接为无损连接。

例题

参考

已知 R<U,F>，U={A,B,C,D,E}，F={A→C,B→C,C→D,DE→C,CE→A}，R 的一个分解为 R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，判断这个分解是否具有无损连接性。

  • 根据每个分解的属性，构造出初始表
  • 然后看第一个依赖 A→C，找到 A 对应的第一列，其中 1 2 5 行的值相等，找到 C 对应的第三列，对应格子没有 a 值，所以全部改成 。
  • 同理看第二个依赖，B→C，把 改成 。
  • 以此类推
  • 最后第三行有 a1 a2 a3 a4 a5，所以该分解具有无损连接性。

3NF 和保持函数依赖的分解

算法

  • F=F 的最小依赖集
  • ={不在 F 出现的属性}
  • U=U-
  • 若 F 中有函数依赖 X→A，使得 XA=U，那么分解就是 R 本身
  • 如果没有，将剩下的 F 按左部分组，得到 ，分解就是 {<,>，…} ∪ <,>

3NF 和保持函数依赖和具有无损连接性的分解

算法

  • 求出 3NF 和保持函数依赖的分解。
  • X 是 R 的码，让已有的分解∪上一个 {<X,>}。
  • 如果分解中有某个 属于 X，那么删掉该 ，如果 X 属于某个 ，那么删掉。

BCNF 和具有无损连接性的分解

算法

  • 类似递归的方法，首先判断自身是不是 BC 范式，如果是，无需分解。
  • 否则，找到当前关系 R 的主码，找到一个左边不含主码的依赖 X→A，设 U1=A，分解出去，剩下的 U2=U-{A} 作为一个关系模式，继续重复上面的步骤。
  • 根据 X→A 的选择的不同，得到的分解也是不同。

4NF 和具有无损连接性的分解

算法

  • 求出 BCNF 和具有无损连接性的分解。
  • 对于一个关系 R<U,F>，如果多值依赖 X⇒Y 成立，则分解 {R1<X,Y>,R2<X,Z>)} 具有无损连接性，其中 Z=U-X-Y。

Graph View