Canonical cover explained

A canonical cover

Fc

for F (a set of functional dependencies on a relation scheme) is a set of dependencies such that F logically implies all dependencies in

Fc

, and

Fc

logically implies all dependencies in F.

Fc

has two important properties:
  1. No functional dependency in

Fc

contains an extraneous attribute.
  1. Each left side of a functional dependency in

Fc

is unique. That is, there are no two dependencies

a\tob

and

c\tod

in

Fc

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

Fc

.

Algorithm for computing a canonical cover

Fc=F

  1. Repeat:
    1. Use the union rule to replace any dependencies in

Fc

of the form

a\tob

and

a\tod

with

a\tobd

.
    1. Find a functional dependency in

Fc

with an extraneous attribute and delete it from

Fc

  1. ... until

Fc

does not change[1]

Canonical cover example

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

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

Fc

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

AB

in

F

, the attribute

a

is extraneous in

A

if

a\subsetA

and any of the functional dependencies in

(F-(AB)\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\subseteqX

, and

(X-Y)+\supseteqA

.[3]

For example:

Extraneous dependent attributes

Given a set of functional dependencies

F

and a functional dependency

AB

in

F

, the attribute

a

is extraneous in

A

if

a\subsetA

and any of the functional dependencies in

(F-(AB)\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:

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.