Find the dependency preserving BCNF decomposition of the given relation

Find the dependency preserving BCNF decomposition of the given relation schema / Is the given decomposition is dependency preserving? / How to decompose a relation into BCNF with dependency preservation? / How to perform a dependency preserving decomposition? / Is the table in BCNF?

Question:

7. Assume a relation R(A, B, C, D, E) with the set of functional dependencies F = { A → B, BC → D } and the candidate key (ACE). The relation is not in BCNF. Which of the following is the dependency preserving decomposition for R into BCNF relations?

(a) R₁(B, C, D), R₂(A, B), R₃(A, C, E)

(b) R₁(A, B), R₂(A, C, D), R₃(A, C, E)

(c) R₁(A, B), R₂(A, C, D, E)

(d) All of the above

 

Answer:

(a) R₁(B, C, D), R₂(A, B), R₃(A, C, E)

• BCNF – In simpler terms, the Left Hand Side (LHS) of all the functional dependencies should be the key.

• Dependency preserving decomposition – If a relation R with set F of functional dependencies is decomposed into relations R₁, R₂, R₃, …, R_i then the closure of set of functional dependencies for these relations should satisfy the following; 
• (F₁ U F₂ U F₃ U … U F_i)⁺ = F⁺ 
• That is the closure of union of set of functional dependencies of relations R₁, R₂, …, R_i should be equal to the closure of set of functional dependencies F of R. In other words, all the functional dependencies in (F₁ U F₂ U F₃ U … U F_i)⁺ should be in F⁺ also.

Given: F = { A → B, BC → D }

Step 1: What is the candidate key for R?

A⁺ = AB

(BC)⁺ = BCD

E is not included in any of the functional dependencies, hence E should be in the left hand side and forms one of the key attributes.

(AE)⁺ = ABE

(BCE)⁺ = BCDE

(ACE)⁺ = ABCDE = R.

Hence, (ACE) is the candidate key for R.

Step 2: Which of the functional dependencies violate BCNF?

For the given table R, the following are the dependencies that violate the conditions for BCNF;

{ A → B, BC → D }

Because, the LHS of both FDs are not candidate keys.

Step 3: Break the relation using the violating FDs

Let us consider the FD BC → D and break (decompose) R using this functional dependency;

We create relation R₁ with the schema R₁(B, C, D). [all the attributes of functional dependency BC → D]

We create relation R₂ with the schema R₂(A, B, C, E). [the attributes for R₂ are derived by performing R – D, ie., {A, B, C, D, E} – {D}]

Step 4: R₁ is in BCNF?

The candidate key for R₁ is BC and the FD that holds in R₁ is BC → D. The LHS of the FD is the candidate key. Hence, R₁ is in BCNF.

Step 5: R₂ is in BCNF?

The candidate key for R₂ is ACE and the FD that holds in R₂ is A → B. The LHS of the FD is not the candidate key. Hence A → B violates the rule for BCNF.

Step 5.1: Break R₂ on FD A → B.

We create relation R₂₁(A, B) using A → B, the violating FD.

We create relation R₂₂(A, C, E) using R₂ – B.

Step 6: Is R₂₁ and R₂₂ are in BCNF?

The candidate key for R₂₁ is A and the LHS of A → B is A. Hence, R₂₁ is in BCNF.

The candidate key for R₂₂ is ACD and the FD holds in R₂₂ is trivial FD. Hence, R₂₂ is in BCNF.

Step 7: R into R₁, R₂₁, and R₂₂ is dependency preserving decomposition?

Let us consider the set of FDs of R, R₁, R₂₁, and R₂₂ as F, F₁, F₂₁, and F₂₂.

Apply the rule (F₁ U F₂ U F₃ U … U F_i)⁺ = F⁺.

(F₁ U F₂₁ U F₂₂)⁺ = F⁺

({BC → D} U {A → B} U {ACE → ACE})⁺ = ({ A → B, BC → D})⁺

All the FDs are found in decomposed relations. Hence, R into R₁(B, C, D), R₂₁(A, B), and R₂₂(A, C, E) is dependency preserving BCNF decompositions.

         Previous Question                                                                                Next Question