Closure, Covers & Minimal Cover
Press Next → or use ← → arrow keys
The Toolkit — Everything Reduces to X⁺
The set of all derivable FDs (F⁺) is enormous — never enumerate it. Instead, compute a small attribute closure X⁺ and answer every question with it.
| Task | Method via closure |
|---|---|
| Testing if X → Y holds | Check whether Y ⊆ X⁺ |
| Verifying X is a superkey | Confirm X⁺ = all attributes |
| Does F cover G? | For each X→Y in G, verify Y ⊆ X⁺F |
| Proving F ≡ G | F covers G and G covers F |
| Is X→Y redundant? | Remove it, recompute X⁺; if Y still appears → redundant |
Closure, keys, covers, equivalence, minimality — all five are just attribute-closure computations in disguise.
Attribute Closure — A Worked Trace
F = {A→B, A→C, BC→D, D→E}. Find A⁺: keep adding right-hand sides whose left side is already inside the set.
A dependency like BC→D only fires when the entire left side (both B and C) is already in the closure — one attribute alone does nothing.
Why a Multi-Attribute LHS Stays Locked
Having just one attribute of a composite left side does nothing. Wait until every LHS attribute is in the closure before applying the FD.
Armstrong's Axioms & Derived Rules
The three axioms derive every valid FD and nothing invalid — but in practice you rarely apply them by hand: the closure algorithm does the work.
Finding All Candidate Keys — The Shortcuts
# R(A,B,C,D,E) F = {AB→C, C→D, D→E, E→A}
RHS = {C, D, E, A} # B never appears on a RHS → B is in every key
B+ = {B} # not a superkey
AB+ = {A,B,C,D,E} ✓ # superkey; and A,C,D,E form a cycle
# each cycle attribute pairs with B → Candidate keys = {AB, BC, BD, BE}Forget the attributes that never appear on a RHS and you'll produce an incomplete or wrong set of candidate keys.
Covers — Does F Derive Every FD in G?
F covers G when every FD in G is derivable from F. Test each of G's dependencies with a closure under F.
# F = {A→B, B→C, C→D} cover G = {A→C, A→D, B→D} ?
A→C : A+ under F = {A,B,C,D} ⊇ {C} ✓
A→D : A+ under F = {A,B,C,D} ⊇ {D} ✓
B→D : B+ under F = {B,C,D} ⊇ {D} ✓
# all hold → F covers G ✓For each X→Y in G, compute X⁺ using F and check that Y ⊆ X⁺. If every one passes, F covers G.
Equivalence — Cover Must Hold Both Ways
✓ Equivalent
# F={A→B, A→C, B→C} G={A→B, B→C}
F covers G: both in F ✓
G covers F: A→C via A→B→C ✓
→ F ≡ G (A→C was redundant)✗ Not equivalent
# F={A→B, B→C} G={A→B, A→C}
F covers G: A+F={A,B,C}⊇C ✓
G covers F: B+G={B} — no C ✗
→ F ≠ G (one direction fails)F ≡ G needs cover in both directions. Checking only "F covers G" is the single most common error — you must also confirm "G covers F."
Non-Redundant Cover — Strip Implied FDs
Test each FD by removing it and checking whether the rest still derives it. If yes, it was redundant — drop it.
# F = {A→B, B→C, A→C, C→A}
A→C : remove it, A+ under {A→B, B→C, C→A} = {A,B,C} # C present → REDUNDANT, drop
A→B : remove it, A+ under {B→C, C→A} = {A} # no B → KEEP
B→C : remove it, B+ under {A→B, C→A} = {B} # no C → KEEP
C→A : remove it, C+ under {A→B, B→C} = {C} # no A → KEEP
→ Non-redundant cover = {A→B, B→C, C→A}Removing one redundant FD can restore the necessity of another. Always recompute closures against the FDs that currently survive — never against the one you're testing.
Minimal Cover — The Three-Step Algorithm
# F = {A→B, B→C, AB→C, A→C}
Step 1 single RHS ....... already single
Step 2 reduce LHS ....... B+ = {B,C} contains C, so A is extraneous in AB→C
AB→C becomes B→C (duplicate → drop)
Step 3 drop redundant ... A+ under {A→B, B→C} = {A,B,C}; C present → A→C redundant
→ Minimal cover = {A→B, B→C}Single RHS → reduce LHS → drop redundant. Doing it out of order can hide extraneous attributes or miss redundancies.
Practice 1–3 — Closure, Keys, Membership
P1: F={A→B, C→D, AB→C}. Find A⁺.
{A} →A→B {A,B} →AB→C {A,B,C}
→C→D {A,B,C,D}
A+ = {A,B,C,D} (A is a key)P3: F={A→B, B→C, C→D}. Is AC→D in F⁺?
(AC)+ = {A,C} →B {A,B,C} →D {A,B,C,D}
D present → YES, AC→D ∈ F+P2: R(A,B,C,D), F={A→B, B→C, C→A, A→D}. All candidate keys?
D on RHS, never on LHS → not in any key
A,B,C form a cycle A→B→C→A
A+ = {A,B,C,D} ✓
B+ = {B,C,A,D} ✓
C+ = {C,A,B,D} ✓
D+ = {D} ✗
→ Candidate keys = {A, B, C}When determinant attributes form a cycle (A→B→C→A), each one alone can reach the rest — so each becomes a candidate key.
Practice 6–7 — Non-Redundant & Minimal Cover
P6: make F={A→B, B→C, A→C, C→D, A→D} non-redundant.
A→C : A→B→C derives it → drop
A→D : A→B→C→D derives it → drop
rest each necessary
→ {A→B, B→C, C→D}P7: minimal cover of F={A→BC, CD→E, B→D, E→A}.
1 single RHS: A→B, A→C, CD→E, B→D, E→A
2 reduce LHS: C+={C}, D+={D} → CD both needed
3 redundant: none removable
→ {A→B, A→C, CD→E, B→D, E→A}In P7 the left side CD→E is already minimal (neither C nor D alone reaches E) and no FD is redundant — a minimal cover can equal the input once split to single RHS.
The Whole Toolkit on One Screen
| Concept | Symbol | How to compute / test |
|---|---|---|
| Attribute closure | X⁺ | Iterate FDs; a multi-attr LHS fires only when complete |
| FD-set closure | F⁺ | Never enumerate — test membership via X⁺ |
| Candidate key | — | Start with must-be-in attrs; grow until X⁺ = all |
| F covers G | G ⊆ F⁺ | Each X→Y in G: verify Y ⊆ X⁺F |
| Equivalence | F ≡ G | Cover must hold both directions |
| Minimal cover | Fc | Single RHS → reduce LHS → drop redundant |
Golden Rules
One Tool, the Whole Theory
Attribute closure is the engine of the whole relational-design toolkit: it finds candidate keys, tests covers and equivalence, and drives the minimal-cover algorithm. With a clean minimal cover in hand, you're ready for the payoff — normalization (1NF → BCNF), where these dependencies decide how tables should be split.
Never enumerate F⁺ — compute a small X⁺; a composite left side fires only when whole; and minimal cover is single-RHS, then reduce-LHS, then drop-redundant.
🧮 End of tutorial · Press ← to review, or click Restart