Wednesday, 16 November 2016

Is the given decomposition is a lossless join decomposition?

Is the given decomposition a lossless join decomposition?


Question:

10. Assume a relation R(A, B, C, D, E) with set F of functional dependencies as follows;

F = {A BC, CD E, B D, E A}

If R is decomposed in to R1(A, B, C) and R2(A, D, E), which of the following holds?

(a) Decomposition is Loss-less Join Decomposition

(c) Decomposition is both (a) and (b)
(d) Decomposition is Lossy-Join Decomposition



Answer:


(a) Decomposition is Loss-less Join Decomposition

Discussion:



Is the given decomposition is loss-less?

YES

If either R1 R2 R1 is true or R1 R2 R2 is true for the given decomposition, then we would say that the decomposition is loss-less join decomposition.

What is R1 R2? – The common attribute(s) between R1 and R2.
In our case, R1 R2 is A. We have to check whether A can determine all attributes of R1 or all attributes of R2 uniquely using the given FDs.
From F we can determine A+ as follows using the closure finding algorithm;
Result = A
Result = ABC from A BC
Result = ABCD from B D
Result = ABCDE from CD E

From this, we would know that A is a candidate key for R.

A determines A, B, and C which is R1. So, R1 R2 R1 is true.
Hence, the given decomposition is loss-less join decomposition.

Is the given decomposition is dependency preserving?

NO

The above said decomposition of R into R1 and R2 is a dependency preserving decomposition if (F1 U F2)+ = F+, where F1 is set of FDs hold by R1, F2 is set of FDs hold by R2, and F is the set of FDs hold by R. (F1 U F2)+ is the closure of (F1 U F2), and F+ is the closure of F.

Step 1: for R1, the derivable non-trivial functional dependency is A BC. Hence, F1 = {A BC}
Step 1: for R1, the derivable non-trivial functional dependency is E A. Hence, F2 = {E A}
(F1 U F2)+ = {A BC, E A}
F+ = {A BC, CD E, B D, E A, E BC, A E}
A BC is there in F+, hence preserved.
E A is there in F+, hence preserved.
CD E, and B D are not there in F+, hence not preserved.
Hence, the decomposition is not dependency preserving.




         Previous Question                                                                                Next Question


No comments:

Post a Comment

Simple introduction to Naive Bayes classifier

Simple introduction to Naive Bayes classifier What is Naive Bayes Classifier? A Naive Bayes classifier is a probabilistic classifier ...