Friday, 15 April 2022

Minimal cover of relation

 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.

A minimal cover of a set of functional dependencies (FD) E is a minimal set of dependencies F that is equivalent to E.

The formal definition is: A set of FD F to be minimal if it satisfies the following conditions −

  • Every dependency in F has a single attribute for its right-hand side.

  • We cannot replace any dependency X->A in F with a dependency Y->A, where Y is a proper subset of X, and still have a set of dependencies that is equivalent to F.

  • We cannot remove any dependency from F and still have a set of dependencies that are equivalent to F.

Canonical cover is called minimal cover which is called the minimum set of FDs. A set of FD FC is called canonical cover of F if each FD in FC is a −

  • Simple FD.
  • Left reduced FD.
  • Non-redundant FD.

 Steps to find minimal cover:

1. Split FD's from RHS only

Example: if it given as A->BC then split it as A->B and A-C

2. Find redundant FD's and delete them

Example: if it is given as A->B , B-C, A->C then the FD A->C is  redundant because it is derived from other two FD's so delete it. Final FD's are A->B , B-C

3. Find the extraneous (redundant) attributes and delete them. It is present in LHS

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.

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}


Post a Comment

Note: only a member of this blog may post a comment.

Find Us On Facebook

Computer Basics


C Programming


Java Tutorial


Data Structures


MS Office


Database Management