Advanced Database Management System - Tutorials and Notes: Find minimal cover of set of functional dependencies Exercise

Search Engine

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

Sunday, 15 May 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.
None of the FDs in F2 is redundant. Hence, F2 is minimal cover.

Hence, set of functional dependencies F2 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














4 comments:

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