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 F_min 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

TOPICS (Click to Navigate)

Pages

Thursday, May 12, 2016