01 函数依赖

一、函数依赖¶

学生选课表¶

学号 (Sno)	姓名 (Sname)	课程号 (Cno)	成绩 (Grade)
101	张三	C01	85
102	李四	C01	90
101	张三	C02	88
103	王五	C02	76

元组 = 表中的一行记录（如 (101, 张三, C01, 85)）。
属性值 = 元组中某一列的值（如 t1[Sno] = 101）。

1. 函数依赖的定义¶

函数依赖（Functional Dependency, FD）是关系模式中属性之间的一种约束，表示一个或一组属性的值可以唯一决定另一个或一组属性的值。

设关系模式 $R(U)$，$X \subseteq U$，$Y \subseteq U$。对于 $R$ 的任意两个元组 $t_1, t_2$，若 $t_1[X] = t_2[X]$，则必有 $t_1[Y] = t_2[Y]$，则称 X 函数决定 Y，记为 $X \to Y$。

$R(U)$
$R$：关系模式（可以理解为一张表的结构定义）
$U$：属性集合（表的所有字段/列名的集合）合起来：关系$R$由属性集$U$定义。
$X \subseteq U$、$Y \subseteq U$
$\subseteq$：包含于（子集符号）
$X、Y$ 都是$U$的子集直白说：$X$和$Y$都是从表的所有字段里，选出来的一部分字段。

2. 函数依赖推理规则¶

Armstrong公理是一组完备且正确的推理规则，用于从已知的函数依赖推导出隐含的函数依赖。

设 $$ X, Y, Z, W $$ 是属性集合的子集，$$ U $$ 为全集。

自反律：
若 $$Y \subseteq X \subseteq U$$，则 $$ X \to Y $$。
增广律：
若 $$ X \to Y $$，且 $$ Z \subseteq U $$，则 $$ XZ \to YZ $$。
（两侧同时增加相同属性）
传递律：
若 $$ X \to Y $$ 且 $$ Y \to Z $$，则 $$ X \to Z $$。

由这三条基本公理可以导出以下附加规则（常用）：

合并律：若 $$ X \to Y $$ 且 $$ X \to Z $$，则 $$ X \to YZ $$。
分解律：若 $$ X \to YZ $$，则 $$ X \to Y $$ 且 $$ X \to Z $$。
伪传递律：若 $$ X \to Y $$ 且 $$ YW \to Z $$，则 $$ XW \to Z $$。

注意：所有推导出的函数依赖都必须满足原关系模式的所有实例，不可凭空臆造。

依赖的基本定义¶

数据库概念：$$X \to Y$$（属性集 $$X$$ 函数决定属性集 $$Y$$）
数学函数类比：给定输入参数 $$x$$，通过函数 $$f$$ 唯一确定输出值 $$y = f(x)$$
类比解释：$$X$$ 相当于输入参数（自变量），$$Y$$ 相当于输出值（因变量）。函数依赖强调“确定性的映射关系”，与数学函数一一对应。

自反律¶

数据库概念：若 $$Y \subseteq X$$，则 $$X \to Y$$
数学函数类比：给定一个元组 $$(x_1, x_2, \dots, x_n)$$，可以唯一确定它的一个子集（如投影操作）
类比解释：平凡依赖好比：已知全部参数，当然能知道其中一部分参数的值。数学上属于“恒等投影”。
（平凡函数依赖，例如 $$ (学号,姓名) \to 姓名 $$）
应用：识别候选键

增广律¶

数据库概念：若 $$X \to Y$$，则 $$XZ \to YZ$$
数学函数类比：若 $$y = f(x)$$，则对于任意额外参数 $$z$$，有 $$(y, z) = (f(x), z)$$，即 $$(x, z) \to (y, z)$$
类比解释：在函数两边同时添加相同的无关参数 $$z$$，新的映射依然是确定性的。类似于在输入输出中增加一个“直通”分量。

合并律¶

数据库概念：若 $$X \to Y$$ 且 $$X \to Z$$，则 $$X \to YZ$$
数学函数类比：给定 $$x$$，同时有 $$y = f(x)$$ 和 $$z = g(x)$$，则 $$x$$ 唯一决定有序对 $$(y, z)$$
类比解释：相当于构造向量值函数 $$h(x) = (f(x), g(x))$$。这是函数合并的直观体现。
应用：识别候选键

分解律¶

数据库概念：若 $$X \to YZ$$，则 $$X \to Y$$ 且 $$X \to Z$$
数学函数类比：若 $$x$$ 唯一确定有序对 $$(y, z)$$，则 $$x$$ 必然唯一确定 $$y$$ 和 $$z$$ 各自的分量
类比解释：这是向量值函数的投影性质：从整体决定关系可以推出分量决定关系。
应用：识别候选键

伪传递律¶

数据库概念：若 $$X\to Y$$ 且 $$YW \to Z$$，则 $$XW \to Z$$
数学函数类比：局部代入的复合：给定 $$(x, w)$$，先由 $$x$$ 得 $$y = f(x)$$，再将 $$(y, w)$$ 代入 $$g$$ 得 $$z = g(y, w)$$
类比解释：类似于 $$z = g(f(x), w)$$。它允许你先用一部分输入计算中间结果，再将该结果与剩余输入一起作为新函数的输入。

传递律¶

数据库概念：若 $$X \to Y$$ 且 $$Y \to Z$$，则 $$X \to Z$$
数学函数类比：函数的复合：若 $$y = f(x)$$ 且 $$z = g(y)$$，则 $$z = g(f(x))$$
类比解释：经典链条：输入 $$x$$ 得到中间结果 $$y$$，再将 $$y$$ 代入 $$g$$ 得到 $$z$$。整个复合 $$g \circ f$$ 也是函数。

3. 候选键的求解（属性闭包）¶

1. 基本概念¶

超键：能唯一标识一个元组的属性集合（可能有冗余）。
候选键：最小的超键，即去掉任一属性后就不再是超键。
主键：被选中的那个候选键。

1. 严格定义与数学类比¶

术语	数据库定义	数学函数视角的类比
超键 (Super Key)	能够唯一标识一个元组的属性集合。	函数的“一组输入参数”。只要给这组参数，就能唯一算出那一行。可能有多余参数（比如多给了个 $z$）。
候选键 (Candidate Key)	最小的超键。即去掉其中任何一个属性，就不再是超键。	函数的“最小完备输入参数集”。少一个就算不准，多一个就冗余。
主键 (Primary Key)	数据库设计者从候选键中人为选定的一个，作为表的主标识符。	人为指定的默认输入方式。
主属性 (Prime Attribute)	任何一个候选键中出现的属性。	任何出现在某个“最小输入集”里的变量。
非主属性 (Non-prime)	不包含在任何候选键中的属性。	纯“输出值”变量。它从来不用作输入的必需部分。

2. 综合举例（学生选课表）¶

假设一个简化场景，表结构为：
学生表(学号, 身份证号, 姓名, 系别)

已知现实世界的语义约束：

学号唯一对应一个人。
身份证号也唯一对应一个人。
一个人只有一个姓名和系别。

第一步：写出函数依赖 (FD)¶

学号 → 身份证号, 姓名, 系别
身份证号 → 学号, 姓名, 系别

第二步：识别超键 (Super Key)¶

只要一个属性集能决定全表所有属性，它就是超键。

{学号} ✅ (能决定身份证、姓名、系别，能决定整行)
{身份证号} ✅
{学号, 姓名} ✅ (虽然是多余的，但它确实能唯一决定一行)
{身份证号, 系别} ✅ (也是多余的，但它是超键)

第三步：识别候选键 (Candidate Key)¶

从超键中找出最小的（不可再精简的）。

候选键只有两个：{学号} 和 {身份证号}。
{学号, 姓名} 不是候选键，因为去掉“姓名”剩下的 {学号} 仍然是超键。

第四步：识别主键 (Primary Key)¶

人为选择。

DBA 选定 {学号} 作为主键。
{身份证号} 就成了备用键 (Alternate Key)。

第五步：识别主属性 vs 非主属性¶

主属性 (Prime Attribute)：
学号：因为它在候选键 {学号} 中。
身份证号：因为它在另一个候选键 {身份证号} 中。
结论：哪怕身份证号没有被选为主键，它依然属于主属性。
非主属性 (Non-prime Attribute)：
姓名：不在任何候选键中，纯粹是被决定的值。
系别：不在任何候选键中，纯粹是被决定的值。

3. 关键误区澄清（这关系到理解 3NF）¶

误区：“我不是主键里的字段，我就是非主属性。” 正解：“只要我是任意一个候选键里的字段，我就是主属性。”

为什么这个区分对 3NF 极其重要？ 3NF 的定义说：“允许存在非主属性对候选键的传递依赖吗？不允许。但如果是主属性对候选键的传递依赖呢？允许（在 3NF 层面暂时容忍）。”

例如：假设存在依赖 系别 → 系主任 且 系主任 → 办公地点。

如果 系别 和 系主任 都是非主属性，这叫传递依赖，3NF 必须消灭它。
如果 系别 是主属性（比如它是某个候选键的一部分），3NF 可能会暂时放过它（这属于 BCNF 才解决的问题）。

2. 属性闭包（Closure）的定义¶

给定关系模式 $$ R(U, F) $$，$$ X \subseteq U $$，属性闭包 $$ X^+ $$ 表示：从 X 出发，利用函数依赖集 F 能推导出的所有属性的集合。

计算方法（迭代算法）：

令 $$ result = X $$。
重复查找：
对于 $$ F $$ 中的每个函数依赖 $$ A \to B $$：
若 $$ A \subseteq result $$，则 $$ result = result \cup B $$。
直到 $$ result $$ 不再扩大。
最终的 $$ result $$ 即为 $$ X^+ $$。

属性闭包算法本质上就是利用函数依赖的传递性（包括直接依赖和间接依赖）不断扩充属性集合。

3. 利用属性闭包求解候选键¶

步骤：

从单个属性开始，计算其闭包，若等于全集 $$ U $$，则该属性是候选键。
若不是，尝试两个属性、三个属性…，直到找到所有最小的能决定全集的属性组合。

示例：

关系模式 $$ R(A,B,C,D) $$，函数依赖集 $$ F = { A \to B,\; B \to C,\; C \to D } $$。

计算 $$ A^+ $$：
初始 {A} → 由 $$ A \to B $$ 得 {A,B} → 由 $$ B \to C $$ 得 {A,B,C} → 由 $$ C \to D $$ 得 {A,B,C,D}。
所以 $$ A^+ = ABCD $$，A 是候选键。
检查 B：$$ B^+ = BCD $$（不含A），不是候选键。
检查 C：$$ C^+ = CD $$。
检查 D：$$ D^+ = D $$。

因此唯一候选键是 $$ A $$。

多属性候选键示例：

$$ R(A,B,C) $$，$$ F = { AB \to C,\; C \to A } $$。

计算 $$ AB^+ $$：{A,B} → 由 $$ AB \to C $$ 得 {A,B,C} → 全集，候选键？但检查是否最小：
去掉A得 B^+ = B，不是；
去掉B得 A^+ = A（C→A 需要C，但C不在A中），也不是。

所以 AB 是候选键。
计算 $$ C^+ $$：{C} → 由 $$ C \to A $$ 得 {A,C} → 无法得到B，不是候选键。
检查 BC？ $$ BC^+ $$：{B,C} → C→A 得 {A,B,C} → 全集。
去掉B得 C^+ = AC ≠ 全集；
去掉C得 B^+ = B ≠ 全集。

所以 BC 也是候选键。最终候选键为 {AB, BC}。

4. 最小函数依赖集（最小覆盖）¶

1. 定义¶

最小函数依赖集（Minimal Cover / Canonical Cover）是与原函数依赖集 $$ F $$ 等价的、满足以下三个条件的依赖集 $$ F_{min} $$：

右部单属性：每个函数依赖的右边只有一个属性（分解律处理）。
左部无冗余属性：没有依赖 $$ X \to A $$ 使得 $$ X $$ 的真子集 $$ Z $$ 也能函数决定 $$ A $$（即左部不可约）。//完全依赖
无冗余依赖：删除任何一个依赖，就不再与 $$ F $$ 等价。

2. 求解算法¶

步骤：

右部分解：将每个 $$ X \to Y $$（Y含多个属性）分解为 $$ X \to A_1, X \to A_2, … $$。
左部化简：对每个依赖 $$ X \to A $$，检查 $$ X $$ 的每个属性 $$ B $$：
假设去掉 $$ B $$，计算 $$ (X-{B})^+ $$（使用当前依赖集）。
如果 $$ A \in (X-{B})^+ $$，则 $$ B $$ 是冗余的，可以从左部删除。
删除冗余依赖：对每个依赖 $$ X \to A $$：
临时从依赖集中去掉该依赖，计算 $$ X^+ $$（使用剩余依赖）。
如果 $$ A $$ 仍然在 $$ X^+ $$ 中，说明该依赖是冗余的，可删除。

3. 示例¶

给定 $$ F = { AB \to C,\; A \to B,\; B \to C } $$。

Step 1：右部已单属性，无需分解。

Step 2：左部化简

对 $$ AB \to C $$：
去掉A，计算 $$ B^+ $$：初始{B}，由 $$ B \to C $$ 得 {B,C}，不含C？实际上B+ = BC，已包含C。所以A是冗余的，可删除，依赖变为 $$ B \to C $$。
再去掉B？但已经得到新依赖，先继续。
更新依赖集后：$$ { B \to C, A \to B, B \to C } $$ （重复了）。
对 $$ A \to B $$：左部只有一个属性，无需化简。
对 $$ B \to C $$：左部单属性，无需化简。

Step 3：删除冗余依赖
当前依赖集 = { $$ B \to C, A \to B $$ } （重复的去掉一个）。
检查 $$ B \to C $$：临时去掉它，计算 $$ B^+ $$（只利用剩余依赖 $$ A \to B $$）：
初始{B}，无依赖能使用，B+ = {B}，不包含C，所以 $$ B \to C $$ 不是冗余。
检查 $$ A \to B $$：临时去掉，计算 $$ A^+ $$（利用 $$ B \to C $$）：
A+ = {A}（因为无法得到B），所以不包含B，$$ A \to B $$ 也不是冗余。

最终最小依赖集：$$ { A \to B,\; B \to C } $$。

（注意：原 $$ AB \to C $$ 被推导掉了，因为 $$ A \to B $$ 和 $$ B \to C $$ 已经能推出 $$ AB \to C $$ 了。）

总结表格¶

概念	核心作用	典型方法
函数依赖	描述属性间决定关系	Armstrong公理推导
属性闭包 $$ X^+ $$	判断X是否为超键/候选键，求最小依赖	迭代扩展法
候选键	无冗余的唯一标识元组的最小属性集	闭包等于全集的极小集合
最小函数依赖集	化简依赖，消除冗余	分解右部→左部化简→删除冗余