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:

  1. No functional dependency in F_c contains an extraneous attribute.
  2. 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]

  1. F_c = F
  2. 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
  3. ... until F_c does not change

References

  1. Database system concepts by Abraham Silberschatz et al
This article is issued from Wikipedia - version of the Thursday, August 27, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.