Equivalence of Functional Dependency Sets

Functional dependencies, like mathematical statements, have an inner logic that allows us to derive new dependencies from existing ones. This derivation process is not arbitrary—it follows precise inference rules that are guaranteed to produce only valid conclusions.

The ability to derive FDs is essential for:

• Computing the complete closure of an FD set
• Identifying redundant dependencies
• Finding candidate keys systematically
• Proving that two FD sets are equivalent
• Understanding why certain constraints follow from others

In this page, we master the inference machinery that powers all FD analysis—Armstrong's axioms and their derived rules.

Armstrong's axioms are the three fundamental inference rules from which all FD derivation flows. Though introduced in an earlier module, we review them here with a focus on their application in derivation.

The Three Axioms

Soundness and Completeness

Armstrong's axioms have two crucial properties:

1. Soundness: Every FD derivable using the axioms is logically valid—it holds in every relation that satisfies the original FDs.

2. Completeness: Every FD that logically follows from a set F can be derived using the axioms—nothing valid is missed.

Together, these properties mean the axioms give us exactly the right set of derivable FDs, no more and no less.

$$\text{F} \vdash (X \to Y) \iff \text{F} \vDash (X \to Y)$$

where ⊢ means "can derive" (syntactic) and ⊨ means "logically implies" (semantic).

While Armstrong's three axioms are sufficient to derive any valid FD, they can be cumbersome to apply step-by-step. Several derived rules provide convenient shortcuts. Each derived rule can be proven from the axioms.

Rule 4: Union (Additive) Rule

If X → Y and X → Z, then X → YZ.

Proof from axioms:

1. X → Y (given)
2. X → Z (given)
3. X → XY (augment step 1 with X)
4. XY → YZ (augment step 2 with Y)
5. X → YZ (transitivity on steps 3 and 4)

Rule 5: Decomposition (Projective) Rule

If X → YZ, then X → Y and X → Z.

Proof from axioms:

1. X → YZ (given)
2. YZ → Y (reflexivity, since Y ⊆ YZ)
3. X → Y (transitivity on steps 1 and 2)
4. YZ → Z (reflexivity, since Z ⊆ YZ)
5. X → Z (transitivity on steps 1 and 4)

Rule 6: Pseudotransitivity Rule

If X → Y and WY → Z, then WX → Z.

Proof from axioms:

1. X → Y (given)
2. WY → Z (given)
3. WX → WY (augment step 1 with W)
4. WX → Z (transitivity on steps 3 and 2)

Rule 7: Composition Rule

If X → Y and Z → W, then XZ → YW.

Proof from axioms:

1. X → Y (given)
2. Z → W (given)
3. XZ → YZ (augment step 1 with Z)
4. YZ → YW (augment step 2 with Y)
5. XZ → YW (transitivity on steps 3 and 4)

Deriving FDs requires a systematic approach. While intuition helps identify likely derivable FDs, a formal process ensures correctness.

The Derivation Question

Given an FD set F and a potential FD X → Y, we want to determine: Can X → Y be derived from F?

Method 1: Direct Proof

Construct a sequence of FDs, each either in F or derived from previous ones using inference rules, ending with X → Y.

Method 2: Attribute Closure

Compute X⁺_F (the attribute closure of X under F). If Y ⊆ X⁺_F, then X → Y is derivable.

This method is faster and less error-prone for verification. It works because:

$$X \to Y \in F^+ \iff Y \subseteq X^+_F$$

Example: Complete Derivation

Given F = {A → B, B → C, CD → E} over U = {A, B, C, D, E}.

Claim: AD → E is derivable from F.

Direct Proof:

Verification via Attribute Closure:

Compute {A, D}⁺_F:

• Start: {A, D}
• Apply A → B: {A, B, D}
• Apply B → C: {A, B, C, D}
• Apply CD → E: {A, B, C, D, E}

Is E ⊆ {A, B, C, D, E}? Yes. ✓

Both methods confirm AD → E is derivable.

Experienced database designers recognize recurring patterns in FD derivation. Internalizing these patterns accelerates analysis.

Pattern 1: Transitive Chains

If A → B, B → C, C → D, ..., then A → X for any X in the chain.

This is repeated application of transitivity. The attribute closure of A includes everything reachable via the chain.

Pattern 2: Parallel Determination

If A → B and A → C, then A → BC (union rule).

This shows that if A determines multiple attributes independently, it determines all of them together.

Pattern 3: Key Extension

If X is a superkey (X → U where U is all attributes) and W is any subset, then XW → U as well.

Augmenting a superkey with additional attributes still yields a superkey. This is why candidate keys are minimal superkeys—we can't remove any attribute without losing the superkey property.

Pattern 4: Composite LHS Building

To derive X → Z where the path goes through an FD with composite LHS, use augmentation:

If A → B and BC → D, then AC → D.

Derivation:

1. A → B (given)
2. AC → BC (augment with C)
3. BC → D (given)
4. AC → D (transitivity)

This is actually pseudotransitivity: from A → B and BC → D, derive AC → D.

Pattern 5: Decomposition for Targeted Derivation

To check if X → A (a single attribute), use closure:

Rather than deriving X → AB...C and then decomposing, just compute X⁺ and check if A ∈ X⁺.

This leverages the fact that X → A iff A ∈ X⁺, avoiding unnecessary derivation of compound FDs.

Complex derivations can be visualized as derivation trees, where each node represents an FD and edges connect premises to conclusions.

Example: Derivation Tree

Given F = {A → B, B → C, A → D, CD → E}, derive A → E.

textual derivation:

1. A → B (given)
2. B → C (given)
3. A → C (transitivity: 1, 2)
4. A → D (given)
5. A → CD (union: 3, 4)
6. CD → E (given)
7. A → E (transitivity: 5, 6)

Reading the Tree:

• Leaf nodes are given FDs or trivial reflexivity applications
• Internal nodes are derived FDs
• Edges show which FDs were used as premises for each derivation step
• Root is the target FD we're proving

Benefits of Derivation Trees:

1. Clarity — Visual structure shows the logical flow
2. Verification — Easy to check each step is valid
3. Dependency tracking — See exactly which given FDs are needed for the conclusion
4. Minimality analysis — If a leaf FD can be removed without breaking the tree, it wasn't necessary for this particular derivation

One of the most important applications of FD derivation is finding candidate keys. A candidate key K is a minimal set of attributes such that K → U (K determines all attributes).

The Key-Finding Strategy

To find candidate keys:

1. Identify attributes that never appear on the RHS of any FD—these must be in every candidate key
2. Identify attributes that only appear on the RHS—these are never in any candidate key
3. Start with the must-have attributes and try to extend them to determine all attributes
4. Verify minimality by checking that no proper subset also determines all attributes

Example: Finding Candidate Keys

Let U = {A, B, C, D, E} with F = {A → B, BC → D, D → E}.

Step 1: Classify attributes

Step 2: Start with must-have attributes

Candidate must include A and C. Try {A, C}:

{A, C}⁺ = ?

• Start: {A, C}
• Apply A → B: {A, B, C}
• Apply BC → D: {A, B, C, D}
• Apply D → E: {A, B, C, D, E} = U

{A, C}⁺ = U, so AC is a superkey.

Step 3: Check minimality

• {A}⁺ = {A, B} ≠ U (not a superkey)
• {C}⁺ = {C} ≠ U (not a superkey)

Neither A nor C alone is a superkey, so AC is minimal.

Conclusion: AC is a candidate key.

Not all FDs can be derived, and not all attributes are reachable from arbitrary starting points. Understanding what cannot be derived is as important as knowing what can.

Definition: Undetermined Attribute

An attribute A is undetermined by a set X under F if A ∉ X⁺_F. This means no sequence of derivations from F can establish X → A.

Why Attributes Remain Undetermined

An attribute A is unreachable from X if:

1. A never appears on RHS of any FD — No FD determines A; it can only be determined by itself or superkeys containing it.

2. Path to A is blocked — The FD(s) that determine A have LHS attributes not in X⁺.

Example: Unreachable Attributes

Let U = {A, B, C, D} with F = {A → B, C → D}.

Compute {A}⁺:

• Start: {A}
• Apply A → B: {A, B}
• (C → D doesn't apply; C not in closure)
• Final: {A, B}

Attributes C and D are undetermined from A. There's no chain of FDs connecting A to C or D.

This tells us:

• A → C is NOT derivable from F
• A → D is NOT derivable from F
• Neither C nor D can be reached without having C in the starting set

Proof of Non-derivability

To prove X → A is NOT derivable from F:

1. Compute X⁺_F completely
2. Show A ∉ X⁺_F
3. Conclude X → A ∉ F⁺

By completeness of Armstrong's axioms, if X → A is not in F⁺, it cannot be derived—period. There's no hidden proof we might be missing.

The ability to derive FDs is a core competency in database theory. With Armstrong's axioms and their derived rules, we have a complete and sound inference system for functional dependencies.

What's Next:

Now that we can derive FDs fluently, we're ready to address a practical question: Given two FD sets, how do we systematically test if they're equivalent? The next page covers Testing Equivalence—efficient algorithms for determining whether two FD sets impose identical constraints.