Functional Dependencies, Closure & Candidate Keys

What is a functional dependency?

In a table of students, the roll number decides the name: two rows with the same roll number must have the same name. We write RollNo → Name and say roll number functionally determines name.

In general, X → Y means: whenever two rows agree on all attributes in X, they also agree on all attributes in Y. Functional dependencies (FDs) describe the rules of the real world, such as “one ISBN, one title” or “one PIN code, one city”.

Why care? FDs tell us which attributes can be a key, and which tables contain redundancy that normalisation should remove.

Attribute closure X⁺

The closure X⁺ is the set of all attributes that X determines, directly or through a chain of dependencies. To compute it:

1. Start with X⁺ = X.
2. Look for a dependency L → R whose left side L is entirely inside X⁺. Add R.
3. Repeat until a full pass adds nothing.

Example. R(A, B, C, G, H, I) with A → B, A → C, CG → H, CG → I, B → H. Compute (AG)⁺:

(AG)⁺ contains every attribute, so AG is a superkey.

Superkeys and candidate keys

• A superkey is any set X with X⁺ = all attributes.
• A candidate key is a minimal superkey: remove any attribute and it stops being a superkey.
• A prime attribute belongs to at least one candidate key. Normal forms (2NF, 3NF, BCNF) are defined using prime and non-prime attributes.

AG is a candidate key, because A⁺ = {A, B, C, H} and G⁺ = {G} are not everything.

Finding all candidate keys

Testing every subset works but is slow. Two shortcuts make it fast by hand:

1. The core. An attribute that never appears on the right side of any FD cannot be determined by anything, so it must be in every key. Start from the core.
2. Skip supersets. Once a key is found, any bigger set containing it is not minimal.

Example. R(A, B, C, D, E) with A → BC, CD → E, B → D, E → A. Every attribute appears on some right side, so the core is empty.

• Single attributes: A⁺ = ABCDE ✓, E⁺ = EABCD ✓, while B⁺ = BD, C⁺ = C and D⁺ = D are not keys.
• Pairs without A or E: BC⁺ = BCDEA ✓, CD⁺ = CDEAB ✓, but BD⁺ = BD.
• Every bigger set contains one of these keys.

The candidate keys are A, E, BC and CD, so every attribute is prime.

Code

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 result

def candidate_keys(R, fds):
    keys = []
    for k in range(1, len(R) + 1):                     # smallest sets first
        for combo in combinations(R, k):
            if any(set(key) <= set(combo) for key in keys):
                continue                               # contains a key: not minimal
            if closure(combo, fds) == set(R):
                keys.append("".join(combo))
    return keys

fds = [("A", "B"), ("A", "C"), ("CG", "H"), ("CG", "I"), ("B", "H")]
print(sorted(closure("AG", fds)))                      # ['A', 'B', 'C', 'G', 'H', 'I']
print(candidate_keys("ABCDE", [("A", "BC"), ("CD", "E"), ("B", "D"), ("E", "A")]))
# ['A', 'E', 'BC', 'CD']

Useful rules (Armstrong’s axioms)

All the dependencies that follow from a set of FDs can be derived with three rules:

From these follow union (X → Y and X → Z give X → YZ) and decomposition (X → YZ gives X → Y and X → Z). Computing X⁺ is a fast way to apply all of them at once: X → Y holds exactly when Y ⊆ X⁺.

Common mistakes

• Firing a dependency when only part of its left side is in the closure. CG → H needs both C and G.
• Stopping after one pass. A later dependency can enable an earlier one, so repeat until nothing changes.
• Calling a superkey a candidate key without checking that it is minimal.
• Forgetting the core attributes that never appear on a right side. Every key must include them.