Closure & Armstrong’s Axioms

To determine if a table is in 2NF, 3NF, or BCNF, you need to calculate the Closure of attribute sets using Armstrong’s Axioms. These are the mathematical foundations of normalization.

---

Learning Objectives

After completing this chapter, you will be able to:

• Apply Armstrong’s Axioms to derive new FDs.
• Calculate the closure of any attribute set.
• Use closure to find candidate keys.
• Understand Canonical Cover and extraneous attributes.
• Determine the minimal set of FDs.
• Answer interview questions on closure and axioms.

---

Armstrong’s Axioms

These are the fundamental rules — sound and complete — for deriving new FDs from existing ones.

Axiom	Rule	Example
Reflexivity	If Y ⊆ X, then X → Y	{A,B} → {A} (if B is a subset of A, trivially true)
Augmentation	If X → Y, then XZ → YZ	A → B implies AC → BC
Transitivity	If X → Y and Y → Z, then X → Z	A → B and B → C implies A → C

Additional Rules (Derived from Axioms)

Rule	Derivation
Union	If X → Y and X → Z, then X → YZ
Decomposition	If X → YZ, then X → Y and X → Z
Pseudo-Transitivity	If X → Y and WY → Z, then WX → Z

---

Attribute Closure (X⁺)

The Closure of an attribute set X, written X⁺, is the set of ALL attributes that can be functionally determined by X.

Algorithm

closure = X
while closure changes:
    for each FD Y → Z in the set:
        if Y ⊆ closure:
            closure = closure ∪ Z
return closure

Step-by-Step Example

Given: R(A, B, C, D, E) with FDs: A → B, A → C, BC → D, D → E

Calculate A⁺:

Step	Closure	Applied FD
1	{A}	Start
2	{A, B}	A → B
3	{A, B, C}	A → C
4	{A, B, C, D}	BC → D (BC ⊆ closure)
5	{A, B, C, D, E}	D → E

Result: A⁺ = {A, B, C, D, E} = all attributes

Conclusion: A is a Candidate Key (A⁺ contains all attributes, and no subset of A does the same since A is a single attribute).

---

Using Closure to Find Candidate Keys

Steps

1. Identify attributes that never appear on the right side of any FD (they MUST be in every candidate key).
2. Calculate the closure of this set.
3. If the closure ≠ all attributes, add other attributes one by one and recalculate.

Example

R(A, B, C, D, E) with FDs: A → B, BC → E, DE → A

Step 1: Attributes on right side: {B, E, A}. Attributes never on right: {C, D}. So every candidate key must contain {C, D}.

Step 2: Calculate {C, D}⁺:

Step	Closure	FD
1	{C, D}	Start
2	{C, D}	No FD applies (C and D alone don’t determine anything)

{CD}⁺ = {C, D} ≠ all attributes. So {C, D} is NOT a candidate key.

Step 3: Try {C, D, A}: {ACD}⁺ = {A, C, D} → using A → B = {A, B, C, D} → using BC → E = {A, B, C, D, E}

{ACD}⁺ = all attributes. Since no subset of {A, C, D} gives all attributes, {A, C, D} is a candidate key.

---

Extraneous Attributes

An attribute in an FD is extraneous if removing it doesn’t change the closure of the FD set.

Type	Example	Extraneous?
Left-side extraneous	AB → C but A → C already holds	B is extraneous on the left
Right-side extraneous	A → BC but A → B and A → C separately	Splitting FDs removes right-side redundancy

---

Canonical Cover (Minimal Cover)

A Canonical Cover Fc is the minimal set of FDs equivalent to the original set F.

Properties:

• No FD in Fc has extraneous attributes
• The left side of each FD is unique
• No FD can be derived from the others

Algorithm

Fc = F
1. Split each FD (decompose right sides) ⇒ single attribute on right
2. Remove extraneous attributes from left sides
3. Remove redundant FDs (those derivable from others)
return Fc

Example

Original: {AB → C, A → B, B → C}

1. Already split (single attributes on right)
2. In AB → C, is B extraneous? Check if A → C can be derived from A → B, B → C. Yes (transitivity). So AB → C becomes A → C
3. Is A → C redundant? Check if it’s derivable from A → B, B → C. Yes. But wait — if we remove it, we lose A → C. Since it’s directly derivable, we check: compute closure of A using remaining FDs {A → B, B → C} — {A, B, C}. Yes, A → C holds. So A → C is redundant.

Fc = {A → B, B → C}

---

Why Closure Matters in Normalization

Normal Form	Closure Check
2NF	Check if any non-prime attribute is partially dependent — i.e., depends on a subset of a candidate key
3NF	Check if any non-prime attribute is transitively dependent — i.e., determined by another non-prime attribute
BCNF	Check if for every FD X → Y (non-trivial), X is a super key (X⁺ = all attributes)
Key discovery	If X⁺ = all attributes, X is a super key

---

Interview Deep Dive

---

Key Takeaways

• Armstrong’s Axioms: Reflexivity, Augmentation, Transitivity — used to derive all logical FDs.
• Closure (X⁺): The set of all attributes determined by X. Calculated iteratively.
• If X⁺ contains all attributes of R, X is a Super Key.
• If no subset of X has the same closure, X is a Candidate Key.
• Extraneous attributes on the left or right of an FD can be removed.
• Canonical Cover is the minimal equivalent set of FDs (no redundancy, no extraneous attributes).
• Closure is essential for checking normal forms (2NF, 3NF, BCNF).