一、函数依赖
1.1 什么是函数依赖
前面通过 ER 图设计的关系表中存在冗余，这些冗余产生的根源在于属性与属性之间存在着一定的语义关系，而在 ER 转换时没有考虑这些关系。
函数依赖（Functional Dependency, FD）是属性与属性之间最重要的一种关系。其形式化定义如下：
设 $R$ 是一个关系模式，$U$ 是 $R$ 上所有属性的集合，$X, Y \subseteq U$。若对于 $R$ 的任意一个当前关系 $r$ 中的任意两个元组 $t$ 和 $s$，只要 $t[X] = s[X]$，就蕴含 $t[Y] = s[Y]$，则称 $X$ 函数确定 $Y$，或 $Y$ 函数依赖于 $X$，记作 $X \to Y$。
直观理解：$X$ 能唯一决定 $Y$ 的取值。如果两个元组在 $X$ 上相同，它们在 $Y$ 上也一定相同。
例子：学号 $\to$ 学生姓名，课程号 $\to$ 课程名，学号+课程号 $\to$ 成绩。
函数依赖的存在本身就意味着有冗余的可能——例如同一门课被多个学生选修时，课程名、教师名、教师年龄等信息会随之重复出现多次。
1.2 函数依赖与基数关系
从一对一、一对多的角度看函数依赖：
- 若 $A$ 到 $B$ 是一对多（一个 $B$ 值对应唯一 $A$ 值），则 $B \to A$ 成立
- 若 $A$ 到 $B$ 是一对一，则 $A \to B$ 和 $B \to A$ 都成立
- 若 $A$ 到 $B$ 是多对多，则两个方向的函数依赖都不成立
1.3 逻辑蕴含
设有函数依赖集合 $F$ 和某个函数依赖 $X \to Y$。如果对于 $R$ 的每个满足 $F$ 的关系 $r$，也都满足 $X \to Y$，则称 $F$ 逻辑蕴含 $X \to Y$。
换言之：从已知的函数依赖集合 $F$ 中可以推导出新的函数依赖。
1.4 Armstrong 公理系统
Armstrong 公理是函数依赖推理的三条基本规则：
A1 自反律（Reflexivity）：若 $Y \subseteq X$，则 $X \to Y$。
证明：因为 $Y$ 是 $X$ 的子集，两个元组在 $X$ 上相同，自然在 $Y$ 上也相同（没有引入新属性）。
A2 增广律（Augmentation）：若 $X \to Y$ 在 $R$ 上成立，$Z \subseteq U$，则 $XZ \to YZ$ 在 $R$ 上也成立。
证明（反证法）：假设 $XZ \to YZ$ 不成立，则存在两个元组 $t, s$ 在 $XZ$ 上相同但在 $YZ$ 上不同。那么 $t$ 和 $s$ 要么在 $Y$ 上不同（与 $X \to Y$ 矛盾，因为它们在 $X$ 上相同），要么在 $Z$ 上不同（与假设 $t$ 和 $s$ 在 $XZ$ 上相同矛盾）。证毕。
A3 传递律（Transitivity）：若 $X \to Y$ 和 $Y \to Z$ 在 $R$ 上成立，则 $X \to Z$ 在 $R$ 上也成立。
证明（反证法）：假设存在两个元组 $t, s$ 在 $X$ 上相同但 $Z$ 上不同。由 $X \to Y$ 知它们在 $Y$ 上相同；再由 $Y \to Z$ 知它们在 $Z$ 上也相同，矛盾。
A4~A8 是常用附加规则，可从 A1~A3 推导得出：
- A4 合并律：若 $X \to Y$ 且 $X \to Z$，则 $X \to YZ$
- A5 分解律：若 $X \to YZ$，则 $X \to Y$ 且 $X \to Z$
A4 推导：由 $X \to Y$，两边增广 $X$：$XX \to XY$ 即 $X \to XY$；由 $Y \to Z$（但注意这里实际是利用 $X$ 也有 $X \to Z$，再增广可得更多，最后合并得到 $X \to YZ$）。
1.5 平凡与非平凡函数依赖
若 $Y \subseteq X$，则 $X \to Y$ 是平凡的（trivial），它没有带来任何新的属性和属性之间的关系。
若 $Y \not\subseteq X$，则称 $X \to Y$ 为非平凡的（non-trivial）。
平凡的函数依赖没有提供新信息——有 $X$ 就一定有 $X$ 的子集，这在逻辑上是必然成立的。
1.6 闭包
函数依赖集合的闭包 $F^{+}$：给定函数依赖集合 $F$，通过 Armstrong 公理能推导出的所有函数依赖构成的集合称为 $F$ 的闭包。
属性集的闭包 $X^{+}$：在函数依赖集合 $F$ 下，由 $X$ 能函数决定的所有属性的集合。
闭包的重要应用：判断两个函数依赖集合是否等价——如果两个 FD 集的闭包相同，则它们等价。
例题：设 $F = {A \to B, B \to C}$ 在关系模式 $R(ABC)$ 上，求 $F^{+}$ 和 $A^{+}$。
- $F^{+}$ 包含 43 个函数依赖：包括 $A \to A$、$A \to B$、$A \to C$（传递）、$A \to AB$、$A \to BC$、$A \to ABC$……以及所有平凡依赖
- $A^{+} = {A, B, C}$（因为 $A$ 可推出 $B$，$B$ 推出 $C$）
- $B^{+} = {B, C}$
定理 4.3：$X \to A_1A_2\ldots A_n$ 成立的充要条件是 $X \to A_i$（$i=1,\ldots,n$）每个都成立。
1.7 Armstrong 公理的性质
- 正确性（Soundness）：用推理规则从 $F$ 推导出的所有函数依赖都在 $F^{+}$ 中（不会推导出”错”的）
- 完备性（Completeness）：$F^{+}$ 中的每个函数依赖都可以通过 Armstrong 公理从 $F$ 推导出来
1.8 函数依赖与键
- 若 $X \to U$（$U$ 为全部属性），则 $X$ 是 $R$ 的一个超键（superkey）
- 若 $X \to U$ 且对 $X$ 的任何真子集都不成立，则 $X$ 是候选键（candidate key）
例子：在学号、姓名、课程号、成绩、老师名、老师年龄的模式中：
- {学号, 课程号} 是候选键（决定所有属性，且去掉任何一个都不行）
- {学号, 姓名, 课程号, 老师名} 是超键但不是候选键（去掉姓名、老师名仍能决定所有属性）
1.9 最小函数依赖集
最小函数依赖集（也称为最小覆盖 / canonical cover）是和原 FD 集等价的最精简集合。它需要满足：
- 闭包等价：两个 FD 集的闭包相同
- 右边最简：每个函数依赖的右边都是单个属性（如 $A \to BC$ 应拆为 $A \to B$ 和 $A \to C$）
- 无冗余 FD：去掉任何一条 FD，闭包会发生变化
- 左边最简：任何 FD 的左边没有冗余属性（删去任何一个左边属性都会改变闭包）
例题：$F = {A \to BC, B \to C, A \to B, AB \to C}$ 在 $ABC$ 上，求最小依赖集。
解：
- 右边拆为单属性：$A \to B, A \to C, B \to C, A \to B, AB \to C$
- 去重：$A \to B$ 重复，去掉一个，得 ${A \to B, A \to C, B \to C, AB \to C}$
- 去掉冗余：$A \to C$ 可由 $A \to B$ 和 $B \to C$ 推出，去掉；$AB \to C$ 同样可由 $A \to B, B \to C$ 推出，去掉
- 最终最小依赖集：${A \to B, B \to C}$
最小函数依赖集是后续第三范式构造算法的基础。
二、模式分解
2.1 为什么需要分解
解决关系表冗余的主要手段就是分解——把一张表分成多张表。
分解定义：设 $R$ 有关系模式，属性集为 $U$。令 $R_1, R_2, \ldots, R_k$ 是 $U$ 的子集，且 $\bigcup_{i=1}^{k} R_i = U$。用 $\rho = {R_1, R_2, \ldots, R_k}$ 代替 $R$ 的过程称为模式分解。
分解时属性集合不发生变化——我们没有抛弃任何属性，只是将它们分散到不同表中。
对于具体的关系 $r$：$r_i = \Pi_{R_i}(r)$（对每个子模式做投影）。
2.2 泛关系假设
泛关系假设（Universal Relation Hypothesis）：在数据库模式设计中，假设先存在一个包含所有属性的”泛关系”，再通过分解将其分成一个一个的小关系表。
- 有泛关系假设：分解后再连接回来，理论上能恢复原关系
- 无泛关系假设：表分别独立存在，连接时可能出现悬挂元组（dangling tuple）——某些元组在其他表中没有对应数据，连接后丢失
例如，某旁听学生在”听课记录表”中有选课记录，但不在”学生信息表”中。当两张表做连接查询时，该旁听学生的信息就会丢失——这就是悬挂元组（dangling tuple）的含义。
2.3 分解要关注的两个问题
- 无损分解（Lossless-join Decomposition）：分解后再连接回来，不丢失信息
- 保持函数依赖（Dependency Preservation）：分解后各子模式的函数依赖集与原来的等价
2.4 无损分解
定义：设 $\rho = {R_1, R_2, \ldots, R_k}$ 是 $R$ 的一个分解，若对 $R$ 中满足 $F$ 的每个关系 $r$ 都有：
\[r = \Pi_{R_1}(r) \bowtie \Pi_{R_2}(r) \bowtie \cdots \bowtie \Pi_{R_k}(r)\]则称 $\rho$ 相对于 $F$ 是无损连接分解。
在数据库的语境中，”信息丢失”并非指数据变少了，反而是指数据多出来了。分解后真正丢失的是约束信息——原来某条元组的存在对信息取值范围形成了约束。约束一旦丢失，连接回来就会产生多出”不合法的”元组。
例子：
- 表 $r(A,B,C) = {(1,1,1), (1,2,1)}$，分解为 $AB$ 和 $AC$：
- $\Pi_{AB}(r) = {(1,1), (1,2)}$，$\Pi_{AC}(r) = {(1,1)}$
- 连接回来：$(1,1) \bowtie (1,1) = (1,1,1)$，$(1,2) \bowtie (1,1) = (1,2,1)$
- 与原表相同，是无损的
- 表 $r(A,B,C) = {(1,4,1), (1,2,3)}$，同样分解为 $AB$ 和 $AC$：
- $\Pi_{AB}(r) = {(1,4), (1,2)}$，$\Pi_{AC}(r) = {(1,1), (1,3)}$
- 连接回来：产生 4 条元组 $(1,4,1), (1,4,3), (1,2,1), (1,2,3)$
- 比原来多了 $(1,4,3)$ 和 $(1,2,1)$，是有损的
2.5 $M_\rho(r)$ 及其性质
定义 $M_\rho(r) = \Pi_{R_1}(r) \bowtie \Pi_{R_2}(r) \bowtie \cdots \bowtie \Pi_{R_k}(r)$，即先投影再连接的结果。
性质：
- $r \subseteq M_\rho(r)$：原关系的每条元组拆开再连回来，仍然在结果中
- 幂等性：$\Pi_{R_i}(M_\rho(r)) = \Pi_{R_i}(r)$——再投影回去，各部分不变
可以通过”带子”的比喻来理解：把每条元组想象成一根带子，分解就是按一定位置将其裁成几段（可能有重叠部分）。这些片段来自同一根带子，公共部分相同，因此连接时能拼回原样。但如果两根不同的带子裁开后，小段的公共部分恰好相同，拼回时就会出错——这就是有损分解产生多余元组的原因。幂等性则意味着：每根小段在连接过程中并不会改变，再次裁开时，仍是原来的那些片段。
2.6 检验无损分解的矩阵方法
给定关系模式 $R(ABCD)$，分解 $\rho = {AB, BC, CD}$，函数依赖集 $F = {B \to A, C \to D}$：
- 构造初始矩阵：行为子模式，列为属性。若属性在子模式中，填 $a_j$（$j$ 为该属性列序号）；否则填 $b_{ij}$
| A | B | C | D | |
|---|---|---|---|---|
| AB | a1 | a2 | b13 | b14 |
| BC | b21 | a2 | a3 | b24 |
| CD | b31 | b32 | a3 | a4 |
-
根据 FD 修改：遍历每个 $X \to Y$，找 $X$ 上相同的行，使其 $Y$ 上的值也相同（用 $a$ 替代 $b$）
- $B \to A$：BC 和 AB 在 $B$ 上都是 a2，但 A 上 AB 是 a1、BC 是 b21，不满足 $B \to A$。将 b21 改为 a1
- $C \to D$：BC 和 CD 在 $C$ 上都是 a3，但 D 上 BC 是 b24、CD 是 a4。将 b24 改为 a4
-
判断：若最终表中有一整行全是 $a$（即 $a_1 a_2 \ldots a_n$），则是无损分解；否则是有损的。
本方法的核心思路：以某一行为基础，利用函数依赖一步步推断出其他属性值。如果最终能推断出一个包含所有属性完整值的”行”，说明可以通过连接恢复完整元组。
2.7 定理 4.7 与 4.8（无损分解的判定条件）
定理 4.7：设 $\rho = {R_1, R_2}$ 是 $R$ 的一个分解，$F$ 是 $R$ 上的函数依赖集。$\rho$ 相对于 $F$ 是无损分解的充要条件是：
\[(R_1 \cap R_2) \to (R_1 - R_2) \quad \text{或} \quad (R_1 \cap R_2) \to (R_2 - R_1)\]定理 4.8：若 $X \to Y$ 在 $R$ 上成立，且 $X \cap Y = \emptyset$，则分解 $\rho = {R - Y, XY}$ 是无损分解。
直观理解：把 $X$（两个子模式的交集部分）看作基础，利用函数依赖 $X \to Y$，从 $R_2$ 中的 $X$ 值可以唯一确定 $R_1$ 中 $Y$ 的值，从而无损地连接回去。
定理 4.8 是后续所有范式分解算法的核心——每一步分解都基于此定理来保证无损性。
2.8 保持函数依赖
投影：$F$ 在 $Z \subseteq U$ 上的投影 $\Pi_Z(F)$ 定义为 ${X \to Y \mid X \to Y \in F^{+} \text{ 且 } XY \subseteq Z}$。
保持函数依赖：分解 $\rho$ 称为保持函数依赖的，如果 $(\bigcup_{i=1}^{k} \Pi_{R_i}(F))^{+} = F^{+}$。
直观理解：分解后，原来所有的函数依赖信息都能在各子模式中”找到”——要么直接保留在某张表中，要么可以通过各表的 FD 推导出来。
例子：$F = {WNO \to WS, WNO \to WG}$，分解为 ${WNO, WS}$ 和 ${WNO, WG}$。两张表各保留一条 FD，合起来等价于原 FD 集，是保持依赖的。
2.9 综合实例：四种分解情况
设 $R(ABC)$，分解 $\rho = {AB, AC}$，在不同的函数依赖集下的表现：
| FD 集 | 是否无损 | 是否保持依赖 | 原因 |
|---|---|---|---|
| $A \to B$ | 无损 | 保持 | $A \to B$ 在 AB 表中保留，$A$ 在 AB 和 AC 的交集中 |
| $A \to C, B \to C$ | 无损 | 不保持 | $A \to C$ 在 AC 中保留，但 $B \to C$ 丢失（没有表同时含 $B$ 和 $C$） |
| $B \to A$ | 有损 | 保持 | $B \to A$ 在 AB 中保留，但从 AC 不能确定 $B$，连接时产生多余元组 |
| $B \to A, C \to B$ | 有损 | 不保持 | 从 AC 不能确定 $B$（因为没 BC），$C \to B$ 丢失 |
三、关系范式
3.1 范式概述
范式是评估关系模式”好坏”的标准，主要从冗余角度来评价。分为四个等级：
- 1NF：属性值都是不可再分的原子值
- 2NF：消除非主属性对候选键的部分函数依赖
- 3NF：消除非主属性对候选键的传递函数依赖
- BCNF：消除所有属性（包括主属性）对候选键的传递函数依赖
数据库设计的评价标准除了冗余以外，还涉及性能等因素，本章只关注冗余问题。冗余和查询效率有时是一对矛盾——表分得越细，冗余越少，但查询时需要更多的连接操作。
3.2 第一范式（1NF）
定义：关系模式中每个属性值都是不可再分的原子值，则属于第一范式。
违反 1NF 的例子：某人的电话号码字段包含两个号码（即属性值为集合），不满足 1NF。
修正方法：拆成两个独立的字段（如电话号码1、电话号码2），或拆成多行。
1NF 是关系数据库最基本的要求。
3.3 第二范式（2NF）
动机
考虑模式 $R(学号, 课程号, 成绩, 老师名, 老师地址)$，主键为 {学号, 课程号}。
冗余产生的原因：课程号 $\to$ 老师名 和 课程号 $\to$ 老师地址，即老师名和老师地址只依赖于主键的一部分（课程号），不需要整个主键来决定。
定义
- 完全函数依赖：若 $X \to Y$，且对 $X$ 的任何真子集 $X’$，$X’ \to Y$ 都不成立，则称 $Y$ 对 $X$ 是完全函数依赖。
- 部分函数依赖（局部依赖）：若 $X \to Y$，但存在 $X$ 的真子集 $X’$ 使得 $X’ \to Y$ 也成立，则称 $Y$ 对 $X$ 是部分函数依赖。
- 主属性：出现在任何候选键中的属性。
- 非主属性：不出现在任何候选键中的属性。
2NF 定义：若 $R \in 1NF$，且每个非主属性都完全函数依赖于 $R$ 的每个候选键，则 $R \in 2NF$。
分解方法
对于违反 2NF 的局部依赖 $W \to Z$（$W$ 是候选键的真子集，$Z$ 是非主属性），按定理 4.8 分解为 ${R-Z, WZ}$。
具体到上面例子：将 {课程号, 老师名, 老师地址} 分离为新表，剩余 {学号, 课程号, 成绩} 为另一张表。
3.4 第三范式（3NF）
动机
即使满足 2NF，仍可能存在冗余。考虑模式 $R(课程号, 老师名, 老师地址)$，候选键为 {课程号}。
- 课程号 $\to$ 老师名（完全依赖，没问题）
- 老师名 $\to$ 老师地址
于是 课程号 $\to$ 老师名 $\to$ 老师地址，形成了传递依赖。如果一位老师上多门课，他的地址会重复多次。
定义
传递函数依赖：若 $X \to Y$、$Y \to A$、$Y \not\to X$，且 $A \not\subseteq Y$，则称 $X \to A$ 是传递的。
3NF 定义：若 $R \in 1NF$，且每个非主属性都不传递依赖于 $R$ 的任何候选键，则 $R \in 3NF$。
注意：3NF 自然也是 2NF，因为部分依赖是传递依赖的特例。（$W \to X’ \to A$，其中 $W$ 是候选键，$X’$ 是真子集）
3NF 的等价判定
$R \in 3NF$ 的充要条件是：对 $R$ 中每个非平凡函数依赖 $X \to A$（$A$ 为单属性），至少满足以下之一：
- $A \subseteq X$（平凡依赖）
- $X$ 是 $R$ 的超键
- $A$ 是主属性
违反 3NF 的三种情况：
- $A$ 是非主属性，依赖候选键的一部分（实际上违反的是 2NF）
- $A$ 是非主属性，中间属性与键有相交但不属于键（标准 3NF 违反）
- $A$ 是非主属性，中间属性与键完全无交集（标准 3NF 违反）
分解方法
对于违反 3NF 的传递依赖（$X \to Z$，$Z$ 是非主属性且 $X$ 不是候选键），分解为 ${R-Z, XZ}$。
具体到上面例子：分解为 {课程号, 老师名} 和 {老师名, 老师地址}。
3.5 从最小依赖集构造 3NF（自底向上方法）
与前面”自顶向下逐层分解”不同，该方法从最小函数依赖集出发构造：
- 求函数依赖集合的最小依赖集 $F_m$
- 将 $F_m$ 中左边相同的函数依赖合并（如 $X \to Y$ 和 $X \to Z$ 合并为 $X \to YZ$）
- 每个合并后的 $X \to Y$ 产生一个关系模式 $R_i = XY$
- 如果这些关系模式中不包含原 $R$ 的任何候选键，则额外添加一个包含候选键的关系模式
这样得到的分解既是 3NF 的，也是无损的。
例题：$R(ABCDE)$，最小依赖集 $F_m = {A \to B, C \to D}$，候选键为 $ACE$。
- $F_m$ 的左边不同，各产生一个模式：$R_1 = AB$，$R_2 = CD$
- 候选键 $ACE$ 不在这两个模式中，单独添加：$R_3 = ACE$
- 最终分解：${AB, CD, ACE}$，无损且 3NF
3.6 BC 范式（Boyce-Codd Normal Form, BCNF）
动机
3NF 只要求非主属性不传递依赖。但如果主属性之间存在一对一的关系，也可能产生冗余。
经典例题：仓库(仓库名, 管理员, 物品名, 数量)
- 一个仓库有一个管理员，一个管理员只在一个仓库工作：仓库名 $\to$ 管理员，管理员 $\to$ 仓库名
- 候选键：{管理员, 物品名} 或 {仓库名, 物品名}
- 所有属性都是主属性，没有非主属性，所以它已经是 3NF
- 但仍存在冗余：仓库名和管理员之间的关联信息被重复存储
定义
BCNF 定义：若 $R \in 1NF$，且对 $R$ 中每个非平凡函数依赖 $X \to Y$，$X$ 都是 $R$ 的超键，则 $R \in BCNF$。
换言之：所有属性（不只是非主属性）都不能传递依赖于非超键的属性集。
BCNF $\Rightarrow$ 3NF，但反之不成立。
分解方法
对于违反 BCNF 的 $X \to Y$（$X$ 不是超键），分解为 ${R-Y, XY}$。
具体到仓库例子：分解为 {仓库名, 管理员} 和 {仓库名, 物品名, 数量}（或 {管理员, 物品名, 数量}）。
3.7 范式总结与实践建议
| 范式 | 解决的问题 | 关注点 |
|---|---|---|
| 1NF | 属性值原子性 | 基础要求 |
| 2NF | 部分依赖 | 非主属性必须完全依赖候选键 |
| 3NF | 传递依赖（非主属性） | 非主属性不传递依赖候选键 |
| BCNF | 所有传递依赖 | 任何 FD 的左边必须是超键 |
在实际应用中，第三范式通常是相对比较合适的水平。分解到 BCNF 有时会把关系分得过散，导致查询时需要频繁连接，降低性能。应根据应用系统中数据访问的特点来做权衡——经常一起访问的数据，适合保留在同一张表中。
四、多值依赖与第四范式
4.1 多值依赖的引入
即使达到 BCNF，仍可能存在冗余。考虑模式：
课程(课程名, 选修学生, 先导课程)
- C4 这门课有先导课程 C1、C2，有学生 S1、S2
- 为了保持完整信息，需要：S1-C4-C1, S1-C4-C2, S2-C4-C1, S2-C4-C2（4 条元组）
- S3 选 C6，C6 有 3 门先导课，S3 选 C6 的信息被重复了 3 次
原因：选修学生和先导课程是两个完全无关的信息，强行放在一起产生了笛卡尔积效应。
4.2 多值依赖的定义
定义 1：设 $U$ 是关系模式 $R$ 的属性集，$X, Y \subseteq U$，$Z = U - X - Y$。若对任意两个元组 $t_1(x, y_1, z_1)$ 和 $t_2(x, y_2, z_2)$ 在 $r$ 中，也存在元组 $t_3(x, y_1, z_2)$ 和 $t_4(x, y_2, z_1)$，则称 $X$ 多值决定 $Y$，记作 $X \to\to Y$。
直观理解：固定 $X$ 的值，$Y$ 和 $Z$ 的取值是彼此独立的——$Y$ 取什么值和 $Z$ 取什么值之间没有约束。
定义 2（等价表述）：若对 $r$ 中任意两个元组 $t$ 和 $s$ 满足 $t[X] = s[X]$，则存在元组 $u$ 使得：
- $u[X] = t[X] = s[X]$
- $u[Y] = t[Y]$
- $u[Z] = s[Z]$（其中 $Z = U - X - Y$）
4.3 多值依赖的推理规则
多值依赖和函数依赖一起，满足以下推理规则：
| 规则 | 内容 |
|---|---|
| FD-自反 | 若 $Y \subseteq X$，则 $X \to Y$ |
| FD-增广 | $X \to Y \Rightarrow XZ \to YZ$ |
| FD-传递 | $X \to Y, Y \to Z \Rightarrow X \to Z$ |
| MVD-互补 | $X \to\to Y \Rightarrow X \to\to (U - X - Y)$ |
| MVD-增广 | $X \to\to Y, V \subseteq W \Rightarrow XW \to\to YV$ |
| MVD-传递 | $X \to\to Y, Y \to\to Z \Rightarrow X \to\to (Z - Y)$ |
| FD→MVD | $X \to Y \Rightarrow X \to\to Y$（函数依赖是多值依赖的特例） |
MVD 传递性的证明思路（反证法）：假设 $X \to\to (Z-Y)$ 不成立，即存在 $t$ 和 $s$ 在 $X$ 上相同但不存在满足条件的 $u$。利用 $X \to\to Y$ 构造元组 $v$，再利用 $Y \to\to Z$ 构造元组 $w$。然后验证 $w$ 恰好满足 $u$ 的三个条件（在 $X$ 上与 $t$ 相同、在 $Z-Y$ 上与 $t$ 相同、在剩余部分与 $s$ 相同），从而导出矛盾。
4.4 第四范式（4NF）
若 $R \in 1NF$，且对 $R$ 中每个非平凡多值依赖 $X \to\to Y$，$X$ 都是 $R$ 的超键，则 $R \in 4NF$。
分解方法：将课程(课程名, 学生, 先导课程) 分解为：
- {课程名, 学生}（选课信息）
- {课程名, 先导课程}（课程先导信息）