极小函数依赖集求解算法：属性闭包与冗余消除四步通关

数据库复习到这个阶段，大部分人的心态是：函数依赖听得懂，属性闭包也算过两遍，一看“极小函数依赖集求解算法”这道大题的步骤，脑子里还是一团浆糊。期末卷子里这道题分值不低，而且它不只是考一个定义，而是把闭包、逻辑蕴含、等价覆盖全部串起来考。一旦某个环节卡住，后面全盘崩。这篇文章我就把极小函数依赖集（也叫最小函数依赖集，英文对应 minimal cover）的求解算法彻底讲透，用一道完整例题带你走一遍标准四步流程，再把考场最容易踩的坑一个一个排掉。

我写这篇文章的受众很明确：正在复习数据库系统概论、准备期末考试或考研的本科生。如果你已经能快速求属性集闭包，那直接跳到第 3 节的例题推演；如果闭包还不太熟，先把第 1 节啃完。整个过程不需要你背任何花哨公式，只要把握住一个核心判断准则：什么情况下删掉某个东西之后，整个依赖集的“能力”仍然不变。理解了这个，所有步骤都会变得顺理成章。

1. 动手之前：先把闭包和逻辑蕴含这两个地基打牢

1.1 函数依赖到底在描述什么

很多同学一上来就背“X→Y 表示 X 函数决定 Y”，但真正做题时还是分不清这个箭头和“推导”“因果”之间的关系。我习惯用一个链条比喻：如果 X→Y，就相当于有一条从 X 指向 Y 的箭头，表示只要你知道了 X 这一组属性的具体取值，Y 的取值就跟着被唯一确定。举个例子，学号如果唯一，那么“学号→姓名”就是一条可用的函数依赖，因为一个学号只会对应一个姓名。

这里要特别提醒一下：函数依赖描述的是关系模式里所有可能实例都满足的约束，不是某一个表里碰巧成立的关系。这是最容易忽略的隐含前提。考试时题目给一个关系模式 R(U, F)，里面的 F 就是这个模式上的全部约束，算法操作的也始终是这组约束，而不是具体数据。

在函数依赖的推理方面，形式上可以记一下 Armstrong 公理：自反律、增广律、传递律。但实际考试计算极少需要你一条条推导引用，更常用的是一套衍生规则：合并律、分解律、伪传递律。极小依赖集的第一步“把右部拆成单属性”，本质上就用到了分解律，这一步在后面的例题里会非常直观。

1.2 属性集闭包怎么求：一把万能钥匙

如果只能选一个技能作为数据库复习的核心，我会选属性集闭包。所谓属性集 X 关于函数依赖集 F 的闭包，记为 X⁺，就是“根据 F 中这些依赖，从 X 出发能一路推出的所有属性组成的集合”。

算法本身不复杂，就是一个反复扫描的过程：

1. 初始化结果集合为 X 本身。
2. 对 F 中每个依赖 Y→Z，如果 Y 的所有属性都已经在结果集合里，就把 Z 的所有属性加进结果集合。
3. 重复第 2 步，直到结果集合不再变大。

伪代码写出来更清楚：

def attr_closure(X, F): result = set(X) changed = True while changed: changed = False for Y, Z in F: if set(Y).issubset(result) and not set(Z).issubset(result): result = result | set(Z) changed = True return result

看着简单，实际做题时最容易出的问题就是“扫一遍就停”。比如属性在第二轮才被加进结果，第三轮才能触发某个新依赖，如果你只扫一遍，就会漏掉后面的推导。所以在草稿纸上计算时，我建议把依赖集整理成“按左部排序”的清单，每一轮从头到尾扫一次，直到某轮完全没有新属性加入才停。这一步做得越快越稳，后面的极小依赖集求解就越有底气。

1.3 逻辑蕴含与覆盖等价：判断“删了之后还等不等价”

极小函数依赖集的所有删除操作，最终都要回答同一个问题：删掉这个东西之后，函数依赖集的“能力”有没有变？这里面有两个概念必须先分清楚，一个是逻辑蕴含，一个是集合等价。

说一个函数依赖 X→Y 被另外一个函数依赖集 F 逻辑蕴含，意思是“只要 F 里所有依赖都成立，那么 X→Y 也必然成立”。判断起来非常直接：算 X 关于 F 的闭包 X⁺，如果 Y 是 X⁺ 的子集，那就说明 X→Y 被 F 蕴含。这个准则整篇文章都在用。

再说两个依赖集 F 和 G 等价。等价的定义是 F⁺ = G⁺，也就是两个集合能推出的依赖完全一样。但实际操作时我们很少真的把闭包全部列出来，而是用一个等价判定：F 中每个依赖都能由 G 推出，同时 G 中每个依赖都能由 F 推出。这其实就是两边互相做一次逻辑蕴含检查。掌握了这个，后面“检验最终结果与原集合等价”那一步就有依据了，而不是凭感觉。

2. 最小依赖集的定义：三条规则到底在防什么

2.1 三条标准的直观理解

教科书上的最小函数依赖集定义通常列三条：每条函数依赖的右部都是单一属性；每条依赖的左部没有冗余属性；整个集合里没有冗余函数依赖。这三条各自解决一类问题，不能混为一谈。

右部必须是单属性，这是为了统一表达。比如 X→AB 和 X→A、X→B 这两种写法本质是一样的，但如果题目里既有 X→AB 又有 Y→A，你很难一眼看出哪些依赖可合并、哪些是多余的。先把右部原子化，等于把所有依赖打成同一规格的“零件”，后面处理才能机械化。

左部无冗余属性，说的是不能存在这样的依赖：X→A，但 X 里有个属性 xi 是多余的，即使把它从左部拿掉，剩下那一组属性仍然能决定 A。最典型的场景就是 AC→E 这类依赖，也许 C 完全是可有可无的，真正起决定作用的是 A，那就必须把依赖简化成 A→E。

没有冗余函数依赖，指的是集合里不能存在一条依赖 X→A，去掉它之后剩余依赖集仍然能推出 X→A。这相当于集合里不能有重复的“推导路径”，不能被别的东西替代的依赖才值得保留。

如果用三个词概括：原子化、去左边赘肉、去重复路径。这三步做完之后，这组依赖就是一张“最精简的逻辑网络”。

2.2 四步求解流程总览

标准的求解算法分四步，顺序不能乱：

1. 右部原子化：把每个函数依赖的右部拆成单一属性。
2. 消除左部冗余属性：对每个左部含多个属性的依赖，逐个检查属性是否冗余。
3. 消除冗余函数依赖：对每条依赖，检查它是否可以被集合中的其他依赖推出。
4. 合并同类项：把左部相同的依赖合并成一条。

这里先说一个很多同学会困惑的问题：第 4 步“合并”到底算不算必要？严格来说，前面三步已经满足了教科书对“最小函数依赖集”的定义，合并只是为了让结果更整洁，也更容易和标准答案对齐。但合并之后你仍然可以随时用分解律把它拆回去，等价性不会变。所以我建议考试时把第 4 步也做了，最终写成一个每条依赖左部都不相同的形式，这样阅卷老师一眼就能看出你掌握了全流程。

2.3 结果为什么不唯一

很多同学做完题发现自己的答案和参考书不一样，立刻开始怀疑自己错了。这里要澄清：最小函数依赖集本来就不唯一，因为等价函数依赖集可以有不同的表达方式。举个例子，{X→A, X→B} 合并成 {X→AB} 之后仍然是一个合法的最小依赖集，而不合并的版本也符合定义。

考试判分通常看的不是“结果完全一致”，而是“你的结果是否满足最小依赖集的三条性质，并且与原集合等价”。所以哪怕最后的形式和老师不一样，只要你能在草稿纸或者卷子上写出等价的推导关系，分数就不会丢。这个认知能帮你省掉大量自我怀疑的时间。

3. 完整案例：四步算出极小函数依赖集

3.1 题目设定

我们来看一道能覆盖所有考点的标准题目。设关系模式 R(U, F)，属性集为 U={A, B, C, D, E}，函数依赖集为：

• A→BC
• B→D
• CD→E
• E→A
• AC→E

目标是求 F 的一个极小函数依赖集。这个题的点在于：AC→E 明显带有“冗余嫌疑”，CD→E 则可能让很多人误以为要删，实际上却必须保留。我们一步一步把它算完。

3.2 第一步：右部原子化

先把所有右部拆成单一属性。这里唯一右部不是单属性的依赖是 A→BC，拆开得到 A→B 和 A→C。其余依赖右部本来就是单属性，不用动。于是得到中间集合 F₁：

• A→B
• A→C
• B→D
• CD→E
• E→A
• AC→E

这一步虽然机械，但千万不要同时去改左部。右部原子化只是把依赖分解成更小的单元，如果你一边拆右部一边顺手删左部属性，后面的检查就全乱了。

3.3 第二步：消除左部冗余属性

扫描 F₁，发现左部含多个属性的依赖有两条：CD→E 和 AC→E。我们需要分别判断它们左部的两个属性是否冗余。

先看 CD→E。检查 C 是否冗余，也就是判断去掉 C 之后，D 单独能否推出 E。把 CD→E 暂时从集合里摘掉，在剩余集合 {A→B, A→C, B→D, E→A, AC→E} 中计算 D 的闭包。D 没有任何依赖左部只包含 D，所以 D⁺ 就是 {D}，里面没有 E。结论是 C 不冗余。再检查 D 是否冗余，去掉 D 之后，C 单独能否推出 E。同理，C 在剩余集合里也推不出任何东西，C⁺={C}，不含 E。所以 D 也不冗余。CD→E 原样保留。

再看 AC→E。先检查 A 是否冗余，也就是 C 单独能否推出 E。把 AC→E 暂时摘掉，在剩余集合 {A→B, A→C, B→D, CD→E, E→A} 中算 C 的闭包，C⁺={C}，不含 E，A 不冗余。再检查 C 是否冗余，也就是 A 单独能否推出 E。同样在摘掉 AC→E 后的集合里算 A 的闭包：A→B、A→C 让 A⁺ 变成 {A, B, C}；接着 B→D 把 D 加进来，变成 {A, B, C, D}；此时 CD→E 的左部 CD 已经全部在集合里，于是 E 被加入，A⁺={A, B, C, D, E}。E 在 A⁺ 里，说明 C 确实是多余的。把 AC→E 替换成 A→E。

到这里，F₂ 变成：

• A→B
• A→C
• B→D
• CD→E
• E→A
• A→E

注意 AC→E 被替换后 A→E 的左部是单属性，不再需要检查左部冗余。而 CD→E 的左部两个属性都确认不可删，所以左部冗余消除完成。

这里要强调一个容易踩的细节：判断左部属性是否冗余时，一定要把“被检查的那条依赖”暂时从集合里摘掉再算闭包。如果带着 AC→E 自己算 A 的闭包，万一某条路径用到 AC→E 本身，就会出现循环论证，导致你误判 C 不冗余。这种错误在考场上是致命的，因为后面所有步骤都会跟着错。

3.4 第三步：消除冗余函数依赖

现在逐条检查 F₂ 里的每条依赖，判断它是否能由其他依赖推出。判断方法：把该条依赖暂时从集合中删掉，在剩余集合里计算左部的闭包，如果右部属性出现在闭包里，说明这条依赖是多余的。

先看 A→B。删掉它之后，剩余集合为 {A→C, B→D, CD→E, E→A, A→E}，计算 A⁺：A→C 得到 {A,C}，A→E 得到 E，但没有 B 的来源，所以 A⁺={A,C,E}，不含 B。A→B 必须保留。

再看 A→C。删掉它之后，剩余集合为 {A→B, B→D, CD→E, E→A, A→E}。计算 A⁺：A→B 得 {A,B}，B→D 得 {A,B,D}，A→E 得 E，但 C 一直进不来，所以 A⁺={A,B,D,E}，不含 C。A→C 必须保留。

再看 B→D。删掉它之后，剩余集合为 {A→B, A→C, CD→E, E→A, A→E}。B 在剩余集合里没有作为任何依赖左部的组成部分，也没有依赖指向 B，所以 B⁺={B}，不含 D。B→D 必须保留。

再看 CD→E。删掉它之后，剩余集合为 {A→B, A→C, B→D, E→A, A→E}。计算 CD⁺：C 没有依赖可用，D 也没有依赖可用，CD 推不出任何新属性，CD⁺={C,D}，不含 E。CD→E 必须保留。

再看 E→A。删掉它之后，剩余集合为 {A→B, A→C, B→D, CD→E, A→E}。E 在剩余集合里没有作为任何依赖的左部，所以 E⁺={E}，不含 A。E→A 必须保留。

最后看 A→E。删掉它之后，剩余集合为 {A→B, A→C, B→D, CD→E, E→A}。计算 A⁺：A→B、A→C 得到 {A,B,C}；B→D 得到 {A,B,C,D}；CD→E 的左部全部在集合里，E 被加入，得到 {A,B,C,D,E}。E 确实能被推出，所以 A→E 是冗余的，删掉。

F₂ 删掉 A→E 之后，得到 F₃：

• A→B
• A→C
• B→D
• CD→E
• E→A

3.5 第四步：合并并验证等价

F₃ 里 A→B 和 A→C 左部相同，可以合并成 A→BC。最终得到最小函数依赖集：

• A→BC
• B→D
• CD→E
• E→A

这个结果已经是“颜值很高”的极简形态。但我强烈建议考试时不要直接交卷，花一分钟做等价性验证。验证思路很清晰：原集合能不能推出 Fmin 里的每一条依赖？显然能，因为 Fmin 里的依赖原本就都在原集合中（A→BC 由 A→B、A→C 合并而来）。反过来，Fmin 能不能推出原集合里的每一条依赖？原集合里唯一需要额外验证的是 AC→E。看 Fmin：由 A→BC 得 A→C，所以 AC 里实际上 C 本来就在；再由 A→BC 得 A→B，配合 B→D 得 D，此时 C 和 D 都有，CD→E 直接推出 E。路径完整，AC→E 成立。两边互相蕴含，等价性确认无误。

这道题完整走下来，你可以发现整个过程的节奏感很强：第二步去掉了一个冗余属性，第三步删掉了一条冗余依赖，最后合并。每一步都有明确依据，不像某些考试题需要“灵光一闪”，这就是为什么我说它是整张卷子里最容易按套路拿分的大题。

4. 考试实战：高频题型、失分点与避坑清单

4.1 闭包计算考场提速技巧

闭包是所有步骤里重复次数最多的操作，一定要练出肌肉记忆。草稿纸上我建议按这种格式写：初始属性集写在左边，每应用一条依赖就往右扩展一次，直到没有变化。同时把依赖按左部字母次序重排，比如 A→B、A→C 排在一起，B→D 放后面，这样扫依赖时不容易漏。

实际做题时有一个小技巧：如果某条依赖的左部非常长，而你的闭包集合只差一个属性就满覆盖，可以优先看哪些依赖的右部是那个“缺口属性”。比如算 A⁺ 时发现 CD→E 是唯一能推出 E 的依赖，那你就该意识到，关键是要先把 C 和 D 都弄进集合里。这种目标导向反而比盲扫更快，尤其在第三步判断冗余依赖时特别管用。

4.2 极易搞混的概念对照表

数据库考试里概念辨析题也常考这道题的周边知识。这里把几组容易混淆的概念放在一起对比：

考试时最怕的不是不会算闭包，而是把 X⁺ 和 F⁺ 混在一起。X⁺ 是属性集合，比如 {A,B,C}；F⁺ 是一个庞大的函数依赖集合，里面是无数条箭头。我们所有手工计算其实都在操作前者，后者只出现在概念题和等价证明里。

4.3 五个典型错误及避坑

我见过太多同学在这道题上丢分，错误基本集中在五个地方。

错误一是先删冗余依赖再做左部冗余检查。这个顺序一旦反过来，第二步判断时用的集合就已经不是原子化后的标准集合，很容易漏判或者误判。四步的顺序不要创新，每一步的输入输出都衔接得刚刚好。

错误二是算闭包只扫一轮就停。前面说过，新加入的属性可能触发后面的依赖，只扫一轮等于把链条强行砍断。宁可每道题多花四十秒，也要让闭包计算完整收敛。

错误三是在判断左部冗余时把被检查的依赖留在集合里。这个在 3.3 已经强调过，摘掉被检查依赖再算闭包是防止循环论证的底线操作。

错误四是在删除冗余依赖之后，后续检查没有使用更新后的集合。比如你删了一条依赖，后面算别的闭包时又把这条删掉的依赖暗戳戳用上了，结果当然会出错。每删完一条，草稿纸上的依赖集合要立刻同步更新。

错误五是做完之后不验证等价性。很多同学以为最后三步都走完就保证了正确性，实际上左部冗余和冗余依赖的判别都依赖闭包计算，闭包一旦算错，答案就是错的。而验证等价性相当于再检查一遍，能救回大量粗心错误。

4.4 不同教材的细节差异说明

另一个让人焦虑的来源是教材表述不统一。有些教材在“消除左部冗余属性”这一步允许直接用当前 F 计算闭包，不做摘除操作；有些教材要求先去除被检查依赖；还有教材会把“合并左部相同项”直接并入最终定义。这些差异不会改变最终结果的核心逻辑，只在细微处影响过程。

如果你用的是某本主流教材，以它的表述为准做题；如果你在复习时发现不同资料给的定义略有不同，不要慌，只要保证最终依赖集满足那三个性质，并且与原集合等价，就是正确答案。阅卷时历来是按等价性给分，不是按“长得像不像参考答案”。

5. 最小依赖集往哪儿用，以及复习阶段的几点建议

5.1 求候选键时的关键作用

很多人学完极小依赖集，以为它只是一道孤立计算题，这其实是大错特错。它最直接的应用就是求候选键。候选键是能唯一确定整个元组的最小属性组，而判断一个属性组是不是超键，只需看它的闭包是否等于全集 U。有了 Fmin，从最小的属性组开始试，效率会高很多，而且 Fmin 本身不含冗余依赖，计算闭包时干扰更少。

考试中常见的考法是给出 Fmin 让你求所有候选键，这时候属性分类法就很好用：只出现在依赖左部的属性是 L 类，只出现在右部的是 R 类，两边都出现的是 LR 类，都不出现的是 N 类。候选键通常从 L 类和 N 类的并集出发，再补上必要的 LR 类属性。这些知识不是这篇文章的重点，但你要意识到，极小依赖集是通往这些后续题型的第一站。

5.2 范式判断与模式规范化

数据库规范化里，3NF 和 BCNF 的分解算法都离不开最小依赖集。3NF 合成算法第一步就是求 Fmin，然后按左部相同的依赖分组构成关系模式，最后检查是否有候选键被包含在其中。如果你 Fmin 求错，后面分解出来的关系模式全部作废。

从考试角度讲，这可能是一道 15 分到 20 分综合题的第一小问。前面的极小依赖集不只是单独考，它往往是整道大题的“入场券”。所以复习时不要抱有“我会算闭包就够了”的心态，一定要把 Fmin 练习到完全熟练，才能在范式题里不卡壳。

5.3 工程上为什么也需要精简依赖

离开试卷看实际开发，最小依赖集的思想同样有价值。业务数据库设计时，函数依赖的冗余意味着约束的重复表达，甚至意味着潜在的更新异常。一张表如果同时存在 A→B、B→C 和 A→C 这样的冗余依赖，修改 B 的值时可能连带破坏 A 与 C 之间的约束一致性。精简后的依赖集能帮助你把表拆分得更干净，也让设计评审时讨论的“约束”数量大幅减少。

我自己的体会是，数据库理论的题目看似抽象，但每一套算法都对应着工程里真实存在的取舍。你用四步法去掉无用的依赖，和你在业务层删掉一段永远执行不到的校验规则，背后的判断逻辑是一样的：留下不可替代的部分。

复习时最忌讳的就是觉得“这个知识偏计算，先放一放”。你可以找十道左右的典型例题，每一道都按四步法完整写一遍，中间所有的闭包计算都写出来而不是心算。写满十道之后，你会发现闭包和极小依赖集的计算速度快到几乎不用过脑子。这个状态，就是考试时最理想的状态。