Minimal Cover

Definition

A minimal cover (also called a canonical cover) of a set of functional dependencies F is an equivalent set F_min such that:

1. Every FD in F_min has a single attribute on the right-hand side.
2. No FD in F_min has an extraneous attribute on the left-hand side (removing any LHS attribute would change what the FD determines).
3. No FD in F_min is redundant (removable without changing the closure of the whole set — i.e., it's already implied by the others).

F_min is equivalent to F (same overall closure behavior) but contains no wasted or derivable information — every FD in it is necessary.

A Naive (Non-Minimal) Starting Set

Suppose a junior designer, working from the running example, wrote down these "obvious-looking" dependencies instead of the clean set from 21.5:

G1: StudentID -> StudentName
G2: CourseID -> CourseName
G3: CourseID -> InstructorID
G4: InstructorID -> InstructorName
G5: InstructorID -> InstructorOffice
G6: CourseID -> InstructorName          (added because "C1 always implies Dr. Rao")
G7: CourseID -> InstructorOffice        (added because "C1 always implies Room 204")
G8: {StudentID, CourseID} -> EnrollmentDate
G9: {StudentID, CourseID} -> StudentName (added out of habit, thinking "the whole key determines everything")

Reducing G to Its Minimal Cover

Step 1 — check for extraneous left-hand-side attributes. Look at G9: {StudentID, CourseID} -> StudentName. Does StudentID alone already determine StudentName? Yes (G1). So CourseID is extraneous in G9 — it reduces to StudentID -> StudentName, which is now a duplicate of G1. Drop G9.

Step 2 — check for redundant FDs (right-hand side already derivable from the rest). Is G6 (CourseID -> InstructorName) implied by the remaining set? Compute {CourseID}+ using only G2, G3, G4, G5, G8: it reaches InstructorID (via G3) then InstructorName (via G4) — so CourseID -> InstructorName is already derivable transitively. G6 is redundant — drop it. By identical reasoning, {CourseID}+ also reaches InstructorOffice via G5, so G7 is redundant too — drop it.

Step 3 — confirm single-attribute RHS. All remaining FDs (G1-G5, G8) already have single-attribute right-hand sides — no splitting needed.

Result — the minimal cover:

StudentID -> StudentName
CourseID -> CourseName
CourseID -> InstructorID
InstructorID -> InstructorName
InstructorID -> InstructorOffice
{StudentID, CourseID} -> EnrollmentDate

This is exactly the clean FD set (F1-F6) used throughout 21.5-21.10 — it was the minimal cover all along; G6, G7, and G9 were noise that added no new information.

Why Minimal Cover Matters

Schema-design algorithms (like the standard 3NF synthesis algorithm) operate directly on a minimal cover — feeding them a redundant FD set can produce extra, unnecessary tables or miss the true dependency structure. Minimal cover is also what makes candidate-key derivation (21.10) and normal-form checking tractable: reasoning about 6 necessary FDs is far easier than reasoning about 9 FDs, three of which say nothing new.

Edge Cases

• A relation can have more than one valid minimal cover (the reduction order can matter in more complex FD sets) — but all valid minimal covers are equivalent in the total closure they produce, even if they look syntactically different.
• Removing an FD is only valid if the closure of the entire remaining set is unchanged — you must recompute closures after each removal, not just visually guess "this looks redundant."

Key Takeaways / Interview Angle

• Q: List the three properties a minimal cover must have. Singleton right-hand sides, no extraneous left-hand-side attributes, no redundant (derivable) FDs.
• Q: Why was CourseID -> InstructorName dropped from the naive set? Because it's already implied transitively by CourseID -> InstructorID and InstructorID -> InstructorName — keeping it added no new information.
• Q: What is minimal cover used for in practice? As the clean input to normalization algorithms (3NF synthesis, candidate key finding) — garbage (redundant/extraneous) FDs in, garbage schemas out.