Functional dependencies

Why it matters

Redundancy in a table is not a matter of taste; it follows from rules about the data, such as "a subject code determines its title". Functional dependencies write those rules down, and once they are written, every normal form, every decomposition and every candidate key can be derived mechanically. Exams ask you to compute closures and keys from a set of dependencies, and the same reasoning tells you in practice why a table keeps getting update anomalies.

The idea

A functional dependency X → Y holds in a relation when any two tuples that agree on the attributes X must also agree on Y. X is the determinant. "roll_no → name" means a roll number fixes the name; "{subject_id, semester} → instructor" means a subject in a semester has one instructor. Dependencies are facts about the meaning of the data, not about the rows you happen to have today: a sample table can suggest a dependency but never prove it.

Kinds of dependencies

Partial and transitive dependencies are exactly what 2NF and 3NF remove in the next lesson.

Armstrong's axioms

From a given set of dependencies F, other dependencies follow. Three rules generate all of them (they are sound and complete):

1. 1

   Reflexivity

   If Y ⊆ X, then X → Y (trivial dependencies).
2. 2

   Augmentation

   If X → Y, then XZ → YZ for any Z.
3. 3

   Transitivity

   If X → Y and Y → Z, then X → Z.
4. 4

   Derived rules

   Union (X → Y and X → Z give X → YZ), decomposition (X → YZ gives X → Y and X → Z) and pseudo-transitivity (X → Y and WY → Z give WX → Z) follow from the three.

Attribute closure: the workhorse

The closure X⁺ is the set of all attributes determined by X under F. Algorithm: start with X; repeatedly, for any dependency A → B where A is already inside the result, add B; stop when nothing changes. Closure answers almost every question: X → Y holds if Y ⊆ X⁺, and X is a super key if X⁺ contains every attribute.

Finding candidate keys

1. 1

   Classify attributes

   Attributes that appear only on left-hand sides (or nowhere) must be in every key; attributes that appear only on right-hand sides are in no key; the rest might be.
2. 2

   Start from the must-haves

   Compute the closure of the attributes that must be in every key. If it covers everything, that is the only candidate key.
3. 3

   Add maybe-attributes one at a time

   Otherwise extend with combinations of the 'might' attributes, smallest first, keeping only minimal sets whose closure is everything.
4. 4

   Mark prime attributes

   Attributes that belong to any candidate key are prime; the rest are non-prime. Normal forms are stated in these terms.

Minimal cover

Different sets of dependencies can be equivalent (each implies the other). A minimal (canonical) cover is the simplest equivalent set: every right-hand side is a single attribute, no left-hand side has an extraneous attribute (check by closure whether a smaller left side still determines the right side), and no dependency is redundant (remove it and check whether the rest still imply it). The minimal cover is the input to the 3NF synthesis algorithm in the decomposition lesson.

Trade-offs

Functional dependencies give a precise vocabulary and algorithms for schema design, at the cost of requiring someone to know the real-world rules; a missed dependency produces a design that looks normalized and is not. Many real constraints are not functional dependencies (a person may have several phones, a rule spans tables), which is where multivalued dependencies, triggers and application logic come in.

In an interview

Show the algorithm, not just the definition: "To test whether {A, D} is a key, compute its closure: A gives B, B gives C, then CD gives E, so the closure is everything. D is never on a right-hand side, so every key needs D, and since D alone only reaches D, {A, D} is a minimal key." Speaking the closure steps aloud is exactly what examiners look for.