我在关系模式r(A, B, C, D, E, F )
上有以下一组函数依赖:
A -> BCD
BC -> DE
B -> D
D -> A
任何人都可以解释如何找到这种关系的候选键吗?
简答:候选键是(A,F),(B,F)和(D,F)。
像这样Wikipedia article说:
例如,可以计算所有候选键的集合。来自功能依赖集。为此,我们需要为属性集α定义属性闭包α+。集合α+包含α在功能上隐含的所有属性。
找到单个候选键非常简单。我们从一组属性α开始,并尝试连续删除每个属性。如果删除属性后属性闭包保持不变,则此属性不是必需的,我们可以永久删除它。我们称结果最小化(α)。如果α是所有属性的集合,则最小化(α)是候选密钥。
所以现在我们只需要将其付诸实践。让我们从所有属性α0=(A,B,C,D,E,F)开始。现在我们可以看看删除A是否会产生问题。 α'0=(B,C,D,E,F),α'0+是(B,C,D,E,F,A)(因为D→ A成立)。现在通过永久地踢出A并试图删除B,我们最终会得到一个候选键。
所以现在我们生成最小化(α0)=α4=(D,F)。我们可以使用强力方法,在每次迭代中,我们迭代我们可以删除的所有可能的键。但这将花费指数时间来生成。
然而,维基百科文章包括一种生成密钥数量和功能依赖性的所有候选密钥多项式的方法。该算法定义为:
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循环并开始迭代所有函数依赖项。
这是第一次迭代的结束。所以K现在是K = [(D,F),(A,F),(B,F)]。 n = 3,现在i = 1。因此,对于K [i] =(A,F),我们现在迭代:
这是第二次迭代的结束。所以K现在是K = [(D,F),(A,F),(B,F)]。 n = 3,现在i = 2。所以对于K [i] =(B,F)我们现在迭代:
所以最后K = [(D,F),(A,F),(B,F)]。这些都是候选键。