Canonical Cover in Database with Simple Examples

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 minimal set of functional dependencies that is equivalent to F, and 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.

How to find extraneous attribute? An example.

To find Extraneous attribute in a given functional dependency / How to find extraneous attribute? / Example for finding extraneous attributes

Finding Extraneous Attributes

Let us consider a set of functional dependencies F and any functional dependency of the form α → β. Assume that α and β are set of one or more attributes. [For example, A → BC or AB → CE etc.]

Case 1 (LHS): To find if an attribute A in α is extraneous or not. That is, to test if an attribute of Left Hand Side of a functional dependency is Extraneous or not.

Step 1: Find ({α} – A)⁺ using the dependencies of F.

Step 2: If ({α} – A)⁺ contains all the attributes of β, then A is extraneous.

Case 2 (RHS): To find if an attribute A in β is extraneous or not. That is, to test if an attribute of Right Hand Side of a functional dependency is Extraneous or not.

Step 1: Find α⁺ using the dependencies in F’ where F’ = (F – {α → β}) U { α → (β – A) }.

Step 2: If α⁺ contains A, then A is extraneous.

Example 1 for LHS:

Given F = {P→Q, PQ→R}. Is Q extraneous in PQ→R?

In this example, we are looking for a LHS attribute. Hence, let us use Case 1 discussed above.

Step 1: Find ({α} – A)⁺ using the dependencies of F.

Here, α is PQ. So find (PQ – Q)⁺, ie., P+ (closure of P).

From F, if you know P, then you know Q (from P→Q).

If you know both P and Q then you know R (from PQ→R).

Hence, the closure of P is PQR.

Step 2: If ({α} – A)⁺ contains all the attributes of β, then A is extraneous.

(PQ – Q)⁺ contains R. Hence, Q is extraneous in PQ→R.

Example 2 for RHS:

Given F = {P→QR, Q→R}. Is R extraneous in P→QR?

In this example, we are looking for a RHS attribute. Hence, let us use the Case 2 given above.

Step 1: Find α⁺ using the dependencies in F’ where F’ = (F – {α → β}) U { α → (β – A) }.

Let us find F’ as stated above.

F’ = (F – {α → β}) U { α → (β – A) } = ({P→QR, Q→R} – {P→QR}) U {P→(QR-R)}

   = ({Q→ R} U {P→Q})

F’ = {Q→R, P→Q}

Here, α is P. So find (P)⁺, ie., closure of P using the F’ which we found.

From F’, if you know P, then you know Q (from P→Q).

If you know Q then you know R (from Q→R).

Hence, the closure of P is PQR.

Step 2: If α⁺ contains A, then A is extraneous.

P+ contains R. Hence, R is extraneous in P→QR.