Advanced Database Management System - Tutorials and Notes: Eliminate the redundant functional dependencies to find minimal cover

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


2 comments:

  1. Give an example of intraquery plus independent operation parallelism, explaining its operations ??. Please answer my question

    ReplyDelete
    Replies
    1. Intra-query parallelism is executing a query in parallel. For example, 'SELECT * FROM Emp ORDER BY Name'. This query involves comparison of each record value with the other. If we divide the data that are to be examined into multiple processors, each processor can perform the ORDER operation(sorting) in parallel and we can get answer quickly. Please refer here for Intraquery parallelism - https://exploredatabase.blogspot.in/2014/08/pipelined-parallelism-and-independent-parallelism.html
      and Independent parallelism here - https://exploredatabase.blogspot.in/2014/08/pipelined-parallelism-and-independent-parallelism.html

      Delete

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