Decomposition In Boyce-Codd Normal Form may lose relations?

Question

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

F = { UtilisateurID → Nom, Prenom
      UtilisateurID, ServeurMail → Login, Passwd;
      AdresseEmail → UtilisateurID;
      AdresseEmail → ServeurEmail;
} 

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}

E1: F¹={AdresseEmail  → ServeurEmail}

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

F²=(UtilisateurID  → Nom, Prenom

    AdresseEmail → UtilisateurID

   )

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?

Answer 1

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) ,
{ AdresseEmail → UtilisateurID
AdresseEmail → ServeurMail } >

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

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

Note that this decomposition preserves the functional dependencies.

Addition

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) 
R2(AdresseEmail 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)
R4(Login Passwd ServeurMail UtilisateurID)

Both relations are in BCNF, and the final decomposition is given by R2, R3, and R4.

Finally, note that sometimes the algorithm can produce different solutions, depending on the functional dependency chosen at each step.