Find a minimal cover for each of the following a A BC B C A

Find a minimal cover for each of the following.

(a) { A BC, B C, AB D}

(b) {A C, AB C, C DI, CD I,EC AB, EI C}

Solution

Functional dependency: A functional dependency is a constraint between two sets of attributes in a relation. For a given relation R, if the set of attributes A 1 , · · · , A n, functionally determine the set of attributes B 1 , · · · , B n, then it means that if two tuples that have the same values for all the attributes A 1 , · · · , A n, then they must also have the same values for all the attributes B 1 , · · · , B n. This is written as A 1 , · · · , A n B 1 , · · · , B n.

Closure:Given a set of functional dependencies F, and a set of attributes X, the closure of X with respect to F, written XF+, is the set of all the attributes whose values are determined by the values of X because of F. Often, if F is understood, then the closure of X is written X +.

Minimal cover: A minimal cover or a canonical cover of a set of functional dependencies F is a minimum set of dependencies that is equivalent to F.A minimal set of dependencies is a set of dependencies with no redundancies.If sevral set of functional dependencies are qualified as minimal covers of F then we choose the mnimal set with smallest number of dependecies.

Steps for minimal cover:

1) Split FD\'s of functional dependency set F such that RHS of FD is a single attribute.

2) Identify the extraneous attribute of LHS of any FD and remove extraneous attribute.

3) Eliminate redundant FD\'s:Let X->Y is the FD of FD set F if (F-{X->Y})=F then X->Y is redundant FD,which can be removed from F.

Extraneous Attribute: An attribute of functional dependency is said to be an extraneous attribute if we can remove it without changing the closure set of FD\'s.If a FD XY->Z and X⁺=Y or Z in FD set F then Y is extraneous in FD XY->Z.

Finding Extraneous Attributes:

Let us consider a set of functional dependencies F and any functional dependency of the form . Assume that and are set of one or more attributes. [For example, A BC or AB CE etc.]
Case 1 (LHS): To find if an attribute A in is extraneous or not. That is, to test if an attribute of Left Hand Side of a functional dependency is Extraneous or not.
Step 1 : Find ({} – A)+ using the dependencies of F.
Step 2: If ({} – A)+ contains all the attributes of , then A is extraneous.

Case 2 (RHS): To find if an attribute A in is extraneous or not. That is, to test if an attribute of Right Hand Side of a functional dependency is Extraneous or not.
Step 1 : Find + using the dependencies in F’ where F’ = (F – { }) U { ( – A) }.
Step 2: If + contains A, then A is extraneous.

Answers:

a)  As we have seen the steps to fnd minimal cover,we apply those steps to find minimal cover for the given

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}

Therefore,the set of FDs F3 is the minimal cover of F

b) As we have seen the steps to fnd minimal cover,we apply those steps to find minimal cover for the given

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.

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:

(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 Functional dependencies in F2 is redundant. Hence, F2 is minimal cover.
Hence, set of functional dependencies F2 is the minimal cover for the set F.