database 最小覆盖和函数依赖

Minimal Cover and functional dependencies

提问by kachilous

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

鉴于以下函数依赖关系，我将如何计算最小覆盖：

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

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.

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

For example for getting rid of ACDF -> E:

例如摆脱ACDF -> E：

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

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

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

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

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

然后我明白ABCD -> E被推导出ACD -> E因为A -> B，但我不明白如何做到这一点的正式过程。

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

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

回答by kuba

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 mustbe done in this order (#1 and then #2), otherwise you can get incorrect result.

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

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

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

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.

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

You will find out, that you can remove Bfrom 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.

您会发现，您可以B从依赖项中删除ABCD -> E，因为ACD -> ABCD（使用第一个 dep.）和 from ABCD -> E。您可以使用完整的 dep。您目前正在减少，这有时起初令人困惑，但如果您考虑一下，就会清楚您可以这样做。

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

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

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

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.

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

2) get rid of redundant dependencies

2）摆脱多余的依赖

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).

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

If you take the left side of the first rule A -> B, hide it for now, you see you can't deduce anything from Aalone. 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).

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

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

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

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

Which is the minimal cover of the original set.

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

回答by Dayama0817

According to me,In the above functional minimal dependencies ACDF -> G should also be included because when you take closure of each letter on left side and their combination none of them produce G without including F

根据我的说法，在上面的函数式最小依赖项中，还应该包含 ACDF -> G，因为当您关闭左侧的每个字母及其组合时，它们都不会产生 G 而不包含 F

So it would be as follows:

所以它会如下：

(A -> B, EF -> G , EF -> H , ACD -> E , ACDF -> G )

(A -> B, EF -> G , EF -> H , ACD -> E , ACDF -> G )