Computing Minimal Cover of a given Functional Dependency

Computing Minimal Cover of a given Functional Dependency

Introduction

A canonical cover Fc for F is a set of dependencies such that F logically implies all dependencies in Fc, and Fc logically implies all dependencies in F. Furthermore, Fc must have the following properties:

1. No functional dependency in Fc contains an extraneous attribute.
2. Each left side of a functional dependency in Fc is unique. That is, there are no two dependencies 

A1->B

A2->C

such that A1=A2

NOTE

An attribute of a functional dependency is said to be extraneous if we can remove it without changing the closure of the set of functional dependencies.

The ALGORITHM

Consider a set of functional dependencies

F={A->BC, B->C, A->B, AB->C}

STEP 1:

Use rule of union to reduce the dependencies of F.

UNION RULE: Dependencies, like

W->Q1, W->Q2 etc. can be merged as

W->Q1Q2.

Applying step 1 to our problem, F will reduce into,

F1={A->BC, B->C, AB->C}

STEP 2:

Now compute the extraneous attribute. It can be computed as-

The extraneous attribute can be either on the left side of the dependency or on the right side. 

In order to check whether an attribute is extraneous. Perform the following operation.

Lets the attribute under investigation be X, if X belongs in dependency T->U, then

1. If X belongs to U, to check if X is extraneous consider the set F`=(F-{T->U}) union {T->(U-X)} and check if T->X can be inferred from F`. To do so, compute T+ (closure of T) under F`; if T+ includes X, then X is extraneous in U.
2. If X belongs to T, to check if X is extraneous, let S=T-{X}, and check if S->U can be inferred from F. To do so, compute S+ under F; if S+ includes all attributes in U, then X is extraneous in T.

Applying step 2 to our problem, F1 will be

Lets check whether A is extraneous or not.

Out of the three dependencies i.e.

A->BC

B->C

AB->C

we can check the extraneous of A on the dependency AB->C.

Since A belongs to AB (i.e. X belongs to T), thereby applying point 2.

Hence, S=AB-{A}

S={B}

S+(on F1)={BC}. 

Since S+ contains C ( i.e. all attributes of U), hence A is extraneous in AB->C. Hence A can be dropped from the dependency AB->C.

So our set of dependencies reduced to,

A->BC

B->C

A->C

STEP 3:

Go to step 1 with the new set of FD's and test extraneous attributes for remaining attributes too.

Applying step 3,

New FD's is

A->BC

B->C

Lets check whether B is extraneous or not.

It can be checked on the dependency A->BC.

Since B belongs to BC ( i.e. in U), so applying point 1.

F`={A->C, B->C}

computing A+ on F`.

A+={AC}

Since A+ does not includes B. Hence B is not extraneous. So our dependencies remains as-

A->BC

B->C

Lets check whether C is extraneous or not.

It can be checked on the dependency A->BC.

Since C belongs to BC ( i.e. in U), so applying point 1.

F`={A->B, B->C}

computing A+ on F`.

A+={ABC}

Since A+ contains C, hence C is extraneous. So, the dependencies reduces to

A->B

B->C.

Hence the minimal cover of the given F is

Fc={A->B, B->C}.