可能的最小覆盖数有多少？

Question

Consider R(A,B,C,D,E,F,G) be a relational schema with the following functional dependencies: AC->G, D->EG, BC->D, CG->BD, ACD->B, CE->AG. The number of different minimal cover possible are___________?

实际上在这个问题中我们应该找到所有可能的最小覆盖。我使用了 this 视频因此，使用该理论，我尝试做这个问题，但最终只得到 2 个最小封面，然后我的教科书中给出的答案是 4。我得到的最小封面是：

1) D->E,D->G,BC->D,CG->D,AC->B(#),CE->A

2) AC->G,D->E,D->G,BC->D,CG->D,CD->B(#), CE->A

实际上视频只给出了寻找最小掩体的标准过程。但是问题有点棘手，因为它询问我们可以找到多少个最小封面。我正在正确应用该算法...唯一的问题是我无法找到给定的 FD 集可以有多少个最小覆盖

Answer 1

生成最小覆盖的常用算法包括三个步骤：

拆分右侧，生成右侧只有一个属性的FD
对于每一个多于一个属性的左边部分，依次尝试去掉每一个属性，看剩下的是否还能判断出右边的部分。在这种情况下，将左边的属性去掉。
对于每个剩余的依赖，尝试看是否可以消除。

在你的情况下，第一步产生：

F = { A C → G
      A C D → B
      B C → D
      C G → B
      C G → D
      C E → A
      C E → G
      D → E
      D → G }

在第二步中，我们必须检查前七个依赖项。对于每个依赖项 A1A2...An -> B，我们尝试依次消除每个 Ai 并查看如果 B 包含在其余属性的闭包中（针对 F 采取的闭包）。在这种情况下，我们有两种可能性：从 ACD -> B 我们可以消除 A 或 D。所以我们现在有两组不同的依赖项：

F1 = { A C → G
       C D → B
       B C → D
       C G → B
       C G → D
       C E → A
       C E → G
       D → E
       D → G }

和

F2 = { A C → G
       A C → B
       B C → D
       C G → B
       C G → D
       C E → A
       C E → G
       D → E
       D → G }

现在我们可以应用最后一步：对于每个依赖项 X -> A，我们可以查看 A 是否包含在 X、X+ 的闭包中所有其他依赖项。在这种情况下，我们可以消除这种依赖性。

结果通常取决于我们应用这些检查的顺序。

这里有四种不同的规范封面：

G1 = { A C → G
       B C → D
       C G → B
       C E → A
       D → E
       D → G }

G2 = { A C → G
       B C → D
       C G → D
       C E → A
       C D → B
       D → E
       D → G }

G3 = { A C → B
       B C → D
       C G → B
       C E → A
       D → E
       D → G }

G4 = { A C → B
       B C → D
       C G → D
       C E → A
       D → E
       D → G }

注意：我不清楚是否还有其他规范封面。

可能的最小覆盖数有多少？

The number of different minimal cover possible are?

database

database-design

relational-database

database-schema

functional-dependencies