Canonical cover

A canonical cover ${\displaystyle F_{c}}$ for F (a set of functional dependencies on a relation scheme) is a set of dependencies such that F logically implies all dependencies in ${\displaystyle F_{c}}$, and ${\displaystyle F_{c}}$ logically implies all dependencies in F.

The set ${\displaystyle F_{c}}$ has two important properties:

1. No functional dependency in ${\displaystyle F_{c}}$ contains an extraneous attribute.
2. Each left side of a functional dependency in ${\displaystyle F_{c}}$ is unique. That is, there are no two dependencies ${\displaystyle a\to b}$ and ${\displaystyle c\to d}$ in ${\displaystyle F_{c}}$ such that ${\displaystyle a=c}$.

A canonical cover is not unique for a given set of functional dependencies, therefore one set F can have multiple covers ${\displaystyle F_{c}}$.

Algorithm for computing a canonical cover [1]

1. ${\displaystyle F_{c}=F}$
2. Repeat:
   1. Use the union rule to replace any dependencies in ${\displaystyle F_{c}}$ of the form ${\displaystyle a\to b}$ and ${\displaystyle a\to d}$ with ${\displaystyle a\to bd}$ ..
   2. Find a functional dependency in ${\displaystyle F_{c}}$ with an extraneous attribute and delete it from ${\displaystyle F_{c}}$
3. ... until ${\displaystyle F_{c}}$ does not change

References

1. Database system concepts by Abraham Silberschatz et al