Closure & Minimal Cover: Solved DBMS Problems

Section 01

Warm-Up — The Toolkit at a Glance

📖 The Drill

One Tool Solves Almost Everything

A carpenter who masters the chisel can do most of the job with it alone. In functional-dependency theory, that one tool is the attribute closure X⁺. Testing a dependency, finding candidate keys, checking covers, proving equivalence, removing redundancy, minimizing a set — every single task is just "compute a closure and look at the result."

This is a practice set: a quick recap, then worked drills with fresh examples, and a stack of problems with full solutions. Keep one rule in mind throughout — never enumerate the giant set F⁺; compute a small X⁺ instead.

Task	Done with closure how?
Does X → Y hold?	Check Y ⊆ X⁺
Is X a superkey?	Check X⁺ = all attributes
Does F cover G?	For each X→Y in G: Y ⊆ X⁺_F
F ≡ G?	F covers G and G covers F
Is X→Y redundant?	Drop it, recompute X⁺; if Y still in, it's redundant

Section 02

Attribute Closure with a Multi-Attribute Left Side

The closure algorithm is unchanged, but watch what happens with an FD like BC → D: it can only fire once both B and C are already inside the set. Many students miss this and stop too early.

🌱 A⁺ under F = {A→B, A→C, BC→D, D→E}

BC→D stays "locked" until both B and C are present. Once they arrive (via A→B and A→C), it unlocks and pulls in D, then D→E finishes the chain.

✅

Result

A⁺ = {A, B, C, D, E} = every attribute, so A is a candidate key of R(A,B,C,D,E).

Section 03

Finding All Candidate Keys — The Shortcuts

Brute-forcing every attribute subset is slow. Two shortcuts make candidate-key hunting fast.

🔑

Must-be-in-key

Never on any RHS

An attribute that appears on the right side of no FD can only be obtained from itself, so it must be inside every candidate key.

✅

Free attributes

On neither side

An attribute that appears in no FD at all must also be in every candidate key — nothing else can determine it.

🔄

Grow from the core

Then add the rest

Start with the must-be-in attributes; if their closure isn't everything, add other attributes one at a time and re-test until you reach a superkey.

✅ Worked Example — R(A,B,C,D,E), F = {AB→C, C→D, D→E, E→A}

RHS scan

Right sides are C, D, E, A. The attribute B never appears on a RHS → B is in every candidate key.

B alone?

B⁺ = {B}. Not a superkey, so pair B with one cycle attribute.

Test AB

AB→C→D→E→A → AB⁺ = {A,B,C,D,E} ✔ key.

Cycle

Since C→D→E→A→(with B)→C form a loop, BC, BD, BE are also superkeys and minimal.

Answer

Candidate keys = {AB, BC, BD, BE}.

💡

Why B Multiplies the Keys

B is mandatory; A, C, D, E sit on a cycle so any one of them "unlocks" the rest. Pairing the mandatory B with each cycle attribute gives exactly four candidate keys.

Section 04

Covers — A Quick Drill

Remember: F covers G means every FD of G is derivable from F. Test each FD of G with a closure computed under F.

✅ Does F = {A→B, B→C, C→D} cover G = {A→C, A→D, B→D}?

A→C

A⁺_F = {A,B,C,D} ⊇ {C} ✔

A→D

A⁺_F = {A,B,C,D} ⊇ {D} ✔

B→D

B⁺_F = {B,C,D} ⊇ {D} ✔

Verdict

All three hold → F covers G.

Section 05

Equivalence — When It Holds and When It Fails

F ≡ G needs cover in both directions. Skipping one direction is the most common error, so here are the two outcomes side by side.

≡ Equivalent vs ≠ Not Equivalent

Left: each set derives the other's FDs. Right: G has only A→B and A→C, so under G we get B⁺={B} — it can never produce F's B→C.

✅ The Failing Case in Detail — F = {A→B, B→C}, G = {A→B, A→C}

F ⊃ G?

A→B ✔; A→C: A⁺_F={A,B,C} ✔. F covers G.

G ⊃ F?

A→B ✔; B→C: B⁺_G={B} — C is missing ✘. G does NOT cover F.

Verdict

One direction fails → F ≠ G.

Section 06

Non-Redundant Cover — Strip the Implied FDs

Test each FD by removing it and checking whether the rest still derive it. Drop the ones that are still implied.

✅ Reduce F = {A→B, B→C, A→C, C→A}

A→C

Drop it; A⁺ under {A→B, B→C, C→A} = {A,B,C} still has C → redundant, remove.

A→B

Drop it; A⁺ under {B→C, C→A} = {A} — no B → keep.

B→C

Drop it; B⁺ under {A→B, C→A} = {B} — no C → keep.

C→A

Drop it; C⁺ under {A→B, B→C} = {C} — no A → keep.

Result

Non-redundant cover = {A→B, B→C, C→A}.

⚠️

Order Can Change the Result

Removing one redundant FD may make another stop being redundant. Always recompute closures against the FDs that currently survive, and test one FD at a time.

Section 07

Minimal Cover — Reduce Both Sides

A minimal (canonical) cover needs single-attribute right sides, no extraneous left-side attributes, and no redundant FDs. This example shows both a left-side reduction and a redundancy removal.

🧱 F = {A→B, B→C, AB→C, A→C} → canonical cover

AB→C collapses to B→C (a duplicate, dropped), and A→C is implied by A→B→C, so it goes too.

✅ Step by Step

Step 1

Right sides already single — nothing to split.

Step 2

AB→C: B⁺ = {B,C} already contains C, so A is extraneous → AB→C becomes B→C (a duplicate → drop).

Step 3

From {A→B, B→C, A→C}, A→C is redundant (A→B→C) → remove.

Result

Canonical cover = {A→B, B→C}.

Section 08

Practice Set — Seven Problems

Problem 1 — Closure with a 2-attribute LHS

❓

Task

F = {A→B, C→D, AB→C} on R(A,B,C,D). Find A⁺.

✅ Solution 1

Trace

{A} → A→B add B {A,B} → AB→C fires add C {A,B,C} → C→D add D.

Answer

A⁺ = {A,B,C,D} → A is a candidate key.

Problem 2 — All candidate keys

❓

Task

R(A,B,C,D), F = {A→B, B→C, C→A, A→D}. Find all candidate keys.

✅ Solution 2

RHS scan

Right sides: B, C, A, D. D never on a LHS but is on a RHS; A, B, C cycle (A→B→C→A).

Test

A⁺={A,B,C,D}, B⁺={B,C,A,D}, C⁺={C,A,B,D} — each is a superkey.

Answer

Candidate keys = A, B, C (D is determined by all, never determines, so it's not in any key).

Problem 3 — FD membership

❓

Task

F = {A→B, B→C, C→D}. Is AC → D in F⁺?

✅ Solution 3

Test

(AC)⁺ = {A,C,B,D} contains D → yes, AC→D ∈ F⁺.

Problem 4 — Does F cover G?

❓

Task

F = {A→B, B→C}, G = {A→C}. Does F cover G? Does G cover F?

✅ Solution 4

F ⊃ G

A⁺_F={A,B,C} ⊇ C → F covers G ✔.

G ⊃ F

A⁺_G={A,C}; B⁺_G={B} → can't derive A→B or B→C → G does not cover F ✘.

Note

So F is strictly stronger than G; they are not equivalent.

Problem 5 — Equivalence

❓

Task

F = {A→B, B→C, A→C}, G = {A→B, B→C}. Are they equivalent?

✅ Solution 5

F ⊃ G

A→B ✔, B→C ✔. ✔

G ⊃ F

A→B ✔, B→C ✔, A→C: A⁺_G={A,B,C} ✔. ✔

Answer

F ≡ G — A→C was redundant.

Problem 6 — Non-redundant cover

❓

Task

Make F = {A→B, B→C, A→C, C→D, A→D} non-redundant.

✅ Solution 6

A→C

A→B→C already → redundant, remove.

A→D

A→B→C→D already → redundant, remove.

Answer

Non-redundant cover = {A→B, B→C, C→D}.

Problem 7 — Full minimal cover

❓

Task

Find the minimal cover of F = {A→BC, CD→E, B→D, E→A}.

✅ Solution 7

Step 1

Single RHS: A→B, A→C, CD→E, B→D, E→A.

Step 2

CD→E: C⁺={C}, D⁺={D} — neither alone gives E, so no extraneous attribute; keep CD→E.

Step 3

Test each for redundancy: none can be dropped without losing its target.

Answer

Minimal cover = {A→B, A→C, CD→E, B→D, E→A}.

Section 09

Summary — The Whole Toolkit

Concept	Symbol	How to compute / test
Attribute closure	X⁺	Iterate FDs (a multi-attr LHS fires only when whole LHS is in)
FD-set closure	F⁺	Don't enumerate — test membership via X⁺
Candidate key	—	Must-be-in attrs first, grow until X⁺ = all
F covers G	G ⊆ F⁺	Each X→Y in G: Y ⊆ X⁺_F
Equivalence	F ≡ G	Cover both ways
Minimal cover	F_c	Single RHS → reduce LHS → drop redundant

Section 10

Common Mistakes to Avoid

⚠️

Mistake 1 — Firing a multi-attribute FD too early

BC→D adds D only when both B and C are already in the closure. Having just one of them does nothing.

⚠️

Mistake 2 — Checking equivalence in one direction

F covering G is only half the proof. You must also confirm G covers F — many "equivalent" answers fail this second check.

⚠️

Mistake 3 — Ignoring must-be-in-key attributes

An attribute never on any RHS must sit in every candidate key. Forgetting it leads to missing or wrong keys.

Section 11

Golden Rules of Closures & Covers

🏆 Closures & Covers — Non-Negotiable Rules

Compute X⁺, never F⁺. Every task reduces to one or more attribute closures.

A multi-attribute LHS fires only when its whole left side is present. Track this carefully.

Attributes never on a RHS are in every candidate key. Start key-hunting from them.

Equivalence = cover both ways. Always test F⊃G and G⊃F.

Test redundancy against surviving FDs only. Never include the FD under test.

Minimal cover order: single RHS, reduce LHS, drop redundant. The result is equivalent but not unique.