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
- Check whether R is in BCNF. If so, nothing to do, return {R}
- If there are BCNF violation, let one be X→Y
- Compute X+
- Choose R1=X+, and let R2 have attributes X and those attributes of R that are not in X+
- Compute the sets of FD’s for R1 and R2, let these S1, S2
- 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:
- Compute
{𝐶}+ = {𝐶,𝐷,𝐴}
- Decompose
R
intoR1(C, D, A)
andR2(B, C)
. - In
R1
,C
is the key, soD→A
is a violation. - Compute
{D}+ = {D,A}
- Decompose
R1(C, D, A)
intoR3(C, D)
andR4(D, A)
- 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.