最小覆盖和功能依赖性

考虑到以下功能依赖性，我将如何计算最小覆盖范围：

A -> B, ABCD -> E, EF -> GH, ACDF -> EG

在讲义中，它给出了最小覆盖率的推导，但我不明白它。

例如为了摆脱ACDF -> E:

A -> B => AACD -> BACD -> E => ACD -> E => ACDF -> E

然后他们说，同样我们也不保留ACDF -> G

然后我明白了ABCD -> E推导为ACD -> E因为甲->乙，但我不明白如何实现这一点的正式流程。

所以我的问题是，任何人都可以解释如何为一组函数依赖项生成最小覆盖吗？

要获得最小覆盖，您必须执行两个步骤。为了演示，我首先将依赖项拆分为多个（右侧只有一个属性）以使其更加干净：

A -> B
ABCD -> E
EF -> G
EF -> H
ACDF -> E
ACDF -> G

以下步骤must按此顺序完成（#1，然后#2），否则您可能会得到错误的结果。

1）去掉多余的属性（减少左侧）：

取左侧的每一侧，并尝试一次删除一个属性，然后尝试推导右侧（现在对于所有依赖项来说只有一个属性）。如果成功，您可以从左侧删除该字母，然后继续。请注意，可能有多个正确结果，这取决于您进行归约的顺序。

你会发现，你可以删除B从依赖ABCD -> E， 因为ACD -> ABCD（使用第一部）并从ABCD -> E。您可以使用完整的 dep。你目前正在减少，一开始有时会令人困惑，但如果你仔细想想，就会清楚你可以做到这一点。

同样，您可以删除F from ACDF -> E， 因为ACD -> ABCD -> ABCDE -> E（显然你可以从字母本身推断出单个字母）。这一步之后你会得到：

A -> B
ACD -> E
EF -> G
EF -> H
ACD -> E
ACDF -> G

这些规则仍然代表与原始规则相同的依赖关系。请注意，现在我们有一个重复的规则ACD -> E。如果您将整个事物视为一个集合（在数学意义上），那么当然您不能在一个集合中出现两次相同的元素。现在，我只是将其留在这里两次，因为无论如何下一步都会将其删除。

2）摆脱多余的依赖

现在，对于每条规则，尝试将其删除，并看看是否仅使用其他规则即可推导出相同的规则。当然，在此步骤中您不能使用 dep。您当前正在尝试删除（您可以在上一步中删除）。

如果你取第一条规则的左侧A -> B，暂时隐藏它，你看你无法从中推断出任何东西A独自的。因此，这条规则并不多余。对所有其他人做同样的事情。您会发现，您可以（显然）删除重复的规则之一ACD -> E，但严格来说，您也可以使用该算法。仅隐藏两条相同规则之一，然后取左侧（ACD），并用另一个推导出右侧。因此你可以删除ACD -> E（当然只有一次）。

您还会看到可以删除ACDF -> G， 因为ACDF -> ACDFE -> G。现在结果是：

A -> B
EF -> G
EF -> H
ACD -> E

这是原版的最小封面。