如何求闭包

闭包就是由一个属性直接或间接推导出的所有属性的集合. 假设我们现在已知一张表的函数依赖集合 $F$, 想要求得该表的闭包.

1. 设最终将成为闭包的属性集是 $Y$, 把 $Y$ 初始化为 $X$.

2. 检查 $F$ 中的每一个函数依赖 $A \rightarrow B$, 如果属性集 $A$ 中所有属性均在 $Y$ 中, 而 $B$ 中有的属性不在 $Y$ 中, 则将其加入到 $Y$ 中.

3. 重复第二步, 直到没有属性可以添加到属性集 $Y$ 中为止.

   最后得到的 $Y$ 就是 $X^{+*}$.

如何求候选码

若关系中的某一属性组的值能唯一地标识一个元组, 则称该属性组为候选码.

1. 找出不在 $FD$ 右边出现的所有属性, 构成属性组 $X$. $X$ 一定会出现在任何候选码中.

2. 计算 $X$ 的闭包.

3. 如果 $X^+=U$, 则 $X$ 是唯一的候选码, 否则继续步骤 4.

4. 计算 $Y=U-X^+$​.

5. 对 $Y$ 的每个子集 $\alpha$, 检查 $X \alpha$ 是否为候选码(方法同2,3).

计算示例

给出 $R(A,B,C,D,E,G)$, $F\{D \rightarrow G, CD \rightarrow E, E \rightarrow D, A \rightarrow B\}$.

1. 找出不在 $FD$ 右边出现的所有属性, 构成属性组 $X$, $X$ 一定会出现在任何候选码中.

   $X = AC$

2. 计算 $X$ 的闭包

   $X^+ = (AC)^+=\{A,C,B\}$​

3. 如果 $X^+=U$, 则 $X$ 是唯一的候选码, 否则继续步骤 4.

   显然当前 $X^+$ 并不满足, 所以继续.

4. 计算 $Y=U-X^+$.

   $Y=\{D,E,G\}$​

5. 对 $Y$ 的每个子集 $\alpha$, 看 $X \alpha$ 是否为候选码(方法同步骤 2, 步骤 3).

   $(ACD)^+=\{A,C,D,B,G,E\}$ ✔️

   $(ACE)^+=\{A,C,E,B,D,G\}$ ✔️

   $(ACG)^+=\{A,C,G,B\}$ ✖️

   故候选码为 {ACD}, {ACE}. 包含在任何候选码中的属性称为主属性.

无损链接和函数依赖

无损连接性

判断两个表是否是无损链接, 其实是在判断它们内容是否等价.

1. 把分解的两个表(设为 $R_1$ 和 $R_2$)的交集找出来.

2. 判断这个交集是否为 $R_1$ 的超码或者是 $R_2$ 的超码.

   超码: 一个或多个属性的集合, 这些属性的组合可以使我们在一个实体集中唯一地标识一个实体.

保持依赖性

判断两个表是否有保持依赖, 其实是判断数据依赖上是否等价.

直接判断在原来的未被分解的表中的每个函数依赖的左右两边的属性是否都在同一个被分解的表中. 即 $R_1$ 中可以构成的所有推导 $F_1$, 和 $R_2$ 中可以构成的所有推导$F_2$, 是否满足 $F_1 \cup F_2 = F^+$​.

范式

第一范式(1NF)

在关系模式 $R$ ​中, 当且仅当所有属性只包含原子值, 即每个分量都是不可再分的数据项, 则满足 1NF.

第二范式(2NF)

当且仅当关系模式 $R$ ​满足 1NF, 且每个非键属性完全依赖于候选键时, 满足2NF. 即在满足 1NF 的基础上, 让所有属性都依赖于候选键.

例如: 已知候选码是 BC, 非主属性是 D, 函数依赖中除了 BC->D, 还有 B->D 或者 C->D, 该模式不符合 2NF.

第三范式(3NF)

当且仅当关系模式 $R$ 满足 1NF, 且 $R$ ​中没有非键属性传递依赖于候选键时, 满足 3NF. 即在 2NF 的基础上, 消除了所有属性对候选键的间接依赖, 让所有属性直接依赖于候选键.

贡献者

• dingyuqi

变更历史

最后更新于: 查看全部变更历史

• 55ecd-

  docs: update docs

  于 2024/11/21
• 69c20-

  docs: update docs

  于 2024/11/21
• 8c78b-

  docs: update docs

  于 2024/11/20
• 805e4-

  docs: add a new article

  于 2024/11/20