如何查找候选密钥



示例:

设R=(A,B,C,D)设F={C->AD,AB->C}

那么我该如何找到候选密钥呢?

答案是{AB,BC}

为什么?

给定一个关系模式R,它具有一组属性T和一组非空的非平凡函数依赖关系F,描述了一组假设在该模式中保持的约束:

  1. 未出现在F中FD右侧部分的每个属性必须出现在任何候选键中。

  2. F中未出现在FD左侧的每个属性都不能出现在任何候选键中。

要找到所有候选键,对于所有其他属性,您应该尝试将它们的每一个可能组合添加到1的属性之上,并查看闭包是否决定了关系的所有属性(这样,您就无法在不丢失此属性的情况下从组合中删除任何属性)。

注意,如果集合F为空,则唯一候选密钥由所有属性T构成。

在实践中,存在相对高效的算法(因为在一般情况下,找到所有密钥的问题是指数的)。

一个简单的方法是从函数依赖关系的规范覆盖开始,在这种情况下,例如从:

{ A B → C
C → A
C → D }

在找到任何候选密钥中必须存在的属性(在本例中为B)后,尝试向它们添加依赖项的左手侧(在本案中同时为AB,即AC)(以任何顺序,并可能将它们组合),并计算闭包以查看它们是否确定了所有属性。当您发现某组属性决定了所有关系属性时,您已经找到了一个候选键(不需要向其中添加其他属性)。在您的示例中:

(A B)+ = A B C D
(B C)+ = A B C D

因此,A BB C是候选键(因为在不丢失确定所有其他属性的属性的情况下,无法删除它们的任何属性)。由于没有其他属性(D中的一部分不能出现在候选关键字中),因此您知道您已经找到了所有候选关键字。

最新更新