Functional Dependencies, Closures and Keys

Rules hidden in the data

A functional dependency (FD) X → Y holds in a relation if any two tuples that agree on attributes X also agree on Y: roll_no → name says one roll number determines exactly one name. FDs come from the meaning of the data, not from one sample. Armstrong's axioms derive new FDs: reflexivity (if Y ⊆ X then X → Y), augmentation (if X → Y then XZ → YZ) and transitivity (if X → Y and Y → Z then X → Z); useful derived rules are union, decomposition and pseudo-transitivity. The closure of an attribute set, X⁺, is every attribute functionally determined by X: start with X and repeatedly add the right side of any FD whose left side is already included. X is a super key if X⁺ contains all attributes, and a candidate key if additionally no proper subset of X is a super key. A minimal (canonical) cover is a simplified equivalent set of FDs with single attributes on the right, no extraneous attributes and no redundant FDs.

Computing an attribute closure

Start from a set of attributes and keep adding everything the dependencies let you reach.

Closure and candidate keys, worked by hand

R(A, B, C, D, E) with F = { A → B, B → C, CD → E }

compute {A, D}+ :
  start          {A, D}
  A -> B         {A, B, D}
  B -> C         {A, B, C, D}
  CD -> E        {A, B, C, D, E}   all attributes -> AD is a super key

is AD minimal?
  {A}+ = {A, B, C}         not all attributes
  {D}+ = {D}               not all attributes
  -> AD is a candidate key

A and D never appear on the right side of any FD, so every key must contain both;
hence AD is the only candidate key.

Attributes never on a right side are in every key

When finding candidate keys, first collect attributes that never appear on the right-hand side of any FD; they must be part of every key. Then add attributes only as needed until the closure covers everything.

Quick check: Given R(A, B, C) and F = { A → B, B → C }, what is {A}⁺?

• {A}
• {A, B}
• {A, B, C}
• {B, C}