函数依赖与属性闭包

形式陈述

依赖约束与语义后承

采用关系数据模型：属性集 $U$ 有限，关系 $r$ 是 $U$ 上的有限元组集合，无 NULL，不计重复行。本页固定无限共同值论域，以便随时选取互异普通值；实际出现的值仍然有限。对 $X\subseteq U$ ， $s[X]$ 表示元组 $s$ 在这些列上的限制。写 $AB$ 表示属性集合 $\{A,B\}$ ，而不是字符串相乘。

函数依赖 $X\to Y$ 的语义为

r\models X\to Y \quad\Longleftrightarrow\quad \forall s,t\in r,\quad s[X]=t[X]\Longrightarrow s[Y]=t[Y].

它要求每个实际出现的 $X$ 值组合最多对应一个 $Y$ 值组合，并不要求所有可能的 $X$ 组合都出现。有限依赖集 $F$ 规定允许哪些关系； $r\models F$ 表示其中每条约束都成立。写 $F\models X\to Y$ ，是说每一个满足 $F$ 的有限关系都满足 $X\to Y$ 。这种全实例后承与眼前某张表是否满足约束是两个层次。

记全部后承依赖为 $F^+$ ，并定义 $X$ 的属性闭包

X_F^+=\{A\in U:F\models X\to A\}.

由定义， $F\models X\to Y$ 当且仅当 $Y\subseteq X_F^+$ 。若 $X_F^+=U$ ，称 $X$ 为超键；若它还是按集合包含关系极小的超键，称为候选键。极小表示删掉任意属性都会失去超键性质，不表示与别的候选键相比基数最小。

闭包的固定点算法

从已知属性 $X$ 出发，只要某条依赖左侧已经全部知道，就把右侧加入。下面的完整扫描一直重复到整轮没有变化；一条依赖暂时不能用，不等于以后不能用。

text

S := X
repeat
    changed := false
    for each (L → M) in F:
        if L ⊆ S and M ⊈ S:
            S := S ∪ M
            changed := true
until changed = false
return S

算法保持 $X\subseteq S\subseteq X_F^+$ ，且 $S$ 只增不减。设 $n=|U|$ ，用布尔数组记录属性成员，令 $\ell=1+\sum_{L\to M\in F}(|L|+|M|)$ 为依赖文本大小。一次扫描耗时 $O(\ell)$ ，每个发生变化的扫描至少新增一个属性，故至多 $n$ 个这样的扫描，加上最后一次检查；时间为 $O((n+1)\ell+n)$ ，工作存储为 $O(n)$ ，含输入为 $O(n+\ell)$ 。这是朴素反复扫描的界，不需要假设一遍扫描就足够。

直觉

知道一个学生编号后能够确定姓名，是“相同编号的两行必须有相同姓名”；它没有告诉我们编号如何编码，也没有给出计算姓名的函数程序。函数依赖中的“函数”表达唯一性，因此即使只存了很少的行，也可以声明这种约束。

闭包把这种唯一性沿依赖传播。若编号决定班级，班级决定教室，那么两个在编号上相同的元组先在班级上相同，再在教室上相同。算法记录的不是具体姓名或教室，而是哪些列的一致性已经被迫成立。一个属性没进入闭包，还需要证明“它确实不能由约束推出”；后面的两行反模型承担的正是这一步。

例子与边界

同一模式上的十六个闭包

以下固定

U=ABCD,\qquad F=\{A\to B,\ BC\to A,\ C\to D\}.

例如从 $AC$ 出发， $A\to B$ 先给出 $ABC$ ， $C\to D$ 再给出 $ABCD$ 。从 $BC$ 出发， $BC\to A$ 给出 $ABC$ ，随后也得到 $ABCD$ 。若从 $AD$ 出发，只能用 $A\to B$ 得到 $ABD$ ；没有任何规则能产生 $C$ ，因此扫描到固定点就停止。

$X$	$X_F^+$	$X$	$X_F^+$
$\varnothing$	$\varnothing$	$D$	$D$
$A$	$AB$	$AD$	$ABD$
$B$	$B$	$BD$	$BD$
$AB$	$AB$	$ABD$	$ABD$
$C$	$CD$	$CD$	$CD$
$AC$	$ABCD$	$ACD$	$ABCD$
$BC$	$ABCD$	$BCD$	$ABCD$
$ABC$	$ABCD$	$ABCD$	$ABCD$

这些结果也能按是否含 $C$ 来理解。不含 $C$ 时永远不能产生 $C$ ，所以不可能成为超键。含 $C$ 而不含 $A,B$ 时，最多得到 $CD$ ；再加 $A$ 或 $B$ 才能触发通往全部属性的链。因此每个超键必须包含 $AC$ 或 $BC$ ，而这两个集合自身都已是超键。它们的真子集均不是超键，故全部候选键恰为 $AC$ 与 $BC$ 。属于至少一个候选键的属性称为主属性，于是 $A,B,C$ 是主属性， $D$ 不是。

一张样本表不能证明模式后承

两行 $(a_1,b_1,c_1,d_1)$ 、 $(a_2,b_2,c_2,d_2)$ 若所有下标不同，就碰巧满足 $B\to A$ ：没有两条不同的行共享 $B$ 。但上表给出 $B_F^+=B$ ，因此 $F$ 并不推出 $B\to A$ 。具体反例可以取 $(0,0,0,0)$ 与 $(1,0,1,1)$ ：两行的 $A$ 、 $BC$ 、 $C$ 都不同，所以满足原来三条依赖；它们的 $B$ 相同而 $A$ 不同，否定了额外依赖。

空表及单行表满足所有函数依赖，同样不能据此推断业务规则。另一方面，若声明了 $\varnothing\to U$ ，空集就是候选键：空列上的两行总是相同，所以合法关系最多一行。这是定义允许的情况，不应由“键必须有一列”的惯例排除。

推论与应用

为什么算法可靠而且完备

先证可靠性。取任意 $r\models F$ 及任意在 $X$ 上相等的两行 $s,t$ 。初始 $S=X$ 时它们在 $S$ 上相等。若一步使用 $L\to M$ ，因为 $L\subseteq S$ ，两行已在 $L$ 上相等； $r$ 满足这条依赖，因而它们也在 $M$ 上相等。归纳得到每次新增的属性都由 $X$ 决定，最终 $S\subseteq X_F^+$ 。

再证没有漏掉后承。设最终集合为 $S$ ，取两个值 $0\ne1$ ，构造两行： $s$ 的所有列都是 $0$ ； $t$ 在 $S$ 内取 $0$ ，在 $U\setminus S$ 内取 $1$ 。对任一 $L\to M\in F$ ，如果这两行在 $L$ 上相同，就有 $L\subseteq S$ 。因为算法已经到固定点，必有 $M\subseteq S$ ，所以两行也在 $M$ 上相同。故两行组成的关系满足全部 $F$ 。

然而，对每个 $A\notin S$ ，两行在 $X\subseteq S$ 上相同、在 $A$ 上不同，因而否定 $X\to A$ 。所以 $X_F^+\subseteq S$ ，结合可靠性得到相等。若 $S=U$ ，本来就没有需要排除的属性。这个反例只有两行，说明闭包完备性在有限关系语义下已经成立；相同可靠性证明也适用于无限关系，因此这里有限与任意关系的 FD 后承一致。

从闭包进入分解设计

计算一次闭包就能判断一个候选依赖是否由 $F$ 推出，也能检查某集合是不是超键。要检查候选键的极小性，只需分别删除其中一个属性再算闭包：若有更小的真子集仍是超键，包含它的某个单属性删除集也会是超键。枚举所有候选键仍可能涉及指数多个子集，不能把一次闭包的多项式界直接当作列出所有键的复杂度。

无损连接分解会使用公共列的闭包判断投影是否能可靠拼回，并在同一 $ABCD$ 模式上区分无损与依赖保持。这里算出的两个候选键也决定那个例子的主属性，从而解释为什么一个分解可以达到第三范式，却仍未达到 BCNF。

参考资料

Serge Abiteboul、Richard Hull、Victor Vianu，Foundations of Databases，作者官方在线稿第 8 章，§8.2，Definition 8.2.1、Algorithm 8.2.7、Proposition 8.2.8，印刷页 163–166：FD 后承、属性闭包算法及两行反模型。本文把值论域固定为无限集合，覆盖该反模型所需的至少两值条件。

形式陈述 ​

依赖约束与语义后承 ​

闭包的固定点算法 ​

同一模式上的十六个闭包 ​

一张样本表不能证明模式后承 ​

为什么算法可靠而且完备 ​

从闭包进入分解设计 ​

反向链接