найти наибольшее количество ключей-кандидатов, которые имеет отношение?

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 с любым другим столбцом также является уникальным. Один набор ключей-кандидатов просто:

• Б
• С
• D
• Е

Если каждый из них являются уникальными, то любой комбинация ключи будут содержать хотя бы один из этих атрибутов, и комбинация также будет уникальной. Следовательно, уникальность этих пяти будет означать уникальность любой другой комбинации.

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