最小覆盖和功能依赖 [英] Minimal Cover and functional dependencies

问题描述

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

Given the following functional dependencies how would I compute the minimal cover:

A - > B，ABCD - > E，EF - GH，ACDF→ EG

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

In the lecture notes it gives the derivation for the minimal cover but I do not understand it.

例如，除去 ACDF - > E ：

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

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

然后他们说，类似地，我们不保留 ACDF - > G

And then they say, similarly we do not keep ACDF -> G

然后，我了解 ABCD - > E 被推断为 ACD - > E ，因为 A - > B ，但我不明白如何获得的正式过程。

And then I understand that ABCD -> E is deduced to ACD -> E because A -> B, but I do not understand the formal process of how to get to that.

所以我的问题是，任何人都可以提供如何生成最小覆盖的解释一个集合的功能依赖？

So my question is, can anyone provide an explanation of how to generate the minimal cover for a set functional dependencies?

推荐答案

要获得最小的封面，您必须执行两个步骤。为了演示，我首先将依赖关系拆分为多个（右侧只有一个属性），以使其更清晰：

To get the minimal cover, you have to make two steps. To demonstrate, I'll first split the dependencies into multiple (only one attribute on the right side) to make it more clean:

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

必须按此顺序执行以下步骤

The following steps must be done in this order (#1 and then #2), otherwise you can get incorrect result.

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

1) get rid of redundant attributes (reduce left sides):

取每个左侧，并尝试一次删除一个属性，然后尝试推导右侧（现在只有一个属性的所有依赖项）。如果你成功，你可以从左侧删除那封信，然后继续。注意，可能有多个正确的结果，这取决于您执行缩减的顺序。

Take each left side and try to remove one each attribute one at a time, then try to deduce the right side (which is now only one attribute for all dependencies). If you suceed you can then remove that letter from the left side, then continue. Note that there might be more than one correct result, it depends on the order in which you do the reduction.

您会发现，您可以删除 B 从依赖 ABCD - > E ，因为 ACD - > ABCD （使用第一个dep。）和 ABCD - > E 。你可以使用完整的dep。你现在正在减少，这有时是混乱的起初，但如果你想，它会变得很清楚你可以这样做。

You will find out, that you can remove B from the dependency ABCD -> E, because ACD -> ABCD (use first dep.) and from ABCD -> E. You can use the full dep. you are currently reducing, this is sometimes confusing at first, but if you think about it, it will become clear that you can do that.

同样，你可以删除 F 来自 ACDF - > E ，因为 ACD - > ABCD - > ABCDE - > E （你显然可以从信函本身中推导出一个字母）。完成此步骤后，您将获得：

Similarly, you can remove F from ACDF -> E, because ACD -> ABCD -> ABCDE -> E (you can obviously deduce a single letter from the letter itself). After this step you get:

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

这些规则仍然表示与原始相同的依赖关系。请注意，现在我们有一个重复的规则 ACD - > E 。如果你把整个事物看作一个集合（在数学意义上），那么当然你不能在一个集合中有同样的元素两次。

These rules still represent the same dependencies as the original. Note that now we have a duplicate rule ACD -> E. If you look at the whole thing as a set (in the mathematical sense), then of course you can't have the same element twice in one set. For now, I'm just leaving it twice here, because the next step will get rid of it anyway.

2）摆脱冗余的依赖性

2) get rid of redundant dependencies

现在，对于每个规则，尝试删除它，并查看是否通过只使用其他规则推导相同的规则。在这一步，你，当然不能使用dep。

Now for each rule, try to remove it, and see if you deduce the same rule by only using others. In this step you, of course, cannot use the dep. you're currently trying to remove (you could in the previous step).

如果您选择第一条规则的左侧 A - > ; B ，现在隐藏它，你看到你不能从 A 单独推断任何东西。因此，此规则不是多余的。对所有其他人也一样。你会发现，你可以（显然）删除一个重复的规则 ACD - > E ，但严格来说，你也可以使用算法。只隐藏两个相同规则中的一个，然后取左侧（ ACD ），并使用另一个推导右侧。因此，您可以删除 ACD - >

If you take the left side of the first rule A -> B, hide it for now, you see you can't deduce anything from A alone. Therefore this rule is not redundant. Do the same for all others. You'll find out, that you can (obviously) remove one of the duplicate rules ACD -> E, but strictly speaking, you can use the algorithm also. Hide only one of the two same rules, then take the left side (ACD), and use the other to deduce the right side. Therefore you can remove ACD -> E (only once of course).

您也可以移除 ACDF - > G ，因为 ACDF - > ACDFE - > G 。现在的结果是：

You'll also see you can remove ACDF -> G, because ACDF -> ACDFE -> G. Now the result is:

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

这是原始集的最小封面。

Which is the minimal cover of the original set.

这篇关于最小覆盖和功能依赖的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！