1

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?

  • 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? – ypercubeᵀᴹ Apr 29 '16 at 10:12
  • @ypercubeᵀᴹ Yes, Indeed! Is it BCNF then? – Revolucion for Monica Apr 29 '16 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). – ypercubeᵀᴹ Apr 29 '16 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? – Revolucion for Monica Apr 29 '16 at 17:33
4

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.

| improve this answer | |
  • Thank you for your answer! But wy does UtilisateurID is not a key of UtilisateurID → Nom relation? Because it lacks AdresseEmail? – Revolucion for Monica May 1 '16 at 15:24
  • Furthermore if you took AdresseEmailas X why for R2, why do you still have UtilisateurID in R3? Shouldn't it be T – X+ + X? – Revolucion for Monica May 1 '16 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. – Renzo May 1 '16 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... – Revolucion for Monica May 2 '16 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). – Renzo May 2 '16 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.