Canonical cover

A canonical cover [math]\displaystyle{ F_c }[/math] for F (a set of functional dependencies on a relation scheme) is a set of dependencies such that F logically implies all dependencies in [math]\displaystyle{ F_c }[/math], and [math]\displaystyle{ F_c }[/math] logically implies all dependencies in F. The set [math]\displaystyle{ F_c }[/math] has two important properties:

1. No functional dependency in [math]\displaystyle{ F_c }[/math] contains an extraneous attribute.
2. Each left side of a functional dependency in [math]\displaystyle{ F_c }[/math] is unique. That is, there are no two dependencies [math]\displaystyle{ a \to b }[/math] and [math]\displaystyle{ c \to d }[/math] in [math]\displaystyle{ F_c }[/math] such that [math]\displaystyle{ a = c }[/math].

A canonical cover is not unique for a given set of functional dependencies, therefore one set F can have multiple covers [math]\displaystyle{ F_c }[/math].

Algorithm for computing a canonical cover

1. [math]\displaystyle{ F_c = F }[/math]
2. Repeat:
   1. Use the union rule to replace any dependencies in [math]\displaystyle{ F_c }[/math] of the form [math]\displaystyle{ a \to b }[/math] and [math]\displaystyle{ a \to d }[/math] with [math]\displaystyle{ a \to bd }[/math] ..
   2. Find a functional dependency in [math]\displaystyle{ F_c }[/math] with an extraneous attribute and delete it from [math]\displaystyle{ F_c }[/math]
3. ... until [math]\displaystyle{ F_c }[/math] does not change

Canonical cover example

In the following example, F_c is the canonical cover of F.

Given the following, we can find the canonical cover: R = (A, B, C, G, H, I) F = {A→BC, B→C, A→B, AB→C}

1. {A→BC, B→C, A→B, AB→C}
2. {A → BC, B →C, AB → C}
3. {A → BC, B → C}
4. {A → B, B →C}

F_c =  {A → B, B →C}

Extraneous Attributes

An attribute is extraneous in a functional dependency if its removal from that functional dependency does not alter the closure of any attributes.

Extraneous Determinant Attributes

Given a set of functional dependencies [math]\displaystyle{ F }[/math] and a functional dependency [math]\displaystyle{ A \rightarrow B }[/math] in [math]\displaystyle{ F }[/math], the attribute [math]\displaystyle{ a }[/math] is extraneous in [math]\displaystyle{ A }[/math] if [math]\displaystyle{ a \subset A }[/math] and any of the functional dependencies in [math]\displaystyle{ (F-(A \rightarrow B) \cup { (A-a) \rightarrow B} ) }[/math] can be implied by [math]\displaystyle{ F }[/math] using Armstrong's Axioms.

Using an alternate method, given the set of functional dependencies [math]\displaystyle{ F }[/math], and a functional dependency X → A in [math]\displaystyle{ F }[/math], attribute Y is extraneous in X if [math]\displaystyle{ Y \subseteq X }[/math], and [math]\displaystyle{ (X-Y)^+ \supseteq A }[/math].

For example:

• If F = {A → C, AB → C}, B is extraneous in AB → C because A → C can be inferred even after deleting B. This is true because if A functionally determines C, then AB also functionally determines C.
• If F = {A → D, D → C, AB → C}, B is extraneous in AB → C because {A → D, D → C, AB → C} logically implies A → C.

Extraneous Dependent Attributes

Given a set of functional dependencies [math]\displaystyle{ F }[/math] and a functional dependency [math]\displaystyle{ A \rightarrow B }[/math] in [math]\displaystyle{ F }[/math], the attribute [math]\displaystyle{ a }[/math] is extraneous in [math]\displaystyle{ A }[/math] if [math]\displaystyle{ a \subset A }[/math] and any of the functional dependencies in [math]\displaystyle{ (F-(A \rightarrow B) \cup \{ A \rightarrow (B-a) \} ) }[/math] can be implied by [math]\displaystyle{ F }[/math] using Armstrong's Axioms.

A dependent attribute of a functional dependency is extraneous if we can remove it without changing the closure of the set of determinant attributes in that functional dependency.

For example:

• If F = {A → C, AB → CD}, C is extraneous in AB → CD because AB → C can be inferred even after deleting C.
• If F = {A → BC, B → C}, C is extraneous in A → BC because A → C can be inferred even after deleting C.