Skills101

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).

RuleStatementExample from F
Reflexivityif Y ⊆ X then X → YAB → A (trivial)
Augmentationif X → Y then XZ → YZA → BC gives AD → BCD
Transitivityif X → Y and Y → Z then X → ZE → 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:

  1. Start with result = X.
  2. For every FD L → R: if L is inside result, add R to result.
  3. Repeat until nothing changes.

Computing the closure of A step by step: start with A; A to BC adds B and C; B to D adds D; CD to E adds E; the result ABCDE is all attributes, so A is a key

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:

  1. Attributes that appear on no right side must be in every key. (Here every attribute appears on some right side, so there are none.)
  2. Attributes that appear only on right sides are never needed in a key.
  3. 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 }

  1. Split right sides: A → B, A → C, B → C, A → B, AB → C. Remove the repeated A → B.
  2. 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.
  3. 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 formLossless split always possible?Dependency preserving always possible?
3NFyesyes
BCNFyesnot 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.

Practice what you learned

📝 Quiz: Functional Dependencies5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →