Decompose this relation into BCNF

Question

Today, I'm reading about BCNF decomposition algorithm. It says that:

BCNF Decomposition Algorithm

Input: a relation R0 with a set of functional dependencies S0

Output: a decomposition of R0 into a collection of relations, all of which are in BCNF

Method: R=R0, S=S0

1. Check whether R is in BCNF. If so, nothing to do, return {R}
2. If there are BCNF violation, let one be X→Y
3. Compute X+
4. Choose R1=X+, and let R2 have attributes X and those attributes of R that are not in X+
5. Compute the sets of FD’s for R1 and R2, let these S1, S2
6. Recursively decompose R1, R2 using this algorithm. Return the union of the result of these compositions

I'm trying to apply that algorithm to decompose this relation:

R(A, B, C, D)
𝑆={AB→C,C→D,D→A}

As you can see, the key is {AB}, and 2 violations are C→D,D→A.Then:

1. Compute {𝐶}+ = {𝐶,𝐷,𝐴}
2. Decompose R into R1(C, D, A) and R2(B, C).
3. In R1, C is the key, so D→Ais a violation.
4. Compute {D}+ = {D,A}
5. Decompose R1(C, D, A) into R3(C, D) and R4(D, A)
6. The final result is: R2(B, C), R3(C, D), R4(D, A)

My first question is: is it correct?

I feel that we can decompose R into 2 relations which are (A, B, C) and (C, D). They are also in BCNF. How do we decompose R into that 2 relations? Which algorithm? Which way is better?

Thanks for your help.

Answer 1

First, let's note that in this case there are three keys, not only one:

AB
BD
BC

This means that all the attributes are primes, so the relation is by definition already in Third Normal Form.

For the BCNF, you have described the “analysis algorithm”, which is the algorithm presented in every good book on databases. But, with this example, you have also discovered that in normalizing, you can have different results, that can depend for instance on the order in which the dependencies that violates the normal form are chosen (not in this case, but possible in other cases with this same algorithm), or by using a different algorithm (there are others, not interesting from a practical point of view).

In your example, the second decomposition, which is in BCNF as you correctly stated, cannot be produced by the analysis algorithm: there is nothing wrong about it, in general there is no guarantee that this algorithm will produce the “best” decomposition (for instance a decomposition with a minimum number of relations), and, if this is an exercise, you have done it correctly!

What instead is interesting to note, also from a practical point of view, is if the decomposition satisfies all the important properties, i.e. if it preserves the dependencies of the original schema (since the decomposition produced by the algorithm is instead guarantee to be always a lossless decomposition).

And you can see that both the decompositions fail under this aspect. The decomposition in R2(B, C), R3(C, D), R4(D, A) does not preserve the dependency A B → C, while the decomposition R1(A, B, C), R2(C, D) does not preserve the dependency D → A. This means that in practice both of them reduce the redundancies and other anomalies of the data, at the expense of losing an important contraint over them.

So, knowing that the relation is already in 3NF, one could be satisfied by this result and leave the relation in this form. This means the preservation of the dependencies, together with a limited amount of redundancy, which in practice can be tolerated.