关系数据理论

问题的提出：为何需要关系数据理论？

在设计关系数据库时，我们常常面临选择：如何将现实世界的信息组织成合适的关系模式？同一个系统可以有多种设计方案，但不同的方案优劣差异很大。

核心问题：

1. 如何评价一个关系模式设计的好坏？
2. 如何设计出性能良好的关系模式？

「关系数据库的规范化理论」正是为了解决这两个问题而提出的。一个「好」的关系模式应该：

• 减少数据冗余：尽可能少地存储重复信息。
• 避免操作异常：避免在进行插入、删除、更新数据时出现问题。

不良设计的后果

如果关系模式设计不当，通常会导致以下几类问题，统称为操作异常（Anomalies）：

• 数据冗余（Redundancy）
• 更新异常（Update Anomaly）
• 插入异常（Insertion Anomaly）
• 删除异常（Deletion Anomaly）

不良模式设计实例分析

我们通过一个简化的学生选课场景来理解这些问题。假设有以下属性：

• Sno：学号
• Sdept：学生所在系
• Mname：系主任姓名
• Cno：课程号
• Grade：成绩

现实语义约束：

1. 一个学生只属于一个系。
2. 一个系有多名学生。
3. 一个系只有一名正职系主任。
4. 一个学生可选修多门课程，一门课程可被多名学生选修。
5. 一个学生修读一门课程只有一个成绩。

设计方案 1：单一关系模式

将所有属性放入一个关系模式 Student(Sno, Sdept, Mname, Cno, Grade)。

根据语义，我们有以下函数依赖（后续会详细定义）：

• Sno -> Sdept：学号确定系
• Sdept -> Mname：系确定系主任
• (Sno, Cno) -> Grade：学号和课程号确定成绩

该方案存在的问题：

1. 数据冗余：
   • 学生每次选课，其 Sdept 和 Mname 都会被存储一次。如果一个学生选了 10 门课，他的系和系主任信息就重复存储了 10 次。
   • 同一个系的所有学生的 Mname 信息都会重复。
   • 这不仅浪费存储空间，更重要的是为数据不一致埋下隐患。
2. 更新异常：
   • 如果某系更换了系主任，需要修改该系所有学生所有选课记录中的 Mname 值。如果遗漏了某些记录，就会导致数据不一致。
3. 插入异常：
   • 如果一个系（如新成立的「信息安全系」，系主任「王必成」）刚成立，还没有学生选课，我们无法将这个系及其主任的信息存入数据库。因为 (Sno, Cno) 是主码或候选码的一部分，不能为空，而此时没有 Sno 和 Cno。
   • 同样，如果一个学生刚入学，尚未选任何课程，也无法单独存储该学生的学号和系信息（如果 (Sno, Cno) 是主码）。
4. 删除异常：
   • 如果某个学生（如 S8）只选修了一门课，并且他是其所在系（如「人工智能」）的最后一名学生。当他毕业或退学，删除其选课记录时，可能会导致「人工智能」这个系及其系主任的信息从数据库中丢失。

设计方案 2：多个关系模式

将 Student 模式分解为三个关系模式：

• S(Sno, Sdept) ：学生信息，FD: Sno -> Sdept
• DEPT(Sdept, Mname)：系信息，FD: Sdept -> Mname
• SC(Sno, Cno, Grade)：选课信息，FD: (Sno, Cno) -> Grade

该方案的优点：

• 数据冗余减少：系主任姓名 Mname 只在 DEPT 表中存储一次。学生所在的系 Sdept 也只在 S 表中存储一次。
• 更新异常解决：更换系主任只需修改 DEPT 表中对应的一条记录。
• 插入异常解决：可以独立地在 DEPT 表中添加新系的信息，也可以在 S 表中添加新学生的信息，无需等待选课。
• 删除异常解决：删除 SC 表中的选课记录不会影响 S 表中的学生信息或 DEPT 表中的系信息。删除 S 表中的学生信息也不会影响 DEPT 表。

结论

方案 2 明显优于方案 1。产生这些差异的根本原因在于关系模式内部属性之间的依赖关系处理不当。

数据依赖

数据依赖（Data Dependency）是关系内部属性与属性之间的一种约束关系，是现实世界属性间相互联系的抽象，是数据内在的性质，体现了语义。

• 主要类型包括：函数依赖（Functional Dependency, FD）和多值依赖（Multi-Valued Dependency, MVD）。
• 不好的模式设计往往源于存在不合适的数据依赖。

核心思想：
规范化理论的目标就是通过模式分解（Schema Decomposition），将一个低级范式的关系模式转换为若干个高级范式的关系模式集合，以此来消除不合适的数据依赖，减少冗余和操作异常。

函数依赖

函数依赖

设 $R(U)$ 是一个属性集 $U$ 上的关系模式，$X, Y$ 是 $U$ 的子集。若对于 $R(U)$ 的任意一个可能的关系 $r$，$r$ 中不可能存在两个元组在 $X$ 上的属性值相等，而在 $Y$ 上的属性值不等，则称 $X$ 函数确定 $Y$ 或 $Y$ 函数依赖于 $X$，记作 $X \to Y$。

• $X$ 称为这个函数依赖的决定因素（Determinant）。
• $Y$ 称为这个函数依赖的依赖因素（Dependent）。

理解要点：

1. 语义层面：FD 是基于现实世界语义的约束，不是单从某个数据库快照（关系实例）推导出来的。例如，「学号确定姓名」（Sno -> Sname）是因为现实世界规定一个学号对应一个学生。
2. 实例的作用：关系实例（表中的数据）不能证明一个 FD 存在，但可以证伪一个 FD。如果在实例中发现存在 $X$ 值相同但 $Y$ 值不同的元组，则 $X \to Y$ 必然不成立。
3. 所有实例：一个 FD 成立，意味着它必须在关系模式 $R$ 的 所有 可能的关系实例上都得到满足。
4. 表示：
   • 如果 $X \to Y$ 且 $Y \to X$，则记为 $X \leftrightarrow Y$。
   • 如果 $Y$ 不函数依赖于 $X$，则记为 $X \nrightarrow Y$。

图形化理解：想象一个二维坐标系，$X$ 轴代表属性（集）$X$ 的值域，$Y$ 轴代表属性（集）$Y$ 的值域。

• 如果 $A \to B$ 成立，那么对于任意一个 $A$ 值，最多只能对应一个 $B$ 值（类似数学函数的定义）。
• 如果 $A \nrightarrow B$，那么至少存在一个 $A$ 值，对应了多个不同的 $B$ 值。

函数依赖的类型

非平凡函数依赖 vs. 平凡函数依赖

• 非平凡 FD：若 $X \to Y$，且 $Y \nsubseteq X$，则为非平凡 FD。例如 Sno -> Sdept。
• 平凡 FD：若 $X \to Y$，且 $Y \subseteq X$，则为平凡 FD。例如 (Sno, Cno) -> Sno。

平凡 FD 总是成立，没有实际意义。我们通常关注和讨论的是「非平凡 FD」。

完全函数依赖 vs. 部分函数依赖

设 $R(U)$ 中有 $X \to Y$，且 $X$ 是属性组合。

• 完全函数依赖（Fully Functional Dependency）：如果对于 $X$ 的任何真子集 $X'$，都有 $X' \nrightarrow Y$，则称 $Y$ 对 $X$ 完全函数依赖。记作 $X \xrightarrow{F} Y$。
  • 例：在 SC(Sno, Cno, Grade) 中，(Sno, Cno) -F> Grade（假设成绩不由学号或课程号单独决定）。
• 部分函数依赖（Partial Functional Dependency）：如果存在 $X$ 的一个真子集 $X'$，使得 $X' \to Y$，则称 $Y$ 对 $X$ 部分函数依赖。记作 $X \xrightarrow{P} Y$。
  • 例：在 SLC(Sno, Sdept, Sloc, Cno, Grade) 中，键为 (Sno, Cno)。因为 Sno -> Sdept，所以 Sdept 部分依赖于 (Sno, Cno)，即 (Sno, Cno) -P> Sdept。

传递函数依赖

设 $R(U)$ 中有 $X \to Y, Y \to Z$。

如果 $Y \nrightarrow X$（Y 不能反过来决定 X），且 $Z \nsubseteq Y$（Z 不被 Y 包含，即 $Y \to Z$ 是非平凡的），则称 $Z$ 对 $X$ 传递函数依赖。记为 $X \xrightarrow{\text{传递}} Z$。

例如在 Student(Sno, Sdept, Mname, ...) 中，Sno -> Sdept, Sdept -> Mname。假设 Sdept -/> Sno（一个系有多个学生），且 Mname 不是 Sdept 的一部分。则 Mname 传递依赖于 Sno。

为何区分依赖类型？

部分函数依赖和传递函数依赖是导致关系模式冗余和操作异常的主要原因之一。规范化过程很大程度上就是为了消除这些不良依赖。

码

码是关系数据库中用于唯一标识元组并建立关系间联系的关键概念，其定义与函数依赖密切相关。

码与相关概念

设关系模式为 $R(U, F)$，其中 $U$ 为属性集，$F$ 为函数依赖集。设 $K \subseteq U$。

• 超码：如果 $K \xrightarrow{F} U$（即 $K$ 能函数确定 $R$ 中的所有属性），则 $K$ 是 $R$ 的一个超码。
• 候选码：如果 $K$ 是一个超码，并且对于 $K$ 的任何真子集 $K'$，$K'$ 都不是超码（即 $K$ 是最小的超码），则 $K$ 是 $R$ 的一个候选码，简称码。
• 主码：如果一个关系模式有多个候选码，则选定其中一个作为主码。主码的选择通常基于简洁性、稳定性等因素。
• 全码：如果关系模式的所有属性构成其唯一的候选码，则称该码为全码。
• 主属性：包含在任何一个候选码中的属性。
• 非主属性或非码属性：不包含在任何候选码中的属性。
• 外码：关系模式 $R$ 中的属性（或属性组）$X$ 不是 $R$ 的码，但 $X$ 是另一个关系模式 $S$ 的主码（或候选码），则称 $X$ 是 $R$ 的外码。外码用于建立和强制关系之间的联系（参照完整性）。

示例：

• S(Sno, Sdept)：Sno 是候选码（也是主码）。Sno 是主属性，Sdept 是非主属性。
• SC(Sno, Cno, Grade)：(Sno, Cno) 是候选码（也是主码）。Sno, Cno 是主属性，Grade 是非主属性。
• DEPT(Sdept, Mname)：Sdept 是候选码（也是主码）。Sdept 是主属性，Mname 是非主属性。
• 在 SC 中，Sno 可以是参照 S 表主码 Sno 的外码。
• Student(Sno, Sname, Ssex, Sage, Sdept)，如果规定 Sno 唯一，Sname 也唯一（不允许重名）。
  • 候选码：Sno, Sname。
  • 可选 Sno 为主码。
  • 主属性：Sno, Sname。
  • 非主属性：Ssex, Sage, Sdept。

规范化

规范化是利用形式化的方法（基于函数依赖等），将关系模式分解，使其达到某种「良好」的标准（范式），从而减少数据冗余和操作异常的过程。

范式（Normal Form, NF）

范式是衡量关系模式「良好」程度的标准。不同级别的范式对模式中允许存在的函数依赖有不同的要求。

主要范式（基于 FD）：

• 第一范式（1NF）：关系模式 $R$ 的所有属性都是原子的（不可再分的）。这是关系模型的基本要求。
• 第二范式（2NF）：在 1NF 基础上，消除非主属性对候选码的部分函数依赖。
• 第三范式（3NF）：在 2NF 基础上，消除非主属性对候选码的传递函数依赖。
• BCNF(Boyce-Codd Normal Form)：在 3NF 基础上，消除任何属性（包括主属性）对码的部分依赖和传递依赖。更严格地说，要求所有函数依赖的决定因素必须包含候选码（即决定因素必须是超码）。

范式间的关系：

$$\text{BCNF} \subset \text{3NF} \subset \text{2NF} \subset \text{1NF}$$

• 满足高一级范式的关系模式必定满足低一级范式。
• 满足低一级范式的关系模式不一定满足高一级范式。

规范化过程：通过模式分解（将一个关系模式分解为多个关系模式），逐步将关系模式从低级范式提升到高级范式。

第一范式（1NF）

定义

如果一个关系模式 $R$ 的所有属性域都是原子的，即每个属性值都是不可再分的基本数据项，则称 $R$ 属于第一范式。

1NF 是关系模型的最低要求，非 1NF 的数据库模式不能称为关系数据库。

满足 1NF 只是基础，并不能保证模式是「好」的，如前面分析的 Student(Sno, Sdept, Mname, Cno, Grade) 就满足 1NF，但存在严重问题。

第二范式（2NF）

定义

若关系模式 $R \in \text{1NF}$，并且每一个非主属性都完全函数依赖于 $R$ 的任何一个候选码，则称 $R \in \text{2NF}$。

核心要求：消除非主属性对码的部分依赖。

检查步骤：

1. 找出 $R$ 的所有候选码。
2. 找出 $R$ 的所有非主属性。
3. 检查每个非主属性是否对每个候选码都存在部分依赖。如果存在任何一个非主属性对任何一个候选码的部分依赖，则 $R \notin \text{2NF}$。

示例：关系模式 SLC(Sno, Sdept, Sloc, Cno, Grade)，候选码为 (Sno, Cno)。

• 非主属性：Sdept, Sloc, Grade。
• 函数依赖：(Sno, Cno) -> Grade, Sno -> Sdept, Sdept -> Sloc（假设学生住处由所在系决定，即一个系的学生住一起）, Sno -> Sloc（由前两个传递得到）。
• 检查：
  • Grade 完全依赖于 (Sno, Cno)（假设）。
  • Sdept 依赖于 Sno，而 Sno 是 (Sno, Cno) 的真子集，所以 Sdept 部分依赖于 (Sno, Cno)。
  • Sloc 依赖于 Sno，所以 Sloc 部分依赖于 (Sno, Cno)。
• 结论：SLC 不属于 2NF。

不满足 2NF 会导致由部分依赖引起的冗余和操作异常（如 SLC 例子中 Sdept, Sloc 的冗余存储、更新/插入/删除异常）。

• 解决方法：投影分解。将 SLC 分解为：
  • SC(Sno, Cno, Grade)：候选码 (Sno, Cno)，非主属性 Grade 完全依赖于码，满足 2NF
  • SL(Sno, Sdept, Sloc)：候选码 Sno，非主属性 Sdept, Sloc 完全依赖于码，满足 2NF

2NF 的局限性

分解到 2NF 后，虽然消除了非主属性对码的部分依赖，但仍可能存在非主属性对码的传递依赖，导致问题。例如，分解后的 SL 仍可能存在冗余（如果 Sdept -> Sloc）。

第三范式（3NF）

定义

设关系模式 $R \in \text{1NF}$。若 $R$ 中不存在这样的候选码 $X$、属性组 $Y$ 及非主属性 $Z$ ($Z \nsubseteq Y$)，使得 $X \to Y, Y \to Z$ 成立，且 $Y \nrightarrow X$（即 $Y$ 不是超码），则称 $R \in \text{3NF}$。

核心要求：消除非主属性对码的传递依赖。

• 等价地说：如果 $R \in \text{2NF}$，且没有任何非主属性传递依赖于任何候选码，则 $R \in \text{3NF}$。
• 更简洁的判断（对 2NF 模式）：检查是否存在非主属性 $Z$ 通过另一个（或一组）非主属性 $Y$ 传递依赖于码 $X$。

检查步骤（基于 2NF）：

1. 确认 $R \in \text{2NF}$。
2. 找出 $R$ 的所有候选码和非主属性。
3. 检查是否存在非主属性 $Z$ 传递依赖于某个候选码 $X$（即存在 $X \to Y, Y \to Z$，其中 $Y$ 本身不是超码，且 $Z$ 是非主属性）。如果存在，则 $R \notin \text{3NF}$。

示例：上面得到的关系模式 SL(Sno, Sdept, Sloc)，候选码 Sno。

• 非主属性：Sdept, Sloc。
• 函数依赖：Sno -> Sdept, Sdept -> Sloc。假设 Sdept -/> Sno。
• 检查：Sno -> Sdept, Sdept -> Sloc，且 Sdept 不是候选码（超码），Sloc 是非主属性。存在非主属性 Sloc 对码 Sno 的传递依赖。
• 结论：SL 不属于 3NF。

不满足 3NF 会导致由传递依赖引起的冗余和操作异常。

• 解决方法：投影分解。将 SL 分解为：
  • SD(Sno, Sdept)：候选码 Sno，满足 3NF
  • DL(Sdept, Sloc)：候选码 Sdept，满足 3NF

此时，原 SLC 模式最终分解为 SC(Sno, Cno, Grade), SD(Sno, Sdept), DL(Sdept, Sloc)。这三个模式都达到了 3NF。

3NF 的改进

达到 3NF 后，基本消除了由非主属性引起的部分依赖和传递依赖，大大改善了模式质量。但在某些特殊情况下，3NF 仍可能存在冗余和异常，特别是当依赖关系涉及到主属性时。

BCNF(Boyce-Codd Normal Form)

BCNF 是修正的第三范式，提出了更强的约束。

定义

设关系模式 $R \in \text{1NF}$。若对于 $R$ 中每个非平凡的函数依赖 $X \to Y$（其中 $Y \nsubseteq X$），$X$ 都必定包含 $R$ 的某个候选码（即 $X$ 必须是 $R$ 的一个超码），则称 $R \in \text{BCNF}$。

核心要求：任何函数依赖的决定因素都必须是超码。

与 3NF 的关系：

• BCNF 必定是 3NF。
• 3NF 不一定是 BCNF。
• 区别在于：3NF 允许非主属性被非超码的属性（组）决定（只要不是传递依赖），而 BCNF 要求任何属性（包括主属性）都不能被非超码的属性（组）决定。

导致 3NF 但非 BCNF 的情况通常发生在：

1. 存在多个候选码。
2. 这些候选码有重叠属性。
3. 存在一个函数依赖，其决定因素是候选码的一部分（但不是超码），且依赖因素也是主属性。

示例 1：仓库管理

关系模式 Warehouse(仓库名, 管理员, 物品名, 数量)

• 语义：
  • 一个仓库可有多个管理员，一个管理员只在一个仓库工作（管理员 -> 仓库名）。
  • 一个仓库可存放多种物品，一种物品可存放于多个仓库。
  • 对于一个仓库中的特定物品，由唯一指定的管理员负责，且有确定数量（(仓库名, 物品名) -> 管理员, (仓库名, 物品名) -> 数量）。
• 函数依赖：管理员 -> 仓库名, (仓库名, 物品名) -> 管理员, (仓库名, 物品名) -> 数量。
• 候选码：(仓库名, 物品名) 和 (管理员, 物品名)。
• 主属性：仓库名, 管理员, 物品名。非主属性：数量。
• 检查 3NF：
  • 数量 完全依赖于两个候选码，没有部分依赖或传递依赖。满足 3NF。
• 检查 BCNF：
  • FD 管理员 -> 仓库名。决定因素 管理员 不是超码（它不能决定所有属性，如 物品名 和 数量）。
• 结论：Warehouse 属于 3NF，但不属于 BCNF。

仍存在冗余（管理员和仓库名的配对可能重复）和操作异常（如更换仓库管理员可能需要修改多条记录）。

• 解决方法：分解为 BCNF。
  • R1(管理员, 仓库名)：FD: 管理员 -> 仓库名，码 管理员，满足 BCNF
  • R2(管理员, 物品名, 数量)：FD: (管理员, 物品名) -> 数量，码 (管理员, 物品名)，满足 BCNF

示例 2：学生-教师-课程

关系模式 STJ(S, T, J)（S: 学生, T: 教师, J: 课程）

• 语义：
  • 每个教师只教一门课（T -> J）。
  • 每门课有若干教师。
  • 一个学生选修一门课，有唯一对应的教师（(S, J) -> T）。
  • 一个学生跟一个老师，也确定了课程（(S, T) -> J，由前两个 FD 可推导）。
• 函数依赖：T -> J, (S, J) -> T。
• 候选码：(S, J) 和 (S, T)。
• 主属性：S, T, J。没有非主属性。
• 检查 3NF：由于没有非主属性，自动满足 3NF。
• 检查 BCNF：
  • FD T -> J。决定因素 T 不是超码（不能决定 S）。
• 结论：STJ 属于 3NF，但不属于 BCNF。

解决方法：分解为 BCNF。

• TJ(T, J)：FD: T -> J，码 T，满足 BCNF
• ST(S, T)：无非平凡 FD，码 (S, T)，满足 BCNF

BCNF 的意义

如果一个关系数据库中的所有关系模式都达到了 BCNF，那么在函数依赖的范畴内，可以说模式已经实现了彻底的分解，达到了最高的规范化程度，从理论上消除了由函数依赖引起的插入和删除异常以及更新异常。

Armstrong 公理系统与函数依赖理论

在关系数据库理论中，函数依赖的推理是进行模式分析和优化的基础。Armstrong 公理系统（Armstrong's Axiom System）提供了一套形式化的规则，用于从已知的函数依赖集合中推导出所有逻辑上被蕴涵的函数依赖。

逻辑蕴涵与函数依赖集的闭包

逻辑蕴涵

设 $F$ 是关系模式 $R(U)$ 上的一个函数依赖集。如果对于 $R$ 的任何一个满足 $F$ 的关系实例 $r$，函数依赖 $X \to Y$ 也都在 $r$ 中成立，则称 $F$ 逻辑蕴涵 $X \to Y$，记作 $F \models X \to Y$。

• 这意味着，只要 $F$ 中的所有函数依赖都得到满足，那么 $X \to Y$ 也必然得到满足。
• 「$F$ 逻辑蕴涵 $X \to Y$」 也可以描述为「$X \to Y$ 可以从 $F$ 出发根据 Armstrong 公理推导得到」。

函数依赖集的闭包（$F^+$）

对于给定的函数依赖集 $F$，所有被 $F$ 逻辑蕴涵的函数依赖的集合称为 $F$ 的闭包（closure of F），记为 $F^+$。

$$F^+ = \{ X \to Y \mid F \models X \to Y \}$$

计算 $F^+$ 本身可能非常复杂（NP 问题），因为它可能包含大量的函数依赖。

Armstrong 公理系统

Armstrong 公理系统^[1]包含三条基本规则和若干条可以由基本规则推导出来的扩充规则。该系统是有效且完备的，这意味着：

• 有效性（sound）：任何从 $F$ 使用 Armstrong 公理推导出的函数依赖 $X \to Y$，都必然满足 $F \models X \to Y$（即 $X \to Y \in F^+$）。
• 完备性（complete）：任何满足 $F \models X \to Y$ 的函数依赖（即 $X \to Y \in F^+$），都可以从 $F$ 使用 Armstrong 公理推导出来。

基本推理规则

设关系模式为 $R(U, F)$，$X, Y, Z, W$ 是 $U$ 的子集。

1. A1 自反律：若 $Y \subseteq X \subseteq U$，则 $X \to Y$ 被 $F$ 所蕴涵。

   • 解释：如果属性集 $Y$ 是属性集 $X$ 的一部分，那么 $X$ 的值自然能确定 $Y$ 的值。这通常产生平凡函数依赖。自反律的使用不依赖于 $F$ 中已有的函数依赖。
   • 证明：对 $R(U,F)$ 的任一关系 $r$ 中的任意两个元组 $t_1, t_2$，若 $t_1[X] = t_2[X]$。因为 $Y \subseteq X$，所以 $t_1[Y]$ 必然等于 $t_2[Y]$。故 $X \to Y$ 成立。

2. A2 增广律：若 $F \models X \to Y$ 且 $Z \subseteq U$，则 $F \models XZ \to YZ$。 ($XZ$ 表示 $X \cup Z$)

   • 解释：如果在 $X$ 的基础上增加一些属性 $Z$ 作为决定因素，那么在 $Y$ 的基础上对应增加相同的属性 $Z$ 后，依赖关系依然成立。
   • 证明：设 $X \to Y$ 为 $F$ 所蕴涵。对任意元组 $t_1, t_2$，若 $t_1[XZ] = t_2[XZ]$，则 $t_1[X] = t_2[X]$ 且 $t_1[Z] = t_2[Z]$。因为 $X \to Y$，所以 $t_1[Y] = t_2[Y]$。因此 $t_1[YZ] = t_1[Y] \cup t_1[Z] = t_2[Y] \cup t_2[Z] = t_2[YZ]$。故 $XZ \to YZ$ 成立。

3. A3 传递律：若 $F \models X \to Y$ 且 $F \models Y \to Z$，则 $F \models X \to Z$。

   • 解释：函数依赖关系可以像链条一样传递。
   • 证明：设 $X \to Y$ 和 $Y \to Z$ 为 $F$ 所蕴涵。对任意元组 $t_1, t_2$，若 $t_1[X] = t_2[X]$。因为 $X \to Y$，所以 $t_1[Y] = t_2[Y]$。又因为 $Y \to Z$，所以 $t_1[Z] = t_2[Z]$。故 $X \to Z$ 成立。

扩充推理规则

由基本规则可以推导出以下常用的扩充规则：

1. 合并规则：若 $X \to Y$ 且 $X \to Z$，则 $X \to YZ$。
2. 分解规则：若 $X \to Y$ 且 $Z \subseteq Y$，则 $X \to Z$。
   • 证明：
     1. $X \to Y$（已知）
     2. $Y \to Z$（因 $Z \subseteq Y$，由 A1 自反律）
     3. $X \to Z$（由 1, 2 和 A3 传递律）
3. 伪传递规则：若 $X \to Y$ 且 $WY \to Z$，则 $XW \to Z$。
   • 证明：
     1. $X \to Y$（已知）
     2. $WY \to Z$（已知）
     3. $XW \to YW$（由 1 和 A2 增广律，用 $W$ 增广 $X \to Y$）
     4. $XW \to Z$（由 3, 2 和 A3 传递律）

$X \to A_1 A_2 \dots A_k$ 成立的充分必要条件是 $X \to A_i$ 对所有的 $i=1, 2, \dots, k$ 都成立。

• 该引理可以由合并规则（证明 $\implies$ 方向）和分解规则（证明 $\impliedby$ 方向）得到。

属性集的闭包

直接计算 $F^+$ 是困难的。一个更实用的方法是计算属性集 $X$ 关于 $F$ 的闭包，记为 $X_F^+$（或简写为 $X^+$ 当 $F$ 明确时）。

属性集闭包（$X_F^+$）

在关系模式 $R(U,F)$ 中，属性集 $X \subseteq U$ 关于函数依赖集 $F$ 的闭包 $X_F^+$ 是指所有能被 $X$ 通过 $F$ 和 Armstrong 公理函数确定的属性的集合。

$$X_F^+ = \{ A \mid X \to A \text{ 可以由 } F \text{ 根据 Armstrong 公理导出，且 } A \in U \}$$

等价地，$X_F^+ = \{ A \mid A \in U \text{ 且 } F \models X \to A \}$。

$F \models X \to Y$ 成立的充分必要条件是 $Y \subseteq X_F^+$。

这意味着，要判断 $X$ 是否函数确定 $Y$，我们只需要计算 $X_F^+$，然后检查 $Y$ 是否是 $X_F^+$ 的子集。

计算属性集闭包的算法

• 输入：属性集 $X \subseteq U$，函数依赖集 $F$。
• 输出：$X_F^+$。

1. 初始化：令 $X^{(0)} = X$。令 $i=0$。
2. 循环计算：$X^{(i+1)} = X^{(i)} \cup \{ A \mid \exists V \to W \in F, V \subseteq X^{(i)} \land A \in W \land A \notin X^{(i)} \}$。
   • 更简洁的写法：$X^{(i+1)} = X^{(i)} \cup \bigcup \{ W \mid \exists V \to W \in F \land V \subseteq X^{(i)} \}$
3. 终止条件：如果 $X^{(i+1)} = X^{(i)}$ 或者 $X^{(i+1)} = U$，则 $X_F^+ = X^{(i+1)}$，算法终止。
4. 否则，令 $i = i+1$，返回步骤 2。

属性集闭包计算示例

已知关系模式 $R(U,F)$，其中 $U = \{A, B, C, D, E\}$，
$F = \{AB \to C, B \to D, C \to E, EC \to B, AC \to B\}$。求 $(AB)_F^+$。

1. $X^{(0)} = AB$
2. $i=0$:
   • $AB \to C \in F$ 且 $AB \subseteq X^{(0)}$，将 $C$ 加入。$X^{(1)} = ABC$。
   • $B \to D \in F$ 且 $B \subseteq X^{(0)}$ (因为 $AB \supseteq B$)，将 $D$ 加入。$X^{(1)} = ABCD$。
3. $X^{(1)} = ABCD \ne X^{(0)}$。
4. $i=1$:
   • $C \to E \in F$ 且 $C \subseteq X^{(1)}$，将 $E$ 加入。$X^{(2)} = ABCDE$。
5. $X^{(2)} = ABCDE = U$，算法终止。

所以，$(AB)_F^+ = ABCDE$。

函数依赖集的覆盖与等价

函数依赖集的覆盖与等价

• 覆盖（Cover）：如果函数依赖集 $F$ 能够逻辑蕴涵函数依赖集 $G$ 中的所有函数依赖（即 $G \subseteq F^+$），则称 $F$ 覆盖 $G$。
• 等价（Equivalent）：如果两个函数依赖集 $F$ 和 $G$ 的闭包相等（即 $F^+ = G^+$），则称 $F$ 与 $G$ 等价，记为 $F \equiv G$。

$F \equiv G$ 的充分必要条件是 $F$ 覆盖 $G$ 且 $G$ 覆盖 $F$（即 $F \subseteq G^+$ 且 $G \subseteq F^+$）。

最小函数依赖集（最小覆盖）

为了简化函数依赖集并进行有效的模式分解，我们通常需要找到一个与原函数依赖集等价的、且尽可能简化的版本，称为最小函数依赖集或最小覆盖。

最小函数依赖集

一个函数依赖集 $F$ 是最小的，如果它满足以下三个条件：

1. 右部单一性：$F$ 中每个函数依赖 $X \to Y$ 的右部 $Y$ 都只包含一个属性。即形如 $X \to A$。
2. 左部无冗余属性：$F$ 中不存在函数依赖 $X \to A$，使得 $X$ 中有某个真子集 $Z \subset X$ 满足 $(F - \{X \to A\}) \cup \{Z \to A\} \equiv F$。也就是说，对于 $F$ 中的任一 $X \to A$，不存在 $X$ 的真子集 $Z$ 使得 $Z \to A$ 能由 $F$ 导出（或者更准确地说，不能用 $Z \to A$ 替换 $X \to A$ 而保持等价性，除非 $X \to A$ 本身是多余的）。这意味着 $X$ 的每个属性都是必需的。
3. 无冗余依赖：$F$ 中不存在函数依赖 $X \to A$，使得 $F - \{X \to A\} \equiv F$。也就是说，每个函数依赖都是必需的。

条件 1（右部单一性）主要是为了方便后续条件的检查。条件 2 确保决定因素中没有不必要的属性。条件 3 确保整个函数依赖本身不是由集合中其他依赖推导出来的。一个给定的 $F$ 可能有多个不等价的最小覆盖。

计算最小覆盖的算法

给定函数依赖集 $F$，计算其最小覆盖 $F_m$ 的步骤如下：

1. 分解右部：将 $F$ 中所有形如 $X \to Y_1 Y_2 \dots Y_k$ 的函数依赖替换为一组函数依赖 $X \to Y_1, X \to Y_2, \dots, X \to Y_k$。得到 $F'$。
2. 消除左部冗余属性：对 $F'$ 中的每个函数依赖 $X \to A$ 和 $X$ 中的每个属性 $B \in X$：
   计算 $(X - \{B\})_{F'}^+$（即在当前整个 $F'$ 集合下计算属性闭包）。如果 $A \in (X - \{B\})_{F'}^+$，则用 $(X - \{B\}) \to A$ 替换 $F'$ 中的 $X \to A$。此步骤可能需要重复进行，直到没有左部冗余属性。
3. 消除冗余依赖：对处理后的 $F'$ 中的每个函数依赖 $X \to A$：
   计算 $X_{(F' - \{X \to A\})}^+$（即在去掉当前 FD 后，用剩余 FD 计算闭包）。如果 $A \in X_{(F' - \{X \to A\})}^+$，则从 $F'$ 中移除 $X \to A$。
   最终得到的 $F'$ 就是一个最小覆盖 $F_m$。

最小覆盖计算

设 $F = \{A \to B, B \to A, AB \to C\}$。

1. 分解右部：$F_0 = \{A \to B, B \to A, AB \to C\}$（已满足）。
2. 消除左部冗余属性：
   • 考虑 $AB \to C$。
     • 去掉 $A$，剩 $B \to C$。计算 $(B)_{F_0}^+$：
       • $B^{(0)} = B$
       • $B \to A \in F_0 \implies B^{(1)} = BA$
       • $A \to B \in F_0 \implies B^{(1)} = BA$（无变化）
       • $AB \to C \in F_0 \implies B^{(2)} = BAC$。
       • 因为 $C \in (B)_{F_0}^+$，所以 $AB \to C$ 中 $A$ 是冗余的。用 $B \to C$ 替换 $AB \to C$。
       • $F_1 = \{A \to B, B \to A, B \to C\}$。
     • 如果先去掉 $B$，剩 $A \to C$。计算 $(A)_{F_0}^+ = ABC$。因为 $C \in (A)_{F_0}^+$，所以 $AB \to C$ 中 $B$ 是冗余的。用 $A \to C$ 替换 $AB \to C$。得到 $F'_1 = \{A \to B, B \to A, A \to C\}$。
     • 我们选择 $F_1 = \{A \to B, B \to A, B \to C\}$ 继续。
3. 消除冗余依赖（基于 $F_1 = \{A \to B, B \to A, B \to C\}$）：
   • 考虑 $A \to B$。去掉它，用 $F_a = \{B \to A, B \to C\}$。计算 $(A)_{F_a}^+ = A$。因为 $B \notin (A)_{F_a}^+$，所以 $A \to B$ 不冗余。
   • 考虑 $B \to A$。去掉它，用 $F_b = \{A \to B, B \to C\}$。计算 $(B)_{F_b}^+ = BC$。因为 $A \notin (B)_{F_b}^+$，所以 $B \to A$ 不冗余。
   • 考虑 $B \to C$。去掉它，用 $F_c = \{A \to B, B \to A\}$。计算 $(B)_{F_c}^+ = BA$。因为 $C \notin (B)_{F_c}^+$，所以 $B \to C$ 不冗余。

最终最小覆盖 $F_m = \{A \to B, B \to A, B \to C\}$。

如果步骤 2 得到 $F'_1 = \{A \to B, B \to A, A \to C\}$，类似地会发现它也是最小的。这说明最小覆盖可能不唯一。

模式分解

规范化理论的核心思想是通过模式分解将一个关系模式分解为若干个更小、结构更好的关系模式的集合，以消除数据冗余和操作异常。

关系模式的分解

关系模式 $R(U, F)$ 的一个分解 $\rho$ 是指一组关系模式的集合 $\rho = \{R_1(U_1, F_1), R_2(U_2, F_2), \dots, R_k(U_k, F_k)\}$，其中：

• $U = \bigcup_{i=1}^k U_i$（所有子模式的属性并集等于原模式的属性集）。
• 通常不要求 $U_i \cap U_j = \empty$，即子模式间可以有共同属性。
• $F_i$ 是 $F$ 在 $U_i$ 上的投影，即 $F_i = \{ X \to Y \in F^+ \mid XY \subseteq U_i \}$。这意味着 $F_i$ 包含了 $F$ 中所有仅涉及 $U_i$ 内属性的（直接或间接）函数依赖。

一个好的模式分解应具备两个主要特性：无损连接性和依赖保持性。

无损连接性

无损连接性确保在分解后，可以通过自然连接操作从子关系中恢复出原始关系的所有信息，而不会产生额外（伪）元组或丢失原有元组。

无损连接

设 $\rho = \{R_1, \dots, R_k\}$ 是 $R(U,F)$ 的一个分解。如果对于 $R$ 的任何关系实例 $r$，都有 $r = \pi_{U_1}(r) \Join \pi_{U_2}(r) \Join \dots \Join \pi_{U_k}(r)$ 成立，则称分解 $\rho$ 具有无损连接性。

• 其中 $\pi_{U_i}(r)$ 是 $r$ 在属性集 $U_i$ 上的投影。
• $\Join$ 表示自然连接。
• 如果分解是「有损」的，则 $r \subset \pi_{U_1}(r) \Join \dots \Join \pi_{U_k}(r)$，这意味着连接操作会产生一些不属于原始关系的「伪元组」。
• 无损连接是模式分解的首要和必须满足的准则。

无损连接的判定（二元分解）

定理

对于关系模式 $R(U,F)$ 的分解 $\rho = \{R_1(U_1), R_2(U_2)\}$，该分解具有无损连接性的充分必要条件是：
$(U_1 \cap U_2) \to (U_1 - U_2) \in F^+$ 或者 $(U_1 \cap U_2) \to (U_2 - U_1) \in F^+$。

• $U_1 \cap U_2$ 是 $R_1$ 和 $R_2$ 的公共属性。
• $U_1 - U_2$ 是只在 $R_1$ 中出现的属性。
• $U_2 - U_1$ 是只在 $R_2$ 中出现的属性。

直观上，公共属性必须能函数确定至少一个子模式中的非公共属性。

无损连接判断

设关系模式 $R(A,B,C)$。

1. 分解为 $R_1(A,B)$ 和 $R_2(A,C)$。$U_1 \cap U_2 = A, U_1 - U_2 = B, U_2 - U_1 = C$。
   若 $F=\{A \to B\}$，则 $A \to B \in F^+$ 成立，分解是无损的。
   若 $F=\{A \to C\}$，则 $A \to C \in F^+$ 成立，分解是无损的。
2. 分解为 $R_1(A,B)$ 和 $R_2(B,C)$。$U_1 \cap U_2 = B, U_1 - U_2 = A, U_2 - U_1 = C$。
   若 $F=\{A \to B\}$，则 $B \to A \notin F^+$ 且 $B \to C \notin F^+$。分解是有损的。
   若 $F=\{B \to C\}$，则 $B \to C \in F^+$ 成立，分解是无损的。

对于分解为多个关系模式的情况，可以迭代使用此定理，或者使用更通用的 Chase 算法（或称为表方法）来判定。

依赖保持性

依赖保持性确保原关系模式中的所有函数依赖在分解后的子模式中仍然能够被强制执行或推导出来。

依赖保持

设 $\rho = \{R_1(U_1, F_1), \dots, R_k(U_k, F_k)\}$ 是 $R(U,F)$ 的一个分解，其中 $F_i$ 是 $F$ 在 $U_i$ 上的投影。如果 $(F_1 \cup F_2 \cup \dots \cup F_k)^+ = F^+$，则称分解 $\rho$ 保持函数依赖。

• 由于 $(F_1 \cup \dots \cup F_k) \subseteq F^+$ 总是成立的，所以我们只需检验是否 $F \subseteq (F_1 \cup \dots \cup F_k)^+$。
• 这意味着，原有的每个函数依赖 $X \to Y \in F$ 都能通过子模式的函数依赖集合推导出来。

模式分解算法

候选码的计算

在进行模式分解和范式判断前，经常需要计算关系模式的候选码。一种常用的方法是基于属性集的分类：

1. 设 $F_m$ 是关系模式 $R(U)$ 的一个最小函数依赖集。
2. 将 $U$ 中的属性分为四类：
   • $L$：仅出现在 $F_m$ 中函数依赖左部的属性。
   • $R$：仅出现在 $F_m$ 中函数依赖右部的属性。
   • $LR$：同时出现在 $F_m$ 中函数依赖左部和右部的属性。
   • $N$：未在 $F_m$ 中任何函数依赖的左部或右部出现的属性。
3. 初步判断：
   • 所有在 $L \cup N$ 中的属性必须是任何候选码的成员。令 $K_{\text{base}} = L \cup N$。
   • 仅在 $R$ 中的属性不能是任何候选码的成员（除非 $R$ 本身是 $K_{\text{base}}$ 的一部分且 $LR$ 为空）。
4. 组合测试：计算 $K_{\text{base}}^+$。如果 $K_{\text{base}}^+ = U$，则 $K_{\text{base}}$ 是唯一候选码。
   否则，从 $LR$ 中选择属性子集 $X_{\text{sub}} \subseteq LR$，逐个加入 $K_{\text{base}}$ 形成 $K = K_{\text{base}} \cup X_{\text{sub}}$，测试是否 $K^+ = U$。寻找满足此条件的最小 $K$。

候选码计算

条件：

• $R(A, B, C)$
• $F_m = \{A \to B, B \to A, A \to C\}$。

步骤：

1. $L = \empty$（没有只在左边的）
2. $R = \{C\}$（C 只在右边）
3. $LR = \{A, B\}$（A, B 左右都出现）
4. $N = \empty$
5. $K_{\text{base}} = L \cup N = \empty$。
6. 从 $LR = \{A, B\}$ 中选子集：
   • 测试 $\{A\}$：$(A)_{F_m}^+ = \{A,B,C\} = U$，所以 $\{A\}$ 是一个候选码。
   • 测试 $\{B\}$：$(B)_{F_m}^+ = \{B,A,C\} = U$，所以 $\{B\}$ 是一个候选码。
7. 候选码为 $\{A\}$ 和 $\{B\}$。

转换为 3NF 的无损且保依赖分解算法

该算法旨在将一个关系模式分解为一组满足 3NF 的子模式，同时保证分解是无损连接且保持函数依赖的。

1. 计算最小覆盖：找出 $F$ 的一个最小覆盖 $F_{\min}$。
2. 按依赖分组：对于 $F_{\min}$ 中的每一个函数依赖 $X \to A$（由于是最小覆盖，右部已是单属性），创建一个关系模式 $R_i(XA)$。分解 $\rho$ 初始化为这些 $R_i$ 的集合。
3. 保证无损连接：检查 $\rho$ 中的关系模式是否包含原模式 $R$ 的某个候选码。
   • 如果没有任何一个 $R_i(U_i)$ 使得 $U_i$ 是 $R$ 的一个超码（即包含 $R$ 的一个候选码），则从 $R$ 的候选码中任选一个 $K$，将 $R_k(K)$ 添加到 $\rho$ 中。
   • 否则，无需操作。
4. （可选）可以合并具有相同候选码或者一个模式的属性集是另一个模式属性集子集的模式，以减少模式数量，但需注意合并后仍需满足 3NF。

SLC 分解到 3NF

• R = SLC(Sno, Sdept, Sloc, Cno, Grade)
• Fmin = {(Sno, Cno) -> Grade, Sno -> Sdept, Sdept -> Sloc}
• 候选码为 (Sno, Cno)。

1. Fmin 已给出。
2. 根据 Fmin 创建子模式：
   • R1(Sno, Cno, Grade)（来自 (Sno, Cno) -> Grade）
   • R2(Sno, Sdept)（来自 Sno -> Sdept）
   • R3(Sdept, Sloc)（来自 Sdept -> Sloc）
   • rho = {R1, R2, R3}。
3. 检查候选码：R1 的属性集 {Sno, Cno, Grade} 包含了原模式的候选码 (Sno, Cno)。因此无需添加候选码模式。

最终分解为：

• SC(Sno, Cno, Grade)
• SD(Sno, Sdept)
• DL(Sdept, Sloc)

这个分解是无损的，保持依赖的，并且每个子模式都达到了 BCNF（因此也是 3NF）。

转换为 BCNF 的无损分解算法

该算法旨在将一个关系模式分解为一组满足 BCNF 的子模式，保证分解是无损连接的，但不一定保持函数依赖。

1. 初始化：$\rho = \{R(U,F)\}$。
2. 循环检查与分解：
   • 如果 $\rho$ 中的所有关系模式都已达到 BCNF，则算法终止。
   • 否则，选择 $\rho$ 中某个不满足 BCNF 的关系模式 $R_i(U_i, F_i)$。
   • 这意味着在 $R_i$ 中存在一个函数依赖 $X \to A$ ($A \notin X, X \to A \in F_i^+$) 使得 $X$ 不是 $R_i$ 的超码。
   • 将 $R_i$ 分解为两个子模式：
     • $R_{i1}(XA, F_{i1}')$（其中 $F_{i1}'$ 是 $F_i$ 在 $XA$ 上的投影）
     • $R_{i2}(U_i - A, F_{i2}')$（其中 $F_{i2}'$ 是 $F_i$ 在 $U_i - A$ 上的投影）
       • 注意：$U_i - A$ 应该理解为 $(U_i - (X \cup A)) \cup X$ 或者 $U_i - (A \text{ attributes not in } X)$，即 $X$ 仍保留在第二个模式中以保证无损连接，因为 $X \cap (U_i-A) = X$ 且 $X \to A$。
     • 更准确的分解是：$R_{i1}(XA)$ 和 $R_{i2}(X \cup (U_i - X - A))$。
   • 用 $\{R_{i1}, R_{i2}\}$ 替换 $\rho$ 中的 $R_i$。返回步骤 2。

STJ 分解到 BCNF

• R = STJ(S, T, J)（学生 S, 教师 T, 课程 J）
• F = {(S, J) -> T, T -> J}。候选码为 (S, J) 和 (S, T)。
• STJ 是 3NF（因为所有属性都是主属性），但不是 BCNF，因为 T -> J 中 T 不是 STJ 的超码。

1. rho = {STJ(S, T, J)}。
2. STJ 不满足 BCNF，因为 T -> J 且 T 不是超码。
3. 分解 STJ 基于 T -> J:
   • R1(T, J)（属性：T, J。FD：T -> J）
   • R2(S, T)（属性：S, T。原 F 在 ST 上的投影不含非平凡 FD，但 (S, J) -> T 意味着 S, T 共同决定 J, 结合 T -> J。
     • 这里 $U_i-A$ 是 (S, T, J) - J = (S, T)。所以是 R2(S, T)。
     • 更准确地，分解为 R1(T, J) 和 R2(S, T)。
   • rho = {R1(T, J), R2(S, T)}。

算法终止。最终分解为 TJ(T, J) 和 ST(S, T)。

这个分解是无损的，但原 FD (S, J) -> T 丢失了，因为无法从 F_TJ = {T -> J} 和 F_ST = {} 中推导出。

多值依赖与第四范式（4NF）

即使关系模式达到了 BCNF，仍可能存在由多值依赖引起的冗余。

多值依赖（MVD）

设 $R(U)$ 是一个关系模式，$X, Y, Z$ 是 $U$ 的子集，且 $Z = U - X - Y$（即 $X,Y,Z$ 是 $U$ 的一个划分，允许为空）。如果对于 $R$ 的任一关系实例 $r$，给定一对 $(x,z)$ 值（$x$ 是 $X$ 上的值，$z$ 是 $Z$ 上的值），$Y$ 的值的集合完全由 $x$ 决定，而与 $z$ 的值无关，则称 $Y$ 多值依赖于 $X$，或 $X$ 多值决定 $Y$，记作 $X \twoheadrightarrow Y$。

等价定义：$X \twoheadrightarrow Y$ 成立，当且仅当对 $R$ 的任一关系 $r$，若元组 $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)$ 也必定在 $r$ 中。

X  | Y  | Z
---+----+---------
x  | y1 | z1  (t1)
x  | y2 | z2  (t2)
---+----+---------
x  | y1 | z2  (t3, must exist if X ->> Y)
x  | y2 | z1  (t4, must exist if X ->> Y)

课程-教师-参考书

考虑关系模式 Teaching(Course, Teacher, Book)。假设一门课程有多位教师授课，使用多本参考书，且每位教师都使用该课程的所有参考书，每本参考书也适用于该课程的所有教师。

• 例如，物理课由李勇、王军教，参考书有《普通物理学》《光学原理》。
• 则存在元组：(物理, 李勇, 普物), (物理, 李勇, 光学), (物理, 王军, 普物), (物理, 王军, 光学)。
• 这里，对于给定的课程（如「物理」），教师集合（{李勇, 王军}）的确定与参考书无关；同样，参考书集合（{普物, 光学}）的确定也与教师无关。
• 因此，存在多值依赖：Course ->> Teacher 和 Course ->> Book。
• 该模式的唯一候选码是 (Course, Teacher, Book)（全码），因此它属于 BCNF。但仍存在明显的冗余。

多值依赖的性质

• 平凡 MVD：若 $Y \subseteq X$ 或 $X \cup Y = U$，则 $X \twoheadrightarrow Y$ 是平凡的。我们关心的是非平凡 MVD。
• 函数依赖是特殊的多值依赖：若 $X \to Y$，则 $X \twoheadrightarrow Y$。
• MVD 补余规则：若 $X \twoheadrightarrow Y$ 且 $Z = U - X - Y$，则 $X \twoheadrightarrow Z$。
• MVD 的有效性依赖于属性全集 $U$，而 FD 不依赖。

第四范式（4NF）

第四范式旨在消除由非平凡且非 FD 的 MVD 引起的冗余。

第四范式（4NF）

关系模式 $R(U,F)$（$F$ 包含 FD 和 MVD）属于 4NF，如果对于 $R$ 上的每一个非平凡多值依赖 $X \twoheadrightarrow Y$（即 $Y \not\subseteq X$ 且 $X \cup Y \ne U$），$X$ 都必须是 $R$ 的一个超码。

• 如果一个关系模式是 4NF，则它必定是 BCNF。
• 4NF 限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。4NF 所允许的非平凡多值依赖实际上是函数依赖。

4NF 的分解

如果关系模式 $R$ 不属于 4NF，则存在某个非平凡 MVD $X \twoheadrightarrow Y$ 且 $X$ 不是 $R$ 的超码。可以将 $R$ 分解为：

• $R_1(X \cup Y)$
• $R_2(X \cup (U - Y))$（或者 $R_2(X \cup Z)$，其中 $Z = U-X-Y$）

这个分解是无损的，并且有助于消除冗余，使子模式更接近或达到 4NF。重复此过程直到所有模式都达到 4NF。

Teaching 模式分解到 4NF

Teaching(Course, Teacher, Book) 存在非平凡 MVD Course ->> Teacher，且 Course 不是超码。分解为：

• CT(Course, Teacher)
• CB(Course, Book)（因为 U - Y = Book）

这两个子模式 CT 和 CB 都达到了 4NF（它们只包含平凡 MVD 或由码决定的 MVD）。

通过 Armstrong 公理、属性闭包、最小覆盖等工具，我们可以分析函数依赖。通过模式分解，特别是针对 3NF、BCNF 和 4NF 的分解算法，我们可以设计出结构良好、冗余较少、不易发生操作异常的关系数据库模式。

---

1. 数学基础中的「公理」（如欧几里得几何）被视为不证自明、无需证明的起点，其真值通过直觉或经验接受；逻辑与数据库理论中的「公理」更强调形式系统的初始规则，用于推导其他定理。这些规则可能是可证明的（例如从更基础的集合论出发），但在当前系统内被设定为不可约简的起点。 ↩︎