BCNF L'algorithme de décomposition ne fonctionne pas

Question

J'ai le problème suivant: R (ABCDEFG) et F = {AB-> CD, C-> EF, G-> A, G-> F, CE -> F}. Clairement, B & G devrait faire partie de la clé car ils ne font pas partie de l'ensemble dépendant. De plus, BG + = ABCDEFG, donc clé candidate. Clairement, AB-> CD viole BCNF. Mais quand je suis l'algorithme, je ne trouve aucune réponse. Probablement faire quelque chose de mal. Quelqu'un peut-il me montrer comment appliquer l'algorithme correctement pour atteindre la décomposition?

Merci d'avance.

Answer 1

D'abord, vous devez calculer une couverture canonique des dépendances. Dans ce cas, il est:

{ A B → C 
    A B → D 
    C → E 
    C → F 
    G → A 
    G → F } > 

Depuis la clé candidat (unique) est B G, aucune dépendance fonctionnelle satisfait la BNCF. Puis, à partir de toute dépendance fonctionnelle X → Y qui viole le BCNF, nous calculons la fermeture de X, X+, et de remplacer la relation originale R<T,F> avec deux relations, R1<X+> et R2<T - X+ + X>. Ainsi, chosing dans ce cas, la dépendance A B → C, nous remplaçons la relation originale avec:

R1 < (A B C D E F) , 
    { A B → C 
     A B → D 
     C → E 
     C → F} > 

et:

R2 < (A B G) , 
    { G → A } > 

Ensuite, nous vérifions chaque relation décomposée pour voir si elle satisfait la BCNF, sinon nous appliquons récursivement l'algorithme.

Dans ce cas, par exemple, dans R1 la clé est A B, si C -> E viole le BCNF, et nous remplacer R1 avec:

R3 < (C E F) , 
    { C → E 
     C → F } > 

et:

R4 < (A B C D) , 
    { A B → C 
     A B → D } > 

deux relations qui satisfont le BCNF.

Enfin, étant donné que R2 ne satisfait pas trop la BCNF (beacuse la clé est B G), nous décomposons R2 dans:

R5 < (A G) , 
    { G → A } > 

et:

R6 < (B G) , 
     { } > 

qui sont en BCNF.

Ainsi, la décomposition finale est constitué par les relations: R3, R4, R5 et R6. Nous pouvons également noter que la dépendance G → F sur la relation d'origine est perdue dans la décomposition.