# Functional Dependencies — Closure, Candidate Keys, Canonical Cover and Lossless Decomposition

Source: https://skills101.in/learn/dbms-sql/dbms-functional-dependencies — Skills101 free tutorial (DBMS & SQL). Updated 2026-11-18.

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:

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](https://skills101.in/learn-img/dbms-sql/fd-closure.svg)

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.

```python
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)
```

```text
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.

```sql
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;
```

```text
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:

```sql
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;
```

```text
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.


Practice quiz and free certificate: https://skills101.in/learn/dbms-sql/dbms-functional-dependencies