Canonical cover

From Wikipedia, the free encyclopedia
Jump to: navigation, search

A canonical cover for F (a set of functional dependencies on a relation scheme) is a set of dependencies such that F logically implies all dependencies in , and logically implies all dependencies in F.

The set has two important properties:

  1. No functional dependency in contains an extraneous attribute.
  2. Each left side of a functional dependency in is unique. That is, there are no two dependencies and in such that .

Algorithm for computing a canonical cover [1][edit]

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

References[edit]

  1. ^ Database system concepts by Abraham Silberschatz et al