Wednesday, November 16, 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

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

data recovery