Tag: canonical cover of functional dependencies

Canonical Cover in DBMS

Database Management System

Canonical Cover in DBMS-

 

Before you go through this article, make sure that you have gone through the previous article on Functional Dependency in DBMS.

 

In DBMS,

  • A canonical 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.

 

Characteristics-

 

  • Canonical cover is free from all the extraneous functional dependencies.
  • The closure of canonical cover is same as that of the given set of functional dependencies.
  • Canonical cover is not unique and may be more than one for a given set of functional dependencies.

 

Need-

 

  • Working with the set containing extraneous functional dependencies increases the computation time.
  • Therefore, the given set is reduced by eliminating the useless functional dependencies.
  • This reduces the computation time and working with the irreducible set becomes easier.

 

Steps To Find Canonical Cover-

 

Step-01:

 

Write the given set of functional dependencies in such a way that each functional dependency contains exactly one attribute on its right side.

 

Example-

 

The functional dependency X → YZ will be written as-

X → Y

X → Z

 

Step-02:

 

  • Consider each functional dependency one by one from the set obtained in Step-01.
  • Determine whether it is essential or non-essential.

 

To determine whether a functional dependency is essential or not, compute the closure of its left side-

  • Once by considering that the particular functional dependency is present in the set
  • Once by considering that the particular functional dependency is not present in the set

 

Then following two cases are possible-

 

Case-01: Results Come Out to be Same-

 

If results come out to be same,

  • It means that the presence or absence of that functional dependency does not create any difference.
  • Thus, it is non-essential.
  • Eliminate that functional dependency from the set.

 

NOTE-

 

  • Eliminate the non-essential functional dependency from the set as soon as it is discovered.
  • Do not consider it while checking the essentiality of other functional dependencies.

 

Case-01: Results Come Out to be Different-

 

If results come out to be different,

  • It means that the presence or absence of that functional dependency creates a difference.
  • Thus, it is essential.
  • Do not eliminate that functional dependency from the set.
  • Mark that functional dependency as essential.

 

Step-03:

 

  • Consider the newly obtained set of functional dependencies after performing Step-02.
  • Check if there is any functional dependency that contains more than one attribute on its left side.

 

Then following two cases are possible-

 

Case-01: No-

 

  • There exists no functional dependency containing more than one attribute on its left side.
  • In this case, the set obtained in Step-02 is the canonical cover.

 

Case-01: Yes-

 

  • There exists at least one functional dependency containing more than one attribute on its left side.
  • In this case, consider all such functional dependencies one by one.
  • Check if their left side can be reduced.

 

Use the following steps to perform a check-

  • Consider a functional dependency.
  • Compute the closure of all the possible subsets of the left side of that functional dependency.
  • If any of the subsets produce the same closure result as produced by the entire left side, then replace the left side with that subset.

After this step is complete, the set obtained is the canonical cover.

 

PRACTICE PROBLEM BASED ON FINDING CANONICAL COVER-

 

Problem-

 

The following functional dependencies hold true for the relational scheme R ( W , X , Y , Z ) –

X → W

WZ → XY

Y → WXZ

Write the irreducible equivalent for this set of functional dependencies.

 

Solution-

 

Step-01:

 

Write all the functional dependencies such that each contains exactly one attribute on its right side-

X → W

WZ → X

WZ → Y

Y → W

Y → X

Y → Z

 

Step-02:

 

Check the essentiality of each functional dependency one by one.

 

For X → W:

 

  • Considering X → W, (X)+ = { X , W }
  • Ignoring X → W, (X)+ = { X }

 

Now,

  • Clearly, the two results are different.
  • Thus, we conclude that X → W is essential and can not be eliminated.

 

For WZ → X:

 

  • Considering WZ → X, (WZ)+ = { W , X , Y , Z }
  • Ignoring WZ → X, (WZ)+ = { W , X , Y , Z }

 

Now,

  • Clearly, the two results are same.
  • Thus, we conclude that WZ → X is non-essential and can be eliminated.

 

Eliminating WZ → X, our set of functional dependencies reduces to-

X → W

WZ → Y

Y → W

Y → X

Y → Z

Now, we will consider this reduced set in further checks.

 

For WZ → Y:

 

  • Considering WZ → Y, (WZ)+ = { W , X , Y , Z }
  • Ignoring WZ → Y, (WZ)+ = { W , Z }

 

Now,

  • Clearly, the two results are different.
  • Thus, we conclude that WZ → Y is essential and can not be eliminated.

 

For Y → W:

 

  • Considering Y → W, (Y)+ = { W , X , Y , Z }
  • Ignoring Y → W, (Y)+ = { W , X , Y , Z }

 

Now,

  • Clearly, the two results are same.
  • Thus, we conclude that Y → W is non-essential and can be eliminated.

 

Eliminating Y → W, our set of functional dependencies reduces to-

X → W

WZ → Y

Y → X

Y → Z

 

For Y → X:

 

  • Considering Y → X, (Y)+ = { W , X , Y , Z }
  • Ignoring Y → X, (Y)+ = { Y , Z }

 

Now,

  • Clearly, the two results are different.
  • Thus, we conclude that Y → X is essential and can not be eliminated.

 

For Y → Z:

 

  • Considering Y → Z, (Y)+ = { W , X , Y , Z }
  • Ignoring Y → Z, (Y)+ = { W , X , Y }

 

Now,

  • Clearly, the two results are different.
  • Thus, we conclude that Y → Z is essential and can not be eliminated.

 

From here, our essential functional dependencies are-

X → W

WZ → Y

Y → X

Y → Z

 

Step-03:

 

  • Consider the functional dependencies having more than one attribute on their left side.
  • Check if their left side can be reduced.

 

In our set,

  • Only WZ → Y contains more than one attribute on its left side.
  • Considering WZ → Y, (WZ)+ = { W , X , Y , Z }

 

Now,

  • Consider all the possible subsets of WZ.
  • Check if the closure result of any subset matches to the closure result of WZ.

(W)+ = { W }

(Z)+ = { Z }

 

Clearly,

  • None of the subsets have the same closure result same as that of the entire left side.
  • Thus, we conclude that we can not write WZ → Y as W → Y or Z → Y.
  • Thus, set of functional dependencies obtained in step-02 is the canonical cover.

 

Finally, the canonical cover is-

X → W

WZ → Y

Y → X

Y → Z

Canonical Cover

 

Next Article- Decomposition of a Relation

 

Get more notes and other study material of Database Management System (DBMS).

Watch video lectures by visiting our YouTube channel LearnVidFun.