Please visit, subscribe and share 10 Minutes Lectures in Computer Science

Wednesday, 2 November 2016

Eliminate the redundant functional dependencies to find minimal cover

Find the functional dependencies that are redundant in a given set of FDs / Eliminate the redundant functional dependencies to find minimal cover / Eliminating unnecessary FDs to find canonical cover in normalization process


Question:

9. Let R(A, B, C) be a relation with the following set F of functional dependencies;
F = { A → B, B → A, A → C, C → A, B → C }
If we would like to find the minimal cover of F, then which of the following redundancies should be eliminated? ;
(a) B → A and A → C
(b) B → C
(c) Either (a) or (b)
(d) F is already minimal


Answer:


(c) Either (a) or (b)
Note: There can be more than one minimal cover for a set of functional dependencies.

Steps to find the minimal cover;
1. Ensure singleton attribute on the right hand side of each functional dependency.
2. Remove extraneous (redundant) attribute from the left hand side of each functional dependency.
3. Remove redundant functional dependency if any.

In our case, the functional dependencies given are already satisfying the first two rules.
According to rule 1, if we have any FDs with more than one attribute on the Right Hand Side, that FD should be decomposed using decomposition rule. We don’t have such FDs.
According to rule 2, if we have any FDs that have more than one attribute on the Left Hand Side (determiner), that FD must be checked for partial dependency. We don’t have such FDs.
Hence, the given set satisfies both rules.
For the third one we need to check.
Given : F = { A → B, B → A, A → C, C → A, B → C }
For the first FD A → B find A+ by hiding the FD A → B. A+ = AC which does not include B in it. Hence, A → B is not redundant.

For the second FD B → A find B+ by hiding the FD B → A.  B+ = ABC which includes A in it. Hence, B → A is redundant. We have to remove it immediately.

Now with the removal of B → A, our F becomes,
F = { A → B, A → C, C → A, B → C }
Find A+ by hiding A → C. A+ = ABC which includes C. Hence A → C is redundant and remove it immediately from F.

After removal of A → C, F becomes,
F = { A → B, C → A, B → C }
Find C+ by hiding C → A. C+ = C and this does not include A in the result. Hence, C → A is not redundant.

Finally find B+ by hiding B → C. B+ = B. Hence, B → C is mandatory.

We don’t have any more FDs. Our final set of functional dependencies are minimal after the removal of FDs B → A and A → C.
Hence, the minimal cover of F is as follows;
Fc = { A → B, C → A, B → C }
[Work out for the option B → C. While applying the above said procedure, start with the FD B → C. You will get the Fc as { A → B, B → A, A → C, C → A }]




         Previous Question                                                                                Next Question


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