关系数据理论

一、概述

1.1 问题的提出

关系数据库逻辑设计的核心问题：针对一个具体问题，如何构造一个适合于它的数据库模式。

数据库逻辑设计的工具：关系数据库的规范化理论。

1.2 关系模式的形式化定义

关系模式由五部分组成，是一个五元组：

R (U, D, D O M, F)

符号	含义
$R$	关系名
$U$	组成该关系的属性名集合
$D$	属性组 $U$ 中属性所来自的域
$D O M$	属性向域的映象集合
$F$	属性间数据的依赖关系集合

简化表示：通常简化为三元组 $R (U, F)$ ，当且仅当 $U$ 上的一个关系 $r$ 满足 $F$ 时， $r$ 称为关系模式 $R (U, F)$ 的一个关系。

1.3 数据依赖

数据依赖是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系。它是：

现实世界属性间相互联系的抽象
数据内在的性质
语义的体现

数据依赖的类型：

函数依赖（Functional Dependency, FD）
多值依赖（Multivalued Dependency, MVD）
其他

1.4 数据依赖对关系模式的影响（引例）

学校数据库示例：

关系模式： $Student ⟨ U, F ⟩$

U = {Sno, Sdept, Mname, Cname, Grade}

语义：

一个系有若干学生，一个学生只属于一个系
一个系只有一名主任
一个学生可以选修多门课程，每门课程有若干学生选修
每个学生所学的每门课程都有一个成绩

函数依赖 F：

$Sno \to Sdept$
$Sdept \to Mname$
$(Sno, Cname) \to Grade$

存在的问题：

问题类型	说明	举例
① 数据冗余太大	浪费大量存储空间	每个系主任姓名重复出现
② 更新异常	维护数据完整性代价大	某系更换主任需修改所有相关元组
③ 插入异常	该插的数据插不进去	新系无学生时无法存入系和主任信息
④ 删除异常	不该删的数据被删除	学生全部毕业时连带删除系和主任信息

结论：Student 不是一个好的关系模式。好的模式应满足：不发生插入/删除/更新异常，数据冗余尽可能少。

解决方法：通过分解关系模式来消除不合适的数据依赖。

二、规范化（Normalization）

规范化理论用来改造关系模式，通过分解关系模式来消除不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题。

2.1 函数依赖

2.1.1 函数依赖的定义

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

说明：

函数依赖不是指某个或某些关系实例，而是指 R 的所有关系实例均要满足的约束条件
函数依赖是语义范畴的概念，只能根据数据语义来确定
数据库设计者可对现实世界作强制规定

示例：

$Student (Sno, Sname, Ssex, Sage, Sdept)$

$Sno \to Ssex$ , $Sno \to Sage$ , $Sno \to Sdept$
若不允许重名，则 $Sno \leftrightarrow Sname$ , $Sname \to Ssex$ , $Sname \to Sage$ , $Sname \to Sdept$
$Ssex ↛ Sage$ （性别不决定年龄）

记法：

$X \to Y$ 且 $Y \to X$ ，记作 $X \leftrightarrow Y$
$Y$ 不函数依赖于 $X$ ，记作 $X ↛ Y$

2.1.2 平凡函数依赖与非平凡函数依赖

类型	条件	说明
非平凡	$X \to Y$ ，且 $Y ⊈ X$	反映新语义，通常讨论此类
平凡	$X \to Y$ ，且 $Y \subseteq X$	必然成立，不反映新语义

例：关系 $SC (Sno, Cno, Grade)$

非平凡： $(Sno, Cno) \to Grade$
平凡： $(Sno, Cno) \to Sno$ , $(Sno, Cno) \to Cno$

2.1.3 完全函数依赖与部分函数依赖

定义 6.2：在关系模式 $R (U)$ 中，如果 $X \to Y$ ，并且对于 $X$ 的任何一个真子集 $X^{'}$ ，都有 $X^{'} ↛ Y$ ，则称 $Y$ 完全函数依赖于 $X$ ，记作 $X \overset{f}{\to} Y$ 。

若 $X \to Y$ ，但 $Y$ 不完全函数依赖于 $X$ ，则称 $Y$ 部分函数依赖于 $X$ ，记作 $X \overset{p}{\to} Y$ 。

【例题】：在关系 $SC (Sno, Cno, Grade)$ 中

由于 $Sno ↛ Grade$ ， $Cno ↛ Grade$
因此 $(Sno, Cno) \overset{f}{\to} Grade$ （ $Grade$ 完全函数依赖于 $(Sno, Cno)$ ）

2.1.4 传递函数依赖

定义 6.3：在关系模式 $R (U)$ 中，如果 $X \to Y$ ， $Y \to Z$ ，且 $Y ⊈ X$ ， $Z ⊈ Y$ ， $Y ↛ X$ ，则称 $Z$ 传递函数依赖于 $X$ 。

注：如果 $Y \to X$ （即 $X \leftrightarrow Y$ ），则 $Z$ 直接依赖于 $X$ 。

【例题】：关系 $Std (Sno, Sdept, Mname)$

$Sno \to Sdept$ ， $Sdept \to Mname$
$Mname$ 传递函数依赖于 $Sno$

2.2 码（Key）

2.2.1 候选码与主码

定义 6.4：设 $K$ 为关系模式 $R ⟨ U, F ⟩$ 中的属性或属性组合。若 $K \overset{f}{\to} U$ ，则 $K$ 称为 $R$ 的一个候选码（Candidate Key）。若关系模式 $R$ 有多个候选码，则选定其中一个作为主码（Primary Key）。

主属性：包含在任何一个候选码中的属性
非主属性：不包含在任何候选码中的属性
全码（ALL KEY）：所有属性共同构成候选码

2.2.2 外部码（Foreign Key）

定义 6.5：关系模式 R 中属性或属性组 X 并非 R 的码，但 X 是另一个关系模式的码，则称 X 是 R 的外部码（外码）。

主码和外部码一起提供了表示关系间联系的手段。

2.3 范式（Normal Form）

范式是符合某一种级别的关系模式的集合。关系数据库中的关系必须满足一定的要求，满足不同程度要求的为不同范式。

范式种类（从低到高）：

第一范式（1NF）
第二范式（2NF）
第三范式（3NF）
BC 范式（BCNF）
第四范式（4NF）
第五范式（5NF）

包含关系： $5 N F \subset 4 N F \subset B C N F \subset 3 N F \subset 2 N F \subset 1 N F$

2.4 第二范式（2NF）

2.4.1 第一范式（1NF）

定义：如果一个关系模式 $R$ 的所有属性都是不可分的基本数据项，则 $R \in 1 N F$ 。

第一范式是对关系模式的最起码要求，不满足 $1 N F$ 的数据库模式不能称为关系数据库。但满足 $1 N F$ 不一定是一个好的关系模式。

2.4.2 2NF 的定义

定义 6.6：若关系模式 $R \in 1 N F$ ，并且每一个非主属性都完全函数依赖于 $R$ 的码，则 $R \in 2 N F$ 。

2.4.3 2NF 示例分析

关系模式： $SLC (Sno, Sdept, Sloc, Cno, Grade)$

Sloc 为学生住处，假设每个系的学生住在同一个地方。

函数依赖：

$(Sno, Cno) \overset{f}{\to} Grade$
$Sno \to Sdept$
$(Sno, Cno) \overset{p}{\to} Sdept$
$Sno \to Sloc$
$(Sno, Cno) \overset{p}{\to} Sloc$
$Sdept \to Sloc$

码： $(Sno, Cno)$

问题： $SLC \in 1 N F$ ，但非主属性 $Sdept$ 和 $Sloc$ 部分函数依赖于码 $(Sno, Cno)$ ，所以 $SLC \notin 2 N F$ 。

SLC 存在的问题：

问题	说明
插入异常	未选课的学生信息无法插入（课程号是主属性）
删除异常	学生退选最后一门课导致整个元组被删除
数据冗余	学生选修 10 门课，Sdept 和 Sloc 重复存储 10 次
修改复杂	转系需修改该学生所有元组的 Sdept 和 Sloc

解决方法：将 SLC 分解为两个关系模式，消除部分函数依赖。

分解：

$SC (Sno, Cno, Grade)$ — 码为 $(Sno, Cno)$
$SL (Sno, Sdept, Sloc)$ — 码为 $Sno$

分解后： $SC \in 2 N F$ ， $SL \in 2 N F$

注意：将一个 1NF 分解为多个 2NF 只能减轻问题，不能完全消除异常和数据冗余。

2.5 第三范式（3NF）

2.5.1 3NF 的定义

定义 6.7：关系模式 $R ⟨ U, F ⟩$ 中若不存在这样的码 $X$ 、属性组 $Y$ 及非主属性 $Z$ （ $Z ⊈ Y$ ），使得 $X \to Y$ ， $Y ↛ X$ ， $Y \to Z$ 成立，则称 $R \in 3 N F$ 。

通俗理解：若 $R \in 3 N F$ ，则 $R$ 的每一个非主属性既不部分函数依赖于候选码，也不传递函数依赖于候选码。

如果 $R \in 3 N F$ ，则 $R$ 也是 $2 N F$ 。

2.5.2 3NF 示例分析

关系模式： $SL (Sno, Sdept, Sloc) \in 2 N F$

函数依赖：

$Sno \to Sdept$
$Sdept \to Sloc$
$Sno \to Sloc$ （传递依赖）

问题： $Sloc$ 传递函数依赖于 $Sno$ （ $Sno \to Sdept$ ， $Sdept \to Sloc$ ， $Sdept ↛ Sno$ ），存在非主属性对码的传递函数依赖，所以 $SL \notin 3 N F$ 。

解决方法：将 SL 分解为两个关系模式，消除传递函数依赖。

分解：

$SD (Sno, Sdept)$ — 码为 $Sno$
$DL (Sdept, Sloc)$ — 码为 $Sdept$

分解后： $SD \in 3 N F$ ， $DL \in 3 N F$

注意：将一个 2NF 分解为多个 3NF 也只能在一定程度上解决问题，不能完全消除异常和数据冗余。

2.6 BC 范式（BCNF）

2.6.1 BCNF 的定义

定义 6.8：设关系模式 $R ⟨ U, F ⟩ \in 1 N F$ ，如果对于 $R$ 的每个函数依赖 $X \to Y$ ，若 $Y$ 不包含于 $X$ ，则 $X$ 必含有候选码，那么 $R \in B C N F$ 。

BCNF 的性质：

每一个决定属性集（因素）都包含（候选）码
R 中的所有属性（主属性和非主属性）都完全函数依赖于码
若 $R \in B C N F$ ，则 $R \in 3 N F$
若 $R \in 3 N F$ ，则 $R$ 不一定 $\in B C N F$

2.6.2 BCNF 示例分析

关系模式： $STJ (S, T, J)$

S：学生，T：教师，J：课程
每一教师只教一门课
每门课由若干教师教
某一学生选定某门课，就确定了一个固定的教师
某个学生选修某个教师的课就确定了所选课的名称

函数依赖：

$(S, J) \to T$
$(S, T) \to J$
$T \to J$

分析：

$STJ \in 3 N F$ （ $S$ 、 $T$ 、 $J$ 都是主属性， $(S, J)$ 和 $(S, T)$ 都是候选码）
$STJ \notin B C N F$ ： $T \to J$ ， $T$ 是决定属性集，但 $T$ 不是候选码

解决方法：将 STJ 分解为两个关系模式

$ST (S, T) \in B C N F$
$TJ (T, J) \in B C N F$

2.6.3 3NF 与 BCNF 的关系

如果 $R \in B C N F$ ，必定有 $R \in 3 N F$
如果 $R \in 3 N F$ ，且 $R$ 只有一个候选码，则 $R$ 必属于 $B C N F$

2.6.4 BCNF 关系模式的性质

所有非主属性都完全函数依赖于每个候选码
所有主属性都完全函数依赖于每个不包含它的候选码
没有任何属性完全函数依赖于非码的任何一组属性

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

2.7.1 问题的提出

关系模式： $Teaching (C, T, B)$

$C$ ：课程， $T$ ：教师， $B$ ：参考书
某一门课程由多个教师讲授，他们使用相同的一套参考书

Teaching 的码： $(C, T, B)$ ，即全码

存在的问题（ $Teaching \in B C N F$ 但仍有问题）：

问题	说明
数据冗余大	有多少名任课教师，参考书就要存储多少次
插入复杂	增加一名教师时，需为每本参考书插入一个元组
删除复杂	去掉一本参考书时，需删除每个教师的对应元组
修改复杂	修改一本参考书时，需修改所有教师的对应元组

产生原因：存在多值依赖。

2.7.2 多值依赖的定义

定义 6.9：设 $R (U)$ 是一个属性集 $U$ 上的关系模式， $X$ 、 $Y$ 和 $Z$ 是 $U$ 的子集，且 $Z = U - X - Y$ 。多值依赖 $X ↠ Y$ 成立当且仅当对 $R$ 的任一关系 $r$ ， $r$ 在 $(X, Z)$ 上的每个值对应一组 $Y$ 的值，这组值仅仅决定于 $X$ 值而与 $Z$ 值无关。

等价的元组定义：在 $R (U)$ 的任一关系 $r$ 中，如果存在元组 $t, s$ 使得 $t [X] = s [X]$ ，那么就必然存在元组 $w, v \in r$ ，使得 $w [X] = v [X] = t [X]$ ，而 $w [Y] = t [Y]$ ， $w [Z] = s [Z]$ ， $v [Y] = s [Y]$ ， $v [Z] = t [Z]$ （即交换 $s, t$ 元组的 $Y$ 值所得的两个新元组必在 $r$ 中），则 $Y$ 多值依赖于 $X$ ，记为 $X ↠ Y$ 。

示例： $Teaching (C, T, B)$ 中，对于 $C$ 的每一个值， $T$ 有一组值与之对应，而不论 $B$ 取何值，因此 $C ↠ T$ 。

2.7.3 多值依赖的性质

对称性：若 $X ↠ Y$ ，则 $X ↠ Z$ ，其中 $Z = U - X - Y$
传递性：若 $X ↠ Y$ ， $Y ↠ Z$ ，则 $X ↠ (Z - Y)$
函数依赖是特殊情况：若 $X \to Y$ ，则 $X ↠ Y$
并规则：若 $X ↠ Y$ ， $X ↠ Z$ ，则 $X ↠ (Y \cup Z)$
交规则：若 $X ↠ Y$ ， $X ↠ Z$ ，则 $X ↠ (Y \cap Z)$
差规则：若 $X ↠ Y$ ， $X ↠ Z$ ，则 $X ↠ (Y - Z)$ ， $X ↠ (Z - Y)$

2.7.4 多值依赖与函数依赖的区别

区别	函数依赖	多值依赖
有效性	与属性集范围无关，在 $U$ 上成立则在任何 $W$ （ $X Y \subseteq W \subseteq U$ ）上成立	与属性集范围有关；在 $U$ 上成立则在 $W$ 上成立，反之不一定（存在嵌入型多值依赖）
子集性质	若 $X \to Y$ 在 $U$ 上成立，则对任何 $Y^{'} \subset Y$ 有 $X \to Y^{'}$	若 $X ↠ Y$ 在 $U$ 上成立，不能断言对任何 $Y^{'} \subset Y$ 有 $X ↠ Y^{'}$

2.7.5 第四范式（4NF）

定义 6.10：关系模式 $R ⟨ U, F ⟩ \in 1 N F$ ，如果对于 $R$ 的每个非平凡多值依赖 $X ↠ Y$ （ $Y ⊈ X$ ）， $X$ 都含有候选码，则 $R \in 4 N F$ 。

如果 $R \in 4 N F$ ，则 $R \in B C N F$
4NF 不允许有非平凡且非函数依赖的多值依赖
4NF 允许的是函数依赖（本身也是非平凡多值依赖）

【例题】： $Teaching (C, T, B) \notin 4 N F$

存在非平凡多值依赖 $C ↠ T$ ，且 $C$ 不是候选码

解决方法：将 Teaching 分解为

$CT (C, T) \in 4 N F$ — $C ↠ T$ 是平凡多值依赖
$CB (C, B) \in 4 N F$ — $C ↠ B$ 是平凡多值依赖

2.8 规范化小结

关系模式规范化基本步骤：

        1NF
         ↓  消除非主属性对码的部分函数依赖
        2NF
         ↓  消除非主属性对码的传递函数依赖
        3NF
         ↓  消除主属性对码的部分和传递函数依赖
        BCNF
         ↓  消除非平凡且非函数依赖的多值依赖
        4NF

规范化的基本思想：

消除不合适的数据依赖
使各关系模式达到某种程度的"分离"
采用"一事一地"的模式设计原则：让一个关系描述一个概念、一个实体或者实体间的一种联系
规范化实质上是概念的单一化

重要提示：不能说规范化程度越高的关系模式就越好。在设计数据库模式结构时，必须结合现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式。

三、数据依赖的公理系统

3.1 逻辑蕴涵与闭包

定义 6.11：关系模式 $R ⟨ U, F ⟩$ ， $F$ 是其函数依赖， $X, Y$ 是其属性子集。如果从 $F$ 的函数依赖能够推出 $X \to Y$ ，则称 $F$ 逻辑蕴涵 $X \to Y$ ，记作 $F ⊢ X \to Y$ 。

定义 6.12：被 $F$ 所逻辑蕴涵的函数依赖的全体所构成的集合称作 $F$ 的闭包，记作：

F^{+} = {X \to Y ∣ F ⊢ X \to Y}

示例： $R (X, Y)$ , $F = {X \to Y}$

F^{+} = {X \to \emptyset, X \to X, X \to Y, X \to X Y, Y \to \emptyset, Y \to Y, X Y \to \emptyset, X Y \to X, X Y \to Y, X Y \to X Y}

3.2 Armstrong 公理系统

设 $U$ 为属性集总体， $F$ 是一组 $U$ 上的函数依赖， $X, Y, Z$ 是属性集，对 $R ⟨ U, F ⟩$ 有：

三条基本公理

公理	符号	含义
自反律（Reflexivity）	若 $Y \subseteq X$ ，则 $X \to Y$	平凡函数依赖必然成立
增广律（Augmentation）	若 $X \to Y$ ，则 $X Z \to Y Z$	两边加相同属性仍成立
传递律（Transitivity）	若 $X \to Y$ ， $Y \to Z$ ，则 $X \to Z$	函数依赖具有传递性

导出推理规则

规则	内容	说明
合并律	若 $X \to Y$ ， $X \to Z$ ，则 $X \to Y Z$	右边可合并
分解律	若 $X \to Y$ ，且 $Z \subseteq Y$ ，则 $X \to Z$	右边可分解
伪传递律	若 $X \to Y$ ， $W Y \to Z$ ，则 $W X \to Z$	带条件的传递

有效性与完备性

有效性：用 Armstrong 公理从 $F$ 中导出的函数依赖一定在 $F^{+}$ 中
完备性： $F^{+}$ 中的每一个函数依赖，必定可由 $F$ 根据 Armstrong 公理推出

引理 6.1： $X \to A_{1} A_{2} \dots A_{k}$ 成立 $\Leftrightarrow$ $X \to A_{i}$ 成立（ $i = 1, 2, \dots, k$ ）

3.3 属性集的闭包

定义 6.13：设 $F$ 为属性集 $U$ 上的一组函数依赖， $X \subseteq U$ 。

X_{F}^{+} = {A ∣ X \to A 能由 F 根据 Armstrong 导出}

称为属性集 $X$ 关于函数依赖集 $F$ 的闭包。

引理 6.2： $X \to Y$ 能由 Armstrong 公理导出 $\Leftrightarrow$ $Y \subseteq X_{F}^{+}$

核心思想：判定 $X \to Y$ 能否由 $F$ 导出，转化为求 $X_{F}^{+}$ ，判断 $Y$ 是否为 $X_{F}^{+}$ 的子集。

算法 6.1：求属性集闭包

输入：属性集 $X$ ，函数依赖集 $F$ 输出： $X_{F}^{+}$

令 $result := X$ 。
对 $F$ 中每个函数依赖 $A \to B$ ，当 $result$ 发生变化时重复检查。
若 $A \subseteq result$ ，则令 $result := result \cup B$ 。
输出 $result$ 。

最多需要 $| U | - | X |$ 步。

闭包计算例题

【例 1】： $R ⟨ U, F ⟩$ , $U = (A, B, C, G, H, I)$ , $F = {A \to B, A \to C, C G \to H, C G \to I, B \to H}$

求 $(A G)_{F}^{+}$ ：

步骤	所用依赖	result
初始	—	AG
1	$A \to B$	$A G B$
2	$A \to C$	$A G B C$
3	$C G \to H$	$A G B C H$
4	$C G \to I$	$A G B C H I$

结果： $(A G)_{F}^{+} = A G B C H I$

思考：AG 是码吗？若且唯若 $(A G)_{F}^{+} = U$ （包含所有属性），且 $A G$ 的任何真子集的闭包不包含 $U$ ，则 $A G$ 是候选码。

【例 2】： $R ⟨ U, F ⟩$ , $U = (A, B, C, D, E)$ , $F = {A B \to C, B \to D, C \to E, C E \to B, A C \to B}$

求 $(A B)_{F}^{+}$ ：

步骤	所用依赖	result
初始	—	AB
1	$A B \to C$	$A B C$
2	$B \to D$	$A B C D$
3	$C \to E$	$A B C D E$

结果： $(A B)_{F}^{+} = A B C D E = U$ ，故 $A B$ 是码。

【例 3】： $R ⟨ U, F ⟩$ , $U = (A, B, C, D, E, G)$ , $F = {A \to E, B E \to A G, C E \to A, G \to D}$

求 $(A B)_{F}^{+}$ ：

步骤	所用依赖	result
初始	—	AB
1	$A \to E$	$A B E$
2	$B E \to A G$	$A B E G$
3	$G \to D$	$A B E G D$

结果： $(A B)_{F}^{+} = A B E G D \neq U$ （缺少 $C$ ），故 $A B$ 不是码。

判定函数依赖是否蕴含于 F

步骤：

计算闭包：根据 $F$ 计算 $(A_{1} A_{2} \dots A_{n})_{F}^{+}$
判断：若 $B \in (A_{1} A_{2} \dots A_{n})_{F}^{+}$ ，则 $A_{1} A_{2} \dots A_{n} \to B$ 蕴含于 $F$ 中，否则不蕴含

【例 4】： $R ⟨ U, F ⟩$ , $U = (A, B, C, D, E, F)$ , $F = {A B \to C, B C \to A D, D \to E, C F \to B}$

判断 $A B \to D$ 和 $D \to A$ 是否蕴含于 $F$ ？

解：

$(A B)_{F}^{+} = {A, B, C, D, E}$ $D \in (A B)_{F}^{+}$ ，所以 $A B \to D$ 蕴含于 $F$ 。
$D_{F}^{+} = {D, E}$ $A \notin D_{F}^{+}$ ，所以 $D \to A$ 不蕴含于 $F$ 。

3.4 函数依赖集的等价与覆盖

3.4.1 等价性

定义 6.14：

函数依赖集 $F, G$ ，若 $F^{+} = G^{+}$ ，则称 $F$ 与 $G$ 等价
$F^{+} = G^{+} \Leftrightarrow F \subseteq G^{+} \land G \subseteq F^{+}$

3.4.2 最小覆盖（正则覆盖）

定义 6.15：满足下列条件的函数依赖集 $F$ 称为最小覆盖，记作 $F_{min}$ ：

单属性化： $F$ 中任一函数依赖 $X \to A$ ， $A$ 必是单属性
无冗余化： $F$ 中不存在这样的函数依赖 $X \to A$ ，使得 $F$ 与 $F - {X \to A}$ 等价
既约化： $F$ 中不存在这样的函数依赖 $X \to A$ ，在 $X$ 中有真子集 $Z$ ，使得 $F$ 与 $F - {X \to A} \cup {Z \to A}$ 等价

算法 6.2：求解最小覆盖 $F_{min}$

步骤：

① 单属性化：逐个检查 $F$ 中各函数依赖 $F D_{i} : X \to Y$ ，若 $Y = A_{1} A_{2} \dots A_{k}$ （ $k \geq 2$ ），则用诸 $X \to A_{i}$ 代替 $Y$ 。

② 无冗余化：逐个检查 $F$ 中各函数依赖 $X \to A$ ，令 $G = F - {X \to A}$ ，若 $A \in X_{G}^{+}$ ，则从 $F$ 中去掉该函数依赖。

③ 既约化：逐个检查 $F$ 中各函数依赖 $X \to A$ ，设 $X = B_{1} B_{2} \dots B_{m}$ ，逐个考查 $B_{i}$ ，若 $A \in (X - B_{i})_{F}^{+}$ ，则以 $(X - B_{i})$ 取代 $X$ 。

最小覆盖例题

【例 5】： $F = {A \to B, B \to A, A \to C, B \to C}$ ，求 $F_{min}$

解：

已为单属性，无需单属性化
先检查无冗余化：
- 检查 $A \to B$ ： $G = {B \to A, A \to C, B \to C}$ ， $A_{G}^{+} = {A, C}$ ， $B \notin {A, C}$ ，不能删除
- 检查 $A \to C$ ： $G = {A \to B, B \to A, B \to C}$ ， $A_{G}^{+} = {A, B, C}$ ， $C \in {A, B, C}$ ，可以删除
- 检查 $B \to A$ ： $G = {A \to B, B \to C}$ ， $B_{G}^{+} = {B, C}$ ， $A \notin {B, C}$ ，不能删除
- 检查 $B \to C$ ： $G = {A \to B, B \to A}$ ， $B_{G}^{+} = {B, A}$ ， $C \notin {B, A}$ ，不能删除
已为既约化形式

所以 $F_{min} = {A \to B, B \to A, B \to C}$ 。

【例 6】： $F = {C \to A, A \to G, C G \to B, B \to A}$ ，求 $F_{min}$

解：

单属性化：已完成
无冗余化：依次检查各函数依赖
既约化（关键步骤）：检查 $C G \to B$
- 先用 $G$ 代替 $C G$ ： $G_{F}^{+} = {G}$ ， $B \notin {G}$ ，不能用 $G$ 代替
- 先用 $C$ 代替 $C G$ ： $C_{F}^{+} = {C, A, G, B}$ ， $B \in {C, A, G, B}$ ，可以用 $C$ 代替 $C G$
- 所以 $C G \to B$ 被 $C \to B$ 替代

最终： $F = {C \to A, A \to G, C \to B, B \to A}$ 。

四、模式的分解

4.1 分解的定义

定义 6.16：关系模式 $R ⟨ U, F ⟩$ 的一个分解：

ρ = {R_{1} ⟨ U_{1}, F_{1} ⟩, R_{2} ⟨ U_{2}, F_{2} ⟩, \dots, R_{n} ⟨ U_{n}, F_{n} ⟩}

满足：

$U = U_{1} \cup U_{2} \cup \dots \cup U_{n}$
不存在 $U_{i} \subseteq U_{j}$
$F_{i}$ 为 $F$ 在 $U_{i}$ 上的投影

定义 6.17：函数依赖集合 ${X \to Y ∣ X \to Y \in F^{+} \land X Y \subseteq U_{i}}$ 的一个覆盖 $F_{i}$ 叫作 $F$ 在属性 $U_{i}$ 上的投影。

4.2 分解的等价标准

三种模式分解的等价定义：

分解具有无损连接性
分解保持函数依赖
分解既要保持函数依赖，又具有无损连接性

4.3 分解示例

关系模式： $SL (Sno, Sdept, Sloc)$ 函数依赖： $F = {Sno \to Sdept, Sdept \to Sloc, Sno \to Sloc}$ $SL \in 2 N F$ ，存在各种异常。

第一种分解（错误）

分解： $SN (Sno)$ , $SD (Sdept)$ , $SO (Sloc)$

问题：丢失大量信息，例如无法查询 95001 学生所在系或所在宿舍。

结论：既不具有无损连接性，也未保持函数依赖，不是等价分解。

第二种分解（有损）

分解： $NL (Sno, Sloc)$ , $DL (Sdept, Sloc)$

问题： $NL ⋈ DL$ 比原始 $SL$ 多了 3 个元组，无法知道某些学生究竟是哪个系的。

结论：保持了函数依赖，但不具有无损连接性。

第三种分解（无损但未保持依赖）

分解： $ND (Sno, Sdept)$ , $NL (Sno, Sloc)$

结果： $ND ⋈ NL$ 与 $SL$ 完全一致，没有丢失信息。

结论：具有无损连接性，但未保持函数依赖（ $Sdept \to Sloc$ 没有投影到任何分解模式）。

第四种分解（既无损又保持依赖，最优）

分解： $ND (Sno, Sdept)$ , $DL (Sdept, Sloc)$

结论：既具有无损连接性，又保持了函数依赖。

4.4 具有无损连接性的模式分解

定义：关系模式 $R ⟨ U, F ⟩$ 的一个分解 $ρ = {R_{1} ⟨ U_{1}, F_{1} ⟩, R_{2} ⟨ U_{2}, F_{2} ⟩, \dots, R_{n} ⟨ U_{n}, F_{n} ⟩}$ ，若 $R$ 与 $R_{1}, R_{2}, \dots, R_{n}$ 自然连接的结果相等，则称分解 $ρ$ 具有无损连接性（Lossless Join）。

注意：具有无损连接性的分解保证不丢失信息，但不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题。

4.5 保持函数依赖的模式分解

定义：设关系模式 $R ⟨ U, F ⟩$ 被分解为 $R_{1} ⟨ U_{1}, F_{1} ⟩$ , $R_{2} ⟨ U_{2}, F_{2} ⟩$ , …, $R_{n} ⟨ U_{n}, F_{n} ⟩$ （其中 $U = U_{1} \cup U_{2} \cup \dots \cup U_{n}$ ，且不存在 $U_{i} \subseteq U_{j}$ ， $F_{i}$ 为 $F$ 在 $U_{i}$ 上的投影），若 $F$ 所逻辑蕴含的函数依赖一定也由分解得到的某个关系模式中的函数依赖 $F_{i}$ 所逻辑蕴含，则称分解是保持函数依赖的（Preserve Dependency）。

4.6 分解标准之间的关系

分解性质	能达到的最高范式
仅要求无损连接	一定能达到 4NF
仅要求保持函数依赖	一定能达到 3NF，但不一定达到 BCNF
既无损连接又保持函数依赖	一定能达到 3NF，但不一定达到 BCNF

两个独立的标准：

具有无损连接性的分解不一定能够保持函数依赖
保持函数依赖的分解也不一定具有无损连接性

本章小结

本章围绕关系数据理论展开，重点掌握函数依赖、码、范式、Armstrong 公理系统和模式分解。

关键内容

数据依赖：函数依赖和多值依赖是关系模式中属性间语义联系的形式化表示。
码与范式：通过候选码、主码、主属性等概念判断关系模式满足 1NF、2NF、3NF、BCNF 和 4NF 的程度。
规范化过程：从 1NF 到 4NF 逐步消除部分函数依赖、传递函数依赖、主属性相关依赖以及非平凡多值依赖。
Armstrong 公理系统：用于函数依赖的推理，属性集闭包可用于判断某个函数依赖是否由依赖集逻辑蕴涵。
最小覆盖与模式分解：通过最小覆盖简化依赖集，通过模式分解改善关系模式，并关注无损连接和保持函数依赖。

核心要点

规范化理论是数据库设计的指南和工具，不是机械追求越高范式越好。
好的模式分解应尽量同时满足无损连接和保持函数依赖。
实际设计需要在规范化程度、查询效率和应用需求之间取得平衡。

关键术语

函数依赖, 多值依赖, 候选码, 主码, 主属性, 1NF, 2NF, 3NF, BCNF, 4NF, Armstrong 公理, 属性集闭包, 最小覆盖, 无损连接, 保持函数依赖。

关系数据理论 ​

一、概述 ​

1.1 问题的提出 ​

1.2 关系模式的形式化定义 ​

1.3 数据依赖 ​

1.4 数据依赖对关系模式的影响（引例） ​

二、规范化（Normalization） ​

2.1 函数依赖 ​

2.1.1 函数依赖的定义 ​

2.1.2 平凡函数依赖与非平凡函数依赖 ​

2.1.3 完全函数依赖与部分函数依赖 ​

2.1.4 传递函数依赖 ​

2.2 码（Key） ​

2.2.1 候选码与主码 ​

2.2.2 外部码（Foreign Key） ​

2.3 范式（Normal Form） ​

2.4 第二范式（2NF） ​

2.4.1 第一范式（1NF） ​

2.4.2 2NF 的定义 ​

2.4.3 2NF 示例分析 ​

2.5 第三范式（3NF） ​

2.5.1 3NF 的定义 ​

2.5.2 3NF 示例分析 ​

2.6 BC 范式（BCNF） ​

2.6.1 BCNF 的定义 ​

2.6.2 BCNF 示例分析 ​

2.6.3 3NF 与 BCNF 的关系 ​

2.6.4 BCNF 关系模式的性质 ​

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

2.7.1 问题的提出 ​

2.7.2 多值依赖的定义 ​

2.7.3 多值依赖的性质 ​

2.7.4 多值依赖与函数依赖的区别 ​

2.7.5 第四范式（4NF） ​

2.8 规范化小结 ​

三、数据依赖的公理系统 ​

3.1 逻辑蕴涵与闭包 ​

3.2 Armstrong 公理系统 ​

三条基本公理 ​

导出推理规则 ​

有效性与完备性 ​

3.3 属性集的闭包 ​

算法 6.1：求属性集闭包 ​

闭包计算例题 ​

判定函数依赖是否蕴含于 F ​

3.4 函数依赖集的等价与覆盖 ​

3.4.1 等价性 ​

3.4.2 最小覆盖（正则覆盖） ​

算法 6.2：求解最小覆盖 Fmin ​

最小覆盖例题 ​

四、模式的分解 ​

4.1 分解的定义 ​

4.2 分解的等价标准 ​

4.3 分解示例 ​

第一种分解（错误） ​

第二种分解（有损） ​

第三种分解（无损但未保持依赖） ​

第四种分解（既无损又保持依赖，最优） ​

4.4 具有无损连接性的模式分解 ​

4.5 保持函数依赖的模式分解 ​

4.6 分解标准之间的关系 ​

本章小结 ​

关键内容 ​

核心要点 ​

关键术语 ​

关系数据理论

一、概述

1.1 问题的提出

1.2 关系模式的形式化定义

1.3 数据依赖

1.4 数据依赖对关系模式的影响（引例）

二、规范化（Normalization）

2.1 函数依赖

2.1.1 函数依赖的定义

2.1.2 平凡函数依赖与非平凡函数依赖

2.1.3 完全函数依赖与部分函数依赖

2.1.4 传递函数依赖

2.2 码（Key）

2.2.1 候选码与主码

2.2.2 外部码（Foreign Key）

2.3 范式（Normal Form）

2.4 第二范式（2NF）

2.4.1 第一范式（1NF）

2.4.2 2NF 的定义

2.4.3 2NF 示例分析

2.5 第三范式（3NF）

2.5.1 3NF 的定义

2.5.2 3NF 示例分析

2.6 BC 范式（BCNF）

2.6.1 BCNF 的定义

2.6.2 BCNF 示例分析

2.6.3 3NF 与 BCNF 的关系

2.6.4 BCNF 关系模式的性质

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

2.7.1 问题的提出

2.7.2 多值依赖的定义

2.7.3 多值依赖的性质

2.7.4 多值依赖与函数依赖的区别

2.7.5 第四范式（4NF）

2.8 规范化小结

三、数据依赖的公理系统

3.1 逻辑蕴涵与闭包

3.2 Armstrong 公理系统

三条基本公理

导出推理规则

有效性与完备性

3.3 属性集的闭包

算法 6.1：求属性集闭包

闭包计算例题

判定函数依赖是否蕴含于 F

3.4 函数依赖集的等价与覆盖

3.4.1 等价性

3.4.2 最小覆盖（正则覆盖）

算法 6.2：求解最小覆盖 $F_{min}$

最小覆盖例题

四、模式的分解

4.1 分解的定义

4.2 分解的等价标准

4.3 分解示例

第一种分解（错误）

第二种分解（有损）

第三种分解（无损但未保持依赖）

第四种分解（既无损又保持依赖，最优）

4.4 具有无损连接性的模式分解

4.5 保持函数依赖的模式分解

4.6 分解标准之间的关系

本章小结

关键内容

核心要点

关键术语