1

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

    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，但我不知道它是如何完成的，也不知道在计算答案时这个词是如何同时起作用的。

4

2 回答 2

2

不是其他集合子集的集合。
例如 {AB} 和 {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 个元素的集合都将包含在上述之一中，因此将不合格。

等等

于 2016-12-12T19:01:22.060 回答
2

对于 5 个键，最好通过蛮力执行此操作。理解想法比计算更重要（DuDu/David 给出了 10 个候选键的一个很好的例子，表明一组 10 个键是可能的，因此最大值至少有这么大）。

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

  • 一个
  • 乙
  • C
  • D
  • 乙

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

5 不是具有此属性的最大候选键数。

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

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

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

5 10 10 5 1

您可以在开头添加一个“1”，您可以识别该模式。这是帕斯卡三角中的一行。这种观察（以及相关的证明）实际上可以很容易地确定任何给定 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
于 2016-12-12T19:17:07.270 回答