Attribute Closure and the Mechanical Derivation of Candidate Keys

A designer writes down a set of functional dependencies that the data must satisfy, and then needs to know which attribute sets determine which others. The answer is not visible by inspection once more than a handful of dependencies are involved, because dependencies compose: if A determines B and B determines C, then A determines C, whether or not anyone declared that fact. Closure computation turns this implicit knowledge into an explicit, checkable answer, and it is the primitive that key finding, normalization, and dependency-preservation testing are all built on.

Dependencies as a set of constraints

A functional dependency X → Y, where X and Y are sets of attributes of a relation R, asserts that for any two tuples t1 and t2 of R, if t1 and t2 agree on every attribute in X they must also agree on every attribute in Y. The dependency is a statement about all legal instances of R, not about any particular instance. A given table may happen to satisfy X → Y by accident of its current contents; the dependency holds only when no legal instance can violate it.

Two attributes determine each other trivially: X → Y where Y ⊆ X is satisfied by every instance, because agreement on X already includes agreement on Y. These trivial dependencies carry no information, and they are the reason closure is defined as a set rather than a minimal set.

A dependency set F implies a dependency f when every instance satisfying all of F also satisfies f. The closure of F, written F+, is the set of all dependencies implied by F. For a set of attributes X, the attribute closure X+ under F is the set of all attributes A such that X → A is in F+. Attribute closure is the practical object: F+ can be enormous — for a relation with n attributes the number of possible dependencies is on the order of 3^n, since each attribute is on the left, on the right, or in neither — while X+ is a single set of at most n attributes.

The three inference rules and what they generate

Armstrong’s axioms are three rules that are sound (they derive only implied dependencies) and complete (they derive every implied dependency):

• Reflexivity. If Y ⊆ X then X → Y.
• Augmentation. If X → Y then XZ → YZ for any attribute set Z.
• Transitivity. If X → Y and Y → Z then X → Z.

Three further rules follow from these and are used so often that they are usually stated separately. Union: X → Y and X → Z give X → YZ. Decomposition: X → YZ gives X → Y and X → Z. Pseudotransitivity: X → Y and WY → Z give WX → Z.

Decomposition deserves a caution. It applies to the right-hand side only. From XY → Z nothing follows about X → Z or Y → Z; a dependency with two attributes on the left says the pair determines Z, and neither half need determine it alone. Confusing this with the valid decomposition rule is the most common error in hand-written dependency reasoning, and it produces keys that are too small and normal forms that are wrongly claimed.

The axioms are also not a decision procedure by themselves. Applying them blindly generates an unbounded stream of dependencies, most of them trivial or redundant. The completeness theorem says every implied dependency has a derivation, not that a naive search will terminate quickly. Closure computation replaces the search with a fixed-point iteration over attribute sets.

Computing attribute closure by iteration

The algorithm takes a set X and a dependency set F and returns X+:

result := X
repeat
    for each dependency V → W in F:
        if V ⊆ result then result := result ∪ W
until result does not change
return result

Correctness rests on two observations. Every attribute added is genuinely implied: at the moment it is added, V ⊆ result, and by induction every attribute in result is implied by X, so X → V holds and transitivity gives X → W. And the iteration reaches the full closure: if some implied attribute were missing, there would be a derivation of it, and the last step of that derivation would add it, since the premises of that step are already in result by induction on derivation length.

Complexity is polynomial, which is the important structural fact. Each pass over F examines |F| dependencies and performs a subset test costing O(n) with a bit-vector representation of attribute sets, so a pass costs O(|F| · n). Each pass that changes result adds at least one attribute, so there are at most n such passes, plus one final pass that adds nothing. Total: O(|F| · n²). With n in the tens and |F| in the hundreds — the realistic range for a hand-designed schema — this is microseconds.

The bit-vector representation matters for a second reason: an attribute set becomes a machine word (or a few words), subset testing becomes V & ~result == 0, and union becomes bitwise or. An implementation of the whole procedure fits in a page.

def closure(attrs: frozenset[str], fds: list[tuple[frozenset[str], frozenset[str]]]) -> frozenset[str]:
    result = set(attrs)
    changed = True
    while changed:
        changed = False
        for lhs, rhs in fds:
            if lhs <= result and not rhs <= result:
                result |= rhs
                changed = True
    return frozenset(result)

The loop terminates because result grows monotonically inside a finite universe; the changed flag only avoids a final wasted pass.

From closure to candidate keys

A set K is a superkey of R under F exactly when K+ = R, the full attribute set. A candidate key is a superkey with no proper subset that is also a superkey.

The naive enumeration tests all 2^n subsets, which is hopeless beyond about twenty attributes. Two reductions make the search practical in the cases that arise.

The first is that every attribute appearing only on the left of dependencies — never on a right-hand side — must belong to every candidate key. If A is never determined by anything, no set omitting A can determine A, so no set omitting A is a superkey. Such attributes are forced into the key, and they can be seeded into the starting set.

The second is that attributes appearing only on the right of dependencies cannot be part of a minimal key unless they are also on some left-hand side, because including them adds nothing that the rest does not already determine. They are candidates for exclusion, which shrinks the search space rather than the answer.

The standard construction: start with the forced attributes X, compute X+. If X+ = R, then X is the unique minimal key. Otherwise, for each remaining attribute A, test whether X ∪ {A} closes to R; if it does, A is a candidate for inclusion. This is a greedy search over an exponential space in general — the problem of finding a minimum-cardinality key is NP-complete — but the reduction usually leaves a handful of attributes to consider, and enumeration over those is trivial.

def candidate_keys(all_attrs, fds):
    forced = set(all_attrs)
    for _, rhs in fds:
        forced -= rhs
    others = [a for a in all_attrs if a not in forced]
    keys = []
    def extend(current, rest):
        if closure(current, fds) == all_attrs:
            keys.append(frozenset(current))
            return
        for i, a in enumerate(rest):
            extend(current | {a}, rest[i + 1:])
    extend(forced, others)
    # drop non-minimal results
    return [k for k in keys if not any(o < k for o in keys)]

The pruning step at the end is not optional. The recursion above finds superkeys, and a superkey whose proper subset is also a superkey is not a candidate key. Checking minimality directly — for each attribute A in K, verify that (K − A)+ ≠ R — is O(n) closure computations per key and is the clearer formulation.

What closure answers beyond keys

Three other schema questions reduce to the same primitive.

Equivalence of dependency sets. F and G are equivalent when F+ = G+. Testing this by generating both closures is infeasible, but the test reduces to n · |G| closure computations: for each X → Y in G, check that Y ⊆ X+ under F, and symmetrically. This is how a normalization tool checks that a decomposition preserved the original constraints.

Redundancy in F. A dependency X → Y is redundant if it is implied by F − {X → Y}. Removing each dependency in turn and testing whether the remainder still implies it gives a minimal cover, and the test is again a closure computation. A minimal cover has no dependency with a redundant attribute on its left, and no dependency implied by the others.

Lossless-join testing. A decomposition of R into R1 and R2 is lossless when (R1 ∩ R2) → R1 or (R1 ∩ R2) → R2 holds under F+ — one closure computation on the intersection.

Each of these is a polynomial-time check that would be intractable if phrased as a search through F+. The reason the whole area is tractable is that attribute closure collapses an exponential object into a set of size n, and the collapse preserves exactly the information the tests need. What it does not preserve is information about which derivation produced a dependency, and there are questions — such as whether a given dependency is implied by a set that is itself changing — where that loss matters. The limits of implication are examined in inclusion dependencies and the limits of implication, and the use of closure results to drive decomposition appears in Boyce-Codd normal form and the cost of losing a dependency.

Where the machinery stops

Attribute closure answers questions about functional dependencies only. Multivalued dependencies, which are needed for fourth normal form, do not have an attribute-closure analogue with the same clean structure: the chase, not closure, is the general decision procedure, and it operates on tableaux rather than attribute sets. Treating an MVD as if it were an FD — taking X →→ Y to mean X+ contains Y — produces answers that are wrong in both directions.

The other limit is semantic. Closure tells what the declared dependencies imply; it says nothing about whether the declared dependencies are true of the domain. A schema whose dependencies are all formally consistent can still encode a false claim about the world, and no amount of closure computation detects that. The derivation is a tool for reasoning about the consequences of a specification, not for validating the specification itself.