找出标准覆盖或最小函数依赖关系数量的程序

Question

我想找出数据库中功能依赖的标准覆盖或最小数量。

举个例子：

如果你有一个表格 = (A,B,C) <-- 这些是列：A、B、C

还有一些依赖关系：

A → BC

B → C

A → B

AB → C

标准覆盖（或者说最少的依赖关系数量）是：

A → B

B → C

有没有程序可以做到这一点？如果没有，任何代码或伪代码来帮助我写一个都非常感谢。最好是用Python或Java。

Answer 1

从你的依赖关系来看，它们可以被看作是对 A, B, C 的一种部分顺序。你想要的东西听起来很像（但并不完全是）一种叫做拓扑排序的东西（这是一种在有向无环图上的部分顺序排序）。

Answer 2

看起来你可以把任何这样的规则：

   A ->  BC

改写成

 A -> B

还有

  A -> C

以及任何这样的规则：

  AB -> C

改写成

  A -> C

还有

  B -> C

经过这样的改写后，你应该会得到一组单例对的规则：

  X -> Y

（可能会有很多重复的部分，你可以马上把它们删掉）。这就形成了rlotun提到的部分顺序。

到目前为止的例子，你最终会得到：

 A -> B
 B -> C
 A -> C

如果你再进一步简化这个部分顺序（比如，去掉任何重复的连接，任何关于部分顺序的数据结构书籍都会告诉你怎么做），你就会得到一个最简的部分顺序，我觉得这就是你想要的答案。

在这个例子中，简化部分顺序时，你会把A -> C删掉，最后得到你的答案。