Идентификация ключа кандидата с функциональными зависимостями

Question

У меня проблемы с пониманием того, как определить ключи в функциональных зависимостях. Я смотрел на примеры, например:

Учитывая отношение ABCD, найдите все ключи, не включая суперключи

A -> BC, C -> D, CD -> AB.

Это дает ключи C и A. То, как я думал, что эта проблема была решена, было то, что BC и D оба зависят от A и C, а AB зависит от CD, что означает, что все три из них являются ключами, но так как CD - суперключ (C является подмножеством, которое также является ключом), CD не считается минимальным суперключем.

Однако, в другом примере,

ABCDE
AB → CD
E → A
D → A

Единственный ключ здесь, по-видимому, БЫТЬ. Почему это так, и кто-нибудь может уточнить, какие шаги нужно предпринять для поиска ключей с этими проблемами?

Спасибо.

Answer 1

Процедура, которая немного более формальна.

Возьмите FD, например (пример 2), AB -> CD.

Увеличивайте это, используя тривиальные FD, пока не получите ВСЕ атрибутына RHS.

Вам не хватает ABE на RHS, поэтому вы должны увеличить с помощью тривиального FD ABE -> ABE, чтобы получить ABE -> ABCDE.

Это говорит о том, что ABE - это суперключпотому что знание значений в определенной строке для ABE будет достаточно для определения значений для всех атрибутов в этой строке.

Теперь осмотрите ДРУГИЕ FD, чтобы увидеть, позволяет ли какой-либо из них уменьшить LHS (ABE) в этом случае.E -> A позволяет вам удалить A из ABE, сохраняя при этом только BE -> ABCDE.Правило сокращения таково: если LHS другого FD (E) является правильным подмножеством суперключа, который вы пытаетесь уменьшить (ABE), то вы можете удалить все атрибуты из суперключа, которые упоминаются ТОЛЬКО в RHS этогодругой FD (вы не можете удалить E, если вы смотрите на «другой» FD, такой как E -> EA !!!).

Эта процедура не подходит для механической реализации, потому что вам также может потребоватьсявзгляд на "комбинации" других FD.Тем не менее, большинство сценариев использования и даже большинство сфабрикованных классных упражнений, как правило, не достаточно сложны, чтобы заставить эту процедуру завершиться с ошибкой (то есть оставить вас с правильным суперключем вместо неприводимого).

(PS, чтобы найти ВСЕ ключи, вам нужно будет применить это ко ВСЕМ данным FD)

Answer 2

Второй вариант немного проще, поэтому сначала возьмем его. , , Вы знаете, что B должен быть в любом ключе, потому что это не на любой правой стороне. (То есть, даже если у вас есть значения ACDE, вы не сможете вывести значение B.) Аналогично для E; поэтому любой ключ должен включать BE. Но BE сам по себе является достаточным ключом, потому что E дает вам A (следовательно, BE → ABE), а AB дает вам CD (следовательно, BE → ABCDE).

В первом мы видим, что A является ключом, потому что A дает вам B и C, а C дает вам D. Аналогично, C является ключом, потому что C дает вам D, а C и D вместе дают вы A и B. И наоборот, мы видим, что A и / или C должны быть в любой тональности, потому что каждая левая сторона включает хотя бы одну из них.