Functional dependencies: closures, keys and covers
Goals and assumptions
Infer consequences of functional dependencies (FDs), compute attribute closures, enumerate candidate keys, and reduce a dependency set without changing its meaning. Work with classical finite relations, no NULL, and set semantics. An FD X→Y means any two tuples agreeing on every attribute in X must agree on every attribute in Y. It does not assert the reverse direction or that X is a key for the whole relation.
1. Read an FD as a pairwise constraint
For Student(sid,dept,building), sid→dept says a student has one department value in every legal instance. dept→building says one building value per department. Together they imply sid→building. They allow many students in the same department and different departments in the same building. A trivial FD has Y⊆X; AB→A always holds. A dependency is nontrivial if some right-side attribute is outside X.
A single instance can violate an FD: (A,B) tuples (1,x),(1,y), x≠y refute A→B. An instance where all A values differ does not establish A→B as a universal schema rule. FDs do not require a particular determinant value to appear at all.
2. Armstrong rules and useful derived rules
Reflexivity: if Y⊆X, then X→Y. Augmentation: X→Y implies XZ→YZ. Transitivity: X→Y and Y→Z imply X→Z. These rules are sound and complete for FD implication. Union combines X→Y and X→Z into X→YZ; decomposition splits X→YZ into X→Y and X→Z. Pseudotransitivity combines X→Y and WY→Z into WX→Z. Do not infer X→Z merely from X→Y and Z→Y: sharing an output does not determine each other.
3. Attribute closure algorithm
To compute X+ under F, start with X. Whenever an FD's entire left side is already in the set, add its right side. Repeat until nothing changes. X→Y follows from F exactly when Y⊆X+. X is a superkey of R when X+ contains all attributes of R.
Worked closure: R(A,B,C,D,E), F={A→BC,C→D,BD→E}. Start A+={A}. Apply A→BC to get {A,B,C}; C→D gives {A,B,C,D}; BD→E gives all five. Thus A is a superkey. It is minimal because the empty set has no applicable FD and does not determine all attributes, so {A} is a candidate key. B+={B}; BD+={B,D,E}, which still misses A and C.
4. Candidate keys need both coverage and minimality
An attribute absent from all right sides of nontrivial dependencies cannot be generated from other attributes and must occur in every key (assuming no additional FDs beyond F's implications). Start with such mandatory attributes, add candidates, compute closure, and prune supersets of known keys. Check minimality by removing one attribute at a time; if no single removal remains a superkey, no smaller subset can be a superkey, by monotonicity of closure.
Worked enumeration: R(A,B,C,D), F={A→B,B→A,C→D}. C never appears on the right and is mandatory. C+={C,D}, so C alone fails. Add A: AC+={A,B,C,D}; add B: BC+={A,B,C,D}. Removing either member of AC or BC fails. Exactly AC and BC are candidate keys: every key needs C and at least one of A or B; adding D cannot supply either. D is not mandatory merely because it is an attribute of the schema.
Candidate keys can have different sizes. For R(A,B,C), F={A→BC,BC→A}, both A and BC are candidate keys. BC is still minimal because B alone and C alone fail, although A has fewer attributes.
5. Minimal covers by implication checks
A minimal cover uses singleton right sides, has no extraneous left-side attributes, and has no redundant dependency. Equivalent covers can look different; uniqueness is not promised. First split right sides. To test whether a left-side attribute can be removed from X→a, compute (X−{b})+ under the current dependency set and see whether it contains a. To test whether an entire FD X→a is redundant, remove that FD temporarily and test whether the remaining set still derives a from X. Failing to remove the candidate FD during this last test makes every FD appear redundant.
Worked reduction: F={A→BC,B→C,A→B,AB→C}. After singleton splitting and removing duplicate A→B, use {A→B,A→C,B→C,AB→C}. AB→C is redundant because B→C already implies it by augmentation/decomposition. A→C is redundant because A→B and B→C imply it. A minimal cover is {A→B,B→C}. Neither remaining dependency follows from the other. Recompute against the current set after each deletion rather than deleting many dependencies based on stale simultaneous tests.
Pitfalls
- A determinant need not identify the whole row.
- Compute closure to a fixed point, not just one scan if later steps enable earlier rules.
- Keys must be minimal; superkeys need not be.
- “Minimal” does not mean globally smallest cardinality or a unique cover.
- Never infer FDs solely from attribute names or one accidental sample.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. If A→B and B→C hold, which FD must hold?
A. C→A B. A→C C. B→A D. C→B
Answer: B
A: The reverse chain is not implied.
B: Transitivity gives A→C.
C: The reverse of A→B is not implied.
D: The reverse of B→C is not implied.
P02. For F={A→B,B→C}, A+ on R(A,B,C,D) is:
A. {A} B. {A,B} C. {A,B,C} D. {A,B,C,D}
Answer: C
A: A→B applies.
B: B→C adds C.
C: A reaches B and then C, but no FD adds D.
D: D cannot be generated by these FDs.
P03. For R(A,B,C,D), F={A→B,B→A,C→D}, candidate keys are:
A. A and B B. AC and BC C. C only D. ACD and BCD
Answer: B
A: Neither A nor B can generate C.
B: C is mandatory and either A or B supplies the remaining pair.
C: C reaches D but not A or B.
D: These are nonminimal supersets of AC and BC.
P04. Which FD is trivial?
A. A→B for distinct A,B B. AB→A C. A→BC for distinct A,B,C D. B→A for distinct A,B
Answer: B
A: B is not a subset of A.
B: The right side A is contained in AB.
C: The right side contains attributes outside A.
D: A is not a subset of B.
P05. To test whether X→a is a redundant FD, compute X+ using:
A. Only X→a B. F with X→a removed C. No dependencies ever D. F plus a→X
Answer: B
A: This proves the FD using itself.
B: Redundancy requires derivation from the other dependencies.
C: Other dependencies may imply it.
D: Adding a new reverse FD changes the problem.
P06. R(A,B,C) has F={A→BC,BC→A}. Which is correct?
A. Only A can be a candidate key because it is smaller B. A and BC are both candidate keys C. B alone is a candidate key D. ABC is a candidate key
Answer: B
A: Minimality is by subset, not global smallest size.
B: Both determine all attributes and neither has a determining proper subset.
C: B alone cannot use BC→A without C.
D: ABC is not minimal because A suffices.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Databases syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in