Canonical cover

A canonical cover $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 $F_c$ , and $F_c$ logically implies all dependencies in F.

The set $F_c$ has two important properties:

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

Algorithm for computing a canonical cover ^[1]

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

References

↑ Database system concepts by Abraham Silberschatz et al

This article is issued from Wikipedia - version of the 8/27/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.