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
- Replace any dependencies in ɑ1→β1 and ɑ1→β2. with ɑ1→β1β2 using the union rule.
- With an extraneous attribute, either in ɑ or β find a functional dependency ɑ→β.
- 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:
- Each functional dependency in F has a distinct left side.
- 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).
- 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.
239+ registered 
