Skip to main content

Armstrong’s Axioms & Closure of Attribute Sets

Armstrong’s Axioms

Given a set of FDs \(F\), these three rules let us mechanically derive new FDs that logically follow from it:

Axiom Rule Intuition
Reflexivity if \(\beta \subseteq \alpha\), then \(\alpha \rightarrow \beta\) A set of attributes always determines its own subsets
Augmentation if \(\alpha \rightarrow \beta\), then \(\gamma\alpha \rightarrow \gamma\beta\) Adding the same extra attributes to both sides keeps an FD valid
Transitivity if \(\alpha \rightarrow \beta\) and \(\beta \rightarrow \gamma\), then \(\alpha \rightarrow \gamma\) If A determines B, and B determines C, then A determines C

Applying these repeatedly to \(F\) gives every FD logically implied by \(F\) — this full set is the closure \(F^+\), and \(F \subseteq F^+\).

Worked Example

For \(R = (A, B, C, G, H, I)\) with \(F = \{A \rightarrow B,\ A \rightarrow C,\ CG \rightarrow H,\ CG \rightarrow I,\ B \rightarrow H\}\):

\[A \rightarrow H \quad \text{(by transitivity, since } A \rightarrow B \text{ and } B \rightarrow H\text{)}\]

This wasn’t stated directly in \(F\), but follows logically — and is therefore part of \(F^+\).

Note: Computing all of \(F^+\) this way (repeatedly applying axioms until nothing new appears) works, but is expensive. Attribute closure, covered next, is the practical shortcut.

Derived Rules

These follow from the three basic axioms — not new rules, just useful shortcuts:

Rule Statement
Union if \(\alpha \rightarrow \beta\) and \(\alpha \rightarrow \gamma\), then \(\alpha \rightarrow \beta\gamma\)
Decomposition if \(\alpha \rightarrow \beta\gamma\), then \(\alpha \rightarrow \beta\) and \(\alpha \rightarrow \gamma\)
Pseudotransitivity if \(\alpha \rightarrow \beta\) and \(\gamma\beta \rightarrow \delta\), then \(\alpha\gamma \rightarrow \delta\)

Closure of Attribute Sets

Instead of computing the entire \(F^+\), we usually just want to know: what does this set of attributes determine? That’s the closure of an attribute set, written \(\alpha^+\) — all attributes functionally determined by \(\alpha\) under \(F\).

How to Compute It

  1. Start with result = α.
  2. Scan through every FD \(\beta \rightarrow \gamma\) in \(F\).
  3. If \(\beta\) is already contained in result, add \(\gamma\) to result.
  4. Repeat steps 2–3 until no new attributes get added.

Worked Example

For \(R = (A, B, C, G, H, I)\) with \(F = \{A \rightarrow B,\ A \rightarrow C,\ CG \rightarrow H,\ CG \rightarrow I,\ B \rightarrow H\}\), compute \((AG)^+\):

Step Result Why
1 AG starting point
2 ABCG \(A \rightarrow B\) and \(A \rightarrow C\) apply
3 ABCGH \(CG \subseteq\) result, so \(CG \rightarrow H\) applies
4 ABCGHI \(CG \rightarrow I\) applies

\((AG)^+ = ABCGHI\) — every attribute in \(R\).

Click Run below, then toggle attributes in the pills bar to test different closures:

R(A, B, C, G, H, I)

A -> B
A -> C
CG -> H
CG -> I
B -> H

Query: AG

Superkeys and Candidate Keys, via Closure

  • \(K\) is a superkey of \(R\) if \(K^+ \supseteq R\) (contains every attribute)
  • \(K\) is a candidate key of \(R\) if \(K^+ \supseteq R\) and no proper subset of \(K\) also satisfies this (minimal)

Applying this to \(AG\): \((AG)^+ = R\), so \(AG\) is a superkey. Checking subsets — \((A)^+ = ABC\) and \((G)^+ = G\) — neither reaches all of \(R\). So \(AG\) is minimal, making it a candidate key.

Prime and Non-Prime Attributes

  • Prime attribute: belongs to some candidate key
  • Non-prime attribute: belongs to no candidate key

Here’s a data instance for \(R = (A,B,C,G,H,I)\) consistent with \(F= \{A \rightarrow B,\ A \rightarrow C,\ CG \rightarrow H,\ CG \rightarrow I,\ B \rightarrow H\}\), compute \((AG)^+\):

A B C G H I
a1 b1 c1 g1 h1 i1
a1 b1 c1 g2 h1 i2
a2 b2 c2 g1 h2 i3
a2 b2 c2 g2 h2 i4

Only the pair \((A, G)\) is unique across every row — no other single column or combination pins down a row on its own (A alone repeats across rows 1–2 and 3–4; G alone repeats across rows 1&3, 2&4). That matches what we found algebraically: \(AG\) is the candidate key.

So: A and G are prime attributes; B, C, H, I are non-prime — each of them is simply determined by the key, not part of it.

Formula: Maximum Number of Superkeys

Given a relation with \(N\) total attributes, the number of possible superkeys depends directly on the number of candidate keys and the size of those keys.

Case 1: Only 1 Candidate Key (Single Attribute)

If the relation has only one candidate key, and that key consists of a single attribute (e.g., Key = \(\{A_1\}\)): \[\text{Total Superkeys} = 2^{N-1}\]

Case 2: Only 1 Candidate Key (Composite Key)

If the relation has only one candidate key, and that key is a composite key formed by \(k\) attributes: \[\text{Total Superkeys} = 2^{N-k}\]

Case 3: Every Single Attribute is a Candidate Key

If the relation has \(N\) candidate keys (meaning every single attribute in the relation is its own independent candidate key): \[\text{Total Superkeys} = 2^N - 1\]

Case 4: Two Distinct Candidate Keys

When a relation contains two distinct candidate keys (which can be composed of one or many attributes), we must use the Principle of Inclusion-Exclusion to avoid double-counting the superkeys that contain both keys.

Generic Set Formula

\[\text{Max Superkeys} = (\text{Superkeys with } A_1) + (\text{Superkeys with } A_2) - (\text{Superkeys with both } A_1 \text{ and } A_2)\]

Mathematical Representation

Let \(m\) be the number of attributes forming the first candidate key, and \(n\) be the number of attributes forming the second candidate key. Assuming the two candidate keys share no overlapping attributes:

\[\text{Max Superkeys} = 2^{N-m} + 2^{N-n} - 2^{N-(m+n)}\]

📌 Note: If the two candidate keys share overlapping attributes, the exponent in the subtraction term changes from \((m+n)\) to the number of attributes in their absolute union: \(|\text{Key}_1 \cup \text{Key}_2|\).

Example: \(R = (A,B,C,G,H,I)\) has \(n = 6\) attributes; candidate key \(AG\) has \(k = 2\). Number of superkeys: \(2^{(6-2)} = 2^4 = 16\).

Why Attribute Closure Matters

Use Case How In Plain English
Test if \(\alpha\) is a superkey Check \(\alpha^+ \supseteq R\) Compute what \(\alpha\) determines — if it covers every column in the table, \(\alpha\) is enough to identify a row
Test if \(\alpha \rightarrow \beta\) holds Check \(\beta \subseteq \alpha^+\) Compute what \(\alpha\) determines, then see if \(\beta\) shows up in that list
Compute all of \(F^+\) For every \(\gamma \subseteq R\), output \(\gamma \rightarrow S\) for each \(S \subseteq \gamma^+\) Try every possible set of columns, work out what each one determines, and write down all those dependencies