# Decomposition In Boyce-Codd Normal Form may lose relations?

Let be the following Realtion `R={UtilisateurID, Nom, Prenom, AdresseEmail, Login, Passwd, ServeurMail}` with the functional dependencies:

``````F = { UtilisateurID → Nom, Prenom
}
``````

What are all minimal keys?

I said that it was `K = { AdresseEmail }` as far it gived every others.

In order to put it BCNF I had the following algorithm

``````We take X→A from F

We create R¹(X,A)

F¹={X → A} R¹ BCNF

R²=R-{A}

E¹:F²=FD from F except those that affect A.

E²: IF R² is BCNF → END

ELSE We decompose R2 returning to E¹
``````

So I did:

R isn't BCNF because no FD looks like `key → attribute ¬key`

``````R¹={AdresseEmail, ServeurEmail}

F²=(UtilisateurID  → Nom, Prenom

)
``````

So my BCNF decomposition would actually be:

`R¹=(AdresseEmail, ServeurMail)` and

``````R²=(UtilisateurID, Nom, Prenom, AdresseEmail, Login, Passwd).
``````

But we lost `AdresseMail → ServeurEmail`

It isn't trivial, X is a (sur)key and A hasn't key attributes therefore it is BCNF.

Is my decomposition right? Did I did a mistake when designing the key?

• Your algorithm says that `R²=R-{A}`. Isn't `A = ServeurEmail` in the application of the algorithm? Why was `UtilisateurID` removed from R2 and not `ServeurEmail`? Apr 29, 2016 at 10:12
• @ypercubeᵀᴹ Yes, Indeed! Is it BCNF then? Apr 29, 2016 at 12:59
• It doesn't look like a correct algorithm. or you have missed some details. Can you always split - according to your algorithm - a relation to `(A,X)` and `R-{A}`? Beacuse you removed the `UtilisateurID, ServeurMail → Login, Passwd` FDs this way (after the last edit). Apr 29, 2016 at 13:05
• @ypercubeᵀᴹ Yes, I removed such a relation because we no longer have `ServeurMail` in R2 to let the DF `UtilisateurID, ServeurMail → Login, Passwd`, but I added `AdresseEmail → UtilisateurID` which I forget. Therfore it doesn't seems BCNF enven if my algorithm doesn't seems to be very accurate... Do you have one better if this one isn't the best? Apr 29, 2016 at 17:33

Your decomposition is not correct, since in R2 you still have dependencies that violates the BCNF, for instance `UtilisateurID → Nom` (`UtilisateurID` is not a key of that relation).

The problem is that your algorithm is not correct. When you find a dependency `X → A` that violates the BCNF, you should decompose a relation in two relations, the first with X+, not XA, and the second one with T – X+ + X. Then you should repeat the algorithm, if you find in one of the two decomposed relation some other dependency that violates the BCNF.

So, in your example, a correct decomposition is:

``````R2 < (AdresseEmail ServeurMail UtilisateurID) ,

R3 < (Nom Prenom UtilisateurID) ,
{ UtilisateurID → Nom
UtilisateurID → Prenom } >

R4 < (Login Passwd ServeurMail UtilisateurID) ,
ServeurMail UtilisateurID → Passwd } >
``````

Note that this decomposition preserves the functional dependencies.

How the decomposition is obtained? Starting from the original relation:

``````R(AdresseEmail Login Nom Passwd Prenom ServeurMail UtilisateurID)
``````

let's consider a dependency that does violates the BCNF, for instance:

``````ServeurMail UtilisateurID → Login
``````

the closure of `ServeurMail UtilisateurID` is `(Login Nom Passwd Prenom ServeurMail UtilisateurID`, so we decompone initially in two relations:

``````R1(Login Nom Passwd Prenom ServeurMail UtilisateurID)
``````

R1 is not in BCNF, since the key is `ServeurMail UtilisateurID`, so for instance the dependency `UtilisateurID → Nom` violates the normal form. Applying the algorithm, R1 is decomposed in:

``````R3(Nom Prenom UtilisateurID)
• Thank you for your answer! But wy does `UtilisateurID` is not a key of `UtilisateurID → Nom` relation? Because it lacks `AdresseEmail`? May 1, 2016 at 15:24
• Furthermore if you took `AdresseEmail`as `X` why for `R2`, why do you still have `UtilisateurID` in R3? Shouldn't it be `T – X+ + X`? May 1, 2016 at 15:30
• @Marine1, I was saying that `UtilisateurID` is not a key for the relation `R²=(UtilisateurID, Nom, Prenom, AdresseEmail, Login, Passwd)` of your decomposition. Of course `UtilisateurID` would be a key of a relation `(UtilisateurID, Nom)`. For the explanation of the decomposition, I am changing the answer. May 1, 2016 at 19:33
• Okay! So with your example, X=`ServeurMail UtilisateurID`, `Login` isn't a key attribute. Then you decomposed it in `X+` and `T – X+ + X`. --- I agree that `UtilisateurID → Nom` violates BCNF as far as the Key of R1 is `UID ServeurMail` but isn't it `UID → Nom, Prenom`? Is it important to notice it? --- Therefore you decomposed in `R3` and `R4` and said that both were BCNF. Yet, only R4 has the key `ServeurMail`... and `X →A` is BCNF iif `X` is a (super)key and `A` isn't a key attribute... May 2, 2016 at 8:28
• "but isn't it `UID → Nom, Prenom`?": yes, and since `UID` is not a (super)key there is the violation of BCNF. “...and `X →A` is BCNF iif `X` is a (super)key and `A` isn't a key attribute”: you are confusing BCNF with 3NF: in the first every determinant must be a superkey, while the second, which is more “tolerant”, allow dependencies in which the determinant is not a superkey, but the determinate is a prime attribute (that is, part of any key). May 2, 2016 at 9:10