最小的封面和功能依赖

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)摆脱冗余属性(减少左侧):

取每个左侧并尝试一次删除一个属性,然后尝试推导出右侧(现在只有一个属性用于所有依赖项).如果你成功,你可以从左侧删除该字母,然后继续.请注意,可能有多个正确的结果,这取决于您进行缩减的顺序.

您会发现,您可以B从依赖项中删除ABCD -> E,因为ACD -> ABCD(使用第一个dep.)和from ABCD -> E.你可以使用完整的dep.你现在正在减少,一开始有时会让人感到困惑,但如果你想一想,你就会明白你可以做到这一点.

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

这是原始套装的最小封面.