관계에있는 후보 키의 수가 가장 많습니까?

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 개 미만의 요소가있는 집합은 위의 중 하나에 포함되므로 정규화되지 않습니다. 5 키에 대해서는

등

Answer 2

, 그것은 폭력하여이 작업을 수행하는 것이 가장입니다. 아이디어를 이해하는 것이 계산보다 더 중요합니다 (DuDu/David는 10 개의 키 집합이 가능한 최대 10 개의 후보 키를 보여주는 좋은 예입니다).

아이디어는 무엇입니까? 후보 키는 고유 한 속성의 조합입니다. 따라서 A가 고유 한 경우 다른 열이있는 A도 고유합니다. 후보 키 중 하나 개 세트는 단순히 :

• B
• C
• D
• E

의 이들 각각은 고유 경우, 어떤 조합 키에는 이러한 속성 중 하나 이상이 포함되며 조합도 고유합니다. 따라서이 5 가지의 고유성은 다른 조합의 고유성을 암시합니다.

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