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.

Normalization in DBMS - Multiple Choice Questions with Answers

Normalization process in RDBMS, multiple choice questions with answers in RDBMS, normal forms and functional dependencies MCQs.

Database Management Systems Quiz - Normalization Process in DBMS

Assume a relation R(A, B, C, D)  with set of functional dependencies F = { C → D, C → A, B → C}. Use this setup to answer the following questions;

1. Which of the following is the candidate keys of R?

a) C

b) BC

c) B

d) Both (b) and (c)

View Answer

Answer: (c) B Only left hand side (LHS) attributes of the given set of FDs are C and B. B determines C uniquely. Hence, we can find the closure of B to check whether it forms the candidate key or not as follows; B+ = BCDA through FDs B → C, C → D, and C → A. And, B+ = R. So, B is the only candidate key for R.

2. Which is the normal form that the relation R is currently complies with?

a) First Normal Form (1NF)

b) Second Normal Form (2NF)

c) Third Normal Form (3NF)

d) All of the above

View Answer

Answer: (b) Second Normal Form (2NF) C → D, and C → A are non-trivial FDs. C is not a super key and D is not part of any candidate key. Hence, R is not in 3NF. No partial key dependencies present in R since B is the only key (and is not composite key). Hence, R is currently in 2NF.

3. R is not in BCNF. Which of the following shows the correct decomposition of R into BCNF relations?

a) R₁(CDA), R₂(BC)

b) R₁(BD), R₂(CA)

c) R₁(BC), R₂(CA), R₃(CD)

d) None of the above

View Answer

Answer: (c) R1(BC), R2(CA), R3(CD) BCNF relation – “The LHS of a functional dependency should be a key for the relation if the relation is in BCNF”. The FDs C → D and C → A violates the properties of BCNF because C is not a candidate key for R. (B → C does not violate because B is the candidate key for R). Let us decompose R using one of the violating FD C → D. To decompose, let us create separate relation for violating FD. We will get R1(A, B, C) and R2(C, D). Is the decomposition in BCNF? R2 is in BCNF due to the FD C → D whereas R1 is not due to the FD C → A. So, let us further decompose R1 by creating a relation for violating FD. We will get R11(B, C) and R12(C, A). Both are in BCNF. Hence, BCNF decomposition of R is R1(B, C), R2(C, A) and R3(C, D).

4. Which among the following is the canonical cover (minimal cover F_c) of the relation R?

a) F_c = {C → DA, B → C}

b) F_c = {BC → A, BC → D}

c) F_c = {C → A, B → C, D → A}

d) All of the above

View Answer

Answer: (a) Fc = {C → DA, B → C} A canonical cover (minimal cover) of a set of FDs F is a minimal set of functional dependencies Fmin that is equivalent to F. To understand the process of finding minimal cover, please refer here. For the relation R and set of FDs F, the set of functional dependencies {C → DA, B → C} is the minimal set.

5. R can be decomposed into set of 3NF relations R₁(C, D, A) and R₂(B, C). This decomposition is a _____.

a) Lossless join decomposition

b) Lossy join decomposition

c) Dependency preserving decomposition

d) Both lossless and dependency preserving decomposition

View Answer

Answer: (d) Both lossless and dependency preserving decomposition Decomposition is lossless if either (R1 ∩ R2) → R1 or (R1 ∩ R2) → R2 holds. According to the question, (R1 ∩ R2) → R1 is TRUE [How? (CDA) ∩ (BC) → (CDA) ⇒ C → CDA]. Hence, the decomposition is lossless. Decomposition is dependency preserving if (F1 U F2 U … Fn)+ = F+. that is, if the closure of union of individual relations functional dependencies is equal to the closure of FDs of original relation. This is also true here. Hence, the decomposition is a dependency preserving decomposition.

*************************

Related posts:

• Go to Multiple Choice Questions in DBMS home

• Go to Normalization - MCQs page

• Go to General Mixed Quiz in all topics of DBMS page

• Go to Advanced DBMS Concepts page

Quiz questions with answers on DBMS normalization

Solved quiz questions on functional dependencies and normalization process of database management systems

MCQ with answers on normalization process of DBMS

Normalization solved exercises in MCQs.

2NF, 3NF, BCNF, lossless and depdendency preserving decomposition