Closure of Attribute Sets

The closure X⁺ is computed by a fixpoint loop: you seed a set with X, then repeatedly scan every functional dependency and, whenever a rule's left side is already fully inside your set, you swallow its right side too — until one full pass adds nothing new. That termination point is the set of every attribute X can functionally determine, and it is the single primitive that powers candidate-key detection, normalization, and dependency checking.

The fixpoint algorithm

Closure is not a single rule application — it is a loop that runs to convergence, because adding one attribute can unlock a dependency that adds the next. Each rule can fire at most once and there are finitely many attributes, so the loop always halts.

closure(X, FDs):
    result = set(X)            # seed with the attributes we start with
    changed = True
    while changed:
        changed = False
        for (lhs -> rhs) in FDs:
            if lhs is a subset of result and not (rhs is a subset of result):
                result = result ∪ rhs
                changed = True   # a new attribute appeared; must re-scan
    return result

The changed flag is the whole trick. A dependency that did nothing on pass 1 (its left side was not yet present) may fire on pass 2 once an earlier rule has grown the set. The loop ends only when a complete pass over all FDs adds zero attributes.

Worked example: a key closure that reaches everything

Take the Student_Course relation with attributes {Student_ID, Course_ID, Instructor, Department} and this set of functional dependencies:

We compute {Student_ID}⁺. Watch the set grow one rule at a time; each new attribute unlocks the next dependency in the chain:

The set reached all four attributes, so {Student_ID}⁺ = R (the whole relation). That is the definition of a superkey. Because no proper subset of {Student_ID} exists (it is a single attribute), it is also minimal, so Student_ID is a candidate key.

The flip side: a closure that stops early proves a non-key

Closure does not only confirm keys — it is how you disprove one. Compute {Course_ID}⁺ over the same FDs:

{Course_ID}⁺ = {Course_ID, Instructor, Department}, which is missing Student_ID. Since the closure does not reach all of R, Course_ID is not a superkey — and the missing attribute tells you exactly why: nothing on the right-hand side of any FD ever yields Student_ID, so no attribute set that excludes Student_ID can ever be a key. This is the standard shortcut: an attribute that never appears on the right side of any FD must be part of every candidate key. Here that forces Student_ID into every key, which is consistent with {Student_ID} being the candidate key.

Why the naive version is wrong

A common bug is computing closure with a single pass over the FD list instead of looping to a fixpoint. With the rules ordered as listed (1: Student_ID→Course_ID, 2: Course_ID→Instructor, 3: Instructor→Department) a single pass happens to work — but reorder them to {Instructor→Department, Course_ID→Instructor, Student_ID→Course_ID} and seed with {Student_ID}: the first two rules see nothing in the set, fire nothing, and a single pass returns just {Student_ID, Course_ID}, wrongly concluding Student_ID is not a key. The correct algorithm re-scans after every change, so attribute order in the FD list never affects the answer. Always loop until a full pass adds nothing.

Pitfalls

• Single-pass instead of fixpoint. As above — the result becomes sensitive to FD ordering and silently understates the closure. The loop must continue until convergence.
• Forgetting to seed with X itself. X⁺ always contains X (reflexivity). If you start the result set empty and only add right-hand sides, you lose the seed attributes and may even fail to fire the first rule.
• Confusing superkey with candidate key. Reaching all of R proves a superkey. To call it a candidate key you must also check that no proper subset's closure already reaches R. {Student_ID, Course_ID} is a superkey but not minimal, so it is not a candidate key.
• Matching a rule when only part of the LHS is present. For a composite dependency AB → C, you may add C only when both A and B are already in the set. Firing on a partial left-hand side is a correctness bug that invents dependencies that do not hold.
• Reading a relation instance as the FD set. The sample rows are illustrative; FDs are constraints declared over the schema, not facts inferred from three rows. A small instance can accidentally look like it satisfies an FD that the schema never promised.

Takeaways

• X⁺ is a fixpoint: seed with X, fire any FD whose left side is fully present, repeat until a complete pass adds nothing.
• Closure = R means X is a superkey; add minimality (no proper subset also reaches R) to get a candidate key.
• A closure that stops short proves a non-key, and the unreachable attributes tell you why — anything appearing on no FD's right-hand side must be in every key.
• Order of FDs is irrelevant to a correct fixpoint computation; if order changes your answer, you wrote a single-pass bug.

Sources: Silberschatz, Korth & Sudarshan, Database System Concepts (7th ed.), §7.4 on closure of attribute sets and the attribute-closure algorithm; Elmasri & Navathe, Fundamentals of Database Systems, on the membership/closure algorithm and candidate-key inference. The fixpoint algorithm and the right-hand-side rule for forced key attributes are standard relational-theory results. Re-authored and deepened for this guide: added the fixpoint pseudocode, the iteration-by-iteration trace tables, two closure-chain diagrams, a second (non-key) closure that terminates early, the "why the naive single-pass version is wrong" note, and the engineer-facing pitfalls.