找到一个关系拥有的最大数量的候选键？

Question

我正在尝试解决这个与关系中的候选键有关的问题。这是问题：

    Consider table R with attributes A, B, C, D, and E. What is the largest number of
candidate keys that R could simultaneously have?

答案是10，但我不知道它是怎么做到的，也不知道这个词在计算答案时是如何同时起作用的。

Answer 1

不是其他集合子集的集合。
例如{A-B}和{A,B,C}不能同时作为候选键，因为{A,B}是{A,B,C}的子集。
2 个属性或 3 个属性的组合生成最大数量的同时候选键。
查看 3 个属性集实际上是 2 个属性集的补充，例如{C,D,E} 是 {A,B} 的补码。

         2               3    
     attributes      attributes
       sets            sets

   1.  {A,B}    -     {C,D,E}
   2.  {A,C}    -     {B,D,E}
   3.  {A,D}    -     {B,C,E}
   4.  {A,E}    -     {B,C,D}
                -     
   5.  {B,C}    -     {A,D,E}
   6.  {B,D}    -     {A,C,E}
   7.  {B,E}    -     {A,C,D}
                -     
   8.  {C,D}    -     {A,B,E}
   9.  {C,E}    -     {A,B,D}
                -     
   10. {D,E}    -     {A,B,C}

如果我选择一组单个属性，我将只有 4 个选项

{A},{B},{C},{D}

任何超过 1 个元素的集合都将包含上述之一，因此不合格。

如果我选择一组 4 个属性，我将只有 4 个选项

{A,B,C,D},{A,B,C,E},{A,B,D,E},{B,C,D,E}

任何超过 4 个元素的集合都将包含上述之一，因此将不合格。任何少于 4 个元素的集合都将包含在上述之一中，因此不会被限定。

等等

Answer 2

对于 5 个键，最好通过暴力破解。理解思路比计算更重要（DuDu/David给出了10个候选键的一个很好的例子，表明一组10个键是可能的，所以最大值至少有这么大）。

这是什么想法？候选键是唯一的属性组合。因此，如果 A 是唯一的，那么 A 与任何其他列也是唯一的。一组候选键很简单：

一个
B
C
D
E

如果这些中的每一个都是唯一的，那么任何键组合将至少包含这些属性中的一个并且该组合也将是唯一的。因此，这五个的唯一性将意味着任何其他组合的唯一性。

5 不是这个属性的最大候选键数。

它变得有点复杂。如果 {A, B, C, D, E} 是唯一的（并且没有子集是候选键），则恰好有 1 个候选键。重新排列列不会更改集合（集合是无序的）。

我们可能假设的一件事是最大的一组候选键具有相同长度的键。这是事实。为什么？好吧，如果我们有一组不同长度的键，我们可以通过添加任意属性来延长较短的键，并且仍然有一个最大的集合。

因此，您只需要准确地考虑 1、2、3、4 和 5 个键的子集。当你算出来的时候，你会发现最大的数字是：

5 10 10 5 1

你可以在开头加一个“1”，你可能会认出这个图案。这是来自 Pascal's Triangle 的一行。这个观察结果（以及相关证明）实际上可以很容易地确定任何给定 n 的最大值。

顺带一提，长度为3的集合是：

A B C
A B D
A B E
A C D
A C E
A D E
B C D
B C E
B D E
C D E

找到一个关系拥有的最大数量的候选键？

finding largest number of candidate keys that a relation has?

sql

functional-dependencies

candidate-key