database - 数据库中的功能依赖性

Question

我有以下一组函数依赖关系
架构：

A -> BCD
BC -> DE
B -> D
D -> A

有人能解释一下如何找到这个关系的候选密钥吗？

Answer 1

简而言之：候选键是（a，f），（b，f）和（d，f）。
像这样说：
可以计算所有候选密钥的集合，例如从
功能依赖性。为此，我们需要定义属性
属性集α的闭包α＋。集合
α+包含所有在功能上
由α暗示。
找到一个候选密钥非常简单。我们从一个
设置属性的α并尝试依次移除每个
属性。如果在移除属性之后
保持不变，那么这个属性是不必要的，我们可以
将其永久移除。我们称之为结果最小化（α）。如果α是所有属性的集合，那么minimize（α）是一个候选密钥。
所以现在我们只需要把它付诸实践。让我们从所有属性α0=（a，b，c，d，e，f）开始。现在我们可以看看移除是否会产生问题。α'0=（b，c，d，e，f），α'0+是（b，c，d，e，f，a）（因为d→a成立）。现在，通过永久地踢出A并尝试删除B，我们将最终得到一个候选密钥。
α1=（b，c，d，e，f）。我们能扔掉B吗？是的，因为α'1=（c，d，e，f）将导致α'1+=（a，b，c，d，e，f）（因为d→a和a→bcd）。
α2=（c，d，e，f）。我们能扔掉C吗？是的，因为α'2=（d，e，f）将导致α'2+=（a，b，c，d，e，f）（因为d→a和a→bcd）。
α3=（d，e，f）。我们能扔掉D吗？不，因为α'3=（e，f）将导致α'3+=（e，f）。
α3=（d，e，f）。我们能扔掉E吗？是的，因为α'3=（d，f）将导致α'3+=（a，b，c，d，e，f）（因为d→a；a→bcd；和bc→de）。
α4=（d，f）。我们能扔掉F吗？不，因为α'4=（d）将导致α'4+=（a，b，c，d，e）（因为d→a；a→bcd；和bc→de）。
现在我们得到了极小值（α0）=α4=（d，f）。我们可以使用蛮力方法，在每次迭代中，我们迭代所有可以删除的键。但这将花费指数时间来产生。
不过，wikipedia文章提供了一种在键的数量和函数依赖项中生成所有候选键多项式的方法。算法定义为：

function find_candidate_keys(A, F)
/* A is the set of all attributes and F is the set of functional dependencies */
K[0] := minimize(A);
n := 1; /* Number of Keys known so far */
i := 0; /* Currently processed key */
while i < n do
  foreach α → β ∈ F do
    /* Build a new potential key from the previous known key and the current FD */
    S := α ∪ (K[i] − β);
    /* Search whether the new potential key is part of the already known keys */ 
    found := false;
    for j := 0 to n-1 do
      if K[j] ⊆ S then found := true;
    /* If not, add if 
    if not found then
      K[n] := minimize(S);
      n := n + 1;
  i := i + 1
return K

所以如果我们运行算法，我们首先要计算最小化（a），但好的是：我们已经在上面做了。所以k[0]=（d，f），n=1，i=0。
现在我们采用while循环并开始迭代所有函数依赖项。
对于a→bcd。现在我们构造一个键（a，f）。我们检查是否已经有一个子集被定义为key（事实并非如此）。现在我们最小化它，比如：（a，f）—（a，f）。所以我们添加了一个新的键（a，f）。
对于b c→de，我们构造一个键（b，c，f）。我们检查是否已经有一个子集被定义为key（事实并非如此）。现在我们把它最小化，比如（b，c，f）—（b，f）—（b，f）。所以我们加上（b，f）。
对于b→d，我们现在构造一个键（b，f）。我们检查是否已经有一个子集被定义为key（就是这样）。我们不加这个。
对于d→a，我们现在构造一个键（d，f）。我们检查是否已经有一个子集被定义为key（就是这样）。我们不加这个。
这是第一次迭代的结束。所以k现在是k=[（d，f），（a，f），（b，f）]n=3现在i=1。所以对于k[i]=（a，f），我们现在迭代：
对于a→bcd。现在我们构造一个键（a，f）。我们检查是否已经有一个子集被定义为key（就是这样）。我们不加这个。
对于b c→de，我们构造一个键（b，c，f）。我们检查是否已经有一个子集被定义为key（就是这样）。我们不加这个。
对于b→d，我们构造一个键（a，b，f）。我们检查是否已经有一个子集被定义为key（就是这样）。我们不加这个。
对于d→a，我们现在构造一个键（d，f）。我们检查是否已经有一个子集被定义为key（就是这样）。我们不加这个。
这是第二次迭代的结束。所以k现在是k=[（d，f），（a，f），（b，f）]n=3现在i=2。所以对于k[i]=（b，f），我们现在迭代：
对于a→bcd。现在我们构造一个键（a，f）。我们检查是否已经有一个子集被定义为key（就是这样）。我们不加这个。
对于b c→de，我们构造一个键（b，c，f）。我们检查是否已经有一个子集被定义为key（就是这样）。我们不加这个。
对于b→d，我们现在构造一个键（b，f）。我们检查是否已经有一个子集被定义为key（就是这样）。我们不加这个。
对于d→a，我们现在构造一个键（b，d，f）。我们检查是否已经有一个子集被定义为key（就是这样）。我们不加这个。
所以在最后k=[（d，f），（a，f），（b，f）]这些都是候选钥匙。