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.

{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}

## 0 comments :

## Post a Comment

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