Canonical cover

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

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][edit]

  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[edit]

  1. ^ Database system concepts by Abraham Silberschatz et al