Skip to content

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

  1. Define a functional dependency precisely, and identify FDs from a description.
  2. State and apply Armstrong's axioms and the derived rules.
  3. Compute the attribute closure X⁺ mechanically and reliably.
  4. Use X⁺ to test whether X is a superkey, and whether an FD is implied.
  5. 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, t2 in r(R): if t1[X] = t2[X] then t1[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 → Y where Y ⊆ X. Always true, carries no information. AB → A.
  • Non-trivial: X → Y where Y ⊄ X (at least one attribute of Y is outside X). AB → BC.
  • Completely non-trivial: X → Y where X ∩ 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:

  1. Every dependency has a single attribute on its right-hand side.
  2. No dependency has an extraneous attribute on its left: removing any attribute from X in X → A yields a set no longer equivalent to F.
  3. 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: is B ∈ A⁺ under {A → C, B → C}? A⁺ = {A, C}. No — keep A → B.
  • Remove A → C: is C ∈ A⁺ under {A → B, B → C}? A⁺ = {A, B, C}. Yes — remove it.
  • Remove B → C: is C ∈ 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 B extraneous? Compute A⁺ under the current set: {A} →(A→B) {A,B} →(AB→C) {A,B,C}. Since C ∈ A⁺, yes — replace AB → C by A → 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

  1. Define a functional dependency.
  2. Why can an FD not be proved from a relation state?
  3. State Armstrong's axioms.
  4. What does it mean for the axioms to be sound and complete?
  5. Distinguish trivial from completely non-trivial FDs.
  6. State the test for X being a superkey.
  7. What are the three conditions for a set of FDs to be minimal?

B. Computation

  1. For R(A,B,C,D) with F = {A → B, B → C, C → D}, compute A⁺, B⁺, C⁺, D⁺ and find all candidate keys.
  2. For R(A,B,C,D,E,F) with F = {A → BC, CD → E, B → D, E → A, F → A}, compute A⁺, F⁺, BC⁺ and find all candidate keys.
  3. For R(A,B,C,D,E) with F = {AB → C, C → D, D → A, D → E}, find all candidate keys.
  4. For R(P,Q,R,S,T) with F = {P → QR, RS → T, Q → S, T → P}, find all candidate keys.
  5. Determine whether each is implied by F = {A → B, BC → D, D → E}: a. AC → D b. A → E c. AC → E d. B → E e. ABC → DE
  6. Compute a minimal cover of F = {A → BC, B → C, AB → D, ABC → D}.
  7. Compute a minimal cover of F = {AB → C, C → A, BC → D, ACD → B, D → EG, BE → C, CG → BD, CE → AG}.
  8. Are F = {A → B, AB → C, D → AC, D → E} and G = {A → BC, D → AE} equivalent? Show your working.

C. Proof and analysis

  1. Prove the decomposition rule from Armstrong's axioms.
  2. Prove the composition rule: if X → Y and Z → W then XZ → YW.
  3. Give a counter-example showing X → Z and Y → Z do not imply X → Y.
  4. Explain why F⁺ is not computed in practice, and what is computed instead.
  5. Show that a minimal cover need not be unique, by giving a set with two different minimal covers.
  6. 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."
  7. A colleague asserts Name → Rollno because 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

  1. X → Y can be verified by examining the current relation state.
  2. Every superkey K satisfies K → R.
  3. AB → C implies A → C.
  4. A → BC implies A → B.
  5. A minimal cover is unique.
  6. Armstrong's axioms are sound but not complete.
  7. If X⁺ = R then X is a candidate key.

Answers to Section D

  1. False. A state can only disprove an FD; an FD constrains all possible states.
  2. True. That is the definition of a superkey in FD terms.
  3. False. Left-side decomposition is invalid. Counter-example: Rollno, SID → Dateofadmission while Rollno → Dateofadmission is false.
  4. True. Right-side decomposition is valid, by reflexivity (BC → B) and transitivity.
  5. False. Different orders of removal can yield different, equally valid minimal covers.
  6. False. They are both sound and complete — they generate exactly F⁺.
  7. False. It makes X a superkey. It is a candidate key only if it is also minimal.

Lesson Summary

  • An FD X → Y constrains 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 → YZ gives X → Y; XY → Z gives nothing about X → 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.