← 🔗 Functional Dependencies
Subtopic 4 of 5

4.4Minimal (canonical) cover

The idea

A minimal (canonical) cover is a smallest equivalent set of FDs: single right attributes, no useless left attributes, no redundant FDs.

Think of it like this: Editing a long email down to the shortest version that still says exactly the same.

Why it exists

It is used to compute normal forms, and GATE asks for the cover or the number of FDs in it.

How it works

  1. Split every right side into single attributes.
  2. For each FD with a long left side, drop an attribute if the rest still implies the right side.
  3. Remove any FD implied by the remaining ones.
  4. Optionally merge FDs with the same left side.

Worked example: F = {A → BC, B → C, A → B, AB → C}.

Split: A→B, A→C, B→C, A→B, AB→C. Drop B in AB→C (A→C works), remove duplicates, remove A→C (A→B, B→C give it). Cover: A → B, B → C.

Now play with it

  • →Step through the cover for each example.
  • →Notice that the final cover may differ if you drop FDs in a different order.
  • Step 1: split every right side into single attributesA → B, A → C, B → C, A → B, AB → C
  • Step 2: A is extraneous in AB → CB already determines C, so drop A
  • Step 2 result (extraneous left attributes removed)A → B, A → C, B → C, A → B, B → C
  • Step 3: A → B is redundantit follows from the other FDs
  • Step 3: A → C is redundantit follows from the other FDs
  • Step 3: B → C is redundantit follows from the other FDs
  • Canonical cover (right sides with the same left side combined)A → B, B → C
Canonical coverA → B, B → C

A canonical cover is not unique. Different removal orders can give different but equivalent covers.

Check yourself

Which is NOT required of a canonical cover?

Remember: Split, drop extraneous left attributes, drop redundant FDs. Not unique.
Exam notes (the dense version)

A minimal cover is an equivalent FD set with: (1) single-attribute right sides, (2) no extraneous attribute on any left side, (3) no redundant FD. Procedure: split right sides; for each FD with a multi-attribute left side test whether an attribute can be dropped (A is extraneous if the rest of the left side already determines the right side); remove FDs implied by the others. The result is not unique.

Previous year questions: Functional Dependencies (6)

PYQs are grouped by topic, so this is the full set for Functional Dependencies; try the ones that match this subtopic. Open all 6 on the topic page.