Lesson 20: Functional Dependencies and Closure¶
Armstrong's axioms, attribute closure, and minimal cover
About this lesson
Course: Database Management Systems
Unit 5: Database Design · 10 Lecture Hours
Lesson duration: 2 lectures
Reading: Elmasri & Navathe, Ch. 14.2, 14.3
Learning Outcomes
- Define a functional dependency precisely, and identify FDs from a description.
- State and apply Armstrong's axioms and the derived rules.
- Compute the attribute closure
X⁺mechanically and reliably. - Use
X⁺to test whetherXis a superkey, and whether an FD is implied. - Compute a minimal (canonical) cover.
20.1 Functional Dependency¶
Functional dependency
Let R be a relation schema and X, Y ⊆ R. The functional dependency
X → Y (read "X functionally determines Y", or "Y is functionally dependent on X")
holds if, for any legal relation state of R, whenever two tuples agree on X they must also agree on Y:
for all tuples
t1, t2inr(R): ift1[X] = t2[X]thent1[Y] = t2[Y].
X is the determinant; Y is the dependent.
An FD is a property of the MEANING, not of the data
An FD is a constraint — an assertion about every possible legal state, present and future — derived from the semantics of the mini-world.
You may disprove an FD by finding two tuples in the current data that agree on X and differ on Y. You can never prove one from data alone: today's data may merely happen to satisfy it.
Example. If today no two students share a name, the data satisfies Name → Rollno. But the FD is false, because two students could share a name. Only the mini-world's rules decide.
Reading an FD¶
| FD | English |
|---|---|
Rollno → Name |
Each roll number belongs to exactly one student, so it determines the name. |
SID → Cname, TotalSeats |
A course id determines its name and seat count. |
Rollno, SID → Dateofadmission |
A student-course pair determines one admission date. |
Name → Rollno |
False — two students may share a name. |
Trivial, non-trivial, completely non-trivial¶
Classification
- Trivial:
X → YwhereY ⊆ X. Always true, carries no information.AB → A. - Non-trivial:
X → YwhereY ⊄ X(at least one attribute ofYis outsideX).AB → BC. - Completely non-trivial:
X → YwhereX ∩ Y = ∅.AB → C.
FDs and keys¶
The link that makes everything work
K is a superkey of R if and only if K → R — that is, K functionally determines every attribute.
K is a candidate key if additionally no proper subset of K determines R.
This is the bridge between the key theory of Unit 3 and the normalisation of Lessons 3 to 5, and it is what makes candidate keys computable rather than guessed.
20.2 Armstrong's Axioms¶
The three axioms (sound and complete)
Let X, Y, Z be sets of attributes of R.
A1 — Reflexivity. If Y ⊆ X then X → Y.
(This generates exactly the trivial dependencies.)
A2 — Augmentation. If X → Y then XZ → YZ, for any Z.
(Adding the same attributes to both sides preserves the dependency.)
A3 — Transitivity. If X → Y and Y → Z then X → Z.
Sound and complete
Sound — every FD derivable by the axioms is genuinely implied by F; the rules never produce a false dependency.
Complete — every FD implied by F is derivable by the axioms; nothing implied is beyond reach.
Together: the axioms derive exactly the set of implied dependencies — no more and no fewer. This is why F⁺ is well defined.
Derived rules (provable from A1–A3, and used constantly)¶
| Rule | Statement | Proof sketch |
|---|---|---|
| Union (additivity) | If X → Y and X → Z then X → YZ |
Augment X→Y by X giving X→XY; augment X→Z by Y giving XY→YZ; transitivity. |
| Decomposition (projectivity) | If X → YZ then X → Y and X → Z |
YZ → Y by reflexivity; transitivity with X → YZ. |
| Pseudotransitivity | If X → Y and WY → Z then WX → Z |
Augment X→Y by W giving WX→WY; transitivity with WY→Z. |
| Composition | If X → Y and Z → W then XZ → YW |
Augment each, then combine. |
Two rules that do NOT hold
X → YZ does give X → Y (decomposition on the right is valid).
But XY → Z does not give X → Z or Y → Z. Decomposition on the left is invalid.
Counter-example. Rollno, SID → Dateofadmission is true, but Rollno → Dateofadmission is false — a student admitted to two courses has two dates.
Similarly, X → Z and Y → Z do not give XY → Z... they actually do, by augmentation; but the converse (splitting the left) fails. Remember: right sides split, left sides do not.
Closure of a set of dependencies¶
F⁺
The closure F⁺ of a set of dependencies F is the set of all FDs implied by F, obtained by applying Armstrong's axioms until nothing new appears.
F⁺ is usually enormous (exponential in the number of attributes), so it is almost never computed. Instead we compute attribute closure, which answers the questions we actually care about.
20.3 Attribute Closure — the Workhorse¶
X⁺
The attribute closure X⁺ of a set of attributes X under F is the set of all attributes functionally determined by X:
X⁺ = { A : X → A is in F⁺ }
The algorithm
result := X
repeat
for each functional dependency Y -> Z in F:
if Y ⊆ result and Z ⊄ result then
result := result ∪ Z
until result does not change
return result
Read it as: "start with X; whenever you already have everything on the left of a dependency, you may add everything on its right; repeat until stuck."
What X⁺ lets you decide¶
| Question | Test |
|---|---|
Is X → Y implied by F? |
Is Y ⊆ X⁺? |
Is X a superkey? |
Is X⁺ = R? |
Is X a candidate key? |
X⁺ = R, and for every proper subset X' of X, X'⁺ ≠ R. |
Are F and G equivalent? |
Every FD of F follows from G, and vice versa (checked by closures). |
Worked example¶
R(A, B, C, D, E) with F = { A → BC, CD → E, B → D, E → A }.
Compute A⁺:
| Step | Dependency used | Added | Result |
|---|---|---|---|
| 0 | start | A | {A} |
| 1 | A → BC (A ⊆ {A}) |
B, C | {A,B,C} |
| 2 | B → D (B ⊆ {A,B,C}) |
D | {A,B,C,D} |
| 3 | CD → E (CD ⊆ {A,B,C,D}) |
E | {A,B,C,D,E} |
| 4 | E → A — A already present |
— | no change |
A⁺ = {A,B,C,D,E} = R, so A is a superkey, and since it is a single attribute it is minimal, so A is a candidate key.
Compute B⁺: start {B}; B → D gives {B,D}; no dependency's left side is now contained in {B,D} (A→BC needs A; CD→E needs C; E→A needs E). So B⁺ = {B,D} — B is not a superkey.
Compute CD⁺: start {C,D}; CD → E gives {C,D,E}; E → A gives {A,C,D,E}; A → BC gives {A,B,C,D,E}. So CD⁺ = R — superkey. Minimal? C⁺ = {C} and D⁺ = {D}, neither is R, so CD is a candidate key.
Compute E⁺: {E} → E→A gives {A,E} → A→BC gives {A,B,C,E} → B→D gives all. E is a candidate key.
Compute BC⁺: {B,C} → B→D gives {B,C,D} → CD→E gives {B,C,D,E} → E→A gives all. Superkey. B⁺={B,D}, C⁺={C} — neither is R, so BC is a candidate key.
Candidate keys of R: A, E, BC, CD.
Checking whether an FD is implied
Is AB → E implied by F?
AB⁺ = start {A,B} → A→BC gives {A,B,C} → B→D gives {A,B,C,D} → CD→E gives all. Since E ∈ AB⁺, yes.
Is D → A implied?
D⁺ = {D}. A ∉ D⁺, so no.
This single technique replaces any attempt to enumerate F⁺.
20.4 Equivalence and Covers¶
Cover and equivalence
F covers G if every FD in G can be inferred from F — that is, G ⊆ F⁺.
F and G are equivalent (F ≡ G) if F covers G and G covers F. Equivalent sets impose exactly the same constraints.
To test F ≡ G: for each X → Y in G, compute X⁺ under F and check Y ⊆ X⁺; then repeat in the other direction. There is no need to build either closure of dependencies.
Minimal (canonical) cover¶
Minimal cover
A set F of dependencies is minimal if:
- Every dependency has a single attribute on its right-hand side.
- No dependency has an extraneous attribute on its left: removing any attribute from
XinX → Ayields a set no longer equivalent toF. - No dependency is redundant: removing any whole dependency yields a set no longer equivalent to
F.
A minimal cover of F is a minimal set equivalent to F. It need not be unique.
The algorithm — the order of the steps matters
Step 1. Split every right-hand side into single attributes. (Valid by the decomposition rule.)
Step 2. For each X → A with |X| > 1, and each attribute B ∈ X: if A ∈ (X − B)⁺ computed under the current set, then B is extraneous — remove it.
Step 3. For each dependency f in the current set: if f is still implied by the set without f, remove f.
Step 1 first, because splitting exposes extraneous attributes; step 2 before step 3, because reducing left sides can make dependencies redundant.
Worked example¶
F = { A → BC, B → C, A → B, AB → C }
Step 1 — split right sides:
A → B, A → C, B → C, A → B (duplicate, drop one), AB → C
Current: { A → B, A → C, B → C, AB → C }
Step 2 — extraneous left attributes. Only AB → C has more than one attribute on the left.
Is A extraneous? Compute B⁺ under the current set: {B, C}. C ∈ B⁺, so yes — AB → C reduces to B → C, which is already present.
Current: { A → B, A → C, B → C }
Step 3 — redundant dependencies.
- Remove
A → B: isB ∈ A⁺under{A → C, B → C}?A⁺ = {A, C}. No — keepA → B. - Remove
A → C: isC ∈ A⁺under{A → B, B → C}?A⁺ = {A, B, C}. Yes — remove it. - Remove
B → C: isC ∈ B⁺under{A → B}?B⁺ = {B}. No — keep.
Minimal cover: { A → B, B → C }.
Minimal covers are not unique
For F = { A → B, B → A, A → C, B → C } two different minimal covers exist:
{ A → B, B → A, A → C } and { A → B, B → A, B → C }.
Both are correct. An examination answer should show the working, which justifies whichever is obtained.
Why minimal covers matter: the 3NF synthesis algorithm (Lesson 5) builds one relation per dependency of a minimal cover. A smaller cover therefore yields a smaller, better schema.
20.5 Solved Questions¶
Solved Question 1
Q. Define a functional dependency. Can an FD be proved from a relation state? Justify.
A. For X, Y ⊆ R, the functional dependency X → Y holds if in every legal state of R, any two tuples agreeing on X also agree on Y.
An FD cannot be proved from a relation state; it can only be disproved.
A relation state is a snapshot. An FD is a constraint on all possible states, present and future. Observing that a snapshot satisfies X → Y shows only that no counter-example happens to be present today.
Illustration. In a small college the data may show that no two students share a name:
| Rollno | Name |
|---|---|
| X2019 | Ankit Sharma |
| X2020 | Riya Verma |
This state satisfies Name → Rollno. But the FD is false, because the mini-world permits two students called Ankit Sharma; admitting one tomorrow would violate it. Declaring it would wrongly reject a legitimate admission.
Disproof, by contrast, is conclusive. Two tuples agreeing on X and differing on Y demonstrate that the constraint does not hold, since a legal state violating it exists.
The practical conclusion: FDs are obtained from the semantics of the mini-world — by asking the users — not by inspecting sample data. Sample data is useful only for catching FDs you asserted wrongly.
Solved Question 2
Q. State Armstrong's axioms. Prove the union and pseudotransitivity rules from them. What is meant by saying the axioms are sound and complete?
A. A1 Reflexivity: if Y ⊆ X then X → Y. A2 Augmentation: if X → Y then XZ → YZ. A3 Transitivity: if X → Y and Y → Z then X → Z.
Union: given X → Y and X → Z, prove X → YZ.
| Step | Justification |
|---|---|
1. X → Y |
given |
2. X → XY |
augment (1) with X: XX → YX, and XX = X |
3. X → Z |
given |
4. XY → YZ |
augment (3) with Y |
5. X → YZ |
transitivity of (2) and (4) |
Pseudotransitivity: given X → Y and WY → Z, prove WX → Z.
| Step | Justification |
|---|---|
1. X → Y |
given |
2. WX → WY |
augment (1) with W |
3. WY → Z |
given |
4. WX → Z |
transitivity of (2) and (3) |
Soundness means every FD derivable using A1–A3 is genuinely implied by F — the rules never generate a dependency that some legal state violates.
Completeness means every FD implied by F is derivable using A1–A3 — no implied dependency is out of reach.
Together they establish that the axioms generate exactly F⁺, which is what makes F⁺ well defined and makes attribute closure a correct decision procedure for implication.
Solved Question 3
Q. For R(A,B,C,D,E) with F = {A → BC, CD → E, B → D, E → A}, compute A⁺, B⁺, CD⁺, AB⁺, and find all candidate keys.
A.
A⁺: {A} →(A→BC) {A,B,C} →(B→D) {A,B,C,D} →(CD→E) {A,B,C,D,E}. A⁺ = R.
B⁺: {B} →(B→D) {B,D}. No further left side is contained. B⁺ = {B,D}.
CD⁺: {C,D} →(CD→E) {C,D,E} →(E→A) {A,C,D,E} →(A→BC) {A,B,C,D,E}. CD⁺ = R.
AB⁺: contains A⁺, so = R (but not minimal, since A alone suffices).
Candidate keys. Test each set: it is a candidate key if its closure is R and no proper subset's closure is R.
| Set | Closure | Superkey? | Minimal? | Candidate key? |
|---|---|---|---|---|
| A | R | yes | single attribute | yes |
| B | {B,D} | no | — | no |
| C | {C} | no | — | no |
| D | {D} | no | — | no |
| E | R | yes | single attribute | yes |
| BC | R | yes | B⁺≠R, C⁺≠R |
yes |
| CD | R | yes | C⁺≠R, D⁺≠R |
yes |
| AB, AE, … | R | yes | contain A or E | no |
| BD, CE, DE | {B,D}, R… | — | E⁺=R so CE, DE contain a key |
no |
Candidate keys: A, E, BC, CD.
Prime attributes: A, B, C, D, E — all of them.
Non-prime attributes: none. (This is why R turns out to be in 3NF despite B → D violating BCNF — see Lesson 4.)
Solved Question 4
Q. Show that decomposition on the left-hand side is invalid: XY → Z does not imply X → Z. Give a concrete counter-example.
A. The rule fails because X alone may not determine enough to fix Z; the dependency asserts something about the combination.
Counter-example from the college database. The true dependency is
Rollno, SID → Dateofadmission
— a student-course pair has exactly one admission date. Suppose Rollno → Dateofadmission also held. Consider:
| Rollno | SID | Dateofadmission |
|---|---|---|
| X2019 | CS01 | 2019-07-15 |
| X2019 | MA02 | 2019-08-01 |
This state is legal: the two tuples differ on (Rollno, SID), so Rollno, SID → Dateofadmission is not violated. But the two tuples agree on Rollno and differ on Dateofadmission, so Rollno → Dateofadmission is violated.
A legal state satisfying the premise while violating the conclusion is exactly a proof that the inference is invalid.
Contrast with the right-hand side, where decomposition is valid: X → YZ implies X → Y, because YZ → Y by reflexivity and transitivity applies. Two tuples agreeing on X must agree on all of YZ, hence in particular on Y.
Mnemonic: right sides split; left sides do not. Getting this backwards is one of the commonest errors in normalisation questions.
Solved Question 5
Q. Compute a minimal cover of F = { AB → C, A → B, B → A, C → AB } over R(A,B,C). Show every step.
A.
Step 1 — single attributes on the right.
AB → C, A → B, B → A, C → A, C → B
Step 2 — remove extraneous left attributes. Only AB → C qualifies.
- Is
Bextraneous? ComputeA⁺under the current set:{A}→(A→B){A,B}→(AB→C){A,B,C}. SinceC ∈ A⁺, yes — replaceAB → CbyA → C. - Now the set is
{ A → C, A → B, B → A, C → A, C → B }. No left side has more than one attribute, so step 2 is complete.
Step 3 — remove redundant dependencies, testing each in turn against the others.
| Candidate | Test | Verdict |
|---|---|---|
A → C |
A⁺ under {A→B, B→A, C→A, C→B} = {A,B}. C ∉ |
keep |
A → B |
A⁺ under {A→C, B→A, C→A, C→B} = {A,C,B}. B ∈ |
remove |
B → A |
B⁺ under {A→C, C→A, C→B} = {B}. A ∉ |
keep |
C → A |
C⁺ under {A→C, B→A, C→B} = {C,B,A}. A ∈ |
remove |
C → B |
C⁺ under {A→C, B→A} = {C}. B ∉ |
keep |
Minimal cover: { A → C, B → A, C → B }.
Verification that it is equivalent to the original: under the cover, A⁺ = {A,C,B} = R, B⁺ = {B,A,C} = R, C⁺ = {C,B,A} = R. So every original dependency — AB → C, A → B, B → A, C → AB — is recovered, and the candidate keys A, B and C are unchanged.
Note the elegant cyclic result A → C → B → A, which correctly captures that all three attributes determine one another.
Solved Question 6
Q. Are F = {A → B, B → C, A → C} and G = {A → B, B → C} equivalent? Prove it.
A. Two sets are equivalent when each covers the other. Test each dependency of one against closures computed under the other.
Does G cover F? For each FD of F, compute the left side's closure under G:
| FD of F | Closure under G | Right side included? |
|---|---|---|
A → B |
A⁺ = {A} →(A→B) {A,B} →(B→C) {A,B,C} |
B ∈ — yes |
B → C |
B⁺ = {B} →(B→C) {B,C} |
C ∈ — yes |
A → C |
A⁺ = {A,B,C} |
C ∈ — yes |
Every FD of F follows from G, so G covers F.
Does F cover G? G ⊆ F literally — both its dependencies appear in F — so trivially yes.
Therefore F ≡ G.
The dependency A → C in F is redundant: it is derivable from A → B and B → C by transitivity. G is in fact a minimal cover of F.
Note on method. It was never necessary to construct F⁺ or G⁺, which would be exponentially large. Testing implication by attribute closure — "is the right side inside the left side's closure?" — is the standard and only practical technique.
20.6 Exercises¶
A. Short answer
- Define a functional dependency.
- Why can an FD not be proved from a relation state?
- State Armstrong's axioms.
- What does it mean for the axioms to be sound and complete?
- Distinguish trivial from completely non-trivial FDs.
- State the test for
Xbeing a superkey. - What are the three conditions for a set of FDs to be minimal?
B. Computation
- For
R(A,B,C,D)withF = {A → B, B → C, C → D}, computeA⁺,B⁺,C⁺,D⁺and find all candidate keys. - For
R(A,B,C,D,E,F)withF = {A → BC, CD → E, B → D, E → A, F → A}, computeA⁺,F⁺,BC⁺and find all candidate keys. - For
R(A,B,C,D,E)withF = {AB → C, C → D, D → A, D → E}, find all candidate keys. - For
R(P,Q,R,S,T)withF = {P → QR, RS → T, Q → S, T → P}, find all candidate keys. - Determine whether each is implied by
F = {A → B, BC → D, D → E}: a.AC → Db.A → Ec.AC → Ed.B → Ee.ABC → DE - Compute a minimal cover of
F = {A → BC, B → C, AB → D, ABC → D}. - Compute a minimal cover of
F = {AB → C, C → A, BC → D, ACD → B, D → EG, BE → C, CG → BD, CE → AG}. - Are
F = {A → B, AB → C, D → AC, D → E}andG = {A → BC, D → AE}equivalent? Show your working.
C. Proof and analysis
- Prove the decomposition rule from Armstrong's axioms.
- Prove the composition rule: if
X → YandZ → WthenXZ → YW. - Give a counter-example showing
X → ZandY → Zdo not implyX → Y. - Explain why
F⁺is not computed in practice, and what is computed instead. - Show that a minimal cover need not be unique, by giving a set with two different minimal covers.
- From this description, write down all the FDs: > "Each student has one roll number, name and date of birth. Each course has one identifier, name, seat count and teacher-in-charge. A student may be admitted to several courses; each admission has one date. Each course is taught in one department, and each department has one head."
- A colleague asserts
Name → Rollnobecause the current 400 rows satisfy it. Explain, with reference to the definition, why this reasoning is invalid, and describe what evidence would be needed instead.
D. Objective — True or False with reason
X → Ycan be verified by examining the current relation state.- Every superkey
KsatisfiesK → R. AB → CimpliesA → C.A → BCimpliesA → B.- A minimal cover is unique.
- Armstrong's axioms are sound but not complete.
- If
X⁺ = RthenXis a candidate key.
Answers to Section D
- False. A state can only disprove an FD; an FD constrains all possible states.
- True. That is the definition of a superkey in FD terms.
- False. Left-side decomposition is invalid. Counter-example:
Rollno, SID → DateofadmissionwhileRollno → Dateofadmissionis false. - True. Right-side decomposition is valid, by reflexivity (
BC → B) and transitivity. - False. Different orders of removal can yield different, equally valid minimal covers.
- False. They are both sound and complete — they generate exactly
F⁺. - False. It makes
Xa superkey. It is a candidate key only if it is also minimal.
Lesson Summary
- An FD
X → Yconstrains every legal state; data can disprove one but never prove one. - Armstrong's axioms — reflexivity, augmentation, transitivity — are sound and complete, and yield union, decomposition and pseudotransitivity.
- Right sides split; left sides do not.
X → YZgivesX → Y;XY → Zgives nothing aboutX → Z. X⁺is the workhorse: it tests implication (Y ⊆ X⁺), superkeys (X⁺ = R) and candidate keys (superkey + minimal).- Two FD sets are equivalent if each covers the other — checked with attribute closures, never by building
F⁺. - A minimal cover has single-attribute right sides, no extraneous left attributes and no redundant FDs. It need not be unique, and it drives 3NF synthesis.