Given a set of columns X and a set of functional dependencies, how do you compute the attribute closure X+, and what design questions does that closure let you answer?
answer
- Seed with X, saturate, stop at fixed point
- Fire A -> B only when all of A is present
- X+ covers R means superkey
- Y inside X+ means X -> Y is implied
- Attributes never on a right side are in every key
basics
~20 sStart with X, then repeatedly add the right side of any dependency whose left side is already contained in the set, until nothing changes. The result X+ is everything X determines. If X+ covers all columns, X is a superkey; X+ also tests whether X -> Y is implied.
solid answer
~60 s**Algorithm.** Set `closure = X`. Loop over the FD set; for every `A -> B` where A is a subset of `closure`, add B to `closure`. Repeat until a full pass adds nothing. The fixed point is `X+`, the set of all attributes functionally determined by X under the given FDs. **What it answers:** - *Is `X -> Y` implied by the FD set?* Yes exactly when Y is a subset of X+. This is the practical substitute for deriving the FD with Armstrong's axioms. - *Is X a superkey?* Yes exactly when X+ equals all attributes of the relation. - *Is X a candidate key?* It is a superkey and, for each attribute a in X, `(X - a)+` fails to cover all attributes. - *Which decompositions are safe?* Lossless-join and normal-form checks are all phrased as closure tests. The order in which dependencies are applied never changes the result; the closure is a unique fixed point. Cost is small - a few passes over the FD list - which is why nobody computes the full dependency closure F+ instead.
code
text · 6 linesstart {A, D}
A -> B {A, B, D}
B -> C {A, B, C, D}
CD -> E {A, B, C, D, E}
E -> A no change -> fixed point
result: (A,D)+ = ABCDE => (A,D) is a superkeygo deeper
Be able to run the algorithm by hand on a small FD set and say what the result means.
Explain the three uses - implication test, superkey test, candidate-key test - and derive candidate keys with the mandatory-core shortcut.
Use closure to review proposed uniqueness constraints and to check decomposition safety, not just as an exam technique.
Frame closure as the cheap decision procedure that replaces exponential reasoning, and note where its answers depend entirely on the correctness of the asserted FD set.
## Why closure exists A declared FD set F is only a starting point. From `A -> B` and `B -> C` it follows that `A -> C`, even though nobody wrote it down. The full set of implied dependencies, F+, is exponentially large, so we never enumerate it. **Attribute closure** answers the only question we actually need - "does F imply this particular FD?" - in near-linear time. `X+` (read "X closure") is defined as the set of all attributes A such that `X -> A` is implied by F. ## The algorithm ``` closure := X repeat for each FD (A -> B) in F if A is a subset of closure closure := closure union B until closure stopped changing return closure ``` It is a straightforward saturation: keep firing rules whose preconditions are met. Termination is guaranteed because `closure` only grows and is bounded by the attribute set. The result is a unique fixed point, independent of the order in which FDs are applied, so two people working the same problem must get the same answer - a useful self-check in an interview. ## Worked example Relation `R(A, B, C, D, E)` with `F = { A -> B, B -> C, CD -> E, E -> A }`. Compute `(A, D)+`: 1. start `{A, D}` 2. `A -> B` fires: `{A, B, D}` 3. `B -> C` fires: `{A, B, C, D}` 4. `CD -> E` fires (both C and D present): `{A, B, C, D, E}` 5. `E -> A` adds nothing new; stop. `(A, D)+ = {A, B, C, D, E}` = all of R, so `(A, D)` is a superkey. Is it minimal? `A+ = {A, B, C}` and `D+ = {D}`, neither covers R, so removing either attribute breaks it: `(A, D)` is a candidate key. Now test whether `B -> E` is implied: `B+ = {B, C}`, which does not contain E, so it is not implied. Test `CD -> A`: `(C, D)+ = {C, D, E, A, B}` contains A, so yes, `CD -> A` is implied even though it was never declared. ## Three things closure decides **1. Implication.** `F` implies `X -> Y` if and only if `Y` is a subset of `X+`. This equivalence is exactly what makes closure the workhorse: soundness and completeness of Armstrong's axioms guarantee the two tests agree. **2. Superkey test.** X is a superkey of R exactly when `X+ = R`. This is the direct definition of superkey applied through implication. **3. Candidate-key test.** X is a candidate key when it is a superkey and every `(X - {a})+` fails to cover R. Practically you compute the superkey closure once, then one closure per attribute you try to drop. ## Finding all candidate keys Closure also drives systematic key enumeration: - Attributes that never appear on the **right** side of any FD cannot be derived from anything, so they must appear in every candidate key. Call this the mandatory core. - Attributes that appear only on right-hand sides and never on a left-hand side can appear in no candidate key. - Compute the closure of the mandatory core. If it covers R, it is the unique candidate key. - Otherwise extend it with one, then two, then more of the remaining attributes, computing closures and keeping the minimal sets that reach R. This prunes an otherwise exponential search dramatically; in the example above, D appears on no right-hand side, so D is in every key, and you only need to try D paired with each other attribute. ## Practical uses beyond exam questions - **Reviewing a proposed uniqueness constraint.** If someone proposes a unique index on a column set, closure tells you whether the FDs already imply it - in which case the constraint is redundant - or whether it asserts a new business rule that must be validated. - **Checking a decomposition.** The lossless-join test asks whether the shared attributes of two fragments determine one of them, which is a closure computation on the shared set. - **Reasoning about query results.** Knowing that a grouping column set determines another column tells you the extra column can be carried through a grouped query without changing its meaning, which is the same reasoning an optimizer applies. ## Common mistakes Firing an FD when only *part* of its left side is present is the classic error: with `CD -> E`, having C alone does not license adding E. The other frequent slip is stopping after one pass; newly added attributes can enable dependencies you already skipped, so you must loop until a full pass changes nothing.
- Why do we compute attribute closure instead of the closure F+ of the whole dependency set?F+ contains every implied dependency and grows exponentially with the number of attributes, so materialising it is impractical. Attribute closure answers the only question that matters - whether one specific dependency is implied - in roughly linear passes over F. Since Armstrong's axioms are sound and complete, the closure test gives exactly the same verdict as deriving the dependency formally.
- You compute X+ and it covers every attribute. What have you shown, and what have you not shown?You have shown X is a superkey: it functionally determines every attribute, so no two distinct rows can agree on X. You have not shown it is minimal. To conclude it is a candidate key you must drop each attribute of X in turn and confirm that every reduced set has a closure falling short of the full attribute list.
saying these in an interview costs you the question
- Applying an FD when only part of its left-hand side is in the closure
- Stopping after a single pass instead of iterating to a fixed point
- Claiming the result depends on the order dependencies are applied
- Concluding a set is a candidate key from the closure alone, without a minimality check
- Thinking closure must be computed over the exponential dependency closure F+