最小的封面和功能依赖[英] Minimal Cover and functional dependencies

本文是小编为大家收集整理的关于最小的封面和功能依赖的处理/解决方法,可以参考本文帮助大家快速定位并解决问题,中文翻译不准确的可切换到English标签页查看源文。

问题描述

给定以下功能依赖性,我将如何计算最小封面:

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 ,但我没有了解如何实现这一目标的正式过程.

所以我的问题是,谁能提供有关如何为设定功能依赖性生成最小封面的解释吗?

推荐答案

要获得最小的封面,您必须迈出两个步骤.为了证明,我首先将依赖项分为多个(右侧只有一个属性),以使其更加干净:

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

以下步骤必须按照此顺序完成(#1,然后是#2),否则您可能会获得不正确的结果.

1)摆脱冗余属性(减少左侧):

乘每个左侧,尝试一次删除每个属性一个属性,然后尝试推断右侧(现在,对于所有依赖项来说,这仅是一个属性).如果您成功了,则可以从左侧删除该字母,然后继续.请注意,可能有多个正确的结果,这取决于您进行减少的顺序.

您会发现,您可以从依赖项ABCD -> E中删除B,因为ACD -> ABCD(使用first dep.)和ABCD -> E.您可以使用完整的DEP.您目前正在减少,这有时一开始会令人困惑,但是如果您考虑一下,很明显您可以做到这一点.

类似地,您可以从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

这是原始集合的最小封面.

其他推荐答案

根据我的说法,在上述功能最小依赖项中,还应包括acdf-> g

所以如下:

(a-> b,ef-> g,ef-> h,acd-> e,acdf-> g)

本文地址:https://www.itbaoku.cn/post/597459.html

问题描述

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.

For example for getting rid of ACDF -> E:

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

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

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

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.

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

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) get rid of redundant dependencies

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

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

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.

其他推荐答案

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

So it would be as follows:

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