Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Normalization
3.
Functional Dependencies
3.1.
Trivial Functional Dependency
3.2.
Non Trivial Functional Dependency 
3.3.
Semi Non-Trivial Functional Dependency 
4.
Canonical Cover
4.1.
Important terms:
5.
Extraneous attributes 
5.1.
Canonical cover 
6.
How to Find Canonical Cover
6.1.
Example 1:
6.2.
Example 2:
7.
How Canonical Cover works in DBMS?
8.
Features of the Canonical Cover
9.
Frequently Asked Questions
9.1.
What is the use of canonical cover? 
9.2.
What is canonical cover and minimal cover in DBMS?
9.3.
What is canonical form in functional dependency?
9.4.
What is the necessity for canonical cover in RDBMS?
10.
Conclusion
Last Updated: Mar 27, 2024
Medium

Canonical Cover In DBMS

Author Ankit Kumar
3 upvotes
Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

In the following script, we will be learning about the canonical cover in DBMS, which comes into play when the functional dependencies get violated while updating the Database. In DBMS, a canonical cover is a set of functional dependencies that is minimal, irreducible, and equivalent to the original set of dependencies.

In the article, we will be checking briefly on Normalization, and Functional Dependencies, and after that, we will be learning about the Canonical covers in detail. 

c++ split string

Read About - Lock based protocol in DBMS

Normalization

Normalization in DBMS is the process of organizing data in a database to eliminate redundancy and dependency. It minimizes data duplication, reduces data anomalies and inconsistencies, and ensures data integrity. It involves breaking down larger tables into smaller ones and establishing relationships between them. Normalization improves data consistency, reduces data storage requirements, and simplifies database maintenance.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Functional Dependencies

A constraint between two sets of attributes related to a database A functional dependency is shown by an arrow ( ). If attribute A functionally determines attribute B, it is written as AB.

Trivial Functional Dependency

A functional dependency AB is trivial only when B is a subset of A.
Example: 
ABC→A
AB→B
ABC→ABC

Non Trivial Functional Dependency 

AB is a functional dependency when B is not a subset of A. It is called completely non-trivial when AB is NULL.

Semi Non-Trivial Functional Dependency 

AB is non-trivial when A∩B is not NULL.

Canonical Cover

When updating a database, the system's role is to ensure that no current functional dependencies are broken in the process. In the event that the new database state violates functional dependencies, the system must be rolled back.

Irreducible functional relationships or a canonical cover FD is a reduced version of FD with a comparable closure to the original FD set.

Important terms:

Extraneous attributes 

If we can delete an attribute of a functional dependency without modifying the closure of the set of functional dependencies, it is said to be unnecessary.

Canonical cover 

Canonical cover Fc is a set of functional dependencies F such that the following properties are not violated: 

  • All dependencies in Fc are logically implied by F.
  • All dependencies in F are logically implied by Fc.
  • There are no extraneous attributes in Fc's functional dependencies.
  • Each functional dependency's left side in Fc is distinct. There are no two dependencies ɑ1→β1 and ɑ2→β2 in such that ɑ1→ɑ2.

Also See, File System vs DBMS

How to Find Canonical Cover

Following is an Algorithm to determine the Canonical cover of set F:

repeat

  1.  Replace any dependencies in ɑ1→β1 and ɑ1→β2. with ɑ1→β1β2 using the union rule.
  2. With an extraneous attribute, either in ɑ or β find a functional dependency ɑ→β. 
  3. Delete any extraneous attribute found in ɑ→β.

until F does not change.

Example 1:

Consider the following set of functional dependencies:

F = { 

X→YZ

Y→Z

X→Y

XY→Z

}

According to the steps mentioned above:

1.  The two functional dependencies

X→YZ

X→Y

with same attributes on the left can be combined to get 

X→YZ.

Now, the new set is:

F = { 

X→YZ

Y→Z

XY→Z

}

2. XYZ is an extraneous attribute because we get the same closures even after removing it from the set. It is since Y→Z is already part of F.

The new set F comes out to be:

F = { 

X→YZ

Y→Z

}

3. X→Y is logically suggested by X→Y and Y→Z, yet Z is an extraneous X→YZ attribute (transitivity).

F = { 

X→Y

Y→Z

}

4. F does not change anymore after this step. The required Canonical cover is,

F = { 

X→Y

Y→Z

}

Example 2:

Consider another set of functional dependencies:

F={

A→BC

CD→E

B→D

E→A

}

According to the algorithm:

  1. Each functional dependency in F has a distinct left side.
  2. There are no extraneous attributes on the left or right sides of any functional dependency (Checked by applying the definition of extraneous attributes on every functional dependency).
  3. Hence, the canonical cover Fc is equal to F.

How to verify if a set of f.d’s F canonically covers a set of f.d’s G?

Consider the two sets of functional dependencies:

F={

A→B

AB→C

D→AC

D→E

}

G={

A→BC

D→AB

}

We must now determine whether one of these f.d.’s canonically covers the other set of f.d.’s. We must decide if F canonically covers G, G canonically covers F, or neither of the two canonically covers the other.

1. Make a singleton on the right side. This indicates that all of the characteristics on the right side of the f.d. arrow must be singletons.

Functional interdependence The functional dependencies D→A and D→C are separated from D→AC.

F={

A→B

AB→C

D→A

D→C

D→E

}

2. Remove any extraneous attributes that aren't necessary.

Consider any XY→Z functional dependence. If X can determine Z by itself, then the attribute Y is extraneous and can be deleted. As can be seen, unnecessary attributes can only exist in functional relationships with many attributes in the LHS.

Take the functional dependency AB→C as an example.

To determine whether any of them are superfluous, we must first find the closures of A and B.

[A]+ = AB

[B]+ = B

As can be seen, B can be deduced from A. This means that B can be removed from the functional dependency AB→C.

F={

A→B

A→C

D→A

D→C

D→E

}

Remove all functional dependencies that are no longer needed.

Check all f.d.’s one by one to verify if eliminating an f.d. X→Y still allows us to deduce Y from X using another f.d. We are testing and checking whether Y is a component of the closure without using the f.d. A more formal way to describe this is to find [X]+ without using the f.d. If this is the case, the f.d. is no longer necessary.

When looking for the f.d. D → C, we notice that the closure of D contains C even after it has been hidden. By combining two other f.d.’s D→A and A→C, we can get C from D. As a result, →C is redundant.

Now, repeat the steps for G.

1. Make a singleton on the right side. This indicates that all of the characteristics on the right side of the f.d. arrow must be singletons.

G = {

A→B

A→C

D→A

D→B

}

2. Remove any extraneous attributes that aren't necessary. There can be no unnecessary attributes because the RHS of all f.d's has only one attribute.

3. Remove all functional dependencies that are no longer needed.

We can see that the f.d. D→B is redundant because it can be obtained by combining two other f.d .'s, D→A and A→B. By looping over all f.d's and checking the closure of the LHS in all cases, we can see that the f.d. D→B is redundant because it can be obtained by combining two other f.d .'s, D→A and A→B.

G={

A→B

A→C

D→A

}

As we can see that all G’s f.d.’s are already covered in F, we conclude that F covers G.

How Canonical Cover works in DBMS?

Canonical Cover in DBMS works by removing redundant functional dependencies while preserving the same meaning and integrity constraints. The process involves finding the closure of the given set of functional dependencies, removing extraneous dependencies, and then ensuring that the remaining set of dependencies is minimal and irreducible. The resulting set is equivalent to the original set and can be used to design a normalized database schema that is free from redundancies and inconsistencies.

Must Recommended Topic, Schema in DBMS

Features of the Canonical Cover

The Canonical Cover is a critical concept in database normalization, offering several key features for efficient data storage and retrieval:

  • Minimized Functional Dependencies (FDs): It represents the smallest set of FDs necessary to derive all others in a relation, ensuring compactness
     
  • Preservation of FDs: The Canonical Cover maintains the original FDs, guaranteeing that all essential dependencies are preserved
     
  • Redundancy Elimination: Redundant FDs, derivable from others, are removed, resulting in a more streamlined data representation
     
  • Key Identification: The Canonical Cover aids in determining superkeys and candidate keys, crucial for database design and normalization
     
  • Dependency Set Simplification: It streamlines FD sets by removing unnecessary attributes, simplifying database operations
     
  • Facilitates Database Design: By providing a clean, minimal set of FDs, the Canonical Cover assists in designing databases with reduced redundancy and enhanced efficiency
     
  • Query Optimization: Canonical Cover minimizes the attributes involved in FDs, potentially leading to more efficient query execution plans.ns

Also read anomalies in database

Frequently Asked Questions

What is the use of canonical cover? 

The use of canonical cover in DBMS is to identify a minimal, irreducible set of functional dependencies that is equivalent to the original set of dependencies. This helps reduce redundancy and simplify the design of a database, resulting in better performance and easier maintenance.

What is canonical cover and minimal cover in DBMS?

In DBMS, a canonical cover is a set of functional dependencies that is minimal, irreducible, and equivalent to the original set of dependencies. A minimal cover is a set of dependencies that is minimal but not necessarily irreducible.

What is canonical form in functional dependency?

In the context of functional dependencies, a canonical form is a form of normalization in which every determinant of a relation is a candidate key, and there are no non-trivial functional dependencies between candidate keys.

What is the necessity for canonical cover in RDBMS?

A canonical cover is a simplified and reduced form of a set of functional dependencies in a database management system. It's also known as an irreducible set because it's a reduced version.

Conclusion

In the article, we briefly discussed the Normalization of databases, Functional dependencies, and Canonical Covers. We came to know about various essential terms of Canonical Cover in DBMS. Then we learned about the algorithm to determine the Canonical covers with the help of Examples. After that, we learned How to verify if a set of f.d’s F canonically covers a set of f.d’s G.

Do check out The Interview guide for Product Based Companies as well as some of the Popular interview problems from top tech companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

You can also consider our Database Management Course to give your career an edge over others.

Live masterclass