Minimal (canonical) cover

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. How do you test whether F and G are equivalent? from Lesson 4.2.4
2. What does decomposition (an Armstrong-derived rule) allow? from Lesson 4.2.2
3. R(A, B, C, D, E), F = {A → B, B → C, CD → E}: what is the only key? from Lesson 4.2.3

1 · The Hook

F = {A → BC, B → C, A → B, AB → C} contains the same information as just {A → B, B → C}. Extra FDs and extra attributes make checking slower and, in the 3NF algorithm, create unnecessary tables. The minimal cover is the stripped-down equivalent version. GATE asks for it directly, or as "how many FDs remain".

2 · Predict First

In F = {A → BC, B → C, A → B, AB → C}, which FDs are redundant?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

A → C (from A → BC) follows from A → B and B → C. AB → C follows from B → C. The duplicate A → B is redundant. What remains: {A → B, B → C}.

Minimal (canonical) cover

A set G is a minimal cover of F if:

1. G ≡ F;
2. every right side in G is a single attribute;
3. no left side has an extraneous attribute (removing any attribute from a left side would change the meaning);
4. no FD in G is redundant (removing it would change the meaning).

Algorithm (do the steps in this order)

1. Split right sides: X → ABC becomes X → A, X → B, X → C.
2. Remove extraneous left-side attributes: for each FD XB → A, if A ∈ X⁺ (closure under the current set), then B is extraneous: replace XB → A by X → A.
3. Remove redundant FDs: for each FD X → A, compute X⁺ using all other FDs; if A ∈ X⁺, delete X → A.

Then (optional, for the 3NF algorithm) group FDs with the same left side: X → A, X → B → X → AB. Some books call that grouped form the canonical cover.

Doing step 3 before step 2 can leave a redundant FD behind. The minimal cover is not unique: different orders of checking can give different (equivalent) answers.

Worked example

F = {ABCD → E, E → D, A → B, AC → D}.

1. Right sides are single already.
2. Extraneous attributes:
   • ABCD → E: A → B, so B is extraneous (A⁺ contains B): ACD → E. AC⁺ = ACBD ⊇ D, so D is extraneous: AC → E. Can A or C go? A⁺ = AB, C⁺ = C: no.
   • AC → D: A⁺ = AB, C⁺ = C: no extraneous attribute.
3. Redundant FDs in {AC → E, E → D, A → B, AC → D}:
   • AC → D: without it, AC⁺ = ACEBD ⊇ D: redundant, delete.
   • AC → E: without it, AC⁺ = ACB: keep. E → D, A → B: keep.

Minimal cover: {AC → E, E → D, A → B}.

Non-uniqueness example

F = {A → BC, B → AC, C → AB}. One minimal cover: {A → B, B → C, C → A}. Another: {A → C, C → B, B → A}. Both have 3 FDs. (Every attribute determines the others, so any cycle works.)

4 · Visual

Minimal cover pipeline

 F  --split RHS-->  single-attribute RHS  --drop extraneous LHS attrs-->  smaller LHS  --drop redundant FDs-->  minimal cover
      X->AB             X->A, X->B              XB->A becomes X->A            X->A gone if X+ (without it) has A

Order matters: LHS first, redundancy last.

5 · Worked Examples

Example 1 Easy

Find a minimal cover of {A → BC, B → C}.

Solution

Split: A → B, A → C, B → C. No left side has two attributes. A → C is redundant (A⁺ without it = ABC). {A → B, B → C}.

Example 2 Medium

Find a minimal cover of {A → B, AB → C, D → AC, D → E}.

Solution

Split: A → B, AB → C, D → A, D → C, D → E. Extraneous: in AB → C, the closure A⁺ under the current set is ABC (A → B, then AB → C), which contains C, so B is extraneous: A → C. Redundant: D → C (D → A → C). Result: {A → B, A → C, D → A, D → E} (4 FDs).

Example 3 GATE

How many FDs are in a minimal cover of {AB → CD, A → E, E → C}?

Solution

Split: AB → C, AB → D, A → E, E → C. Extraneous in AB → C: A⁺ = AEC ⊇ C → becomes A → C. AB → D: A⁺ = AEC, B⁺ = B: keep. Redundant: A → C (A → E → C): delete. Result {AB → D, A → E, E → C}: 3 FDs.

8 · Connect the Dots

Chapter 4.2 is complete: FDs, axioms, closures, keys, equivalence, minimal covers. Next: the Chapters 4.1–4.2 Lock-in, then Chapter 4.3: how to split a table safely: lossless joins and dependency preservation.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 2 mark(s) — Minimal cover

How many FDs are in a minimal cover of {A → B, B → C, A → C, AB → C}?

Numerical answer: ________

Q2 · MCQ · 2 mark(s) — Minimal cover

A minimal cover of {AB → C, A → B, B → C, A → C} is:

1. (A) {A → B, B → C}
2. (B) {AB → C, A → B}
3. (C) {A → C, B → C}
4. (D) {A → B, A → C, B → C}

Q3 · MCQ · 1 mark(s) — Order

In the minimal cover algorithm, extraneous left-side attributes are removed:

1. (A) never
2. (B) after removing redundant FDs
3. (C) before removing redundant FDs
4. (D) only if the right side has several attributes

Q4 · MSQ · 2 mark(s) — Properties

Which are true of minimal covers?

1. (A) A set of FDs has exactly one minimal cover.
2. (B) Every right side is a single attribute.
3. (C) No FD in it is implied by the others.
4. (D) A minimal cover is equivalent to the original set.

Q5 · NAT · 2 mark(s) — Minimal cover

How many FDs are in a minimal cover of {ABCD → E, E → D, A → B, AC → D}?

Numerical answer: ________

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

minimal covercanonical coverextraneous attributeredundant FDminimal cover algorithm