Определение ключей-кандидатов по функциональным зависимостям
Если бы у меня был 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
В схеме есть четыре ключа-кандидата: EF, EH, FG, GH. Вы можете легко проверить этот факт, вычислив замыкание каждой пары атрибутов и заметив, что оно содержит все атрибуты.
Вопрос, естественно, в том, как их найти. Тривиальный метод - просто попытаться закрыть все подмножества атрибутов отношения, но это явно неэффективно, поскольку является экспоненциальным процессом.
Существуют более эффективные алгоритмы поиска всех ключей-кандидатов, но они довольно сложны. Существуют простые эвристики, которые могут помочь уменьшить сложность решения без использования формального алгоритма.
Во-первых, вы должны начать с канонической обложки, иначе эти эвристики не могут быть применены (в вашем примере у вас уже есть каноническая обложка). Первый шаг заключается в том, что вы можете исключить любой атрибут, который появляется только в правой части зависимостей (не в этом случае), и учитывать, что все атрибуты, появляющиеся только в левой части, всегда должны быть частью любого ключа (также не в этом случае).
Затем вы можете начать с левых сторон зависимостей и вычислить их замыкания, чтобы увидеть, могут ли эти наборы атрибутов определять все остальные. Если это не так, вы можете добавлять другие атрибуты по одному и снова вычислять замыкание результирующего набора, прекращая рассмотрение этих атрибутов, когда вы нашли ключ или набор включает уже рассмотренное подмножество.
Например, из EF вы обнаружили, что можете определить все остальные атрибуты, так что это ключ-кандидат. Затем, учитывая G, вы можете добавить E, отметив, что EG + = EG, так что это не кандидатный ключ, затем добавить H, отметив, что GH + = EFGH, так что это кандидатный ключ, и, наконец, добавить F, обнаружив, что FG является ключ кандидата. Конечно, когда набор атрибутов является ключом-кандидатом, вы не добавляете к нему другие атрибуты. Другой набор тестов начинается с H, сначала HE (который создает ключ-кандидат), затем HF, который не создает ключ-кандидат. На этом этапе мы должны проверить, добавляя атрибут в EG или в HF, мы получаем ключ-кандидат, но мы можем спокойно остановиться на этом, поскольку мы получим только расширенный набор из уже рассмотренного набора (например, EGF, который содержит GF) .
Спасибо за четкое объяснение, теперь у меня другой вопрос. Будет ли R считаться 2НФ или 3НФ в его высшей нормальной форме? Я думал, что это следует рассматривать как 3NF, поскольку я не вижу каких-либо частичных зависимостей или транзитивных свойств среди функциональных зависимостей.
@ smith1453 Есть такие ФД, но они не ФД с СК определяют непервичные атрибуты. И искали ли вы среди все FD по аксиомам Армстронга, а не только те, что в какой-то обложке? Точно применяйте определения и алгоритмы.
CK не просто подразумевает все атрибуты, но и не имеет меньшего подмножества. Таким образом, вы показываете, что эти наборы являются суперключами, но не CK. Также не понятно «из этих ФД». Нам нужно знать, что набор - это крышка, чтобы найти CK. Иногда для определения или алгоритма нам нужно покрытие или минимальное / несводимое / каноническое покрытие.