最小覆盖和函数依赖

Question

最小覆盖和函数依赖

databasefunctional-dependencies

32

给定以下函数依赖关系，如何计算最小覆盖集合：

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，但我不理解如何正式推导到这一步。

所以我的问题是，有人能提供一个如何生成函数依赖关系最小覆盖集合的解释吗？

- kachilous

您可以在这里找到最小覆盖算法。http://functionaldependencycalculator.ml/algorithm/3 - Q123

2个回答

-3

据我所知，在上述的最小功能依赖中，ACDF -> G 也应该被包括进来，因为当你对左边每个字母以及它们的组合进行闭包操作时，没有一个能够生成G而不包括F。

因此，应该如下列出：

（A -> B, EF -> G , EF -> H , ACD -> E , ACDF -> G）

- Dayama0817

2

这是不正确的。在这里 ACDF -> G 是多余的（因此该集合不是最小的），因为如果你有 ACDF，你可以通过 ACD -> E 推断出 E，所以现在你有了 ACDEF，它可以轻松地推断出 G（通过 EF -> G）。 - kuba

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kuba · Accepted Answer

为了获得最小化覆盖，您需要分两步进行操作。为了演示，我将首先将依赖项拆分为多个（仅右侧有一个属性），以使其更加清晰：

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

以下步骤必须按照顺序进行（先执行#1，然后是#2），否则可能导致结果不正确。

1）消除冗余属性（减少左侧）：

对于每个左侧，尝试逐个删除一个属性，然后尝试推导出右侧（现在对于所有依赖项只剩下一个属性）。如果成功了，则可以从左侧中删除该字母，然后继续。请注意，可能有多个正确的结果，这取决于你进行缩减的顺序。

你会发现，你可以从依赖项ABCD -> E中删除B，因为ACD -> ABCD（使用第一条依赖项）以及从ABCD -> E中删除它。你可以使用你当前正在缩减的完整依赖关系，这有时会令人困惑，但如果你思考一下，就会明白你可以这样做。

同样地，你可以从ACDF -> E中删除F，因为ACD -> ABCD -> ABCDE -> E（你可以很明显地从字母本身中推导出单个字母）。完成这一步之后，你会得到：

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

这些规则仍然代表与原始规则相同的依赖关系。请注意，现在我们有了一个重复的规则ACD -> E。如果将整个内容视为一组（在数学意义上），那么当然不能在一个集合中两次拥有相同的元素。目前，我将其重复两次，因为下一步会将其删除。

2）消除冗余依赖

现在对于每个规则，尝试删除它，并查看是否可以仅使用其他规则推导出相同的规则。在此步骤中，您当然不能使用正在尝试移除的依赖项（但在上一步中可以）。

如果您暂时隐藏第一条规则A -> B的左侧，则可以看到仅从A本身无法推导出任何内容。因此，此规则不是冗余的。对所有其他规则执行相同操作。您会发现，可以（显然）删除其中一个重复规则ACD -> E，但严格来说，您也可以使用算法。仅隐藏其中一个相同的规则，然后取左侧（ACD），并使用另一个规则推导右侧。因此，可以删除ACD -> E（当然只能删除一次）。

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

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

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