Showing posts with label Minimal cover. Show all posts
Showing posts with label Minimal cover. Show all posts

Monday, October 30, 2017

Minimal Cover (Canonical cover) Solved Exercises

Minimal cover solved exercises / Canonical cover solved exercises / Finding equivalent set of functional dependencies exercises / Finding extraneous attributes exercises / Eliminating redundant functional dependencies exercises

Exercises




Solved Exercises in DBMS

Solved exercises in DBMS / Solved exercises in all areas of DBMS / Solved exercises on ER Diagrams, Normalization, Query Processing, Transaction Processing, SQL, Relational algebra etc. / Solved exercises in DBMS with answers explained.


TOPICS




List of solved exercises in RDBMS

Solved exercises in Entity relationship modeling

solved problems in relational algebra

solved exercises in normalization in dbms

solved exercises in disk access and memory management in DBMS

solved exercises in transaction processing in DBMS

solved exercises in query processing in RDBMS

Important exercises with answers in RDBMS

Top interview questions and exercises in RDBMS with solutions

Tuesday, September 19, 2017

What are the properties of Functional dependencies in canonical cover

What are the properties of canonical cover in DBMS? List down the properties that are to be held by set of FDs in a minimal cover, Discuss about the properties of canonical cover 

Properties of functional dependencies in canonical cover (minimal cover)


Canonical cover of a set of functional dependencies F is mentioned as Fc.

A canonical cover Fc of a set of functional dependencies F has the following properties;

1. Canonical cover Fc is equivalent to F.
F logically implies all dependencies in Fc and Fc logically implies all dependencies in F. 

2. Any functional dependency in Fc cannot be redundant. Fc is minimal set of FDs.

If we remove any functional dependency from Fc, then Fc will no longer be equivalent to F. Removal of any FD from Fc eliminates property 1.

3. The functional dependencies in Fc do not contain redundant attributes on either side.

If X is a set of attributes and Y is another set of attributes, then X → Y is a functional dependency. If X → Y is part of Fc, then removal of any attributes on either side of the functional dependency X → Y result in loss of equivalency between Fc and F.

**************





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


Sunday, May 15, 2016

Find minimal cover of set of functional dependencies Exercise

Find minimal cover of set of functional dependencies example, Solved exercise - how to find minimal cover of F? Easy steps to find minimal cover of FDs, What is minimal cover?

Question:
6. Find the minimal cover of the set of functional dependencies given; {A → C, AB → C, C → DI, CD → I, EC → AB, EI → C}

Solution:
Minimal cover:
Definition 1:
A minimal cover of a set of FDs F is a minimal set of functional dependencies Fmin that is equivalent to F. There can be many such minimal covers for a set of functional dependencies F.
Definition 2:
A set of FDs F is minimum if F has as few FDs as any equivalent set of FDs.


Simple properties/steps of minimal cover:
1. Right Hand Side (RHS) of all FDs should be single attribute.
2. Remove extraneous attributes. [What is extraneous attribute? Refer here].
3. Eliminate redundant functional dependencies.

Let us apply these properties to F = {A → C, AB → C, C → DI, CD → I, EC → AB, EI → C}

1. Right Hand Side (RHS) of all FDs should be single attribute. So we write F as F1, as follows;
F1 = {A → C, AB → C, C → D, C → I, CD → I, EC → A, EC → B, EI → C}

2. Remove extraneous attributes.
Extraneous attribute is a redundant attribute on the LHS of the functional dependency. In the set of FDs, AB → C, CD → I, EC → A, EC → B, and EI → C have more than one attribute in the LHS. Hence, we check one of these LHS attributes are extraneous or not.
To check, we need to find the closure of each attribute on the LHS; [apply the closure finding algorithm – refer here]
(i) A+ = ACDI
(ii) B+ = B
(iii) C+ = CDI
(iv) D+ = D
(v) E+ = E
(vi) I+ = I
From (i), the closure of A included the attribute C. So, B is extraneous in AB → C, and B can be removed.
From (iii), the closure of C included the attribute I. So, D is extraneous in CD → I, and D can be removed.
No more extraneous attributes are found. Hence, we write F1 as F2 after removing extraneous attributes from F1 as follows;
F2 = {A → C, C → D, C → I, EC → A, EC → B, EI → C}

3. Eliminate redundant functional dependency.
Here, EI → C is redundant (C can be determined using other FD, in this case, A → C). Hence, the minimal cover Fc = {A → C, C → D, C → I, EC → A, EC → B}.

Hence, set of functional dependencies Fc is the minimal cover for the set F.




**************************


Similar topics

How to find closure of set of functional dependencies?

How to find closure of attributes?

How to find canonical cover for a set of functional dependencies?

How to find extraneous attribute?




Go back to Question/QUIZ page














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