数据库中的函数依赖

Question

我对关系有以下一组函数依赖性架构 r(A, B, C, D, E, F ) :

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

谁能解释一下如何找到这个关系的候选键？

Answer 1

简答：候选键为(A,F),(B,F) 和 (D,F).

像这样Wikipedia article说：

The set of all candidate keys can be computed e.g. from the set of functional dependencies. To this end we need to define the attribute closure α⁺ for an attribute set α. The set α⁺ contains all attributes that are functionally implied by α.

It is quite simple to find a single candidate key. We start with a set α of attributes and try to remove successively each attribute. If after removing an attribute the attribute closure stays the same, then this attribute is not necessary and we can remove it permanently. We call the result minimize(α). If α is the set of all attributes, then minimize(α) is a candidate key.

那么现在我们只需要将其付诸实践即可。让我们从所有属性 α₀=(A,B,C,D,E,F).现在我们可以看看删除 A 是否会产生问题。用α'₀=(B,C,D,E,F),α'₀⁺ 是 (B,C,D,E,F,A)（因为 D→ A持有）。现在，通过永久踢出 A 并尝试删除 B，我们最终会得到 a 候选密钥.

α₁=(B,C,D,E,F)。我们可以扔掉B吗？是的，因为 α'₁=(C,D,E,F) 将导致 α'₁⁺=(A,B,C,D,E,F)（因为D→A 和 A→BCD).
α₂=(C,D,E,F)。我们可以扔掉C吗？是的，因为 α'₂=(D,E,F) 将导致 α'₂⁺=(A,B,C,D,E,F)（因为 D→A 和A→BCD).
α₃=(D,E,F)。我们可以扔掉D吗？否，因为 α'₃=(E,F) 将导致 α'₃⁺=(E,F).
α₃=(D,E,F)。我们可以扔掉 E 吗？是的，因为 α'₃=(D,F) 将导致 α'₃⁺=(A,B,C,D,E,F)（因为D→A；A→BCD; 和 BC→DE).
α₄=(D,F)。我们可以扔掉 F 吗？否，因为 α'₄=(D) 将导致 α'₄ ⁺=(A,B,C,D,E)（因为 D→A; A&rightarrow ;BCD; 和 BC→DE).

所以现在我们生成了minimize(α₀)=α₄=(D,F)。我们可以使用蛮力方法，在每次迭代中我们迭代所有可以删除的可能键。但这将花费 指数级 时间来生成。

Wikipedia 文章 然而包括一种生成 all 候选键的方法键的数量和功能依赖性。算法定义为：

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

所以如果我们运行算法，我们首先必须计算 minimize(A)，但好的是：我们已经在上面做了。所以 K[0] = (D,F)、n=1 和 i=0。

现在我们使用 while 循环并开始迭代所有函数依赖项。

对于A→ BCD.所以现在我们构造一个键(A,F)。我们检查是否已经有一个子集定义为键（事实并非如此）。现在我们将它最小化，例如：(A,F)→(A,F)。所以我们添加一个新的key (A,F).
对于 BC→DE。所以现在我们构造一个键(B,C,F)。我们检查是否已经有一个子集定义为键（事实并非如此）。现在我们最小化它，比如 (B,C,F)→(B,F)→(B,F)。所以我们添加 (B,F).
对于 B→D。所以现在我们构造一个键(B,F)。我们检查是否已经有一个子集定义为键（是这种情况）。这个我们不加。
对于 D→A。所以现在我们构造一个键(D,F)。我们检查是否已经有一个子集定义为键（是这种情况）。这个我们不加。

第一次迭代到此结束。所以 K 现在是 K=[(D,F),(A,F),(B,F)]。 n=3 现在 i=1。所以对于 K[i]=(A,F) 我们现在迭代：

对于A→ BCD.所以现在我们构造一个键(A,F)。我们检查是否已经有一个子集定义为键（是这种情况）。这个我们不加。
对于 BC→DE。所以现在我们构造一个键(B,C,F)。我们检查是否已经有一个子集定义为键（是这种情况）。这个我们不加。
对于 B→D。所以现在我们构造一个键(A,B,F)。我们检查是否已经有一个子集定义为键（是这种情况）。这个我们不加。
对于 D→A。所以现在我们构造一个键(D,F)。我们检查是否已经有一个子集定义为键（是这种情况）。这个我们不加。

第二次迭代到此结束。所以 K 现在是 K=[(D,F),(A,F),(B,F)]。 n=3 现在 i=2。所以对于 K[i]=(B,F) 我们现在迭代：

对于A→ BCD.所以现在我们构造一个键(A,F)。我们检查是否已经有一个子集定义为键（是这种情况）。这个我们不加。
对于 BC→DE。所以现在我们构造一个键(B,C,F)。我们检查是否已经有一个子集定义为键（是这种情况）。这个我们不加。
对于 B→D。所以现在我们构造一个键(B,F)。我们检查是否已经有一个子集定义为键（是这种情况）。这个我们不加。
对于 D→A。所以现在我们构造一个键(B,D,F)。我们检查是否已经有一个子集定义为键（是这种情况）。这个我们不加。

所以最后 K=[(D,F),(A,F),(B,F)]。这些都是候选键。

数据库中的函数依赖

Functional dependencies in database

database

database-normalization

relational-algebra

functional-dependencies