Equivalence of Functional Dependency Sets

In the previous page, we defined equivalence between FD sets as mutual coverage—each set covers the other. But what exactly does it mean for one FD set to cover another? This asymmetric relationship is both more fundamental and more frequently used than full equivalence.

The cover relationship answers a practical question that arises constantly in database design: Given that I have a set of FDs F, does another set G capture all the constraints that F imposes? This is subtly different from asking if F and G are equivalent—G might impose additional constraints beyond those in F.

Understanding the cover concept is essential for:

• Verifying that a simplified FD set still enforces original constraints
• Checking if decomposed relations preserve dependencies
• Computing canonical covers (minimal equivalent sets)
• Validating database migrations and schema changes

We now establish the precise mathematical definition of what it means for one FD set to cover another.

Definition: FD Set Cover

Let F and G be two sets of functional dependencies over the same attribute set U. We say that F covers G (also written as F ⊇ₗ G, or "F logically contains G") if and only if every functional dependency in G can be derived from F.

Formally:

$$F\ \text{covers}\ G \iff G^+ \subseteq F^+$$

Equivalently:

$$F\ \text{covers}\ G \iff \forall (X \to Y) \in G : (X \to Y) \in F^+$$

In words: F covers G if every FD that is in G's closure is also in F's closure. Since G ⊆ G⁺, this means every FD explicitly in G, plus every FD derivable from G, must be derivable from F.

Relationship to Equivalence

Recall that F ≡ G (equivalence) means F⁺ = G⁺. The cover relationship gives us:

• F covers G means G⁺ ⊆ F⁺
• G covers F means F⁺ ⊆ G⁺
• F ≡ G means F covers G AND G covers F

Thus equivalence is mutual coverage, while the cover relationship itself is asymmetric.

Simplified Testing (Key Optimization)

To test if F covers G, we don't need to compute full closures. It suffices to check that, for each FD (X → Y) ∈ G, the right-hand side Y is contained in the attribute closure of X under F:

$$F\ \text{covers}\ G \iff \forall (X \to Y) \in G : Y \subseteq X^+_F$$

This is because (X → Y) ∈ F⁺ if and only if Y ⊆ X⁺_F.

A critical aspect of the cover relationship is its asymmetry. Just because F covers G does not mean G covers F. Understanding this asymmetry is essential for correctly reasoning about FD set relationships.

Example Demonstrating Asymmetry

Consider attributes {A, B, C} with:

Does F cover G?

We check if A → B (the only FD in G) is derivable from F:

• Compute {A}⁺_F = {A, B, C} (starting with A, we get B from A → B, then C from B → C)
• Is B ⊆ {A, B, C}? Yes.

✓ F covers G.

Does G cover F?

We check each FD in F:

1. A → B: Compute {A}⁺_G = {A, B} (starting with A, we get B from A → B)

   • Is B ⊆ {A, B}? Yes. ✓

2. B → C: Compute {B}⁺_G = {B} (starting with B, no FD in G has B on the left)

   • Is C ⊆ {B}? No! ✗

✗ G does not cover F.

The relationship is asymmetric: F covers G, but G does not cover F.

Visualizing Asymmetry

We can visualize the relationship between F and G's closures:

The Venn-like diagram shows that G⁺ is a proper subset of F⁺. F covers G (everything in G⁺ is in F⁺), but G doesn't cover F (things in F⁺ are not in G⁺).

The cover relationship is intimately connected to logical implication of functional dependencies. Understanding this connection deepens our theoretical grasp and clarifies practical applications.

Logical Implication of a Single FD

We say that F logically implies a functional dependency X → Y (written F ⊨ X → Y) if every relation instance that satisfies all FDs in F must also satisfy X → Y.

By the soundness and completeness of Armstrong's axioms:

$$F \vDash (X \to Y) \iff (X \to Y) \in F^+$$

Cover as Universal Implication

F covers G if and only if F logically implies every FD in G:

$$F\ \text{covers}\ G \iff \forall (X \to Y) \in G : F \vDash (X \to Y)$$

Since Armstrong's axioms are sound and complete, this is equivalent to:

$$F\ \text{covers}\ G \iff \forall (X \to Y) \in G : (X \to Y) \in F^+$$

The Role of Trivial FDs

Recall that a trivial FD is one of the form X → Y where Y ⊆ X. Trivial FDs are in every closure and are always satisfied. They play a subtle role in coverage:

• Every FD set covers all trivial FDs (they're in every closure)
• When checking if F covers G, trivial FDs in G are automatically covered
• In practice, we often focus on non-trivial FDs when reasoning about coverage

Minimal Cover Intuition

If F covers G and F has fewer or simpler FDs than G, then F is a more efficient representation. This leads to the concept of minimal cover or canonical cover—the smallest F that covers (and is covered by) the original FD set.

We can characterize a minimal cover as an FD set that:

1. Covers the original set (imposes all original constraints)
2. Is covered by the original set (doesn't impose extra constraints)
3. Has no redundant FDs (removing any FD would break coverage)
4. Has no extraneous attributes (simplest possible left and right sides)

Let's work through several examples of increasing complexity to build solid intuition for the cover relationship.

Example 1: Simple Cover Check

Let U = {A, B, C, D} with:

• F = {A → B, B → C, C → D}
• G = {A → D}

Question: Does F cover G?

Solution: Check if A → D is derivable from F:

• Compute {A}⁺_F:
  • Start: {A}
  • Apply A → B: {A, B}
  • Apply B → C: {A, B, C}
  • Apply C → D: {A, B, C, D}
• Is D ⊆ {A, B, C, D}? Yes.

✓ F covers G.

Example 2: Cover Check with Composite LHS

Let U = {A, B, C, D} with:

• F = {A → B, C → D}
• G = {AC → BD}

Question: Does F cover G?

Solution: Check if AC → BD is derivable from F:

• Compute {A, C}⁺_F:
  • Start: {A, C}
  • Apply A → B: {A, B, C}
  • Apply C → D: {A, B, C, D}
• Is BD ⊆ {A, B, C, D}? Yes.

✓ F covers G.

Note: Even though F has FDs with single-attribute LHS, it can derive an FD with composite LHS.

Example 3: Non-Cover Scenario

Let U = {A, B, C, D} with:

• F = {A → B, C → D}
• G = {A → B, B → C}

Question: Does F cover G?

Solution: Check each FD in G:

1. A → B: Compute {A}⁺_F:

   • Start: {A}
   • Apply A → B: {A, B}
   • (C → D doesn't apply, A and B not on LHS)
   • Is B ⊆ {A, B}? Yes. ✓

2. B → C: Compute {B}⁺_F:

   • Start: {B}
   • (A → B doesn't apply, A not subset of {B})
   • (C → D doesn't apply, C not subset of {B})
   • Final: {B}
   • Is C ⊆ {B}? No! ✗

✗ F does NOT cover G.

F cannot derive B → C because no FD in F has B on the left-hand side.

Example 4: Mutual Coverage (Equivalence)

Let U = {A, B, C} with:

• F = {A → BC}
• G = {A → B, A → C}

Question: Do F and G mutually cover each other?

Does F cover G?

• A → B: {A}⁺_F = {A, B, C}. B ⊆ {A,B,C}? Yes. ✓
• A → C: {A}⁺_F = {A, B, C}. C ⊆ {A,B,C}? Yes. ✓

✓ F covers G.

Does G cover F?

• A → BC: {A}⁺_G:
  • Start: {A}
  • Apply A → B: {A, B}
  • Apply A → C: {A, B, C}
  • Is BC ⊆ {A,B,C}? Yes. ✓

✓ G covers F.

Conclusion: F ≡ G (they are equivalent).

This confirms the decomposition rule: an FD with composite RHS is equivalent to multiple FDs with singleton RHS.

One of the most important applications of the cover concept is in dependency-preserving decomposition. When we decompose a relation into smaller relations, we need to ensure that the FDs that can be enforced on the decomposed relations collectively cover the original FDs.

The Decomposition Problem

Consider a relation R with attribute set U and FD set F. When we decompose R into R₁, R₂, ..., Rₙ with attribute sets U₁, U₂, ..., Uₙ, each Rᵢ can only enforce FDs that involve attributes entirely within Uᵢ.

Let Fᵢ = π_{Uᵢ}(F) be the projection of F onto Uᵢ—the set of FDs in F⁺ that involve only attributes in Uᵢ.

The decomposition is dependency-preserving if:

$$(F_1 \cup F_2 \cup ... \cup F_n)^+ \supseteq F^+$$

That is, the union of projected FD sets covers the original FD set.

Example: Dependency-Preserving Decomposition

Consider R(A, B, C) with F = {A → B, B → C}.

Decompose into:

• R₁(A, B) with F₁ = {A → B}
• R₂(B, C) with F₂ = {B → C}

Check: Does F₁ ∪ F₂ = {A → B, B → C} cover F = {A → B, B → C}?

Each FD in F is in F₁ ∪ F₂, so trivially yes.

✓ This decomposition is dependency-preserving.

Example: Non-Preserving Decomposition

Consider R(A, B, C) with F = {A → B, B → C, A → C}.

Suppose we decompose into:

• R₁(A, B) with F₁ = {A → B}
• R₂(A, C) with F₂ = {A → C}

Check: Does F₁ ∪ F₂ = {A → B, A → C} cover F?

• A → B: Is B ⊆ {A}⁺_{F₁∪F₂}? {A}⁺ = {A, B, C}. Yes. ✓
• B → C: Is C ⊆ {B}⁺_{F₁∪F₂}? {B}⁺ = {B}. No! ✗
• A → C: Is C ⊆ {A}⁺_{F₁∪F₂}? {A}⁺ = {A, B, C}. Yes. ✓

The FD B → C cannot be derived from F₁ ∪ F₂.

✗ This decomposition is not dependency-preserving.

The constraint "every B value determines a C value" is lost. It cannot be enforced by looking at R₁ and R₂ separately.

While the theoretical definition of coverage involves closures of potentially exponential size, practical cover testing is highly efficient due to the attribute closure technique.

Time Complexity Analysis

To test if F covers G:

1. For each FD (X → Y) in G, compute X⁺_F
2. Check if Y ⊆ X⁺_F

Let:

• |G| = number of FDs in G = m
• |F| = number of FDs in F = n
• |U| = number of attributes = k

Each attribute closure computation takes O(n × k) time (we iterate over FDs in F up to k times until fixed point).

For m FDs in G, total time is O(m × n × k).

This is polynomial time, making cover testing practical even for large schemas.

Optimization: Early Termination

When checking if F covers G, we can short-circuit as soon as we find a single FD in G that isn't derivable from F:

• If G has many FDs, we might terminate after just one or two closure computations
• In practice, cover tests during canonical cover computation often fail early, saving significant work

Optimization: Caching Closures

If we need to test coverage repeatedly (e.g., during an iterative canonical cover algorithm), we can cache computed attribute closures:

• If an FD X → Y is removed from F, closures might shrink; invalidate cache entries containing X
• If an FD is added, closures might grow; invalidation is more complex

For one-time cover tests, caching adds overhead, but for iterative algorithms, it can provide significant speedup.

The cover relation has several important mathematical properties that are essential for reasoning about FD sets.

Reflexivity

Every FD set covers itself: F covers F.

This is trivially true since F⁺ ⊆ F⁺.

Transitivity

If F covers G and G covers H, then F covers H.

Proof: G⁺ ⊆ F⁺ and H⁺ ⊆ G⁺ implies H⁺ ⊆ F⁺.

Anti-symmetry (Up to Equivalence)

If F covers G and G covers F, then F ≡ G.

This follows directly from the definition: G⁺ ⊆ F⁺ and F⁺ ⊆ G⁺ implies F⁺ = G⁺.

These properties make the cover relation a preorder (a reflexive, transitive relation) on FD sets, with equivalence classes defined by mutual coverage.

Additional Properties

The cover concept is a fundamental building block in FD theory, underlying equivalence, canonical covers, and dependency preservation. Let's consolidate the key insights.

What's Next:

With the cover concept firmly established, we're now equipped to tackle the next topic: Deriving FDs. We'll explore systematic methods for deducing new functional dependencies from a given set, using Armstrong's axioms and their derived rules. This combines with our coverage understanding to form the complete theoretical toolkit for FD analysis.