Canonical cover explained

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.F _{c} has two important properties:

1. No functional dependency in

F _{c} contains an extraneous attribute.

1. 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 .

A canonical cover is not unique for a given set of functional dependencies, therefore one set F can have multiple covers

F _{c} .

Algorithm for computing a canonical cover

F _{c} = F

1. 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 .

1. 1. Find a functional dependency in

F _{c} with an extraneous attribute and delete it from F _{c}

1. ... until

F _{c} does not change^[1]

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 =

F_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.^[2]

Extraneous determinant attributes

Given a set of functional dependencies

F and a functional dependency A → B in F , the attribute a is extraneous in A if a \subset A and any of the functional dependencies in (F - (A → B) \cup { (A - a) → B} ) can be implied by F using Armstrong's Axioms.

Using an alternate method, given the set of functional dependencies

F , and a functional dependency X → A in F , attribute Y is extraneous in X if Y \subseteq X , and (X - Y) ^{+} \supseteq A .^[3]

For example:

• If F =, 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 =, B is extraneous in AB → C because logically implies A → C.

Extraneous dependent attributes

Given a set of functional dependencies

F and a functional dependency A → B in F , the attribute a is extraneous in A if a \subset A and any of the functional dependencies in (F - (A → B) \cup \{ A → (B - a) \} ) can be implied by F 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 =, C is extraneous in AB → CD because AB → C can be inferred even after deleting C.
• If F =, C is extraneous in A → BC because A → C can be inferred even after deleting C.

Notes and References

1. Book: Silberschatz . Abraham . Database system concepts . 2011 . McGraw-Hill . New York . 978-0073523323 . Sixth . https://web.archive.org/web/20201108175024/https://mucse44.net/wp-content/uploads/2019/09/Database-System-Concepts-7th-Edition.pdf . 2020-11-08.
2. Book: Elmasri, Ramez . Fundamentals of database systems . 2016 . Sham Navathe . 978-0-13-397077-7 . Seventh . Pearson . Hoboken, NJ . 913842106.
3. Web site: K . Saravanakumar . asamy . How to find extraneous attribute? An example. . 2023-03-14 . en.