Functional Dependencies

A rule X -> Y says knowing X fixes Y. Computing the closure X+ tells you everything X determines — and whether it is a key.

10 min read Watch it move Build it

A functional dependency X -> Y is a rule saying the columns in X *fix* the value of the columns in Y: any two rows that agree on X must agree on Y. FDs are the raw material of normalization and the way we discover keys.

Armstrong's axioms

Three rules are sound (they derive only true FDs) and complete (they can derive every FD that holds). Every closure step is really just these, applied quietly:

1Reflexivity — if Y is a subset of X, then X -> Y. (A set determines its own parts.)
2Augmentation — if X -> Y, then XZ -> YZ for any Z. (Add the same columns to both sides.)
3Transitivity — if X -> Y and Y -> Z, then X -> Z. (Chaining.)

Handy derived rules

From the three axioms follow *union* (X->Y and X->Z give X->YZ), *decomposition* (X->YZ gives X->Y and X->Z), and *pseudotransitivity* (X->Y and WY->Z give WX->Z). You never need new axioms — these all fall out.

The attribute closure X+

The closure X+ is everything X determines: start with X, then keep adding the right-hand side of any FD whose left-hand side you already hold, until nothing new appears.

closure(X, F):
  result = X
  repeat until result stops growing:
    for each FD  L -> R  in F:
      if L is a subset of result:
        result = result union R
  return result

Worked example

Relation R(A, B, C, D, E) with F = { A -> BC, CD -> E, B -> D, E -> A }. Compute {A}+:

start:  {A}
A -> BC   :  {A, B, C}
B -> D    :  {A, B, C, D}
CD -> E   :  {A, B, C, D, E}   (we now hold both C and D)

{A}+ = {A, B, C, D, E}  = all attributes

Closure is the key test

Because {A}+ is every column, A alone identifies any row — so A is a superkey, and since a single-column set has nothing to remove, it is a candidate key. Running the same computation, {E}+ is also all attributes (E -> A -> BC ...), so E is a second candidate key.

Finding candidate keys

A set is a superkey exactly when its closure is every column. A candidate key is a superkey with no removable column. To find them, test small sets first and never grow a set that is already a superkey.

OperationTimeSpace

closure(X) · near-linear with a good implementationO(|F| · |attrs|)O(|attrs|)

is-superkey · does X+ cover all attributes?one closureO(|attrs|)

Check yourself

For R(A,B,C,D) with F = { A -> B, B -> C, C -> D }, what is {A}+?