Minimal Cover of Functional Dependencies

By RTI (DBMS Series)

Definition

• Simplified version of the original set of functional dependencies
• Helps remove redundant functional dependencies

Why Minimal Cover?

1. Remove Redundant Functional Dependencies
   • Using transitivity, e.g., A → B, B → C implies A → C, so A → C is redundant and can be removed
2. Reduce Complexity
   • Fewer functional dependencies mean reduced complexity
3. Ensure No Unnecessary Dependencies
   • Prevents anomalies in database operations (insertion, deletion, updation)

Steps to Find Minimal Cover

Step 1: Decompose the Functional Dependencies

• If you have X → AB, decompose it into X → A and X → B
• Only decompose RHS (right-hand side); LHS remains as is

Step 2: Remove Redundant Functional Dependencies

1. Identify Potential Redundancies
   • Exclude one dependency and create a new set
   • E.g., exclude A → B to see the effects
2. Compute Closure
   • Find the closure of LHS from the remaining functional dependencies
   • If closure determines all table attributes, the excluded dependency is redundant
   • Repeat for each dependency

Step 3: Remove Unnecessary Attributes from LHS

• If AB → X is present, check if A alone or B alone can determine all attributes
• Reduce to minimal candidate key (if AB is a superkey)

Example

Functional Dependencies to Minimize

• A → BC
• B → C
• A → B
• A → C

Step-by-Step Minimization

1. Decompose RHS

   • A → BC becomes A → B and A → C
   • Revised set: A → B, A → C, B → C, A → B (remove duplicate)
   • Final RHS decomposed set: A → B, A → C, B → C

2. Remove Redundant Dependencies

   • Exclude A → B, new set: A → C, B → C
     • Compute A+: A+ = {A, C}, does not determine all attributes, so A → B is not redundant
   • Exclude A → C, new set: A → B, B → C
     • Compute A+: A+ = {A, B, C}, determines all attributes, so A → C is redundant
   • Remaining sets: A → B, B → C

3. Check Further Redundancies

   • Exclude B → C, new set: A → B, A → C
     • Compute B+: B+ = {B}, does not determine all attributes, so B → C is not redundant
   • Exclude AB → C, not found in current set

Result

• Final minimal cover: A → B, B → C

Conclusion

• These steps help find the minimal cover effectively
• No need for step 3 as remaining LHS attributes are single

Closing

• Like and subscribe for more tech content
• Follow on social media for updates (links in the description)

Take care, keep learning, keep growing, keep smiling!