Minimal Cover

#database #computerscience

A minimal cover is a simplified and reduced version of the given set of functional dependencies.
Since it is a reduced version, it is also called as Irreducible set.
It is also called as Canonical Cover.

Steps to Find Minimal Cover

1) Split the right-hand attributes of all FDs.
Example
A->XY => A->X, A->Y

2) Remove all redundant FDs.
Example
{ A->B, B->C, A->C }
Here A->C is redundant since it can already be achieved using the Transitivity Property.

3) Find the Extraneous attribute and remove it.
Example
AB->C, either A or B or none can be extraneous.
If A closure contains B then B is extraneous and it can be removed.
If B closure contains A then A is extraneous and it can be removed.

Example 1
Minimize {A->C, AC->D, E->H, E->AD}

Step 1: {A->C, AC->D, E->H, E->A, E->D}

Step 2: {A->C, AC->D, E->H, E->A}
Here Redundant FD : {E->D}

Step 3: {AC->D}
{A}+ = {A,C}
Therefore C is extraneous and is removed.
{A->D}

Minimal Cover = {A->C, A->D, E->H, E->A}

Example 2
Minimize {AB->C, D->E, AB->E, E->C}

Step 1: {AB->C, D->E, AB->E, E->C}

Step 2: {D->E, AB->E, E->C}
Here Redundant FD = {AB->C}

Step 3: {AB->E}
{A}+ = {A}
{B}+ = {B}
There is no extraneous attribute.

Therefore, Minimal cover = {D->E, AB->E, E->C}