sql - 如何从功能依赖中获取最小密钥？

Question

我需要一些帮助和指导。

我有以下关系：R = {A, B, C, D, E, F}和函数依赖集

F = {
  {AB -> C};
  {A -> D};
  {D -> AE};
  {E -> F};
}

R 的主键是什么？

如果我应用推理规则，我会得到这些额外的函数依赖项：

D -> A
D -> E
D -> F

D -> AEF

A -> E
A -> F
A -> DEF

我该如何继续？

Answer 1

有一个众所周知的算法可以做到这一点。我不记得了，但练习似乎很简单，不用它。

我认为这都是关于传递性的：

CurrentKey = {A, B, C, D, E, F}

你知道D决定E，E决定F。因此，D通过传递性决定F。由于 F 不能确定任何内容，我们可以将其删除，并且由于 E 可以从 D 中获得，我们也可以将其删除：

CurrentKey = {A, B, C, D}

由于 AB 确定 C 并且 C 无法确定任何我们知道它不能成为密钥的内容，因此我们将其删除：

CurrentKey = {A, B, D}

最后我们知道 A 决定了 D，所以我们可以从键中删除后者：

CurrentKey = {A, B}

如果一旦你有了这个可能的键，你就可以重新创建所有的功能依赖，它就是一个可能的键。

PS：如果您碰巧有该算法，请发布它，因为我很高兴重新学习:)

Answer 2

算法：密钥计算（调用 x = ∅）

procedure key(x;A;F)
foreach  ! B 2 F do
if   x and B 2 x and B ̸2  then
return; /* x not minimal */
fi
od
if x+ = A then
print x; /* found a minimal key x */
else
X   any element of A  x+;
key(x [ fXg;A;F);
foreach  ! X 2 F do
key(x [ ;A;F);
od
fi