第7章关系规范化

课程：0A102 数据库设计与实践（陈立军，北京大学）类型：PowerPoint 97-2003 二进制格式（图片+公式对象为主，文本部分提取）状态：partial_extraction（公式对象和数学符号无法完整提取，基于文本提取+标准知识体系整理）

一、问题引入：为什么需要规范化

1.1 关系模式中的不良特性

以学生关系 S(S#, SN, SD, DEAN, C#, G) 为例：

插入异常：如果学生没有选课，他的个人信息及所在系的信息就无法插入
删除异常：如果删除学生的选课信息，则有关他的个人信息及所在系的信息也随之删除了
更新异常：如果学生转系，若他选修了k门课，则需要修改k次
数据冗余：如果一个学生选修了k门课，则有关他的所在系的信息重复存储k次

课程中用”工资-职工”、“课程-教员-参考书”等多个示例反复说明四大问题

1.2 解决之道：模式分解

“分解！分解！！再分解！！！” —— 课程原文

通过模式分解将一个低级范式转换为若干个高级范式的过程称作规范化（概念的纯粹化）。

分解的基本代数运算：

投影（Projection）
自然连接（Natural Join）

分解的三大目标：

无损连接分解（Lossless Join）：分解后再自然连接能还原
保持函数依赖（Dependency Preservation）：分解后的依赖集的并的闭包等于原闭包
达到更高级范式：1NF → 2NF → 3NF → BCNF → 4NF → 5NF

二、函数依赖（Functional Dependency）

2.1 基本概念

函数依赖定义：关系模式 R，F 是其函数依赖，X、Y 是属性子集，如果从 F 的函数依赖能够推出 X→Y，则称 X 函数决定 Y。

辨识：

满足依赖的关系：依赖在模式的某个关系实例上成立
模式上成立的依赖：依赖在模式的所有关系实例上都成立

闭包 F+：被 F 所逻辑蕴涵的函数依赖的全体所构成的集合，记作 F+ = {X→Y | …}

2.2 Armstrong 公理系统

推理规则系统：正确的、完备的推理规则集（公理、定理、推论，如欧几里得几何）

Armstrong 公理（X、Y、Z 是属性集）：

自反律（Reflexivity）：若 Y ⊆ X，则 X→Y
增广律（Augmentation）：若 X→Y，则 XZ→YZ
传递律（Transitivity）：若 X→Y 且 Y→Z，则 X→Z

2.3 由 Armstrong 公理导出的推理规则

合并律（Union Rule）：若 X→Y 且 X→Z，则 X→YZ
分解律（Decomposition Rule）：若 X→YZ，则 X→Y 且 X→Z
伪传递律（Pseudotransitivity Rule）：若 X→Y 且 WY→Z，则 WX→Z

2.4 Armstrong 公理的正确性及完备性

A = { f | 可用 Armstrong 公理从 F 中导出的函数依赖 f }
B = { f | 被 F 所逻辑蕴涵的函数依赖 f }
正确性：用 Armstrong 公理从 F 中导出的函数依赖必为 F 所蕴涵 → A ⊆ B
完备性：F 所蕴涵的函数依赖都能用 Armstrong 公理从 F 中导出 → B ⊆ A

即 A = B，公理系统既正确又完备

2.5 属性集的闭包

定义：X+ = {A | X→A 能由 F 根据 Armstrong 公理导出}，称为属性集 X 关于函数依赖集 F 的闭包。

算法：求属性集 X 关于函数依赖集 F 的闭包 X+

Input: X, F
Output: X+
  X+ := X
  while (X+ 发生变化) do
    for each 函数依赖 A→B in F do
      if A ⊆ X+ then X+ := X+ ∪ {B}

如果 X+ = X，则称 X 是封闭的。

2.6 候选码的计算

候选码定义：设 K 为 R<U, F> 的超码，若 K →→ U（完全函数依赖），则称 K 为 R 的候选码。

快速判定定理（属性分类法）：

左部属性：只出现在 F 左边的属性 → 一定出现在任何候选码中
右部属性：只出现在 F 右边的属性 → 一定不出现在任何候选码中
双部属性：出现在 F 两边的属性 → 需要进一步判断
外部属性：不出现在 F 中的属性 → 一定出现在任何候选码中（？原文如此，需注意外部属性本身不被决定，所以必须在码中）

即：左部 + 外部属性是候选码的必选元素，右部一定不在码中，双部需验证

2.7 函数依赖集的等价性和最小覆盖

等价性定义：函数依赖集 F、G，若 F+ = G+，则称 F 与 G 等价。

最小覆盖 Fmin（也叫最小依赖集 / 最小函数依赖集）的三个条件：

单属性化（右部单属性）：F 中任一函数依赖 X→A，A 必是单属性
无冗余化：F 中不存在这样的函数依赖 X→A，使得 F - {X→A} 与 F 等价
既约化（左部无多余属性）：逐个检查 F 中各函数依赖 X→A，若 X 中有多余属性则去掉

求解 Fmin 的三步法：

右部单属性化
去冗余依赖
左部既约化

三、范式（Normal Form）

3.1 范式层级

范式是对关系的不同数据依赖程度的要求，级别越高约束越强：

1NF ⊃ 2NF ⊃ 3NF ⊃ BCNF ⊃ 4NF ⊃ 5NF

每一级范式都是前一级的子集（条件更严格）

3.2 第一范式（1NF）

定义：关系模式的所有属性都是不可再分的基本数据项（原子性）。

是关系模型的最低要求
较细的原子粒度有助于标准化，施加约束，避免输入错误，从而提高数据质量

3.3 第二范式（2NF）

定义：若 R∈1NF，且每一个非主属性完全函数依赖于码，则 R∈2NF。

消除了非主属性对码的部分函数依赖
例子：S(S#, SN, SD, DEAN, C#, G)，码是(S#, C#)，但 SN、SD、DEAN 只依赖于 S#（部分依赖），所以不是 2NF

3.4 第三范式（3NF）

定义：关系模式 R 中若不存在这样的码 X、属性组 Y 及非主属性 Z（Z∉Y），使得 X→Y、Y→Z、Y↛X 成立，则称 R∈3NF。

消除了非主属性对码的传递函数依赖
等价定义：每一个非主属性既不部分依赖于码，也不传递依赖于码
3NF 不彻底：主属性对码的传递依赖和部分依赖仍然可能存在

3.5 Boyce-Codd 范式（BCNF）

定义：关系模式 R<U, F>∈1NF，若 X→Y 且 Y⊈X 时 X 必含有码，则 R∈BCNF。

消除了主属性对码的部分依赖和传递依赖
即：所有非平凡的函数依赖的左部都包含候选码
是函数依赖范畴内的最高范式
一个只有一个候选码的 3NF 关系模式，一定是 BCNF（因为码唯一，不存在主属性对码的传递/部分依赖）

3.6 范式对比与常见结论

范式	消除的依赖类型	范畴
1NF	属性的原子性	最低要求
2NF	非主属性对码的部分依赖	函数依赖
3NF	非主属性对码的传递依赖	函数依赖
BCNF	主属性对码的部分/传递依赖	函数依赖（最高）
4NF	非平凡多值依赖（非函数依赖）	多值依赖
5NF	连接依赖	连接依赖

思考题（课程原文）：

任何一个二目关系模式 R(A, B) 一定属于 BCNF 吗？一定属于 4NF 吗？
一个候选码全是单属性的关系模式最高一定可以达到第几范式？
一个全是主属性的关系模式最高一定可以达到第几范式？
一个全码的关系模式最高一定可以达到第几范式？
一个只有一个候选码的 3NF 关系模式是 BCNF 的吗？

答：(1) 是，是 (2) BCNF (3) 3NF (4) 全码即所有属性都是主属性，最高 3NF 不一定是 BCNF，但全码本身一定是 BCNF（因为任何非平凡依赖左部都是码）(5) 是

四、模式分解

4.1 模式分解的定义

关系模式 R<U, F> 的一个分解是指： ρ = { R1<U1, F1>, R2<U2, F2>, …, Rn<Un, Fn> }

其中 U = ∪Ui，并且没有 Ui ⊆ Uj。

Fi 是 F 在 Ui 上的投影：Fi = {X→Y | X→Y ∈ F+ 且 XY ⊆ Ui}

4.2 无损连接分解（Lossless Join Decomposition）

定义：若对于 R<U, F> 的任一个关系 r，都有 r = mρ(r)（即 r = πR1(r) ⋈ πR2(r) ⋈ … ⋈ πRn(r)），则称 ρ 是无损连接分解。

判别算法（chase 追踪法）：

建立一个 n 列 k 行的矩阵 TB = {Cij}
- 若 Aj ∈ Ui，则 Cij = aj（表示该属性在该关系模式中）
- 否则 Cij = bij（表示不确定）
对 F 中每个函数依赖 X→Y 反复检查：
- 若 TB 中存在元组 t1、t2，使得 t1[X] = t2[X]，t1[Y] ≠ t2[Y]
- 则修改：若 t1[Ai]、t2[Ai] 中有一个等于 aj，则另一个也改为 aj
如果最终有一行全是 a（a1, a2, …, an），则是无损连接分解

二元分解的简单判定定理：设 ρ = {R1, R2} 是 R 的一个分解，则 ρ 是无损连接分解当且仅当：

R1∩R2 → R1-R2 ∈ F+，或者
R1∩R2 → R2-R1 ∈ F+

即两个模式的公共属性集函数决定其中一边的差集

4.3 保持函数依赖的分解

定义：若 F+ = (∪Fi)+，则称分解 ρ 保持函数依赖。

即：分解后的各关系模式上的函数依赖集的并，其闭包等于原函数依赖集的闭包
保持函数依赖意味着不需要跨表连接就能验证数据完整性约束

4.4 分解算法

（1）达到 BCNF 的无损连接分解算法

基本思想：反复找出违反 BCNF 的函数依赖 X→Y（X 不含码），将关系模式拆分为 XY 和 R-Y。

注意：BCNF 分解一定是无损的，但不一定保持函数依赖

（2）达到 3NF 的保持函数依赖分解算法

基本思想：

先求 F 的最小覆盖 Fmin
对 Fmin 按具有相同左部的原则分组（设为 k 组）
每一组函数依赖所涉及的属性全体为 Ui，令 Fi 为 Fmin 在 Ui 上的投影
若某个候选码没有出现在任何 Ui 中，则额外加一个只包含候选码的关系模式

3NF 合成法可以同时做到保持函数依赖和无损连接（加码的那个关系模式保证无损）

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

5.1 多值依赖（Multi-Valued Dependency, MVD）

函数依赖 vs 多值依赖的区别：

函数依赖规定某些元组不能出现在关系中，也称为相等产生依赖
多值依赖要求某种形式的其它元组必须在关系中，称为元组产生依赖

多值依赖定义：关系模式 R(U)，X、Y ⊆ U，X→→Y 当且仅当对 R 的任一关系 r：若 t1、t2 ∈ r，t1[X] = t2[X]，则存在 t3 = (t2[X], t1[Y], t2[R-X-Y]) 也在 r 中。

多值依赖的有效性仅决定于 X、Y 属性集上的值，它在任何属性集 W（XY ⊆ W ⊆ U）上都成立。

5.2 第四范式（4NF）

定义：关系模式 R<U, D>∈1NF，若 R 的每个非平凡多值依赖 X→→Y（Y⊈X），X 都含有候选码，则 R∈4NF。

4NF 限制更严格的多值依赖
BCNF 不一定是 4NF，4NF 一定是 BCNF
4NF 是多值依赖范畴内的最高范式

达到 4NF 的无损连接分解算法：类似于 BCNF 分解，反复找出违反 4NF 的非平凡多值依赖，分解关系模式。

六、连接依赖与第五范式（5NF）

6.1 连接依赖（Join Dependency, JD）

连接依赖定义：*(R1, R2, …, Rn) 中，若有某个 Ri 等于 R，则称之为平凡的连接依赖。

与多值依赖的关系：根据定理，连接依赖 *(R, S) 等价于多值依赖 R∩S →→ R（即二元连接依赖就是多值依赖）。

多值依赖是连接依赖的特例（二元），连接依赖是多值依赖的推广（n 元）

6.2 第五范式（5NF）

定义：关系模式 R∈1NF，若 R 的每个连接依赖都由 R 的候选码蕴涵，则 R∈5NF。

也叫投影-连接范式（PJ/NF, Project-Join Normal Form）
5NF 是基于连接依赖的最高范式
4NF 不一定是 5NF，5NF 一定是 4NF

课程提到：大多数连接依赖的判定是 NP 完全问题

七、规范化的计算复杂性

课程中有一段关于算法复杂度的讨论：

“大多数指数级时间算法只是穷举搜索法的变种，而多项式时间算法通常只有在对问题的结构有了某些比较深入的了解之后才有可能给出。”

“完全问题，这就给我们提供了有价值的信息，告诉我们采用什么样的途径可以是最有成效的。一定不要去寻找有效的、精确的算法，比较适当的途径是集中精力致力于较低目标的方法。比如，你可以寻找解决这个问题的各种特殊情况的有效算法。”

这部分讨论实际上是在讲连接依赖的判定是 NP 完全问题，因此 5NF 在实际工程中难以精确判定，实际数据库设计通常做到 BCNF 或 3NF 即可。

八、模式分解的权衡

8.1 分解的粒度不是越细越好

以银行账户为例（account_ID, address, balance）：

模式 1：(account_ID, address, balance)
模式 2：(account_ID, address) + (account_ID, balance)

应用场景：每月给客户邮寄一张报告单，每天多次对帐户余额进行更新和查找

此时模式 2 较好，因为：

(account_ID, balance) 较小
索引小
内存装纳更多 account_ID-balance 对，提高随机存取命中率
对于扫描大部分 account_ID-balance 对的查询，读取的页少

但也有例外：如果 address 由 street address 和 zip code 构成，且一般一起存取，分别存放（模式 3）反而会造成空间浪费、降低性能。

规范化是减少冗余和异常的手段，但过度分解会增加连接开销，需要在数据完整性和查询性能之间权衡。

九、本章知识脉络

函数依赖 FD
  ├── Armstrong 公理系统（自反/增广/传递 + 合并/分解/伪传递）
  ├── 属性集闭包 X+（算法）
  ├── 候选码求解（左部/右部/双部/外部属性分类法）
  ├── 函数依赖集等价（F+ = G+）
  └── 最小覆盖 Fmin（单属性化 / 无冗余化 / 既约化）

范式层级（函数依赖范畴）
  ├── 1NF：属性原子性
  ├── 2NF：消除非主属性对码的部分依赖
  ├── 3NF：消除非主属性对码的传递依赖
  └── BCNF：消除主属性对码的部分/传递依赖（FD 范畴最高）

模式分解
  ├── 无损连接分解（chase 算法 / 二元分解定理）
  ├── 保持函数依赖分解
  ├── BCNF 分解（无损，不一定保依赖）
  └── 3NF 合成法（保依赖 + 加码保无损）

多值依赖 MVD → 4NF（MVD 范畴最高）
连接依赖 JD → 5NF（JD 范畴最高，PJ/NF）

来源：田浩然上传的资料 / 0A102 数据库设计与实践 / chap07 关系规范化.ppt（7.63MB，PowerPoint 97-2003 二进制格式，图片+公式对象为主，文本部分提取，基于标准知识体系补充整理）

知识库

探索

第7章 关系规范化 - 数据库设计与实践

第7章 关系规范化