Объяснение алгоритма разложения 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). Что пошло не так? или, возможно, лучший алгоритм?


database functional-dependencies decomposition bcnf
person user2637293    schedule 15.12.2015    source источник
comment
Нужны ли запятые для (A,B,C,D,E,G)? похоже, вы работаете с (ABCDEG)   -  person Abundance    schedule 15.12.2015
comment
@Изобилие, я отредактирую   -  person user2637293    schedule 15.12.2015
comment
Цитата из вашего связанного ответа: где вы вычисляете, что тест S имеет отношение R ', которого нет в BCNF? Когда вы выбираете FD: X->Y, где вы показываете, что он выполняется в R' и нарушает BCNF? Вы следуете алгоритму?   -  person philipxy    schedule 16.12.2015

Ответы (2)


arrow_upward
9
arrow_downward

Чтобы преобразовать отношение 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)

  • Singleton RHS: Таким образом, мы можем записать наши FD как {BG->C, BG->D, G->A, CD->A, CD->E, C->A, C- >Г, А->Г}.
  • Нет лишнего атрибута 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 собственную подсхему. Итак, теперь у нас есть - (ключи для каждого отношения выделены жирным шрифтом)

R1={B,G,C}
R2={G,A}< br> R3={C,E}
R4={C,G}< br> R5={A,D}

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

S1 = {B,G,C}
S2 = {A,G}
S3 = {C ,E,G}
S4 = {A,D}

Это в 3NF. Теперь, чтобы проверить BCNF, мы проверяем, есть ли какие-либо из этих отношений (S1,S2,S3, S4) нарушают условия BCNF (т.е. для каждой функциональной зависимости X->Y левая часть (X) имеет быть суперключом). В этом случае ни один из них не нарушает BCNF, и, следовательно, он также разлагается на BCNF.

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

person Karup    schedule 18.12.2015

arrow_upward
1
arrow_downward

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

Выход: разложение R на набор отношений, все из которых находятся в НФБК.

Алгоритм: R ‹- R0 и S ‹- S0 Повторять до тех пор, пока R не окажется в НФБК. Если существует 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

person jitendra singh    schedule 07.04.2016