Определить ключи от функциональных зависимостей

Question

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

У меня есть пример проблемы:

Найти все ключи отношения R (ABCDEFG) с функциональными зависимостями

AB → C
CD → E
EF → G
FG → E
DE → C
BC → A

Продемонстрируйте свои знания, указав, какое из следующего является ключевым.

a. BCDEF             
b. ADFG           
c. BDFG           
d. BCDE 

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

Answer 1

Возьмите FD, например AB → C

Увеличивайте, пока не будут упомянуты все атрибуты, например, ABDEFG → CDEFG (обратите внимание, что это эквивалентно ABDEFG → ABCDEFG, потому что тривиально верно, что A-> A и B-> B).

Это говорит о том, что ABDEFG - суперключ.

Проверьте другие FD, в которых LHS является подмножеством вашего суперключа, и что в его RHS содержится какой-то другой атрибут вашего суперключа.

Есть два. EF → G и FG → E. Удалите атрибуты RHS этих из вашего суперключа. Это дает вам два ключа, которые, безусловно, являются суперключами, но не обязательно неприводимыми: ABDEF и ABDFG.

Однако из AB → C и CD → E можно также вывести, что ABD → E. Следовательно, мы также можем удалить E из нашего ключа ABDEF. Здесь неприятно то, что когда я сказал «Проверьте другие FD», это, очевидно, означает, что вы также должны проверить любой FD, который появляется при закрытии вашего набора FD (т.е. любой FD, который выводится из вашего данного набора FD) ... И это немного непрактично делать вручную ...

Полезный сайт для проверки правильности ваших результатов:

http://www.koffeinhaltig.com/fds/ueberdeckung.php

Теперь вы сможете определить, что опция c является ключом.

UPDATE

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

Answer 2

Это видео очень хорошо объясняет

http://www.youtube.com/watch?v=s1DNVWKeQ_w

Answer 3

Ну, это должно быть довольно просто.Все, что вам нужно сделать, это взять закрытие каждого данного ключа и посмотреть, содержит ли оно все атрибуты R. Например, закрытие BCDEF = ABCDEFG, поскольку BC -> A и BC - это подмножество BCDEF, и поэтому, если EF для FDEF -> G. Так как это замыкание содержит все атрибуты R, ключ BCDEF.Основная цель создания замыканий - посмотреть, сможем ли мы «добраться» до каждого атрибута из заданного набора атрибутов.Закрытие - это набор атрибутов, которые мы можем реально достичь, перемещаясь по FD.

Answer 4

Поскольку вы находитесь на курсе теории БД, я предполагаю, что у вас есть опыт работы с SQL, и постараюсь связать теорию с контекстом реализации.

По сути, отношение - это то, что вы бы назвали таблицей в реализации, а ключ - это ЛЮБОЙ набор атрибутов (столбцы чтения), которые можно использовать для идентификации УНИКАЛЬНОЙ строки (в теории БД это будет кортеж). Простейшая аналогия здесь заключается в том, что ключ - это ваш первичный ключ, а также любой другой возможный набор столбцов, которые вы можете использовать для идентификации одного кортежа в вашем отношении (строки в вашей таблице). Итак, вот основные шаги для этого (я покажу пример А, а затем вы можете попробовать остальные):

1. Перечислите все атрибуты, которых нет в предложенном вами ключе (поэтому BCDEF не включает A и G).

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

                a. So for A, you have BC -> A.  Since both B and C are in the proposed
                   key BCDEF, you can infer that BCDEF -> A.  Your set now becomes
                   BCDEFA.
                b. For G, again going through your FDs you find EF -> G.  Since both
                   E and F are in BCDEFA, you can infer BCDEFA -> G.
   

Поскольку вы смогли вывести как A, так и G из BCDEF, опция a является ключом отношения ABCDEFG. Я знаю, что есть алгоритм для этого, и он, вероятно, где-то в вашем тексте курса. Существует также, вероятно, пример. Вы должны пройти его вручную, пока шаблон не станет интуитивно понятным.

РЕДАКТИРОВАТЬ: Причина, по которой я хотел бы вернуться к тексту для поиска этого алгоритма, состоит в том, что скорее всего ваш экзамен будет написан, а не множественный выбор, так как это курс теории БД. Если это так, то вы получите более частичный кредит, если будете методично следовать обозначениям, приведенным в тексте / примечаниях к вашему курсу.

Основная цель - превратить ключ в отношение, которое должно доказать, что предложенный ключ на самом деле является ключом.

Answer 5

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

в данном случае:

ни один из ваших FD не "дает" вам B, D или F ..., поскольку они являются частью отношения, не может быть суперключа, который не содержит B, D и F ... удалить ответ b (B отсутствует) ... удалить ответ d (F отсутствует)

Теперь давайте проверим оставшиеся ответы, если они содержат достаточно информации, чтобы получить все части отношения

ответ a (BCDEF) «даст» вам B, C, D, E и F, поэтому вам нужно найти A и G с помощью FD ... A может быть достигнуто BC, а G может быть достигнуто EF, так что ответом является ключ

ответ c (BDFG) «даст» вам B, D, F и G, поэтому вам нужно найти A, C и E, используя FDs ... E может быть достигнуто с помощью FG ... C может быть достигнуто с помощью DE (после достижения E FG) ... и, наконец, A может быть достигнуто BC (после достижения C) ...

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

Answer 6

Код

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

https://github.com/lovasoa/find-candidate-keys/blob/master/find-candidate-keys.js

Пример

candidate_keys(["A","B","C","D","E","F","G"], [ [['A','B'], 'C'], [['C','D'], 'E'], [['E','F'], 'G'], [['F','G'], 'E'], [['D','E'], 'C'], [['B','C'], 'A'] ]) возвращается [["B","D","F","G"],["B","D","E","F"],["B","C","D","F"],["A","B","D","F"]]

Answer 7

step1: since AB->C and CD->E.  then we get ABD->ABCDE(1)
step2: Given (1) and EF->G, then we get ABDF->ABCDEF, then ABDF->ABCDEFG(2), 

так что ABDF - это супер Ключ.Затем мы будем использовать результат зависимостей, чтобы определить, являются ли они ключами.(вот почему я использую BC-> A, потому что A является частью моего суперключа, который зависит от BC).

step3: Given (2) and BC->A, we get BCDF->ABDF, so BCDF->ABCDEFG(3)   
step4: Given (3) and DE->C, we get BDEF->BCDE, so BDEF->ABCDEFG(4)   
step5: Given (4) and FG->E, we get BDFG->BDEF, so BDFG->ABCDEFG,    
So the Answer BDFG is right.