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

Question

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

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

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

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

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

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

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

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

45

database functional-dependencies

Источник

user641455 20 апр '11 в 19:26

7 ответов

Решение

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

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

17

Источник

user2237469 21 май '13 в 11:31

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

3

Источник

user1082475 05 дек '11 в 22:42

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

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

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

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

             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. Я знаю, что есть алгоритм для этого, и он, вероятно, где-то в вашем тексте курса. Существует также, вероятно, пример. Вы должны пройти через это вручную, пока образец не станет интуитивно понятным.

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

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

2

Источник

user513828 20 апр '11 в 20:04

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

в этом случае:

ни один из ваших 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, поэтому ответьте a это ключ

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

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

1

Источник

user706119 20 апр '11 в 20:03

Код

Если код говорит вам больше, чем длинные объяснения, вот 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"]]

1

Источник

user3579309 17 янв '16 в 14:51

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.

-1

Источник

user3569580 24 апр '14 в 15:38

Другие вопросы по тегам database functional-dependencies

user1388192 20 апр '11 в 20:23 2011-04-20 20:23 · Accepted Answer · 2011-04-20 20:23

Возьмите 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 является ключом.

ОБНОВИТЬ

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