Объяснение алгоритма декомпозиции BCNF

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

Рассматривать R=(ABCDEG) & F={BG->CD, G->A, CD->AE, C->AG, A->D},
Я начинаю выбирать A->D,
Теперь я получил S=(AD), R'=(ABCEG).
я поднял G->A,
Теперь я получил S=(AD,AG) R'=(BCEG),
я поднял C->G, Теперь я думаю, что мне нужно получить S=(AD,AG,CG) а также R'=(BCE), Но ответ в конце концов, (AD,AG,CGE,BC).что пошло не так? или, может быть, лучший алгоритм?

Источник

2 ответа

Решение

Чтобы преобразовать отношение R и набор функциональных зависимостей (FD's) в 3NF Вы можете использовать синтез Бернштейна. Чтобы применить синтез Бернштейна -

  • Сначала мы убедимся, что данный набор FD's минимальное покрытие
  • Второе мы берем каждый FD и сделайте это своей собственной подсхемой.
  • В-третьих, мы пытаемся объединить эти подсхемы

Например, в вашем случае:

R = {A, B, C, D, E, G}
FD's = {BG-> CD, G-> A, CD-> AE, C-> AG, A-> D}

Сначала мы проверим, FD's минимальное покрытие (синглтон с правой стороны, без постороннего атрибута с левой стороны, без избыточного FD)

  • Синглтон RHS: Итак, мы можем написать наши FD как { BG->C, BG->D, G->A, CD->A, CD->E, C->A, C->G, A->D}.
  • Нет посторонних атрибутов LHS: мы можем удалить D от LHS из CD->A а также CD->E поскольку D является посторонним атрибутом здесь (Как мы можем получить D от C так как C-> A и A-> D). Итак, теперь у нас есть {BG->C, BG->D, G->A, C->A, C->E, C->G, A->D}
  • Нет избыточных FD: отметим, что здесь много избыточных зависимостей. Удаляя их, мы имеем {BG->C, G->A, C->E, C->G, A->D}

Второе мы делаем каждый FD своя собственная схема. Итак, теперь мы имеем - (ключи для каждого отношения выделены жирным шрифтом)

R 1 = { B, G, C}
R 2 = { G, A}
R 3 = { C, E}
R 4 = { C, G}
R 5 = { A, D}

В-третьих, мы видим, можно ли объединить любую из подсхем. Мы видим, что R 3 и R 4 могут быть объединены, так как они имеют одинаковый ключ. Итак, теперь у нас есть -

S 1 = {B, G, C}
S 2 = {A, G}
S 3 = {C, E, G}
S 4 = {A, D}

Это в 3НФ. Теперь, чтобы проверить BCNF, мы проверяем, нарушает ли какое-либо из этих отношений (S 1, S 2, S 3, S 4) условия BCNF (т.е. для каждой функциональной зависимости). X->Y левая сторона ( X ) должен быть суперключем). В этом случае ни один из них не нарушает BCNF и, следовательно, он также разлагается на BCNF.

Примечание Мой окончательный ответ выше (AD,AG,CGE,BCG), Решение, которое вы ожидаете, (AD,AG,CGE,BC) но это неправильно Последнее соотношение здесь (S 1) также должно иметь G атрибут, как показано выше.

Источник

Введите входные данные: отношение R0 с установленным (минимальным) S0 для FD.

Вывод: Разложение R в набор отношений, все из которых находятся в BCNF

Алгоритм: R <- R0 и S <- S0 Повторять до тех пор, пока R не окажется в BCNF. Если существует FD X -> Y, который нарушает условие BCNF. Вычислите {X}+ и выберите {X}+ в качестве одного отношения в качестве R1, а другой R2 в качестве {(R - X +) U X}. Сопоставьте набор FD S на R1 и R2 (определите FD на R1 и R2). Рекурсивно повторить алгоритм на R1 и R2.

Правило: 1. Должно быть сохранение атрибутов. 2. Должен быть без потерь 3. Должен быть сохранением FD

Пример: R(xyz) FD xy -> z; key : xy z-> y;

Решите: z-> y фиолетовый в состоянии BCNF.

Так разложим отношение R {z}+= yz; R1(yz) where key is z and R2(xz) key is x

Источник
Другие вопросы по тегам