函数依赖 — rin.contact

函数依赖是对数据的一个承诺：只要两行在这几列上相同，它们在那一列上也相同。数据库设计有很大一部分工作，就是把这些承诺写下来，再安排表的结构，让每个事实只存在一个地方。这篇笔记讲一个依赖说的是什么，怎样从几个依赖推出它们蕴含的全部依赖，以及为什么无视依赖的表会让每次更新都有机会自相矛盾。

基本想法

当知道列 $X$ 的值就能确定列 $Y$ 的值时，写作 $X \to Y$ ，读作“ $X$ 决定 $Y$ ”。在一张售票表里，票号决定票种，票种决定票价。依赖是对系统任何时候可能存的每一张表的断言，而不只是今天表里那些行。所以它是一条业务规则，来自这些列的含义。

键是能决定所有其他列、又没有多余列的一组列。声明主键，就是声明一个从键到整行的依赖。这也是为什么一个随手选的键，会悄悄地让表存不下实际发生的事情。

麻烦始于依赖的左边不是键。想象一张很宽的展馆扫描表，每一行都抄着票种和票价。成人票价就出现在每一条成人票扫描记录里。改票价时你得改所有这些行，漏掉一行，表里就同时有两个成人票价。这叫更新异常。你也没法在有人用新票种扫码之前记录它的票价，而删掉最后一条会员票扫描记录，就忘了会员票卖多少钱。规范化通过拆表一次解决这三个问题，让每个依赖的左边成为它自己那张表的键。数据库系统主题会一步步讲把这件事精确化的各个范式。

数学

形式上，如果一个关系里没有两行在 $X$ 上相同却在 $Y$ 上不同，就说它满足 $X \to Y$ 。

X \to Y \iff \text{for all rows } t_1, t_2:\; t_1[X] = t_2[X] \;\Rightarrow\; t_1[Y] = t_2[Y]

一对行就足以推翻一个依赖。多少行都不足以证明一个依赖。

从一组声明的依赖 $F$ 出发，Armstrong 的三条规则能推出所有必然成立的依赖：自反律、增广律和传递律。

\frac{Y \subseteq X}{X \to Y} \qquad\qquad \frac{X \to Y}{XZ \to YZ} \qquad\qquad \frac{X \to Y \quad Y \to Z}{X \to Z}

这些规则是可靠的，不会推出错误的依赖，也是完备的，能推出每一个正确的依赖。

实际上很少有人手工套这些规则，而是计算闭包：从 $X$ 开始，只要某个声明的依赖的左边落在当前集合里，就把它的右边加进来，直到不再变化。

X^{+} = \{\, A : X \to A \text{ follows from } F \,\}, \qquad X \text{ is a superkey} \iff X^{+} = R

键就是去掉任何一列都不再是超键的超键。

Boyce–Codd 范式要求每个成立的依赖左边都是超键。第三范式稍微放宽，允许右边是某个键的一部分，这样在 BCNF 做不到的时候，每个依赖仍然能在单张表里检查。

R \text{ is in BCNF} \iff \text{every non-trivial } X \to Y \text{ that holds has } X^{+} = R

平凡指 Y 已经包含在 X 里，比如票号和时间决定时间。

拆表不能丢信息。把拆出来的表再连接回去，必须正好得到原来的行，不多也不少。当共享的列是其中一张表的键时，这一点就有保证。

R \to R_1, R_2 \text{ is lossless} \iff (R_1 \cap R_2) \to R_1 \;\text{ or }\; (R_1 \cap R_2) \to R_2

按依赖 X 到 Y 拆分：用 X 和 Y 组成一张表，另一张表保留 X。

动手试

下面的工具存着一家虚构博物馆的展馆扫描日志，每次扫描一行，还有设计者声明的四条规则。用按钮拼出一个依赖，工具会分别回答两个问题：这份样本有没有违反它，它能不能从声明的规则推出来。

设计者声明的规则

票号 → 票种
票种 → 票价
展馆 → 楼层
票号, 时间 → 展馆

左边 X（选一个或多个）

右边 Y

样本行数16

种子 1

票号 → 展馆

在这份样本里

不成立。第 1 行和第 4 行的票号相同（T08），展馆却不同：East 对 West。

从声明的规则推出

{票号}⁺ = {票号、票种、票价}。展馆不在闭包里，所以规则没有承诺这一点。左边不是键。

推导：票号 → 票种，再票种 → 票价。

按时间排序的前 16 条展馆扫描记录。X 列标 (X)，Y 列标 (Y)。
#	票号 (X)	票种	票价	展馆 (Y)	楼层	时间
1冲突	T08	Member	0	East	L2	09:10
2	T03	Adult	22	East	L2	09:14
3	T01	Adult	22	West	L0	09:17
4冲突	T08	Member	0	West	L0	09:18
5	T01	Adult	22	East	L2	09:57
6	T08	Member	0	North	L1	09:59
7	T01	Adult	22	West	L0	10:02
8	T02	Adult	22	West	L0	10:25
9	T05	Adult	22	West	L0	10:41
10	T04	Member	0	West	L0	10:53
11	T02	Adult	22	West	L0	11:08
12	T04	Member	0	East	L2	11:12
13	T04	Member	0	North	L1	11:54
14	T06	Adult	22	East	L2	12:10
15	T07	Adult	22	North	L1	12:38
16	T06	Adult	22	West	L0	12:43

按规则拆分这张表

不成立。第 1 行和第 4 行的票号相同（T08），展馆却不同：East 对 West。展馆不在闭包里，所以规则没有承诺这一点。

扫描记录来自一个遵守四条声明规则的带种子生成器，所以你找到的任何违反，都是没有人承诺过的依赖。

默认问的是票号能不能决定展馆。数据违反了它，因为一张票会去好几个展馆，而票号的闭包只有票号、票种和票价。
在左边加上时间。票号和时间一起决定展馆，闭包覆盖了所有列，这一对就是键。
试试票价决定票种。16 行时它成立。把行数拖到 24，会发现一张儿童票和一张会员票都是 0 元。票种决定票价，反过来从来不是规则。
试试时间决定票号。32 行以内，每次扫描都落在不同的分钟上，样本推翻不了它。到 40 行时，好几个分钟出现了重复。样本可以推翻依赖，却永远证明不了依赖。
勾上拆分。有三条声明的规则左边不是键，按它们拆分后存的单元格更少，成人票价也只存在一行里。

我在哪用到它

INFO20003 · COMP90050

2020 年在 INFO20003 里，我为卢浮宫的售票和访客数据库设计了实体关系模型，这是一份个人作业，这门课在讲 ER 建模的同时也讲依赖和范式。2026 年我把它复活成Louvre Ops DB，把五年的合成活动数据回放进 2020 年的表里，设计评审的十二条发现中有好几条是依赖问题。Wings 表只用展馆名称作键，等于声称名称决定这一行的其他所有列，结果 19,545 次展馆参观只能存下 3 次。Entrance 表的键记录不了访客从同一个入口再次入场，而作业要求是允许再入场的。一个“营业日”标记重复了日期本身已经说明的信息，一个存下来的访客人数复制了本来用查询就能算出的行。改进后的模式给展馆扫描和入场记录各建了一张有自己键的表。

2023 年的 COMP90050 高级数据库系统，接着讲模式设计之后的事。我们小组的综述讲自驱数据库，我合写了其中索引选择的那一半。在它 2026 年的复活版自驱数据库实验室里，INFO20003 的卢浮宫数据库作为第二个数据集，配上博物馆的查询负载，于是同一个模式又遇上了索引顾问。

容易出错的地方

五个陷阱

从数据里读出依赖。样本能推翻 $X \to Y$ ，却永远确立不了它，上面的时间和票号就是例子。依赖来自列的含义，所以要去问懂规则的人。
把依赖读反。票种决定票价，票价却不决定票种。假设它成立的设计，会把所有免费票合并成一种。
选了一个断言过多的键。键意味着两行永远不会有相同的键值。声明之前先问：两件真实发生的事会不会有相同的值？同一个展馆的两次参观，显然会。
拆表却不检查连接。如果共享的列不是任何一边的键，连接回去时会多出行来。删掉宽表之前，先确认拆分是无损的。
把规范化当成最终答案。以读取为主的报表常常故意反规范化。这是用冗余换速度，最安全的做法是让这些冗余从规范化的源头派生，而不是手工录入两遍。

参考资料

A relational model of data for large shared data banksCodd，Communications of the ACM 第 13 卷第 6 期，1970，第 377–387 页。开创关系数据库的论文，其中第一次讨论了关系的规范化。
A simple guide to five normal forms in relational database theoryKent，Communications of the ACM 第 26 卷第 2 期，1983，第 120–125 页。短小直白，每个范式一个例子。至今仍是看懂每个范式禁止什么的最快途径。
Database Management SystemsRamakrishnan 与 Gehrke，第 3 版，McGraw-Hill，2003。第 19 章。讲模式求精的标准教材章节：闭包、键、BCNF 和 3NF，以及无损且保持依赖的分解。