Décomposer une relation en BCNF

Question

Je n'arrive pas à établir quand une relation est dans Boyce-Codd Normal Form et comment décomposer l'information BCNF si ce n'est pas le cas. Compte tenu de cet exemple:

R (A, C, B, D, E) avec des dépendances fonctionnelles: A -> B, C -> D

Comment puis-je faire pour le décomposer?

Les étapes que j'ai prises sont:

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

R4 = ACE (pas de fermeture de FD résident dans cette relation)

Alors maintenant, je sais que ACE composera la relation ensemble, mais la réponse à la décomposition est: AB, CD, ACE. Je suppose que je suis aux prises avec la façon de décomposer correctement une relation en forme BCNF et comment savoir quand vous avez terminé. J'apprécierais vraiment n'importe qui qui peut me guider à travers leur processus de pensée en résolvant ces problèmes. Merci!

Answer 1

Bien que la question soit ancienne, les autres questions/réponses ne semblent pas fournir une réponse générale étape par étape très claire sur la détermination et la décomposition des relations avec BCNF.

1. Déterminer BCNF:
Pour relation R soit en BCNF, toutes les dépendances fonctionnelles (fds) qui détiennent en R doivent satisfaire la propriété que les déterminants X sont tous de R. à savoir super-clés si X- > Y tient dans R, alors X doit être une super-clé de R pour être dans BCNF.

Dans votre cas, il est possible de montrer que la seule clé candidate (superkey minimale) est ACE. Ainsi, les deux IFD: A-> B et C> D violent BCNF à la fois A et C ne sont pas super-clés ou R.

2. Décomposer R en forme de BCNF:
Si R ne soit pas en BCNF , nous décomposons R en un ensemble de relations S qui sont dans BCNF.
Ceci peut être accompli avec un algorithme très simple:

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 

Dans votre cas, les étapes itératives sont les suivantes:

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 

Ainsi R (A, B, C, D, E) est décomposé en un ensemble de relations: R1 (A, C, E), R2 (A, B) et R3 (C, D) qui vérifie BCNF.

Notez également que dans ce cas, la dépendance fonctionnelle est préservée mais la normalisation à BCNF ne le garantit pas.

J'espère que cela aide.

Answer 2

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

Selon FD ensemble donné des formes "ACE" la touche. Clairement R (A, B, C, D, E) n'est pas dans 2NF. La décomposition par 2NF donne R1 (A, B), R2 (C, D) et R3 (A, C, E). ces décompositions de décomposition sont en 3NF et également en BCNF.