Canonical Cover: Minimizing Functional Dependencies

When analyzing a database schema, you often discover numerous functional dependencies (FDs). These dependencies may have been gathered from domain experts, inferred from existing data, or derived through formal analysis. However, raw FD sets typically contain significant redundancy—dependencies that can be derived from others, attributes that are unnecessarily included, or multiple ways of expressing the same constraint.

This redundancy isn't just inelegant—it's actively harmful for database design. Redundant FDs lead to:

• Confusion during normalization: Multiple equivalent decompositions obscure the "correct" design
• Inefficient integrity checking: Enforcing redundant constraints wastes computational resources
• Maintenance nightmares: Updating one FD requires updating logically equivalent ones
• Design ambiguity: Teams cannot agree on the essential constraints that govern the schema

The solution is minimization: reducing an FD set to its essential, non-redundant form while preserving all the information it contains. The result is called a minimal cover or canonical cover—a streamlined representation that is equivalent to the original but contains no unnecessary elements.

Before defining minimal cover, we must understand what makes an FD set redundant. Redundancy in functional dependencies takes several distinct forms, each requiring specific treatment.

Type 1: Completely Derivable FDs

An FD is completely derivable when it can be derived from other FDs in the set using Armstrong's axioms. For example:

• Given: A → B and B → C
• By transitivity: A → C is derivable

If all three FDs are in your set, A → C is redundant because removing it doesn't change what can be derived from the remaining FDs.

Type 2: Partially Redundant Determinants

Sometimes a determinant (left-hand side) contains more attributes than necessary. For example:

• If A → C holds in your set
• Then AB → C is partially redundant—the B is extraneous because A alone determines C

Type 3: Partially Redundant Dependents

Sometimes a dependent (right-hand side) includes attributes that can be determined through other paths. For example:

• If A → B, A → C, and A → BC are all in your set
• Then A → BC is partially redundant—it can be derived from the union of A → B and A → C

Two FD sets are equivalent if and only if they have exactly the same closure—that is, they can derive the same set of functional dependencies.

Formal Definition:

Let F and G be two sets of functional dependencies over schema R.

• F covers G if every FD in G can be derived from F (i.e., G⁺ ⊆ F⁺)
• G covers F if every FD in F can be derived from G (i.e., F⁺ ⊆ G⁺)
• F and G are equivalent (F ≡ G) if F covers G and G covers F (i.e., F⁺ = G⁺)

Example:

Consider the following two FD sets over R = {A, B, C, D}:

F = {A → BC, B → D, AB → D}
G = {A → B, A → C, B → D}

Are F and G equivalent?

Testing if G covers F:

• A → BC: From G, we have A → B and A → C. By union, A → BC. ✓
• B → D: This is directly in G. ✓
• AB → D: From G, B → D. By augmentation (trivially true), if B → D then AB → D. ✓

Testing if F covers G:

• A → B: From F, A → BC and by decomposition A → B. ✓
• A → C: From F, A → BC and by decomposition A → C. ✓
• B → D: This is directly in F. ✓

Since each covers the other, F ≡ G. They are equivalent sets.

Testing Equivalence Algorithmically:

To test if F covers G:

1. For each FD X → Y in G
2. Compute X⁺ under F
3. Check if Y ⊆ X⁺

If this holds for all FDs in G, then F covers G.

To test equivalence, perform this test in both directions.

Practical Implications:

Equivalence means we can replace one FD set with another without losing any constraints. This is crucial because:

1. During normalization, we simplify FDs but must ensure the schema enforces the same constraints
2. When merging schemas, equivalent FD sets can be combined
3. For optimization, simpler equivalent sets are computationally cheaper to enforce

A minimal cover (also called canonical cover) of a set of functional dependencies F is a set Fc that satisfies the following conditions:

Condition 1: Equivalence

Fc ≡ F (Fc and F have the same closure)

Condition 2: Single Attribute on Right-Hand Side

Every FD in Fc has exactly one attribute on its right-hand side. Instead of A → BC, we write A → B and A → C.

Condition 3: No Extraneous Left-Hand Attributes

For every FD X → A in Fc, no proper subset of X determines A. That is, we cannot remove any attribute from X and still derive A using Fc.

Condition 4: No Redundant FDs

No FD in Fc is derivable from the other FDs in Fc. If we remove any FD from Fc, the closure changes.

Mathematical Formulation:

Fc is a minimal cover of F if and only if:
1. (Fc)⁺ = F⁺
2. ∀(X → A) ∈ Fc: |A| = 1
3. ∀(X → A) ∈ Fc, ∀Y ⊂ X: A ∉ Y⁺ under Fc
4. ∀(X → A) ∈ Fc: A ∉ X⁺ under (Fc - {X → A})

The requirement that each FD in a minimal cover has exactly one attribute on the right-hand side might seem arbitrary. After all, A → BC and the pair {A → B, A → C} are semantically equivalent by the union/decomposition rules. So why insist on the decomposed form?

Reason 1: Uniform Representation

With single-attribute RHS, every FD has a standardized form: X → A where A is a single attribute. This uniformity simplifies algorithms—there's no need to handle different cases for single vs. multiple attributes.

Reason 2: Precise Redundancy Detection

Consider A → BC where only A → B is essential (because A → C follows from other FDs). With multi-attribute RHS, we'd need to reason about partial redundancy of the right side. With single-attribute RHS, we simply check if each separate FD is redundant.

Reason 3: Extraneous Attribute Analysis

Analyzing AB → C for extraneous left attributes is simpler when C is a single attribute. If C were CD, we'd need to analyze extraneous attributes relative to each of C and D separately.

Reason 4: Normalization Compatibility

The 3NF synthesis algorithm creates one relation for each FD in the minimal cover. With single-attribute RHS, this mapping is direct. With multi-attribute RHS, additional decomposition would be needed.

It's important to distinguish between an equivalent cover (any FD set equivalent to the original) and a minimal cover (an equivalent set satisfying all minimality conditions).

Equivalent Cover:

Any FD set G where G ≡ F. There are infinitely many equivalent covers:

F = {A → B, B → C}

Equivalent covers include:
- {A → B, B → C} (same as F)
- {A → B, B → C, A → C} (adds transitively derived FD)
- {A → B, B → C, AB → C, ABC → C, ...} (all derivable FDs)

All of these are valid equivalent covers, but only the first is minimal.

Minimal Cover:

A minimal cover is the "tightest" equivalent cover—one where nothing can be removed or simplified without changing the closure. It's the essential core of the FD set.

Why "Minimal"?

The term "minimal" refers to:

1. Minimal number of FDs (no redundant FDs)
2. Minimal attributes on LHS (no extraneous attributes)
3. Minimal representation of RHS (single attribute)

Note that "minimal" does NOT mean the minimum possible number of FDs. Different orderings of the algorithm may produce minimal covers with different numbers of FDs (though they're always equivalent).

Minimal covers have several important properties that make them useful in database design and normalization theory.

Property 1: Existence

Every finite set of FDs has at least one minimal cover. This is guaranteed by the algorithm (covered in a later page) which always terminates with a valid minimal cover.

Property 2: Non-Uniqueness

A set of FDs may have multiple distinct minimal covers. Different processing orders during minimization can lead to different results.

Example:

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

Minimal cover 1: {A → B, B → A, A → C}
Minimal cover 2: {A → B, B → A, B → C}

Both are valid minimal covers because:

• In cover 1: B → C can be derived as B → A → C
• In cover 2: A → C can be derived as A → B → C

Property 3: Equivalence Among Minimal Covers

All minimal covers of F are equivalent to each other (and to F). If Fc1 and Fc2 are both minimal covers of F, then Fc1 ≡ Fc2 ≡ F.

Property 4: Attribute Preservation

A minimal cover never introduces new attributes. If Fc is a minimal cover of F, then all attributes appearing in Fc also appear in F.

Property 5: Closure Preservation

For any attribute set X appearing in F, the attribute closure X⁺ is identical whether computed under F or under any minimal cover of F.

Minimal cover computation is not merely an academic exercise—it's a critical step in practical database schema design.

3NF Synthesis Algorithm

The standard algorithm for achieving Third Normal Form (3NF) directly uses the minimal cover:

1. Compute minimal cover Fc of the original FD set F
2. For each FD X → A in Fc, create a relation with attributes X ∪ {A}
3. If no relation contains a candidate key, add one

Without minimal cover, this algorithm would create redundant tables (one for each redundant FD) and tables with extraneous columns (from extraneous LHS attributes).

BCNF Decomposition

While BCNF decomposition uses a different approach, starting from a minimal cover simplifies analysis by ensuring you work with truly essential dependencies.

Constraint Enforcement

Database systems must enforce FD constraints (either explicitly or through key definitions). A minimal set of constraints is:

• Cheaper to check (fewer constraints to verify)
• Easier to maintain (fewer definitions to update)
• Less likely to have inconsistencies (no redundant definitions)

Schema Documentation

Minimal covers provide the clearest documentation of a schema's constraints. Instead of listing dozens of FDs (many derivable from others), you document only the essential ones.

Let's work through a complete example that we'll continue developing throughout this module.

Scenario:

A university course registration system has the following relation:

Registration(StudentID, CourseID, InstructorID, Semester, Grade, StudentName, 
             CourseTitle, InstructorName, DepartmentID, DepartmentName)

The domain experts have identified these functional dependencies:

F = {
  StudentID → StudentName,
  CourseID → CourseTitle,
  CourseID → DepartmentID,
  InstructorID → InstructorName,
  DepartmentID → DepartmentName,
  CourseID → DepartmentName,                    // Derivable!
  StudentID, CourseID → Grade,
  StudentID, CourseID, Semester → Grade,        // Extraneous LHS!
  StudentID, CourseID → InstructorID,
  StudentID, CourseID → Semester,
}

Identifying Redundancy:

1. CourseID → DepartmentName is derivable:

   • CourseID → DepartmentID and DepartmentID → DepartmentName
   • By transitivity: CourseID → DepartmentName ✓

2. StudentID, CourseID, Semester → Grade has extraneous LHS:

   • StudentID, CourseID → Grade already exists
   • Semester is extraneous on the LHS

This FD set needs minimization!

In the subsequent pages, we'll learn exactly how to transform this into a minimal cover and why each step is performed.

We've established the foundational concepts necessary for computing minimal covers. Let's consolidate the key points:

What's Next:

Now that you understand what minimal cover means and why it matters, the next page examines extraneous attributes in detail. You'll learn exactly how to identify attributes on the left-hand side that can be removed without changing the FD set's closure—a critical step in the canonical cover algorithm.