Please visit, subscribe and share 10 Minutes Lectures in Computer Science
Showing posts with label Minimal cover. Show all posts
Showing posts with label Minimal cover. Show all posts

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. .
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 extraneous attribute?

Go back to Question/QUIZ page

Go back to

## Normalization – Find keys, find minimal cover, check for equivalent FDs

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

Go back to

## Cover set

Given 2 sets of functional dependencies F and G, the set of functional dependencies F is the cover of the set of functional dependencies G if every functional dependency in the set G can be inferred (derived) from the functional dependencies in the set F.

Example 1:
Let R (A, B, C, D, E, F) is a relation with set of functional dependencies F = { A BC, D DF } and G = { A B }.

Does F cover G?
If set of FDs of G can be inferred from F, then we would say that F covers G.
The FD A B of G can be inferred from the FD A BC of F.
No more functional dependencies are there in G. Hence, F covers G.

Does G cover F?
If set of FDs of F can be inferred from G, then we would say that G covers F.
No functional dependencies of F can be inferred from the FD A B of G.
Hence, G does not cover F.

Example 2:
Let R (A, B, C, D, E) be a relation with set of functional dependencies F = { A BC, A D, CD E } and G = { A BCE, A ABD, CD E }.

Does F cover G?
If set of FDs of G can be inferred from F, then we would say that F covers G.
The FD A BCE of G can be inferred from the FDs A BC, A D, and CD E of F. [here, A gives BCD. If you know C and D then E can be derived]
The FD A ABD of G can be inferred from the FDs A BC, and A D of F.
The FD CD E of G can be inferred from the FD CD E of F.
All the three FDs of G can be inferred from FDs of F. Hence, F covers G.

Does G cover F?
If set of FDs of F can be inferred from G, then we would say that G covers F.
The FD A BC of F can be inferred from the FD A BCE of G.
The FD A D of F can be inferred from the FD A ABD of G.
The FD CD E of F can be inferred from the FD CD E of G.
All the three FDs of F can be inferred from FDs of G. Hence, G covers F.

Similar topics

## 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...

data recovery