Finding keys: closure and Armstrong's axioms
Given a table's FDs, how do you prove which columns form a key? Two tools.
Armstrong's axioms
Three rules let you derive every FD that follows from the ones you know (they're sound: they never give a wrong FD, and complete: they find all of them).
| Rule | If | Then | Example |
|---|---|---|---|
| Reflexivity | Y is a subset of X | X → Y | (StudentID, CourseID) → StudentID |
| Augmentation | X → Y | XZ → YZ | StudentID → StudentName gives (StudentID, CourseID) → (StudentName, CourseID) |
| Transitivity | X → Y and Y → Z | X → Z | StudentID → DepartmentID → DepartmentName |
Three handy rules follow from them:
- Union: if X → Y and X → Z, then X → YZ.
- Decomposition: if X → YZ, then X → Y and X → Z.
- Pseudotransitivity: if X → Y and WY → Z, then WX → Z.
Attribute closure
The closure of X, written X⁺, is every attribute that X determines. Compute it by starting with X and applying FDs until nothing new appears.
Table R(A, B, C, D) with A → B, B → C and AC → D. Find A⁺:
| Step | Use | A⁺ so far |
|---|---|---|
| Start | — | {A} |
| 1 | A → B | {A, B} |
| 2 | B → C | {A, B, C} |
| 3 | AC → D (A and C are both in) | {A, B, C, D} |
A⁺ contains every attribute of R, so A is a superkey. It's a single column, so nothing smaller could work: A is a candidate key.
Closure answers three questions: is X a superkey? (Does X⁺ contain everything?) What are the candidate keys? Does some FD follow from the others? (Is its right side in the closure of its left side?)