A (FD) X → Y says: any two tuples that agree on X also agree on Y. "X determines Y."
staff
| emp_id | dept | building |
|---|---|---|
| 1 | Sales | North |
| 2 | Sales | North |
| 3 | Support | North |
| 4 | Finance | South |
- X is the determinant, Y the dependent.
X → Yis trivial when Y is part of X:(emp_id, dept) → dept.- K is a superkey exactly when
K → every attribute. A key is a functional dependency.
Test an FD on data
X → Y is broken when one X value has more than one Y value:
sql
SELECT dept FROM staff
GROUP BY dept
HAVING COUNT(DISTINCT building) > 1;No rows: the data does not break dept → building. One row: that dept breaks it.
Data can disprove an FD. It cannot prove one: FDs come from the rules of the real world. "Each department is in one building" is a rule; the data only follows it.
Closure
From some FDs, others follow. Three rules (Armstrong's axioms) give all of them:
| Rule | If | Then |
|---|---|---|
| reflexivity | Y is part of X | X → Y |
| augmentation | X → Y | XZ → YZ |
| transitivity | X → Y and Y → Z | X → Z |
The closure of a set of attributes, X+, is every attribute that X determines. To find it:
- Start with X.
- For each FD
A → B: if every attribute of A is already in the set, add B. - Repeat until nothing changes.
text
R(A, B, C, D, E) A → B, B → C, CD → E
A+ = A → AB → ABC (stops: no D for CD → E)
AD+ = AD → ABD → ABCD → ABCDE (every attribute: AD is a superkey)If X+ holds every attribute, X is a superkey. If no smaller part of X does, X is a candidate key (Chapter 5).