I am working with relation H that is detailed below:

H = {A,B,C,D}

It shows the following functional dependencies (FD[s]):

F = { A -> B, B -> C, {C,D} -> A}

The candidate keys are

{A,D}, {B,D}, {C,D}

I belive relation H is in 3NF.

I also believe there are two FD that prevent this relation from satisfying BCNF:

A -> B and B -> C

Then I have:

A -> B 
H1 = {A,B}  F1 = {A -> B} <- this is BCNF
H2 = {A,C,D} F2 = {A -> C, {C,D} -> A} <- this isnt' BCNF

B -> C
H11 = {B,C} F11 = {B -> C} <- this is BCNF
H12 = {A,B,D} F12 = {A -> B} <- this is in BCNF

The questions

I have partial information about this algorithm, so I am not sure about certain things:

  1. What should I do with H2? Just throw it away and say that H1, H11, H12 are decompositions of H to meet BCFN?

  2. Can this relation be converted to BCNF with functional dependency preservation? (I would say no! because it is impossible to derive the FD {C,D} -> A from F1 sum F11 sum F12. Can you confirm that?

  • 1
    Is H12 in BCNF? Doesn't look like it. You have the (derived) BD->A. – ypercubeᵀᴹ Feb 10 '17 at 17:02
  • That's right, what should i do in this situation? – Hadson Feb 10 '17 at 17:21

First, you assumption about the 3NF is correct.

Then, in the analysis algorithm to find the BNCF, when you start to remove a dependency X → Y since it violates the BCNF, you should put in the first relation H1 not only XY, but X+, while in the second relation you should have H2 = H - X+ + X.

So, in the first step, the two resulting relations are:

H1 = {A,B,C) with dependencies A → B and B → C and key `A`,
H2 = {A, D} (with no dependencies)

In H1 the dependency B → C violates the BCNF since B is not a superkey, and you can decompose it in:

H11 = {A, B} with the dependency A → B and key A
H12 = {B, C} with the dependency B → C and key B

So, at the end, the final decomposition is H11, H12 and H2. Note that this decomposition determines the loss of the dependency {C, D} → A, and this happens also if we start by considering first the dependency B → C (obtaining the same decomposition).

|improve this answer|||||
  • Can you explain why this is wrong X -> Y in F+ H1 = {X,Y} H2 = {H - Y} – Hadson Feb 10 '17 at 18:07
  • Is not really wrong, simply it does not follow the analysis algorithm, which is the algorithm presented in all the books on databases. In some sense, it is less effective that splitting the original relation in X+ and H - X+ + X. – Renzo Feb 10 '17 at 18:13
  • One more question, is it possible to get decomposition with loss if i start decomposition with one FD and without loss when i start with the other FD? – Hadson Feb 11 '17 at 14:22
  • 1
    Good question! Yes, it is possible. Try for instance this example: relation {A B C D E F}, dependencies AB → C, A → F, B → E, D → B. If you start with D → B, then A → F, and finally B → E, there is the loss of the dependency AB → C. If instead you start with AB → C, then D → B, B → E and finally A → F you get a decomposition that maintains all the dependencies. – Renzo Feb 11 '17 at 16:40

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.