1. To minimize the number of functional dependencies that need to be tested in case of an update we may restrict F to a canonical cover Fc.
2. A canonical cover for F is a set of dependencies such that F logically implies all dependencies in Fc, and vice versa.
3. Fc must also have the following properties:
- Every functional dependency α→ β in Fc contains no extraneous attributes in (ones that can be removed from without changing F+c ). So A is extraneous in if A 2 and
(Fc - {α→ β}) ∪[ α-A→ β}
logically implies Fc
- Every functional dependency → in Fc contains no extraneous attributes in (ones that can be removed from without changing F+c ). So A is extraneous in if A 2 and
(Fc - {α→ β} ∪[ α→ β-A}
logically implies Fc.
Each left side of a functional dependency in Fc is unique. That is there are no two dependencies → β1 and α2→ β2 in Fc such that α1 = α2.
4. To compute a canonical cover Fc for F,
repeat
Use the union rule to replace dependencies of the form
→ β1 and α1 → β2 with α1 → β1 β2.
Find a functional dependency α→ β with an extraneous attribute in or in .
If an extraneous attribute is found, delete it from α→ β
until F does not change.
5. An example: for the relational scheme R = (A,B,C), and the set F of functional dependencies
A → BC
B → C
A → B
AB → C
we will compute Fc.
- We have two dependencies with the same left hand side:
A → BC
A → BWe can replace these two with just A → BC . - A is extraneous in AB → C because B → C logically implies AB → C .
- Then our set is
A → BC
B → C - We still have an extraneous attribute on the right-hand side of the rst dependency. C is extraneous in
A → BC because A → B and B → C logically imply that A → BC . - So we end up with
A → B
B → C