Advanced Database Management System - Tutorials and Notes: Find the dependency preserving BCNF decomposition of the given relation

Tuesday, 25 October 2016

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) R1(B, C, D), R2(A, B), R3(A, C, E)
(b) R1(A, B), R2(A, C, D), R3(A, C, E)
(c) R1(A, B), R2(A, C, D, E)
(d) All of the above
 


Answer:

(a) R1(B, C, D), R2(A, B), R3(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 R1, R2, R3, …, Ri then the closure of set of functional dependencies for these relations should satisfy the following; 
    • (F1 U F2 U F3 U … U Fi)+ = F+ 
    • That is the closure of union of set of functional dependencies of relations R1, R2, …, Ri should be equal to the closure of set of functional dependencies F of R. In other words, all the functional dependencies in (F1 U F2 U F3 U … U Fi)+ 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 R1 with the schema R1(B, C, D). [all the attributes of functional dependency BC D]
We create relation R2 with the schema R2(A, B, C, E). [the attributes for R2 are derived by performing R – D, ie., {A, B, C, D, E} – {D}]

Step 4: R1 is in BCNF?
The candidate key for R1 is BC and the FD that holds in R1 is BC D. The LHS of the FD is the candidate key. Hence, R1 is in BCNF.

Step 5: R2 is in BCNF?
The candidate key for R2 is ACE and the FD that holds in R2 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 R2 on FD A B.
We create relation R21(A, B) using A B, the violating FD.
We create relation R22(A, C, E) using R2 – B.

Step 6: Is R21 and R22 are in BCNF?
The candidate key for R21 is A and the LHS of A B is A. Hence, R21 is in BCNF.
The candidate key for R22 is ACD and the FD holds in R22 is trivial FD. Hence, R22 is in BCNF.

Step 7: R into R1, R21, and R22 is dependency preserving decomposition?
Let us consider the set of FDs of R, R1, R21, and R22 as F, F1, F21, and F22.
Apply the rule (F1 U F2 U F3 U … U Fi)+ = F+.
(F1 U F21 U F22)+ = F+
({BC D} U {A B} U {ACE ACE})+ = ({ A B, BC D})+

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




         Previous Question                                                                                Next Question


No comments:

Post a comment

Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents