0

I am performing the BCNF decomposition for the relation R = (A, B, C, D, E), that has the set of functional dependencies AB -> C, CD -> A, C -> E, and C -> B.

After checking that the first dependency AB -> C violates the BCNF (by calculating the closure of AB), I split the original relation into two - R1 = (A, B, C) and R2 = (A, B, D, E).

At this point, the functional dependencies associated with R1 are AB -> C and C -> B, so I can see that R1 is in the BCNF. When it comes to R2, I cannot use any of the functional dependencies to verify if there are any violations to the BCNF, as all of them have the C attribute. How can I proceed if I do not have any functional dependencies to check?

1
  • hm .. it seems your general "approach" is flawed as AB->C , C->B and CD->A make it circular in my opinion ....which explains your problems when splitting the relations into 2 groups - but they aren't independent
    – eagle275
    Jan 15, 2020 at 10:30

1 Answer 1

2

When you decompose R(T) to find the BCNF, if the dependency X -> Y violates the BCNF, the decomposition that the classical algorithm requires is not R1(X) and R2(T-X), but R1(X+) and R2(T-(X+ - X)).

So the first decomposition, considering AB → C, should be:

R1(A, B, C, E) (since AB+ = ABCE)
R2(A, B, D) (= {ABCDE - (ABCE - AB))

In R1 the remaining dependencies are AB → C, C → E, C → B, while in R2 there are no (non-trivial) dependencies.

R1 is not in BCNF, since the two dependencies C → E, C → B violates that form (the only candidate keys are AB and AC). So it can be decomposed in R3(B, C, E), with dependencies C → E, C → B, and R4(A, C) (again without non-trivial dependencies).

So the final decomposition is:

R2 < (A B D) ,
{ } >

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

R4 < (A C) ,
{ } >

Note that the dependencies:

{ C D → A
A B → C }

are not preserved in this normalization.

Finally, note that if, during this process, you get a relation schema without (non-trivial) dependencies, this schema is already normalized, since the only candidate key is formed by all the attributes and there is no dependency that violates the BCNF.

5
  • Why are you doing the first decomposition into R1(A, B, C, E) and R2(A, B, D)? Shouldn't it be R1(A, B, C) and R2(A, B, D, E) since that for X->Y the decomposition should follow the rule R1(X,Y) and R2(X,<remaining attributes>)?
    – pn_
    Jan 15, 2020 at 11:57
  • @PedroN., the classical “analysis” algorithm for BCNF says that one should decompose with R1(X+) and R2(T-(X+ - X)). For instance, since AB+ (= A,B,C,E) then R1 should contain those four attributes. Are you following another algorithm? From which book?
    – Renzo
    Jan 15, 2020 at 12:17
  • Not sure if it is another algorithm but it is what I understand from one of the book references of the course that I am taking - "Database System Concepts" (Silberschatz, Korth, Sudarshan) - when it goes into BCNF: result := {R}; done := false; compute F+; while (not done) do if (there is a schema Ri in result that is not in BCNF) then begin let a → b be a nontrivial functional dependency that holds on Ri such that a → Ri is not in F+, and a ∩ b = ∅; result := (result − Ri ) ∪ (Ri − b) ∪ (a, b); end else done := true;
    – pn_
    Jan 15, 2020 at 12:49
  • You are right, in that book the algorithm is simplified. I found the description that I gave above in "Garcia-Molina, Hector. Database Systems: The Complete Book. 2nd ed. Upper Saddle River, N.J: Pearson Prentice Hall, 2009”, and in some research paper. The version that you cited can present some problem. For instance R1 is not in BCNF (since the key is AB, and C->B), so one should decompose further in R2(B C) and R3(A C), so also the dependency C->E is lost.
    – Renzo
    Jan 15, 2020 at 14:21
  • As final note, since, as in this case, the algorithms can lose the dependencies, from the practical point of view is better to use the 3NF since the decomposition in such normal form is guaranteed to preserve both data and dependencies.
    – Renzo
    Jan 15, 2020 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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