AdvancedDBMS & SQL · Lesson 15 of 17 · Updated ·
Functional Dependencies — Closure, Candidate Keys, Canonical Cover and Lossless Decomposition
The normalization lesson used functional dependencies (FDs) informally. University exams and GATE-style tests go further: "find the closure of A", "find all candidate keys", "find the canonical cover", "is this decomposition lossless?". This lesson solves each type step by step.
Reminder: an FD X → Y means: two rows that agree on X must also agree on Y. X is the determinant. For example, roll_no → name.
We use one running example: relation R(A, B, C, D, E) with
F = { A → BC, CD → E, B → D, E → A }
1. Armstrong's axioms
These rules let you derive new FDs from given ones. They are sound (they never produce a wrong FD) and complete (they produce every FD that follows).
| Rule | Statement | Example from F |
|---|---|---|
| Reflexivity | if Y ⊆ X then X → Y | AB → A (trivial) |
| Augmentation | if X → Y then XZ → YZ | A → BC gives AD → BCD |
| Transitivity | if X → Y and Y → Z then X → Z | E → A and A → BC give E → BC |
Useful rules that follow from these:
- Union: X → Y and X → Z give X → YZ.
- Decomposition: X → YZ gives X → Y and X → Z. So A → BC means A → B and A → C.
- Pseudo-transitivity: X → Y and WY → Z give WX → Z.
An FD is trivial if the right side is a subset of the left side (AB → B). Trivial FDs hold in every table.
2. Attribute closure (X⁺)
The closure X⁺ is the set of all attributes that X determines. Algorithm:
- Start with result = X.
- For every FD L → R: if L is inside result, add R to result.
- Repeat until nothing changes.
So A⁺ = ABCDE. Because A determines every attribute, A is a super key, and since a single attribute cannot be reduced, it is a candidate key.
Compare B⁺: start with B, B → D adds D, then nothing else fires (we need A, CD or E). B⁺ = BD, so B alone is not a key.
Closure also answers "does X → Y follow from F?" — check whether Y ⊆ X⁺. Does B → E follow? B⁺ = BD does not contain E, so no.
3. Finding all candidate keys
A candidate key is a minimal set of attributes whose closure is all of R. A quick method:
- Attributes that appear on no right side must be in every key. (Here every attribute appears on some right side, so there are none.)
- Attributes that appear only on right sides are never needed in a key.
- Test small sets first; skip any set that contains a key already found (it would not be minimal).
The code below does exactly this, by brute force over all subsets — fine for exam-sized relations.
from itertools import combinations
def closure(attrs, fds):
result = set(attrs)
changed = True
while changed:
changed = False
for lhs, rhs in fds:
if set(lhs) <= result and not set(rhs) <= result:
result |= set(rhs)
changed = True
return ''.join(sorted(result))
F = [('A', 'BC'), ('CD', 'E'), ('B', 'D'), ('E', 'A')]
R = 'ABCDE'
for x in ['A', 'B', 'C', 'BC', 'CD']:
print(x, '+ =', closure(x, F))
keys = []
for size in range(1, len(R) + 1):
for combo in combinations(R, size):
if closure(combo, F) == R and not any(set(k) <= set(combo) for k in keys):
keys.append(''.join(combo))
print('Candidate keys:', keys)
A + = ABCDE
B + = BD
C + = C
BC + = ABCDE
CD + = ABCDE
Candidate keys: ['A', 'E', 'BC', 'CD']
There are four candidate keys: A, E, BC and CD. So the prime attributes (those that belong to some candidate key) are A, B, C, D and E — all of them. That matters for normal forms: with every attribute prime, R is automatically in 3NF.
Why is BC a key? BC⁺: B → D gives BCD, CD → E gives BCDE, E → A gives ABCDE. And neither B⁺ = BD nor C⁺ = C is everything, so BC is minimal.
4. Canonical (minimal) cover
A canonical cover Fc is a simplest set of FDs equivalent to F. It has:
- a single attribute on every right side (split A → BC into A → B, A → C);
- no extraneous attribute on any left side;
- no redundant FD (one that can be derived from the others).
Worked example: F = { A → BC, B → C, A → B, AB → C }
- Split right sides: A → B, A → C, B → C, A → B, AB → C. Remove the repeated A → B.
- Extraneous left attributes: in AB → C, is B extraneous? Check A⁺ using the FDs: A → B, then B → C, so A⁺ contains C. Yes — replace AB → C by A → C, which we already have.
- Redundant FDs: now { A → B, A → C, B → C }. Is A → C redundant? Without it, A⁺ = {A, B, C} (via A → B, B → C). C is still reached, so remove it.
Fc = { A → B, B → C }. Two FDs carry all the information of the original four.
5. Lossless and lossy decomposition
Normalization splits a table into smaller tables. A split is lossless if joining the pieces gives back exactly the original rows — no fewer, no more.
Test for two tables: a decomposition of R into R1 and R2 is lossless if the common attributes form a key of at least one side:
(R1 ∩ R2) → R1 or (R1 ∩ R2) → R2
Let us see a lossy split happen. The table person(roll, name, city) has roll → name, city. Two different students are both called Asha.
CREATE TABLE person (roll INT PRIMARY KEY, name VARCHAR(20), city VARCHAR(20));
INSERT INTO person VALUES (1, 'Asha', 'Jaipur'), (2, 'Asha', 'Pune'), (3, 'Ravi', 'Delhi');
CREATE TABLE p1 AS SELECT roll, name FROM person;
CREATE TABLE p2 AS SELECT name, city FROM person;
SELECT p1.roll, p1.name, p2.city FROM p1 JOIN p2 ON p1.name = p2.name ORDER BY p1.roll, p2.city;
roll | name | city
1 | Asha | Jaipur
1 | Asha | Pune
2 | Asha | Jaipur
2 | Asha | Pune
3 | Ravi | Delhi
Five rows instead of three. Rows like (1, Asha, Pune) are spurious tuples — invented by the join. The common attribute name is not a key of either piece, so the test fails. "Lossy" means we lost information: we can no longer tell which Asha lives where.
Now split on roll, which is a key:
CREATE TABLE q1 AS SELECT roll, name FROM person;
CREATE TABLE q2 AS SELECT roll, city FROM person;
SELECT q1.roll, q1.name, q2.city FROM q1 JOIN q2 ON q1.roll = q2.roll ORDER BY q1.roll;
roll | name | city
1 | Asha | Jaipur
2 | Asha | Pune
3 | Ravi | Delhi
Exactly the original three rows: lossless, because roll → name (the common attribute is a key of q1).
6. Dependency preservation
A decomposition is dependency preserving if every FD can be checked inside a single smaller table, without a join. Each FD should have all its attributes in one table (or be derivable from FDs that do).
Example: R(A, B, C) with A → B and B → C.
- Split into (A, B) and (B, C): A → B lives in the first, B → C in the second. Preserving, and lossless (B is a key of (B, C)).
- Split into (A, B) and (A, C): lossless (A is a key of both), but B → C now spans two tables. Not preserving — checking it needs a join.
| Normal form | Lossless split always possible? | Dependency preserving always possible? |
|---|---|---|
| 3NF | yes | yes |
| BCNF | yes | not always |
This is the main reason designers sometimes stop at 3NF instead of BCNF.
Common mistakes
- Stopping the closure loop after one pass. Keep going until a full pass adds nothing.
- Calling a super key a candidate key without checking that it is minimal (AB⁺ = ABCDE, but AB is not minimal because A alone works).
- Forgetting that one relation can have several candidate keys.
- Testing losslessness by looking at the data once. The rule (common attributes form a key of one side) must hold by the FDs.
- Mixing up lossless (no spurious rows) with dependency preserving (no FD needs a join).
Quick recap
- Armstrong's axioms: reflexivity, augmentation, transitivity (+ union, decomposition, pseudo-transitivity).
- X⁺: keep adding right sides whose left side is already inside, until nothing changes.
- Candidate key = minimal X with X⁺ = all attributes; test small sets first.
- Canonical cover: single right sides, no extraneous left attributes, no redundant FDs.
- Lossless if (R1 ∩ R2) is a key of R1 or R2; 3NF can always keep FDs, BCNF sometimes cannot.