database - 如何找到候选键？

Question

例子：

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

那么我怎样才能找到候选键呢？

答案是 {AB, BC}

为什么？

Answer 1

给定一个关系模式，该模式R具有一组属性T和一组非空函数依赖项F，描述了假定在该模式中存在的一组约束：

1. 没有出现在 FD 右侧的每个属性都F 必须出现在任何候选键中。

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

要找到所有候选键，对于所有其他属性，您应该尝试在它们的每个可能组合之上添加 1 的属性，并查看闭包是否确定关系的所有属性（并且您无法删除任何来自组合的属性而不会丢失此属性）。

请注意，如果集合F为空，则唯一的候选键由所有属性 T 构成。

在实践中，有些算法可以相对有效（因为找到所有密钥的问题在一般情况下是指数的）。

一个简单的方法是从功能依赖的规范覆盖开始，在这种情况下，例如从：

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

并在找到必须存在于任何候选键中的属性（在本例中B）之后，尝试将依赖项的左侧添加到它们（在本例AB中为 ，即A和C）（以任何顺序，并可能组合它们）并计算闭包以查看它们是否确定所有属性。当您发现某组属性决定了所有的关系属性时，您就找到了一个候选键（并且没有必要向其中添加其他属性）。在您的示例中：

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

A B候选键也是如此B C（因为您不能在不丢失确定所有其他属性的属性的情况下删除它们的任何属性）。并且由于没有其他属性（其中的一部分D不能出现在候选键中），您知道您已经找到了所有候选键。