Question

Suppose you are given a relation R with four attributes ABCD. For each of the following sets of FDs, assuming those are the only dependencies that hold for R, do the following: (a) Identify the candidate key(s) for R. (b) Identify the best normal form that R satisfies (1NF, 2NF, 3NF, or BCNF). (c) If R is not in BCNF, decompose it into a set of BCNF relations that preserve the dependencies.
1. C → D, C → A, B → C
2. B → C, D → A
3. ABC → D, D → A
4. A → B, BC → D, A → C
5. AB → C, AB → D, C → A, D → B

Answer 1

Solution :

1.

a). Candidate keys : $B$

b). R is in $2F$ but not $3NF$

c). C → $D$ and C → $A$, both causes violations of $BCNF$. The way to obtain the join preserving decomposition is to decompose $R$ into $AC, BC$ and CD.

2.

a). Candidate keys : $BD$

b). $R$ is in $1NF$ but not $2NF$.

c). Both B → $C$ and D → $A$ cause $BCNF$ violations. The decomposition : $AD$, $BC, BD$ is $BCNF$ and lossless and the join preserving.

3.

a). Candidate keys : $ABC, BCD$

b). R is in $3NF$ but not $BCNF$

c).$ABCD$ is not in $BCNF$ since D → $A$ and $D$ is not a key. But if we split up the $R$ as $AD,BCD$ therefore we cannot preserve dependency $ABC$ → D. So there is no $BCNF$ decomposition.

4.

a). Candidate keys : $A$

b). R is in $2NF$ but not $3NF$

c). BC → $D$ violates $BCNF$ since $BC$ does not contain the key. And we split up R as in $BCD, ABC$.

5.

a). Candidate keys : $AB, BC, CD, AD$

b). $R$ is in $3NF$ but not $BCNF$.

c). C → $A$ and D → $B$ both causes a violations. The decomposition into $AC,BCD$ but this will not preserve $AB$ → C and $AB$ → D, and $BCD$ is still not $BCNF$ because $D$ → $B$. So we need to decompose further into $AC,BD,CD$ However when we try to revive the lost functional dependencies by adding $ABC$ and $ABD$, we that these relations are not in $BCNF$ form. Therefore, there is no $BCNF$ decomposition.