VII. Normal Forms

First Normal Form

• 第一范式(first normal form)：当且仅当该关系模式 $R$ 的所有属性的 域(domain) 都是 原子的(atomic)．

  • 称域是原子的，当且仅当域的元素都是不可分割的单元．典型反例：复合属性（set）、多值属性（list）、复杂数据类型．

  • 关系型数据库要求所有关系都是 1NF．

Functional Dependencies

• 函数依赖(functional dependency)

  • 定义（简单版）：如果某个属性集 $\alpha$ 可以决定另一个属性集 $\beta$ 的值，就称 $\alpha \rightarrow \beta$ 是一个函数依赖．

  • 定义（完整版）：对于一个关系模式 $R$，如果 $\alpha \in R$ 并且 $\beta \in R$ 则函数依赖 $\alpha \rightarrow \beta$ 定义在 $R$ 上，当且仅当：如果对于 $R$ 的任意关系 $r(R)$，其中的任意两个元组 $t_{1}$ 和 $t_{2}$，如果他们的 $\alpha$ 属性值相同，那么他们的 $\beta$ 属性值也相同（$t_{1}\lbrack\alpha\rbrack = t_{2}\lbrack\alpha\rbrack \Rightarrow t_{1}\lbrack\beta\rbrack = t_{2}\lbrack\beta\rbrack$）．

  • 所以函数依赖不仅仅是针对属性来说的，而需要考虑到每个属性的域．

  • 注意具体的说法:

• 函数依赖和键的关系：函数依赖实际上是键的概念的一种泛化．

  • $K$ 是关系模式 $R$ 的超键当且仅当 $K \rightarrow R$；

  • $K$ 是关系模式 $R$ 的候选键当且仅当 $K \rightarrow R$ 并且不存在 $\alpha \in K$ 满足 $\alpha \rightarrow R$．

  • 函数依赖能够表达键无法表达的约束．

• 平凡(trivial)依赖 与 非平凡(nontrivial)依赖：

  • 如果函数依赖能被所有关系所满足，则该函数依赖是平凡的．

  • 函数依赖 $\alpha \rightarrow \beta$ 是平凡的当且仅当 $\beta \subseteq \alpha$．（也就是说右边是左边的子集．）

• 函数依赖的闭包(closure of functional dependecies)：根据原始函数依赖集 $F$ 推导出的包含所有函数依赖的集合称为 $F$ 的闭包，记作 $F^{+}$．

• Armstrong 公理．

  • 自反律(reflexivity)：如果 $\beta \subseteq \alpha$，那么 $\alpha \rightarrow \beta$．——子集一定对自己函数依赖，这样的函数依赖称为 平凡的(trivial)．

  • 增补律(augmentation)：如果 $\alpha \rightarrow \beta$，那么 $\gamma\alpha \rightarrow \gamma\beta$．——进一步地，$\gamma\alpha \rightarrow \beta$．

  • 传递律(transitivity)：如果 $\alpha \rightarrow \beta$ 并且 $\beta \rightarrow \gamma$，那么 $\alpha \rightarrow \gamma$．

• Armstrong 公理是 完备的(complete)，仅通过三条 Armstrong 公理就可以推导出所有的函数依赖．

• Armstrong 公理的推论．

  • 合并律(union)：如果 $\alpha \rightarrow \beta$ 并且 $\alpha \rightarrow \gamma$，那么 $\alpha \rightarrow \beta\gamma$．

  • 分解律(decomposition)：如果 $\alpha \rightarrow \beta\gamma$，那么 $\alpha \rightarrow \beta$ 并且 $\alpha \rightarrow \gamma$．

  • 伪传递律(pseudotransitivity)：如果 $\alpha \rightarrow \beta$ 并且 $\gamma\beta \rightarrow \delta$，那么 $\alpha\gamma \rightarrow \delta$．

    • 证明：$\alpha \rightarrow \beta \Longrightarrow \alpha\gamma \rightarrow \beta\gamma \rightarrow \delta$．

• 函数闭包的计算方法：不断放进来即可，全都要写．

• 属性集的闭包(closure of attribute sets)：对于 $R$ 的属性 $\alpha$，定义其在函数依赖集 $F$ 下的属性集闭包为所有能通过 $F$ 约束下能被 $\alpha$ 确定的属性集合，记为 $\alpha^{+}$．

• 属性闭包的用途：

  • 进行函数依赖验证：要验证 $\alpha \rightarrow \beta$ 是否成立（即 $\alpha \rightarrow \beta$ 是否属于 $F^{+}$），只需检查 $\beta \subseteq \alpha^{+}$．

  • 计算函数依赖 $F$ 的闭包：对于每个 $\gamma \subseteq R$，求出 $\gamma^{+}$；然后对于每个 $\delta \subseteq \gamma^{+}$，输出函数依赖 $\gamma \rightarrow \delta$．

Canonical Cover

• 正则覆盖(canonical cover)：称依赖集 $F_{c}$ 是依赖集 $F$ 的正则覆盖当且仅当：

  • (1) $F_{c}$ 与 $F$ 可以互相逻辑推导得出．

  • (2) $F_{c}$ 中不存在包含无关属性的函数依赖．

  • (3) $F_{c}$ 中的每个函数依赖的左部都是唯一的．（如果有两个函数依赖的左部相同，可以直接把他们的右部合并．）

• 无关属性(extraneous attribute)：对于函数依赖集 $F$ 和其中的函数依赖 $\alpha \rightarrow \beta$

  • (1) 称属性 $A$ 在 $\alpha$ 中是无关的当且仅当 $A \in \alpha$，并且 $F$ 能逻辑推理出 $\left( F - \left\{ \alpha \rightarrow \beta \right\} \right) \cup \left\{ (\alpha - A) \rightarrow \beta \right\}$．

  • (2) 称属性 $B$ 在 $\beta$ 中是无关的当且仅当 $B \in \beta$，并且 $\left( F - \left\{ \alpha \rightarrow \beta \right\} \right) \cup \left\{ \alpha \rightarrow (\beta - B) \right\}$ 能逻辑推理出 $F$．

  • 注：在上述两种情形中，反向蕴含关系是显然成立的，因为后者属于是”更强的”函数依赖关系．

Algorithm: 求解正则覆盖

• 初始化 $F_{c} = F$．

• 循环直到 $F_{c}$ 没有修改：

  • 运用合并律进行合并：$\alpha \rightarrow \beta_{1},\alpha \rightarrow \beta_{2} \Longrightarrow \alpha \rightarrow \beta_{1}\beta_{2}$．（根据正则覆盖的第三条定义）．

  • 检查关系中的所有函数依赖，删除其中的无关属性（注意左右两侧的无关属性都需要检查）．

Problem: 练习卷1 T3

The functional dependency set $F = \{A \rightarrow B, B \rightarrow C, A \rightarrow CD, BD \rightarrow C\}$ holds on the relation $R(A,B,C,D,E)$.

What is the Canonical Cover of $F$?

(A) $F = \{A \rightarrow BCD, B \rightarrow C, BD \rightarrow C\}$

(B) $F = \{A \rightarrow BCD, B \rightarrow C\}$

(C) $F = \{A \rightarrow B, A \rightarrow D, B \rightarrow C\}$

(D) $F = \{A \rightarrow BD, B \rightarrow C\}$

Answer

D．易错选 B．

Decomposition

• 规范化(normalization) 的目标：

  • 对于不是”良好”范式的关系模式 $R$，需要将其分解为 $\left\{ R_{1},R_{2},\cdots,R_{n} \right\}$，满足：

    • 无损连接分解．

    • 依赖保持．

    • 每一个 $R_{i}$ 都属于”良好”范式，是 BCNF 或者 3NF，没有荣誉．

• 分解(decomposition)：设 $R$ 为关系模式，$R_{1}$ 和 $R_{2}$ 是 $R$ 的分解，即 $R = R_{1} \cup R_{2}$．

• 无损连接分解(lossless-join decomposition)：称分解是 无损的(lossless) 当且仅当对于所有关系模式 $R$ 上可能的关系 $r$，$\prod_{R_{1}}(r) \bowtie \prod_{R_{2}}(r) = r$ 都成立．

  • （充要条件）将 $R$ 分解成 $R_{1}$ 和 $R_{2}$ 是无损的，当且仅当 $\left\{ R_{1} \cap R_{2} \right\} \rightarrow R_{1}$ 或 $\left\{ R_{1} \cap R_{2} \right\} \rightarrow R_{2}$ 成立，即充要条件是分解后两个子模式的共同属性必须是 $R_{1}$ 或 $R_{2}$ 的超键．

• 依赖保持(dependency preserving)：一个分解是依赖保持的，当且仅当 $\left( F_{1} \cup F_{2} \cup \cdots F_{n} \right)^{+} = F^{+}$，其中 $F_{i}$ 是 $F^{+}$ 在 $R_{i}$ 上投影，即只保留属性全部在 $R_{i}$ 中出现过的函数依赖．

  • 换句话说，若只需检验分解后各独立关系上的函数依赖即可确保所有函数依赖成立，则该分解具有依赖保持性．

  • 换句话说，不需要将分解后的关系重新自然连接起来就可以验证所有原有函数依赖成立，则该分解具有依赖保持性．

Algorithm: 测试是否依赖保持

• 对于 $F$ 中的每一个函数依赖 $\alpha \rightarrow \beta$ 都进行检查．

• 检查方法为：初始右侧集为 $\text{result } = \alpha$，之后对于每一个 $F_{i}$ 都看能否推广 $\text{result}$，最后得到的 $\text{result}$ 如果是 $\beta$ 的超级则说明依赖 $\alpha \rightarrow \beta$ 得到了保持．

Boyce-Codd Normal Form

• BCNF 范式(Boyce-Codd Normal Form)：设关系模式 $R$ 和其上的函数依赖集 $F$ 满足 BCNF，当且仅当对于 $F^{+}$ 中的每个函数依赖 $\alpha \rightarrow \beta$，至少满足以下条件之一：(1) $\alpha \rightarrow \beta$ 是平凡的．(2) $\alpha$ 是 $R$ 的超键．

  • 换句话说，BCNF 中 对于所有非平凡的函数依赖 $\alpha \rightarrow \beta$，$\alpha$ 一定是 $R$ 的超键．

Algorithm: BCNF 测试

• 测试 $\alpha \rightarrow \beta$ 是否违反 BCNF．$\alpha \rightarrow \beta$ 不是 BCNF 违例当且仅当 $\alpha^{+}$ 包含 $R$ 的全部属性．

• 可在 $F$ 下判别 $R$ 是否违反 BCNF（而不需要做 $F^{+}$），但必须在 $F^{+}$ 中检查 $R$ 的分解式是否违反 BCNF．

Algorithm: BCNF 分解

• 假设存在关系模式 $R$，且 $(\alpha \rightarrow \beta) \in F^{+}$ 导致 BCNF 违例，则可将 $R$ 分解为：$\left( R - (\beta - \alpha) \right)$ 和 $(\alpha \cup \beta)$．

• 完整的分解流程：每次找到一个非平凡的、并且 $\alpha$ 不是超键（$\alpha^{+}$ does not contain $R_{i}$）的函数依赖 $\alpha \rightarrow \beta$ 进行分解．这里要求 $\alpha \cap \beta = \varnothing$，因为如果有重复的属性直接将其从 $\beta$ 中去掉即可．即令 $\text{result } ≔ \left( \text{result } - \left\{ R_{i} \right\} \right) \cup \left\{ \left( R_{i} - \beta \right) \right\} \cup \left\{ \alpha \cup \beta \right\}$．

$$\begin{aligned} 1.\quad & \mathit{result} \coloneqq \{R\}; \\ 2.\quad & \mathit{done} \coloneqq \mathrm{false}; \\ 3.\quad & \mathbf{while}\ (\neg\mathit{done})\ \mathbf{do} \\ 4.\quad & \qquad \mathbf{if}\ \text{there is a schema }R_i \in \mathit{result}\text{ that is not in BCNF} \\ 5.\quad & \qquad \mathbf{then}\ \mathbf{begin} \\ 6.\quad & \qquad\qquad \text{let }\alpha \rightarrow \beta\text{ be a nontrivial functional dependency that} \\ 7.\quad & \qquad\qquad \text{holds on }R_i\text{ such that }\color{red}{R_i \nsubseteq \alpha^{+}\text{ and }\alpha \cap \beta = \varnothing}; \\ 8.\quad & \qquad\qquad \color{red}{\mathit{result} \coloneqq \left(\mathit{result} - \{R_i\}\right) \cup \{R_i - \beta\}} \\ & \qquad\qquad\qquad\qquad \color{red}{{}\cup \{\alpha \cup \beta\};} \\ 9.\quad & \qquad \mathbf{end} \\ 10.\quad & \qquad \mathbf{else}\ \mathit{done} \coloneqq \mathrm{true}. \end{aligned}$$

Note: each $R_i$ is in BCNF, and decomposition is lossless-join.

• BCNF 分解不一定是依赖保持的！！！

无法依赖保持地进行 BCNF 分解的情况

考虑 $R = (J,K,L)$，$F = \left\{ JK \rightarrow L,L \rightarrow K \right\}$，候选键为 $JK$ 和 $JL$，但无论怎么分解都无法保证依赖保持性．

Third Normal Form

• 第三范式(third normal form)：设关系模式 $R$ 和其上的函数依赖集 $F$ 满足 3NF，当且仅当对于 $F^{+}$ 中的每个函数依赖 $\alpha \rightarrow \beta$，至少满足以下条件之一：(1) $\alpha \rightarrow \beta$ 是平凡的．(2) $\alpha$ 是 $R$ 的超键．(3) $\beta - \alpha$ 中的每个属性 $A$ 都包含在 $R$ 的候选键中（注：可能包含在 $R$ 的不同的候选键中）．

  • 换句话说，对于非平凡的函数依赖 $\alpha \rightarrow \beta$ 且 $\alpha \cap \beta = \varnothing$，如果 $\alpha$ 不是超键，那么 $\beta$ 的每个属性就在候选键中．

  • 3NF 相较于 BCNF 允许更多的冗余，但有点在于可以进行依赖保持的无损分解．

Example: 是 3NF 但是不是 BCNF

• 这里是 3NF 但不是 BCNF，并且 BCNF 也无法做到无损分解．

• 冗余的就是 $L \rightarrow K$ 这个关系，因为一个老师只上一门课，所以可以通过老师 $L$ 推出课程 $K$．

• 3NF 的测试是 NP Hard 的．

• 3NF 分解既是无损分解也是依赖保持的．

Algorithm: 3NF 分解

• 求出 $F$ 的正则覆盖 $F_{c}$．

• 对于 $F_{c}$ 中的每个函数依赖 $\alpha \rightarrow \beta$，创建一个关系模式 $R_{i} = \alpha \cup \beta$．

• 如果 $R$ 的所有候选键都不在任何一个 $R_{i}$ 中，则创建一个 $R_{i}$，其属性为 $R$ 的任意一个候选键．

Multivalued Dependencies

• 多值依赖(MVD)，设 $R$ 是一个关系模式，设 $\alpha \subseteq R$ 和 $\beta \subseteq R$，则多值依赖 $\alpha \rightarrow \rightarrow \beta$ 在 $R$ 上成立当且仅当在任何合法关系 $r$ 中，对于所有 $t_{1}\lbrack\alpha\rbrack = t_{2}\lbrack\alpha\rbrack$．那么在 $r$ 中存在元组 $t_{3}$ 和 $t_{4}$ 使得：$t_{1}\lbrack\alpha\rbrack = t_{2}\lbrack\alpha\rbrack = t_{3}\lbrack\alpha\rbrack = t_{4}\lbrack\alpha\rbrack$，$t_{3}\lbrack\beta\rbrack = t_{1}\lbrack\beta\rbrack$

Fourth Normal Form

• 如果关系是 4NF，那么他一定是 BCNF．

Algorithm: 4NF 分解

与 BCNF 分解类似：对于非平凡多值依赖 $\alpha \rightarrow \rightarrow \beta$ 在 $R_{i}$ 上成立，且 $\alpha \rightarrow R_{i}$ 不在 $D_{i}$ 中，并且 $\alpha \cap \beta = \varnothing$，则将 $R_{i}$ 分解为 $\alpha \cup \beta$ 和 $R_{i} - \beta$．