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

Saturday, 24 February 2018

Find minimal cover/canonical cover in a set of FDs

Find minimal cover/canonical cover in a set of given functional dependencies


Question:
For a relation schema R = (A, B, C, D, E), consider the following set of functional dependencies;
F = {A BC, CD E, B D, E A}
Using the functional dependencies compute the canonical cover Fc.

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.


Follow these steps to find the canonical (minimal) cover;
1. Decompose each functional dependency in F to have singleton (single) attribute on the Right Hand Side (RHS).
2. Remove extraneous (redundant) attributes from Left Hand Side of each functional dependency.
[What is extraneous attribute? Refer here].
3. Find and eliminate redundant functional dependencies.

Let us apply the above said properties to F;
F = {A BC, CD E, B D, E A}

1. RHS of all functional dependencies should be singleton. To achieve this we decompose each functional dependency that has two or more attributes in their RHS. We get the following set of functional dependencies F1;
F1 = {A B, A C, CD E, B D, E A}

2. Remove extraneous (redundant) attributes. This is applicable only for those functional dependencies that have two or more attributes on its LHS.
We need to check whether or not an attribute/set of attributes of LHS of a functional dependency is redundant or not. For checking this, we have to find the closure of each individual LHS attribute of each FD that has two or more LHS attributes.
With this property we have only one FD, CD E. We need to check whether C alone or E alone can find E uniquely.
C+ = C by reflexivity rule
D+ = D by reflexivity rule
From this we found that either C or D alone cannot determine the value of E. Hence, the FD CD E does not have any extraneous attributes.
Hence, our F1 is as follows;
F1 = {A B, A C, CD E, B D, E A}

3. Eliminate redundant functional dependencies.
To find redundant FDs, we have to find whether the RHS of a FD can be determined using other FDs.
(i) Let us check first for FD, A B. To proceed, we forget , A B from F, and use only the remaining FDs A C, CD E, B D, E A of F. That is our F becomes F1 = {A C, CD E, B D, E A}
No FD have B on RHS. Hence, A B is not redundant.
(ii) Now check for A → C. can we find C using following FDs?
F1 = {A B, CD E, B D, E A}
A+ = ABD
B+ = BD
We are not able to determine C using F1. Hence, A C is not redundant.
If we repeat this for each FD in F, we found that none of them are redundant.

Hence our Fc is as follows;
Fc = {A → BC, CD → E, B → D, E → A} which is same as F in the question.

***********


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




find canonical cover of F
what is minimal cover? how to find minimal cover
minimal cover solved exercise
find extraneous attributes
 





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














Thursday, 12 May 2016

Find minimal cover of set of functional dependencies

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:

5. Find the minimal cover of the set of functional dependencies given; {A → BC, B → C, AB → D}


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 → BC, B → C, AB → D}
1. Right Hand Side (RHS) of all FDs should be single attribute. So we write F as F1, as follows;
F1 = {A → B, A → C, B → C, AB → D}
2. Remove extraneous attributes.
Extraneous attribute is a redundant attribute on the LHS of the functional dependency. In the set of FDs, on AB → D has more than one attribute in the LHS. Hence, we check one of A and B is extraneous or not.
First we check whether A is extraneous or not. To do that, we need to find the closure of the remaining attribute B with respect to F1.
B+ = BC.
This does not include D, so A is not extraneous.
Now we check whether B is extraneous or not. To do that, we need to find the closure of the remaining attribute A with respect to F1.
A+ = ABCD.
This includes D, so B is extraneous, ie., we can identify D without B on the LHS.
Now, we can write the new set of FDs, F2 as follows;
F2 = {A → B, A → C, B → C, A → D}
3. Eliminate redundant functional dependency.
If A → B, and B → C, then A → C is true (according to transitive rule). Hence, the FD A → C is redundant. We can eliminate this and we get final set of FDs F3 as follows;
F3 = {A → B, B → C, A → D}

The set of FDs F3 is the minimal cover of 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











SQL exercises for beginners one

SQL Exercises for Beginners / Simple SQL Exercises with Answers / Solved SQL exercises / SQL solved exercises with simple conditions / So...