Functional Dependencies

Good database design starts from the rules that hold in the data. The most important kind of rule is the functional dependency.

Definition

In a relation R, the functional dependency X → Y ("X determines Y") holds if any two tuples that agree on the attributes X also agree on Y. In other words, each X value comes with exactly one Y value.

In Student(roll, name, dept, hod):

• roll → name, dept: a roll number identifies one student.
• dept → hod: each department has one head.
• name → roll does not hold if two students can have the same name.

An FD is a statement about every legal instance of the schema. A single table instance can show that an FD does not hold (two rows with the same X and different Y), but it can never prove that an FD holds.

An FD X → Y is trivial if Y ⊆ X, such as roll, name → name. Trivial FDs hold in every relation.

Armstrong's axioms

From a given set F of FDs, other FDs follow. Armstrong's axioms derive all of them, and only correct ones (they are sound and complete):

The set of all FDs implied by F is the closure F⁺.

Attribute closure

Computing F⁺ is expensive, but we rarely need it. The workhorse is the closure of an attribute set X, written X⁺: all attributes that X determines.

Example: R(A, B, C, D, E, F) with F = { A → B, B → C, C → D, AE → F }. To find (AE)⁺: start with {A, E}; A → B adds B; B → C adds C; C → D adds D; AE → F adds F. So (AE)⁺ = {A, B, C, D, E, F}, all of R, which makes AE a superkey.

Attribute closure answers the common questions:

• Does X → Y follow from F? Exactly when Y ⊆ X⁺.
• Is X a superkey? Exactly when X⁺ contains every attribute of R.
• Is X a candidate key? When X is a superkey and no proper subset of X is.

Finding all candidate keys

A quick observation narrows the search: an attribute that never appears on the right side of any FD can never be determined by others, so it must be in every candidate key. An attribute that appears only on the right side (never on the left) is in no candidate key.

Example: R(A, B, C, D, E) with F = { A → BC, CD → E, B → D, E → A }.

• A⁺ = {A, B, C, D, E} (A → BC, B → D, CD → E): A is a candidate key.
• Since E → A, E⁺ ⊇ A⁺, so E is a candidate key too.
• (BC)⁺: B → D gives D, CD → E gives E, E → A gives A: BC is a key.
• (CD)⁺: CD → E, E → A, A → BC: CD is a key.
• (BD)⁺ = {B, D} only, so BD is not a superkey.

This program checks every attribute set in order of size, keeping only the minimal ones:

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(relation, fds):
    keys = []
    for size in range(1, len(relation) + 1):
        for combo in combinations(relation, size):
            if closure(combo, fds) == set(relation) and not any(set(k) <= set(combo) for k in keys):
                keys.append("".join(combo))
    return keys

fds = [("A", "BC"), ("CD", "E"), ("B", "D"), ("E", "A")]
print("(BD)+ =", "".join(sorted(closure("BD", fds))))
print("candidate keys:", candidate_keys("ABCDE", fds))

(BD)+ = BD
candidate keys: ['A', 'E', 'BC', 'CD']

Equivalence of FD sets

Two FD sets F and G are equivalent if F⁺ = G⁺. To check, test that every FD of G follows from F (using closures under F) and every FD of F follows from G.

Example: F = { A → B, B → C } and G = { A → B, B → C, A → C } are equivalent: A → C follows from F by transitivity, and F ⊆ G.

Minimal (canonical) cover

A minimal cover of F is an equivalent set with no redundancy. Build it in three steps:

1. Split right sides into single attributes: A → BC becomes A → B and A → C.
2. Remove extraneous left-side attributes: in XA → B, attribute A is extraneous if X → B already follows (B ∈ X⁺).
3. Remove redundant FDs: drop X → B if B ∈ X⁺ computed with the other FDs.

Example: F = { A → B, AB → C, D → AC, D → E }.

1. Split: A → B, AB → C, D → A, D → C, D → E.
2. In AB → C, B is extraneous because A⁺ = {A, B, C} already contains C: it becomes A → C.
3. D → C is redundant: without it, D⁺ = {D, A, E, B, C} still contains C.

Minimal cover: { A → B, A → C, D → A, D → E }, 4 FDs. A set can have more than one minimal cover, depending on the order in which the steps are applied.

Practice questions