How to Find Canonical Cover?
Below mentioned is the algorithm to compute canonical cover for set F.
Repeat
1. Use the union rule to replace any dependencies in α1 → β1 and α2 → β2 with α1 → β1β2
2. Find a functional dependency α → β with an extraneous attribute either in α or in β.
3. If an extraneous attribute is found, delete it from α → β.
until F does not change
Example 1:
Consider the following set F of functional dependencies: F= { A → BC, B → C, A → B, AB → C }. Below mentioned are the steps to find the canonical cover of the functional dependency given above.
Step 1: There are two functional dependencies with the same attributes on the left: A → BC, A → B. These two can be combined to get A → BC. Now, the revised set F becomes F = { A → BC, B → C, AB → C}.
Step 2: There is an extraneous attribute in AB → C because even after removing AB → C from the set F, we get the same closures. This is because B → C is already a part of F. Now, the revised set F becomes: F = { A → BC, B → C }
Step 3: C is an extraneous attribute in A → BC, also A → B is logically implied by A → B and B → C (by transitivity). F= { A → B B → C }
Step 4: After this step, F does not change anymore. So, Hence the required canonical cover is, Fc = { A → B, B → C}
Example 2:
Consider another set F of functional dependencies: F={ A → BC, CD → E, B → D, E → A }
- The left side of each functional dependency in F is unique.
- None of the attributes on the left or right side of any functional dependency is extraneous (Checked by applying the definition of extraneous attributes on every functional dependency).
- Hence, the canonical cover Fc is equal to F.
Note: There can be more than one canonical cover Fc of a set F of functional dependencies.
Canonical Cover of Functional Dependencies in DBMS
Whenever a user updates the database, the system must check whether any of the functional dependencies are getting violated in this process. If there is a violation of dependencies in the new database state, the system must roll back. Working with a huge set of functional dependencies can cause unnecessary added computational time. This is where the canonical cover comes into play. A canonical cover of a set of functional dependencies F is a simplified set of functional dependencies that has the same closure as the original set F.
An attribute of a functional dependency is said to be extraneous if we can remove it without changing the closure of the set of functional dependencies