Scribd
Upload
8 views2 pages

Understanding Canonical and Minimal Covers

A minimal cover in a relational database is a simplified set of functional dependencies (FDs) that maintains the same closure as the original set, eliminating extraneous attributes and redundant dependencies. The process to determine a minimal cover involves applying the split rule, removing extraneous attributes, and eliminating redundant functional dependencies. The document provides examples and steps to find the minimal cover for given sets of functional dependencies.

Uploaded by

Suvan B 23BPS1023
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views2 pages

Understanding Canonical and Minimal Covers

A minimal cover in a relational database is a simplified set of functional dependencies (FDs) that maintains the same closure as the original set, eliminating extraneous attributes and redundant dependencies. The process to determine a minimal cover involves applying the split rule, removing extraneous attributes, and eliminating redundant functional dependencies. The document provides examples and steps to find the minimal cover for given sets of functional dependencies.

Uploaded by

Suvan B 23BPS1023
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

07/03/2025

10 March 2025 10:48

Canonical / Minimal cover

• In a relational database management system (DBMS), a minimal cover is a


simplified set of functional dependencies (FDs) that is equivalent to the original
set. It's also known as a canonical cover or irreducible set.

If a functional dependency set F is given, F’ is a canonical cover of given FD set if it


does not have:
i) Extraneous Attributes / Redundant Attributes
ii) Redundant Functional Dependancies

A canonical cover or irreducible a set of functional dependencies FD is a


simplified set of FD that has a similar closure as the original set FD.

Extraneous attributes: An attribute of an FD is said to be extraneous if we can


remove it without changing the closure of the set of FD.

Steps to Determine Minimal Cover:


Step 1: Apply Split Rule such that every FD has only single attribute on the RHS of
the FD.
Step 2: Remove Extraneous Attribute
Step 3: Remove Redundant Functional Dependencies

Example: Given F {AB -> C, C -> AB, B -> C, ABC -> AC, A -> C, AC -> B} for
R(A,B,C), find the minimal cover.
Solution:

Step 1: Apply Split rule:

FD will become {AB->C, C->A, C->B, B->C, ABC->A, ABC->C, A->C, AC->B}

In the above FD set ABC->A, ABC->C are trivial FDs and hence can be
discarded.

The revised FD set will be {AB->C, C->A, C->B, B->C, A->C, AC->B}

Step 2: Remove Extraneous / Redundant Attributes:


{AB->C, C->A, C->B, B->C, A->C, AC->B}

In the above FD set, it can be seen that AB->C and B->C => B alone can determine
C.

Like wise A->C and AC ->B => A alone can determine B.

{AB->C, C->A, C->B, B->C, A->C, AC->B} => {B->C, C->A, C->B, B->C, A->C,
A->B}

{C->A, C->B, B->C, A->C, A->B}. This is the FD set at the end of step 2.

Step 3: Remove Redundant Functional Dependencies:


{C->A, C->B, B->C, A->C, A->B}. This is the FD set at the end of step 2.

Consider C->A, To check if this is redundant, take attribute closure for C without
considering FD C->A.

Perform C+ over {C->B, B->C, A->C, A->B}


C+ = CB => Closure not attained => Cannot discard => C-> A cannot be removed

Now consider C->B in {C->A, C->B, B->C, A->C, A->B}

Perform C+ over {C->A, B->C, A->C, A->B}


C+ = CAB => Closure attained => C-> B can be discarded.

The revised FD set will be {C->A, B->C, A->C, A->B}

Now check for B->C in {C->A, B->C, A->C, A->B}

Perform B+ over {C->A, A->C, A->B}

B+ = B => Closure not attained => Cannot discard => B->C cannot be removed

Now check for A->C in {C->A, B->C, A->C, A->B}

Perform A+ over {C->A, B->C, A->B}

A+ = ABC => Closure attained => Can discard => A->C can be removed

Now the FD set will be {C->A, B->C, A->B}. Check for A->B

Perform A+ over {C->A, B->C}

A+ = A => Closure not attained => Cannot discard => A->B cannot be removed

The final refined FD set F’ = {C->A, B->C, A->B}. This is the minimal cover set.

Solve:

1: Given a relational Schema R( A, B, C, D) and set of Function Dependency FD =


{ B → A, AD → BC, C → ABD }. Find the canonical cover?

2: Given a relational Schema R( W, X, Y, Z) and set of Function Dependency FD =


{ W → X, Y → X, Z → WXY, WY → Z }. Find the canonical cover?

You might also like