从功能依赖关系中确定候选键

Question

如果我有 R(E, F, G, H)，这些函数依赖的候选键是什么？

    FD1: EF -> G
    FD2: EF -> H
    FD3: G -> E
    FD4: H -> F

我的想法是 EF 将被视为候选密钥，因为 EF -> G 和 EF -> H，因此 EF+ = {E, F, G, H}。我可以说 GH 也是候选键吗，因为 G -> E，H -> F，因此 GH -> EF 和 GH+ = {E，F，G，H}？还有其他候选键吗？

Answer 1

架构有四个候选键：EF、EH、FG、GH。您可以通过计算每对属性的闭包并注意到它包含所有属性来轻松验证这一事实。

问题自然是如何找到他们。简单的方法是简单地尝试关闭关系的所有属性子集，但这显然是低效的，是一个指数过程。

有更有效的算法可以找到所有候选键，但它们相当复杂。有一些简单的启发式方法可以帮助降低解决方案的复杂性，而无需使用正式的算法。

首先，您应该从规范封面开始，否则无法应用这些启发式方法（在您的示例中，您已经有了规范封面）。第一步是您可以排除任何仅出现在依赖项右侧的属性（在这种情况下不是），并考虑所有仅出现在左侧的属性必须始终是任何键的一部分（也不是在这种情况下）。

然后，您可以从依赖项的左侧开始，计算它们的闭包，看看这些属性集是否可以确定所有其他属性集。如果不是这种情况，您可以添加其他属性，一次一个，然后再次计算结果集的闭包，当您找到一个键或该集包含已考虑的子集时停止考虑这些属性。

比如你从EF中发现你可以确定其他所有的属性，所以这是一个候选键。然后考虑G，可以加上E，注意EG+ = EG，所以这不是候选键，然后加上H，注意GH+ = EFGH，所以这是候选键，最后加上F，发现FG是一个候选键。当然，当一组属性是候选键时，您不会向它添加其他属性。另一组测试以 H 开头，首先是 HE（生成候选键），然后是 HF，它不生成候选键。此时我们应该检查是否将属性添加到 EG 或 HF 我们获得了候选键，但我们可以安全地停在这里，因为我们将获得已经考虑过的集合的超集（例如，包含 GF 的 EGF） .

从功能依赖关系中确定候选键

Determining Candidate Keys from Functional Dependencies

database

relational-database

functional-dependencies