2

如何通过删除冗余属性来创建最小的 FD 覆盖？

例如，给定这个 FD：

A1 ⟶ A3
A1A2 ⟶ A3
A3 ⟶ A4A6
A3A4 ⟶ A6
A3A5 ⟶ A1A2
A5A6 ⟶ A3

最小覆盖是

A1 ⟶ A3
A3 ⟶ A4
A3 ⟶ A6
A3A5 ⟶ A1
A3A5 ⟶ A2
A5A6 ⟶ A3

如果有人可以向我解释这些步骤，我会很高兴:)

4

1 回答 1

3

我将解释这些步骤并将输出添加到每个步骤。

  1. A1 ⟶ A3 已经很小了。所以就这样吧。 
    A1 ⟶ A3
  2. A1A2 ⟶ A3 表示你给了 A1 和 A2 你可以识别 A3。正如您从上一步中知道的那样，给定 A1 您已经可以识别 A3，那么这实际上并没有添加任何额外信息。请注意，得出 A2 ⟶ A3 的结论在逻辑上是不正确的。所以我们可以删除整个 FD，因为它是多余的。 
    A1 ⟶ A3
  3. A3 ⟶ A4A6 表示 A3 ⟶ A4 和 A3 ⟶ A6。所以我们去掉这个FD，把它分成2个。 
    A1 ⟶ A3
A3 ⟶ A4
A3 ⟶ A6
  4. A3A4 ⟶ A6 与步骤 2 类似。作为 A3 ⟶ A6 然后 A3A4 ⟶ A6 没有添加任何额外的信息，使其冗余。 
    A1 ⟶ A3
A3 ⟶ A4
A3 ⟶ A6
  5. A3A5 ⟶ A1A2 与步骤 3 类似。我们可以将它们拆分为 2 个不同的 FD A3A5 ⟶ A1 和 A3A5 ⟶ A2。这是最小的，因为没有其他 FD，例如 A3 ⟶ A1。 
    A1 ⟶ A3
A3 ⟶ A4
A3 ⟶ A6
A3A5 ⟶ A1
A3A5 ⟶ A2
  6. A5A6 ⟶ A3 已经很小了。 
    A1 ⟶ A3
A3 ⟶ A4
A3 ⟶ A6
A3A5 ⟶ A1
A3A5 ⟶ A2
A5A6 ⟶ A3
于 2013-11-09T07:10:52.637 回答