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. [How to find minimal cover? – Refer here].

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

Go back to Online Quizzes home page

Normalize the table, find keys, find minimal cover - Solved exercise

Normalization Quiz - Find the keys, candidate keys of a relational table, find the minimal cover of set of functional dependencies, check whether two sets of FDs are equivalent

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

 

1. Let F = {A → B, AB → E, BG → E, CD → I, E → C}. The closures, A+, (AE)+ and (ADE)+ will be ________.
(a) ABCE, ABDE, ABCDEI	(b) ABCE, ABCE, ABCDEI
(c) ABDE, ABCE, ABCDE	(d) ABCE, ABDE, ABCDI
Solution: Visit for detailed answer here.
2. Let F = {A → B, A → C, BC → D}. Can A determine D uniquely?
(a) Yes	(b) No
Solution: Visit for detailed answer here.
3. Let F = {AB → D, B → C, BC → D}. Can AC determine D uniquely?
(a) Yes	(b) No
Solution: Visit for detailed answer here.
4. Let F1 = {A → C, AC → D, E → AD} and F2 = {A → CD, E → AH}. Are F1 and F2 are equivalent?
(a) Equivalent	(b) Not Equivalent
Solution: Visit for detailed answer here.
5. Find the minimal cover of the set of functional dependencies given; {A → BC, B → C, AB → D}
(a) {A → C, B → C, AB → D}	(b) {A → C, B → C, B → D}
(c) {A → B, B → C, A → D}	(d) {A → BC, B → C, A → D}
Solution: Visit for detailed answer here.
6. Find the minimal cover of the set of functional dependencies given; {A → C, AB → C, C → DI, CD → I, EC → AB, EI → C}
(a) {A → C, C → DI, C → I, E → A, EI → C}	(b) {A → C, C → D, C → I, EC → A, EC → B}
(c) {B → C, C → DI, D → I, E → AB, EI → C}	(d) {A → C, C → DI, CD → I, I → C}
Solution: Visit for detailed answer here.
7. Consider a relation R with set of functional dependencies F as follows; {A → B, C → D, AC → E, D → F}. How many keys does R have and what are they?
(a) 1, {(AC)}	(b) 2, {(AC), (AD)}
(c) 3, {(AC), (BC), (ABD)}	(d) 2, {(AC), (ABD)}
Solution: Visit for detailed answer here.
8. Consider a relation R(A, B, C, D, E) with FDs AB → C, CD → E, C → A, C → D, D → B. What are the keys of R?
(a) AB, AC, D	(b) AC, BD
(c) AC, AD	(d) AB, AD, C
Solution: Visit for detailed answer here.
9. Consider a relation R(A, B, C, D, E) with FDs AB → C, C → A, C → BD, D → E. What are the keys of R? Decompose R into 3NF relations.
(a) {C}, R1(ABCD), R2(DE)	(b) {BD, AB}, R1(ABCD), R2(DE)
(c) {AB, C}, R1(ABCD), R2(DE)	(d) {BD}, R1(ABC), R2(CDE)
Solution: Visit for detailed answer here.
10. Consider a relation with schema R(A, B, C, D) with functional dependencies, BC → A, AD → B, CD → B, AC → D. Find all the candidate keys of R.
(a) AC, BC, CD	(b) AC, BC
(c) AC, AD	(d) BC, CD, A
Solution: Visit for detailed answer here.

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

Go back to Online Quizzes home page

Covers for functional dependencies - what is cover set

Cover set for functional dependencies - What is cover set? - What are the steps to find a cover set? - How would we say that a set of functional dependencies covers another set of functional dependencies? - Given 2 sets of functional dependencies F1 and F2, how to find F1 covers F2 or F2 covers F1? - Finding cover set of a functional dependency set

Covers for functional dependencies

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

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?