最小依赖集的求法

最小依赖集（解法+例题）

网上看了很多最小依赖集的解法和例题，许多都存在错误，故自己参考总结写了一篇，如果有错误，感谢指正。

一、求最小依赖集的算法

①根据推理规则的分解性，右部最小化

②消除左边的冗余属性

③消除冗余的FD（依赖）

重点：操作步骤的顺序不能颠倒，颠倒了可能消除不了FD中左边冗余的属性，或冗余的依赖。

二、具体操作详解（以下两种意思相同，表述略有区别罢了）

（1）右部最小化：右切，使每个函数依赖的右部仅有一个属性
（2）规则最小化：除本求包（对每个函数依赖的左部做除本求包，求包的结果如果不包含本函数依赖的右部，本函数依赖保留；求包的结果如果包含了本函数依赖的右部，删除本函数依赖）
（3）左部最小化

注意，解题一定要先（3）后（2）

三、例题，反例等

反例，假如将②③步骤颠倒

例：求**F＝{ABD→AC，C→BE，AD→BF，B→E}**的最小函数依赖集 $F_m$

注意：当在函数依赖已经改变的地方开始一个新步骤时，重写函数依赖集很重要，这样可以在下一步中方便引用。

第一步对F中的函数依赖运用分解原则来创建一个等价函数依赖集H，该集合中每一个函数依赖的右部是单个属性：

H＝｛①ABD→A，②ABD→C，③C→B，④C→E，⑤AD→B，⑥AD→F，⑦B→E｝

第二步考察每一个函数依赖是否是必须的，去除非必要的函数依赖

（1）ABD→A是平凡的函数依赖（就是A是ABD的子集，所以他是平凡的依赖），所以显然是非必要的函数依赖，因此去除。保留在H中的函数依赖是H＝｛②ABD→C，③C→B，④C→E，⑤AD→B，⑥AD→F，⑦B→E｝

（2）考察ABD→C，去掉此函数依赖将会得到新的函数依赖集J＝｛③C→B，④C→E，⑤AD→B，⑥AD→F，⑦B→E｝。如果ABD→C是非必要的，则 $ABD)_J^+$ =ABDFE，不包含C，因此ABD→C是必要的函数依赖，不能去掉。

H＝｛②ABD→C，③C→B，④C→E，⑤AD→B，⑥AD→F，⑦B→E｝

（3）考察C→B，J＝｛②ABD→C，④C→E，⑤AD→B，⑥AD→F，⑦B→E｝，则** $C_J^+$ =CE**，不包含B，因此C→B是必要的函数依赖，保留在H中。

（4）考察C→E，J＝｛②ABD→C，③C→B，⑤AD→B，⑥AD→F，⑦B→E｝，则 $C_J^+$ =CBE，包含E，因此是不必要的，去除后得到的函数依赖集为H＝｛②ABD→C，③C→B，⑤AD→B，⑥AD→F，⑦B→E｝

（5）同理考察函数依赖⑤、⑥和⑦，最后得到的函数依赖集为H＝｛②ABD→C，③C→B，⑤AD→B，⑥AD→F，⑦B→E｝。为了第三步方便引用，我们进行重新编号：

H＝｛①ABD→C，②C→B，③AD→B，④ AD→F，⑤ B→E｝。

第三步考察每一个左部为多个属性的函数依赖，看左部的每个属性是否是必须的，能否用更小的属性集替代原有的属性集。

首先从函数依赖①ABD→C开始。

（1）去除A？

如果A可以去除，那么可得到新的函数依赖集J＝｛①BD→C，②C→B，③AD→B，④ AD→F，⑤ B→E｝。去掉A后BD在J上的闭包将比在H下函数决定更多的属性，如果 $BD)_J^+$ = $BD)_H^+$ 或者C∈ $BD)_H^+$ ，则说明去掉A得到的函数依赖集和原有的函数依赖集是等价的，可以用BD→C替换ABD→C。