Разложение отношения в BCNF

Question

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

R (A, C, B, D, E) с функциональными зависимостями: A -> B, C -> D

Как мне разложить это?

Я предпринял следующие шаги:

A+ = AB  
C+ = CD  
R1 = A+ = **AB**  
R2 = ACDE (since elements of C+ still exist, continue decomposing)  
R3 = C+ = **CD**  

R4 = ACE (в этом отношении нет закрытий FD)

Так что теперь я знаю, что ACE будет составлять целое отношение, но ответ для разложения: AB, CD, ACE.

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

Answer 1

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

1. Определите BCNF:
Чтобы отношение R находилось в BCNF, все функциональные зависимости (FD), которые хранятся в R, должны удовлетворять свойству того, что все определители X являются суперключами R. То есть, если X->Y выполняется в R, то X должен быть суперключем R находиться в BCNF.

В вашем случае может быть показано, что единственным подходящим ключом (минимальный суперключ) является ACE. Таким образом, оба FD: A->B и C->D нарушают BCNF, так как A и C не являются суперключами или R.

2. Разложить R в форму BCNF:
Если R отсутствует в BCNF, мы разлагаем R на набор отношений S, которые находятся в BCNF.
Это можно сделать с помощью очень простого алгоритма:

Initialize S = {R}
While S has a relation R' that is not in BCNF do:   
   Pick a FD: X->Y that holds in R' and violates BCNF
   Add the relation XY to S
   Update R' = R'-Y
Return S

В вашем случае итерационные шаги заключаются в следующем:

S = {ABCDE}       // Intialization S = {R}
S = {ACDE, AB}    // Pick FD: A->B which violates BCNF
S = {ACE, AB, CD} // Pick FD: C->D which violates BCNF
// Return S as all relations are in BCNF

Таким образом, R(A,B,C,D,E) раскладывается в набор отношений: R1(A,C,E), R2(A,B) и R3(C,D), который удовлетворяет BCNF.

Отметим также, что в этом случае функциональная зависимость сохраняется, но нормализация к BCNF не гарантирует этого.

Надеюсь, это поможет.

Answer 2

1NF -> 2NF -> 3NF -> BCNF

В соответствии с данным набором FD "ACE" образует ключ. Ясно, что R(A,B,C,D,E) не в 2NF. Разложение 2NF дает R1(A,B), R2(C,D) и R3(A,C,E). это разложение разложенных отношений в 3NF, а также в BCNF.