## Canonical Cover Explained / Canonical Cover in Database with Simple Examples / Minimal Cover with Examples / What is Canonical Cover? / What is Minimal Cover?

## Canonical Cover

### Definition:

A Canonical Cover for a set of
functional dependencies F is another set of functional dependencies Fc such
that all the functional dependencies in F logically imply all the functional
dependencies in Fc and vice versa. We insist the Fc to meet the following
requirements;

1. F should logically imply all
FDs in Fc, [F = Fc]

2. Fc should logically imply all
FDs in F,

3. Functional dependencies of Fc
should not contain any

**Extraneous attribute**. (Refer for Extraneous attributes)
4. The left side of all the
functional dependencies in Fc should be unique.

Actually, a Canonical cover Fc is
a

In other words, every functional dependency of Fc is very much needed and it is as small as possible when compared to the size of F.

**set of functional dependencies that is equivalent to F, and***minimal***.***have no redundant functional dependencies or redundant attributes as part of functional dependencies*In other words, every functional dependency of Fc is very much needed and it is as small as possible when compared to the size of F.

__Canonical Cover Algorithm:__**ALGORITHM CanonicalCover(FD set F)**

**BEGIN**

**REPEAT UNTIL STABLE**

**1. Wherever possible, apply UNION rule from Armstrong’s Axioms**

**(e.g., A**→

**BC, A**→

**CD becomes A**→

**BCD)**

**2. Remove “extraneous attributes”, if any, from every FD**

**(e.g., AB**→

**C, A**→

**B becomes A**→

**B, B**→

**C i.e., A is extraneous in AB**→

**C)**

**END**

__Example:__###
**Redundant Functional Dependency****:**

A →
C is redundant in {A →
B, B → C, A → C}

Observe from the given set of
functional dependencies, A →
B and B → C will
automatically include A →
C as a result of Transitivity. Hence, we do not need to check whether C is
uniquely determined by A or not [in other words, A uniquely determines C or
not].

**Hence, A**→**C is redundant**.
And, the set of functional
dependencies {A →
B, B → C} is
semantically equivalent to given set of functional dependencies {A → B, B →
C, A → C}.

###
**Redundant Attributes or Redundant Part of Set of Attributes****:**

**→**

*Attribute C is redundant on the Right Hand Side (RHS) of FD A***→**

*CD in {A***→**

*B, B*

**→**

*C, A*

*CD}.*
Here, C is already determined by
B. Hence, we do not need to include in another FD to check the dependency. So,
the given set of functional dependencies can be simplified as {A → B, B →
C, A → D}. And, this
is equivalent.

**→**

*Attribute C is redundant on the Left Hand Side (LHS) of FD AC*

**→**

*D in {A***→**

*B, B*

**→**

*C, AC*

*D}.*
Here, if we know A, intuitively we
know C as well through Transitivity rule. Hence, A → D is suffice to represent. So, the
given set of functional dependencies can be simplified as {A → B, B →
C, A → D}. And, this
is equivalent to the given set of FDs.

## No comments:

## Post a Comment