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

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

0 голосов
/ 26 октября 2018

Если у меня есть R (E, F, G, H), какими будут ключи-кандидаты из этих функциональных зависимостей? 

    FD1: EF -> G
    FD2: EF -> H
    FD3: G -> E
    FD4: H -> F

Мой мыслительный процесс состоял в том, что EF будет считаться ключом-кандидатом, поскольку EF -> G и EF -> H, поэтому EF + = {E, F, G, H}. Могу ли я сказать то же самое, сказав, что GH также является ключом-кандидатом, поскольку G -> E, H -> F, следовательно, GH -> EF и GH + = {E, F, G, H}? Будут ли еще какие-нибудь ключи-кандидаты?

1 Ответ

0 голосов
/ 26 октября 2018

Схема имеет четыре возможных ключа: EF, EH, FG, GH.Вы можете легко проверить этот факт, вычислив замыкание каждой пары атрибутов и отметив, что он содержит все атрибуты.

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

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

Во-первых, вы должны начать с канонического покрытия, иначе эти эвристики не могут быть применены (в вашем примере у вас уже есть каноническое покрытие).Первым шагом является то, что вы можете исключить любой атрибут, который появляется только в правой части зависимостей (не в этом случае), и учтите, что все атрибуты, появляющиеся только в левой части, должны всегда быть частью любого ключа (также нев этом случае).

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

Например, из EF вы обнаружили, что можете определить все остальные атрибуты, так что это ключ-кандидат.Затем, учитывая G, вы можете добавить E, отметив, что EG + = EG, так что это не ключ-кандидат, затем добавить H, отметив, что GH + = EFGH, так что это ключ-кандидат, и, наконец, добавить F, обнаружив, что FGключ-кандидат.Конечно, когда набор атрибутов является ключом-кандидатом, вы не добавляете к нему другие атрибуты.Другой набор тестов начинается с H, сначала HE (который производит ключ-кандидат), затем HF, который не производит ключ-кандидат.На этом этапе мы должны проверить, если при добавлении атрибута к EG или к HF мы получим ключ-кандидат, но мы можем смело остановиться на этом, поскольку мы получим просто расширенный набор уже рассмотренного набора (например, EGF, который содержит GF)..

...