Поиск ключей-кандидатов от заданных отношений

Question

Я провел некоторое исследование по этой проблеме и, похоже, не могу найти ответ.

R = (A, B, C, D, E)

Функциональные зависимости:

A => B
ED => A
BC => E

Затем он перечисляет ключи-кандидаты как:

ACD, BCD, CDE

Как эти ключи-кандидаты получены из вышеупомянутых FD?

Точно так же, где R = (A, B, C, D):

Функциональные зависимости:

D => B 
AB => D 
AB => C 
C=> A

Затем он перечисляет ключи-кандидаты как:

AB, BC, CD, AD

Опять же, моя проблема здесь в том, что я не уверен, как ключи-кандидаты были получены из FD?

Заранее спасибо.

Answer 1

В этой статье описывается, как ключи-кандидаты получены из данного отношения.
http://en.wikipedia.org/wiki/Candidate_key.
Также взгляните на: ключи-кандидаты из функциональных зависимостей
функциональные зависимости.
Это тоже хорошо, я думаю:
http://www.cs.newpaltz.edu/~pletcha/BuildingCandidateKeys.html.
так что это в основном:
A => B (первый случай):
ED => A
BC => E
Поскольку C и D не зависят ни от какого fd, очевидно, что CD является частью каждого выбранного ключа.

ACD, BCD, CDE
Второй:
D => B
AB => D
AB => C
C => A

Все синглы зависят от одного из fd, поэтому ни один из них не включен во все ключи-кандидаты.
A зависит не от D и не от B, ни явного, ни неявного. ТАК ОБЪЯВЛЕНИЕ и АБ это один
кандидатский ключ. B не зависит от C и A, поэтому AB и BC. С не зависит от D,
для этого CD.

AB, BC, CD, AD

этот также полезен: http://csc.lsu.edu/~jianhua/fd_slide2_09.pdf

Answer 2

Это немного старовато, но имеет много точек зрения, поэтому я подумал, что это может помочь добавить мои собственные объяснения.

Для первой проблемы:

R = (A, B, C, D, E)
A => B
ED => A
BC => E

По сути, ключ-кандидат должен удовлетворять двум критериям:

1) Ключ-кандидат должен уметь определять все остальные переменные. Это в основном означает, что используя переменные в ключе-кандидате, вы сможете найти любую другую переменную, следуя стрелкам в функциональных зависимостях.

2) Ключ-кандидат должен быть минимальным. Например, мы можем найти каждую переменную из ABCDE, потому что ACBDE - это уже каждая переменная. Тем не менее, мы могли бы снять некоторые переменные. Например, можно обнаружить, что ACD является ключом-кандидатом. Поскольку ACD является допустимым ключом-кандидатом, а ACD является подмножеством ABCDE, мы знаем, что ABCDE не может быть ключом-кандидатом. Другими словами, мы можем отсоединять переменные от ABCDE и при этом иметь ключ-кандидат, поэтому ABCDE не минимален.

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

Давайте начнем только с переменной A. Наша первая функциональная зависимость говорит нам, что A определяет B, поэтому теперь у нас есть две переменные, A и B. Однако AB не удовлетворяет ни одной из других функциональных зависимостей, поэтому у нас нет удачи. Мы определили, что A сам по себе не является ключом-кандидатом (и, как и логически, AB тоже не является логическим, так как мы уже выяснили, что мы не можем получить C, D и E с AB).

Далее давайте попробуем ABC. Поскольку мы знаем, что мы всегда можем получить B с A (из A => B), на самом деле не имеет смысла иметь A и B в одном и том же ключе-кандидате. Это потому, что если ABC работает, то AC должен работать, потому что мы можем получить ABC от AC.

Давайте попробуем снова с AC вместо ABC. A определяет B, поэтому теперь у нас есть переменные A, B и C. BC определяет E (BC => E), поэтому теперь у нас есть A, B, C и E. Однако у нас нет способа получить переменную D! На самом деле, логически, поскольку C и D не являются результатом какой-либо функциональной зависимости (они никогда не находятся справа), мы знаем, что C и D должны быть частью каждого ключа-кандидата (как указано в другом сообщение).

Мы могли бы попытаться выяснить, является ли CD ключом-кандидатом, но логически, поскольку C не определяет ничего самостоятельно, D не определяет ничего сам, а CD ничего не определяет, CD не может быть ключом-кандидатом.,

Давайте попробуем ACD. Прежде всего, как мы знаем, A определяет B, поэтому у нас есть переменные A, B, C и D. BC определяет E (BC => E), поэтому у нас есть все 5 переменных, поэтому у нас есть ключ-кандидат!

Однако возможно использование нескольких ключей-кандидатов, поэтому мы еще не закончили. Помните, что каждый ключ должен включать C и D, поэтому давайте попробуем BCD. BC определяет E, поэтому у нас есть B, C, D и E. ED определяет A (ED => A), поэтому у нас есть все 5 переменных. У нас есть еще один ключ-кандидат!

Давайте попробуем последний возможный ответ: CDE. ED определяет A, поэтому у нас есть A, C, D и E. A определяет B, поэтому у нас есть все 5 переменных и у нас есть ключ-кандидат.

Наши 3 возможных ключа-кандидата - это ACD, BCD и CDE. Мы знаем, что если мы уберем какую-либо переменную из одного из этих ключей, это не будет действительный ключ, поэтому мы знаем, что все эти ключи также минимальны.

Давайте перейдем ко второй проблеме:

R = (A, B, C, D)
D => B 
AB => D 
AB => C 
C => A

Поскольку сейчас у нас есть базовые знания, давайте делать меньше проб и ошибок и больше аналитических рассуждений.

Во-первых, AB определяет и C, и D. Кроме того, A и B, очевидно, не являются ключами-кандидатами, поэтому мы знаем, что AB минимален. AB - наш первый ключ-кандидат.

CD определяет A и B, а C и D, очевидно, сами по себе не являются ключами, поэтому CD - наш второй кандидатный ключ.

Глядя на наши функциональные зависимости, мы знаем, что если мы получим либо A и B, либо C и D, мы сможем найти любую другую переменную. Зная это, мы видим, что, поскольку D дает нам B, все, чего нам не хватает, это A. Поэтому AD является ключом-кандидатом.

Используя ту же логику, поскольку C определяет A, если мы добавим B, у нас будет AB и мы сможем найти все, чего не хватает. Поэтому BC также является ключом. Опять же, как и другие ключи-кандидаты для этого упражнения, BC тривиально минимален.

Наши последние возможные ключи-кандидаты - AB, CD, AD и BC.

Answer 3

Минимальный набор атрибутов, замыкание атрибута которого является набором всех атрибутов отношения, называется ключом-кандидатом отношения.

Алгоритм поиска ключа K для R по набору F функциональных зависимостей

Вход: универсальное отношение R и набор функциональных зависимостей F от атрибутов R.

         1. Set K:= R;
   2. For each attribute A in K {
      Compute (K - A)+ with respect to F;
      If (K - A)+ contains all the attributes in R,
          then set K := K - {A};

}

Согласно этому алгоритму замыкания атрибутов ACD+, BCD+, CDE+ содержат все атрибуты в R и минимальны.