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

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

Для данного отношения 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

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

Спасибо.


relational-database relation functional-dependencies candidate-key
person dxu    schedule 16.10.2011    source источник

Ответы (3)


arrow_upward
5
arrow_downward

Второй немного проще, поэтому беру его первым. . . вы знаете, что B должна быть в любой тональности, потому что она не находится ни в одной правой части. (То есть, даже если у вас есть значения ACDE, вы не можете вывести значение B.) Аналогично для E; поэтому любой ключ должен включать BE. Но БЫТЬ само по себе является достаточным ключом, потому что Е дает вам А (отсюда БЫТЬ → АВЕ), а АВ дает вам CD (отсюда БЫТЬ → АВСДЕ).

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

person ruakh    schedule 16.10.2011
comment
Подождите, значит ли это, что любой атрибут в отношении, который не находится в правой части данного FD, будет ключом, несмотря ни на что, поскольку вы не можете вывести их из какого-либо FD? Как вы можете знать это наверняка? - person dxu; 16.10.2011
comment
@ user924199: Нет, это означает, что любой атрибут, не найденный в правой части любого FD, должен быть частью каждого ключа. - person Mike Sherrill 'Cat Recall'; 16.10.2011
comment
Извините, вы можете объяснить, почему это так? Кроме того, в качестве другого примера, если вам даны AB -> C и C -> D, единственным ключом в этом случае будет AB, верно, поскольку по транзитивному свойству AB -> D и, следовательно, C не является ключом ? Предполагая, что это правда, почему ключи не могут быть A, B по отдельности? - person dxu; 16.10.2011
comment
Извините, нет, вы не совсем правы. Давайте сделаем это немного менее абстрактным. Предположим, у вас есть таблица базы данных с полями A, B, C и D, где C = абс (A - B) и D = пол (C). Например, если A = 2,1 и B = -3,4, то C = 1,3, поэтому D = 1. Тогда AB → C и C → D: если две записи имеют одинаковые A и B, то они имеют одинаковые C, и если у них один и тот же C, то у них один и тот же D. Следовательно: если у них одинаковые A и B, то они полностью идентичны, поэтому AB является суперключом. (продолжение) - person ruakh; 17.10.2011
comment
(продолжение) Но две записи могут иметь один и тот же A, один и тот же B или один и тот же C, но различаться в других полях; поэтому ни A, ни B, ни C не являются суперключом. Если вы немного поиграете, вы сможете понять, почему единственными суперключами являются AB, ABC, ABD и ABCD. Из них единственным ключом-кандидатом является AB, поскольку все остальные суперключи содержат AB (и, следовательно, содержат больше полей, чем нужно). Имеет ли это смысл? - person ruakh; 17.10.2011

arrow_upward
6
arrow_downward

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

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

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

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

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

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

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

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

person Erwin Smout    schedule 16.10.2011
comment
Этот ответ, если он работает, намного лучше, поскольку он касается алгоритма, а не только конкретных случаев. - person Niklas R.; 04.06.2012

arrow_upward
0
arrow_downward

введите здесь описание изображения

Справочник http://www.ict.griffith.edu.au/~jw/normalization/assets/Functional%20Dependencies%20and%20Normalization.pdf

Доказательство алгоритма (краткое и простое, раздел 3)
 Х. Сайедян и Т. Спенсер, «Эффективный алгоритм вычисления ключей-кандидатов схемы реляционной базы данных», Компьютер Журнал, том. 39, нет. 2, февраль 1996 г. [онлайн]. Доступно: https://pdfs.semanticscholar.org/ab3f/f65010b50d78d583b1c2b6ce514fa072d23d. [Доступ: 31 июля 2019 г.]

Объяснение видео
 https://www.youtube.com/watch?v=s1DNVWKeQ_w

person Leponzo    schedule 04.08.2019
comment
Пожалуйста, не отвечайте на повторяющиеся вопросы, помечайте их как дубликаты. - person philipxy; 04.08.2019