database - 最小覆盖和功能依赖

Question

给定以下函数依赖性，我将如何计算最小覆盖:

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，但我不知道了解如何实现这一目标的正式流程。

所以我的问题是，谁能解释一下如何为一组函数依赖生成最小覆盖？

Answer 1

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

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

以下步骤必须按此顺序完成(#1 然后#2)，否则您会得到不正确的结果。

1) 去除冗余属性(减少左侧):

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

你会发现，你可以从依赖项 ABCD -> E 中删除 B，因为 ACD -> ABCD(先使用dep.) 和 ABCD -> E。您可以使用完整的部门。你目前正在减少，一开始有时会感到困惑，但如果你仔细想想，就会清楚你可以做到这一点。

同样，您可以从 ACDF -> E 中删除 F，因为 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

这是原始集合的最小覆盖。