Canonical Cover

1. To minimize the number of functional dependencies that need to be tested in case of an update we may restrict to a canonical cover .
2. A canonical cover for is a set of dependencies such that logically implies all dependencies in , and vice versa.
3. must also have the following properties:
   • Every functional dependency in contains no extraneous attributes in (ones that can be removed from without changing ). So is extraneous in if and

     

     logically implies .

   • Every functional dependency in contains no extraneous attributes in (ones that can be removed from without changing ). So is extraneous in if and

     

     logically implies .

   • Each left side of a functional dependency in is unique. That is there are no two dependencies and in such that .
4. To compute a canonical cover for ,
   • Use the union rule to replace dependencies of the form and with .

   • Test each functional dependency to see if there is an extraneous attribute in .

   • Test each functional dependency to see if there is an extraneous attribute in .
   • Continue until there are no changes occurring in the loop.
5. An example: for the relational scheme , and the set of functional dependencies

   

   we will compute .

   • We have two dependencies with the same left hand side:

     

     We can replace these two with just A BC .

   • is extraneous in AB C because B C logically implies AB C .

   • Then our set is

     

   • We still have an extraneous attribute on the right-hand side of the first dependency. is extraneous in A BC because A B and B C logically imply that A BC .
   • So we end up with