SyntaxPilot
Courses/CS Fundamentals for Placements/Lesson 49
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

CS Fundamentals for Placements · Lesson 49 of 90

Functional dependencies 2: minimal cover and decomposition

canonical/minimal coverextraneous attributesequivalence of FD setsdecompositionlossless-join decomposition and its test (common attribute is a key, chase/tableau)lossy decomposition and spurious tuplesdependency preservation and its checknumericals

These are the notes for CS Fundamentals for Placements, episode 49. We test when two FD sets are equivalent, find extraneous attributes and redundant FDs, compute the canonical / minimal cover, and then split tables safely: decomposition, lossy decomposition and spurious tuples, the lossless-join test (common attributes form a key; the chase / tableau test), and dependency preservation with its check, plus GATE-style numericals. Every term is explained in plain words the first time it appears, and there is a full glossary at the end.

All program outputs below are real: every Python program was run with python3 (Python 3.13) on Linux x86-64 on 9 November 2026.

From episode 48 you need: an FD X → Y (equal X values force equal Y values), F (the given FDs), F+ (every FD that follows from F), the attribute closure X+ (every attribute X determines), super key (X+ = all attributes) and candidate key (a minimal super key). In exercises attributes are single letters and AB means the set {A, B}.

1. Why trim an FD set?

A school gate notice board says:

Rule What it really is
1. A student with an ID card may enter the rule that does the work
2. A student with an ID card and a uniform may enter "uniform" is an extraneous attribute: removing it changes nothing
3. A class 10 student with an ID card may enter a redundant FD: it follows from rule 1

A database checks every FD whenever a row is inserted or updated. Repeated or bloated FDs waste that work and hide the real design. But a trimmed set must mean exactly the same thing.

2. Equivalent FD sets

  • F covers G if every FD in G follows from F (is in F+).
  • F and G are equivalent (F ≡ G) if F covers G and G covers F. Equivalent sets allow exactly the same tables.
  • Test without computing F+: for each X → Y in G, compute X+ using F; F covers G if Y ⊆ X+ every time.
def closure(X, F):
    result, changed = set(X), True
    while changed:
        changed = False
        for lhs, rhs in F:
            if set(lhs) <= result and not set(rhs) <= result:
                result |= set(rhs); changed = True
    return result

def covers(F, G):          # every FD of G follows from F
    return all(set(r) <= closure(l, F) for l, r in G)

F = [("A", "BC"), ("B", "C"), ("A", "B"), ("AB", "C")]
G = [("A", "B"), ("B", "C")]
H = [("A", "B"), ("A", "C")]
print("F covers G:", covers(F, G), "| G covers F:", covers(G, F))
print("F covers H:", covers(F, H), "| H covers F:", covers(H, F))
print("{B}+ under F:", "".join(sorted(closure("B", F))),
      "| under H:", "".join(sorted(closure("B", H))))

Output:

F covers G: True | G covers F: True
F covers H: True | H covers F: False
{B}+ under F: BC | under H: B
  • F and G are equivalent, so the four FDs of F say no more than the two of G.
  • H looked like a harmless shortcut ("B → C repeats A → C, drop it"), but under H, {B}+ is just B: the fact B → C was thrown away. Never trim by eye; test with closures.

3. Extraneous attributes and redundant FDs

Kind Definition Test Example (F above)
Extraneous attribute on the left a ∈ X of X → Y can be removed Y ⊆ (X − a)+ computed with F AB → C: {B}+ = BC contains C, so A is extraneous
Extraneous attribute on the right b ∈ Y can be removed F with X → Y − b still implies X → b A → BC: A → B and B → C give A → C, so C is extraneous
Redundant FD the whole FD follows from the others Y ⊆ X+ computed with F minus this FD A → C follows from A → B, B → C

4. Canonical / minimal cover

A minimal cover Fc of F is an FD set that is equivalent to F, has a single attribute on every right side, no extraneous attribute and no redundant FD. Algorithm:

  1. Split right sides (decomposition rule): A → BC becomes A → B, A → C.
  2. Remove extraneous attributes from every left side.
  3. Remove redundant FDs.

Do step 2 before step 3: trimming a left side can create a duplicate or make another FD redundant. Many textbooks finally merge FDs with the same left side (A → B, A → C into A → BC) and call the result the canonical cover; both forms are accepted, just say which one you use.

def closure(X, F):
    result, changed = set(X), True
    while changed:
        changed = False
        for lhs, rhs in F:
            if set(lhs) <= result and not set(rhs) <= result:
                result |= set(rhs); changed = True
    return result

def minimal_cover(F):
    F = list(dict.fromkeys((l, r) for l, rhs in F for r in rhs))   # 1. split right sides
    print("step 1:", F)
    for i, (l, r) in enumerate(F):                     # 2. extraneous left attributes
        for a in l:
            if len(l) > 1 and r in closure(l.replace(a, ""), F):
                print(f"  {a} is extraneous in {l}->{r}"); l = l.replace(a, "")
        F[i] = (l, r)
    F = list(dict.fromkeys(F)); print("step 2:", F)
    for fd in list(F):                                 # 3. redundant FDs
        rest = [g for g in F if g != fd]
        if fd[1] in closure(fd[0], rest):
            print(f"  {fd[0]}->{fd[1]} is redundant"); F = rest
    return F

print("cover:", minimal_cover([("A", "BC"), ("B", "C"), ("A", "B"), ("AB", "C")]))

Output:

step 1: [('A', 'B'), ('A', 'C'), ('B', 'C'), ('AB', 'C')]
  A is extraneous in AB->C
step 2: [('A', 'B'), ('A', 'C'), ('B', 'C')]
  A->C is redundant
cover: [('A', 'B'), ('B', 'C')]

Fc = {A → B, B → C}: exactly the G we proved equivalent in section 2.

A minimal cover is not unique

def closure(X, F):
    result, changed = set(X), True
    while changed:
        changed = False
        for lhs, rhs in F:
            if set(lhs) <= result and not set(rhs) <= result:
                result |= set(rhs); changed = True
    return result

def drop_redundant(F):
    for fd in list(F):
        rest = [g for g in F if g != fd]
        if fd[1] in closure(fd[0], rest):
            F = rest
    return F

F = [("A", "B"), ("B", "A"), ("A", "C"), ("B", "C")]
print("checking A->C first:", drop_redundant(F))
print("checking B->C first:", drop_redundant(F[:2] + [F[3], F[2]]))

Output:

checking A->C first: [('A', 'B'), ('B', 'A'), ('B', 'C')]
checking B->C first: [('A', 'B'), ('B', 'A'), ('A', 'C')]

A and B determine each other, so only one of A → C and B → C is needed. Which one survives depends on the order you test them. Both covers are correct.

Numerical by hand

F = { A → BC, CD → E, B → D, E → A }

  1. Split: A → B, A → C, CD → E, B → D, E → A.
  2. Only CD → E has two attributes on the left. {C}+ = C and {D}+ = D, neither contains E: nothing is extraneous.
  3. Test each FD without itself: without A → B, {A}+ = AC (no B); without A → C, {A}+ = ABD (no C); without CD → E, {CD}+ = CD; without B → D, {B}+ = B; without E → A, {E}+ = E. Nothing is redundant.

Fc = { A → B, A → C, CD → E, B → D, E → A }. Sometimes the answer is "nothing to remove".

5. Decomposition

A decomposition of a relation R replaces it with smaller relations R1, R2, ..., Rn whose attributes together are all of R's attributes (R1 ∪ ... ∪ Rn = R). Each Ri holds the projection of R's rows on its columns (the rows, keeping only those columns, duplicates removed). To answer questions we natural join the parts back: join rows whose shared columns are equal.

A college's single register (roll, name, course, teacher, room, fees) repeats data, so we want to split it (episode 50 shows why). But a careless split can damage the data.

6. Lossy decomposition and spurious tuples

students = [(1, "Asha", "DBMS"), (2, "Asha", "OS"), (3, "Ravi", "CN")]  # roll, name, course

# split 1: (roll, name) and (name, course): the common column is name
R1 = [(r, n) for r, n, c in students]
R2 = [(n, c) for r, n, c in students]
back = sorted({(r, n, c) for r, n in R1 for n2, c in R2 if n == n2})   # natural join
print("split on name:", len(back), "rows")
for row in back:
    print("  ", row, "" if row in students else "<- spurious")

# split 2: (roll, name) and (roll, course): the common column is roll
R2 = [(r, c) for r, n, c in students]
back = sorted({(r, n, c) for r, n in R1 for r2, c in R2 if r == r2})
print("split on roll:", len(back), "rows, same as before:", back == sorted(students))

Output:

split on name: 5 rows
   (1, 'Asha', 'DBMS') 
   (1, 'Asha', 'OS') <- spurious
   (2, 'Asha', 'DBMS') <- spurious
   (2, 'Asha', 'OS') 
   (3, 'Ravi', 'CN') 
split on roll: 3 rows, same as before: True
  • Splitting on name brought back 5 rows from 3. The 2 fake rows are spurious tuples: rows produced by the join that were never in the original table.
  • That is a lossy decomposition. Nothing was deleted; extra rows were added, and that loses information: you can no longer tell which Asha takes which course.
  • Splitting on roll gave back exactly the original rows: a lossless-join decomposition.

7. The lossless-join test (two parts)

A decomposition of R into R1 and R2 is lossless if R1 ⋈ R2 = R for every legal instance of R (every table that satisfies F), not just today's rows.

Test: with F, the decomposition is lossless if and only if

R1 ∩ R2 → R1 or R1 ∩ R2 → R2 is in F+

In words: the common attributes are a (super) key of at least one part. Compute (R1 ∩ R2)+ and check.

Split Common Closure Verdict
(roll, name), (roll, course) roll roll → name: key of part 1 lossless
(roll, name), (name, course) name name determines nothing lossy
(A, B), (C, D) ∅ nothing lossy (a cross product)

Also required: every attribute of R appears in some part.

For more than two parts you can apply the test two at a time: join two parts that pass, then test the result with the next part. If that order-based approach fails, use the chase.

8. The chase (tableau) test

  1. Build a tableau: one row per part Ri, one column per attribute of R. Put a (a known, "distinguished" value) where Ri contains the attribute, otherwise b (an unknown value; here b<row>).
  2. For each FD X → Y: whenever two rows agree on all of X, make them agree on Y. If one of the values is a, both become a; otherwise pick one b. Rename that symbol in the whole column.
  3. Repeat until nothing changes.
  4. If some row is all a, the decomposition is lossless. If not, the final tableau is a real counter-example table whose join contains a spurious row: lossy.
R, parts = "ABCDE", ["AD", "AB", "BE", "CDE", "AE"]
F = [("A", "C"), ("B", "C"), ("C", "D"), ("DE", "C"), ("CE", "A")]

def show(title):
    print(title)
    for p, row in zip(parts, T): print(f"  {p:4}", " ".join(f"{row[c]:3}" for c in R))

# tableau: one row per part; "a" if the part has the column, else "b<row>"
T = [{c: "a" if c in p else f"b{i+1}" for c in R} for i, p in enumerate(parts)]
show("start:")
changed = True
while changed:                        # chase: apply FDs until nothing changes
    changed = False
    for lhs, rhs in F:
        for s in T:
            for t in T:
                if all(s[c] == t[c] for c in lhs):
                    for c in rhs:
                        if s[c] != t[c]:      # equate them, prefer "a"
                            old, new = max(s[c], t[c]), min(s[c], t[c])
                            for u in T:       # rename in the whole column
                                if u[c] == old: u[c] = new
                            changed = True
show("after the chase:")
print("lossless:", any(all(v == "a" for v in row.values()) for row in T))

Output:

start:
  AD   a   b1  b1  a   b1 
  AB   a   a   b2  b2  b2 
  BE   b3  a   b3  b3  a  
  CDE  b4  b4  a   a   a  
  AE   a   b5  b5  b5  a  
after the chase:
  AD   a   b1  a   a   b1 
  AB   a   a   a   a   b2 
  BE   a   a   a   a   a  
  CDE  a   b4  a   a   a  
  AE   a   b5  a   a   a  
lossless: True

The BE row became all a, so this 5-part decomposition is lossless, although no pair of parts shows it directly.

9. Dependency preservation

Postal records R(city, street, zip) with the model's rules (city, street) → zip and zip → city. Split into (street, zip) and (city, zip): the shared column zip determines city, a key of (city, zip), so the split is lossless. But no table contains both city and street, so the rule city, street → zip can't be checked without a join on every insert.

  • The projection of F on Ri, written Fi, is the set of FDs in F+ that use only Ri's attributes: the rules Ri can check by itself.
  • A decomposition is dependency preserving if (F1 ∪ F2 ∪ ... ∪ Fn)+ = F+.
  • Test for one FD X → Y (no need to compute F+):
result = X
repeat until result stops growing:
    for each part Ri:
        result = result ∪ ((result ∩ Ri)+ ∩ Ri)      # closure under F
X → Y is preserved  iff  Y ⊆ result
def closure(X, F):
    result, changed = set(X), True
    while changed:
        changed = False
        for lhs, rhs in F:
            if set(lhs) <= result and not set(rhs) <= result:
                result |= set(rhs); changed = True
    return result

def preserved(lhs, rhs, F, parts):    # grow lhs using each part's own FDs only
    result = set(lhs)
    while True:
        old = set(result)
        for p in parts:
            result |= closure(result & set(p), F) & set(p)
        if result == old:
            return set(rhs) <= result

for name, F, parts in [("R(ABC)", [("A", "B"), ("B", "C"), ("C", "A")], ["AB", "BC"]),
                       ("R(city street zip)", [("CS", "Z"), ("Z", "C")], ["SZ", "CZ"])]:
    print(name, "split into", parts)
    for l, r in F:
        print(f"  {l}->{r}:", "kept" if preserved(l, r, F, parts) else "LOST")

Output:

R(ABC) split into ['AB', 'BC']
  A->B: kept
  B->C: kept
  C->A: kept
R(city street zip) split into ['SZ', 'CZ']
  CS->Z: LOST
  Z->C: kept
  • In R(ABC), C → A looks lost (no part contains both C and A), but C → B holds in BC and B → A holds in AB (both are in F+), so together they enforce C → A. Always test against F+, not only the FDs as written.
  • In the postal example CS → Z is truly lost: lossless does not mean dependency preserving. Episode 51 shows this is the price BCNF sometimes makes you pay.

10. Numericals

R(A, B, C, D), F = { A → B, B → C, C → D }, split AB, BC, CD. AB ∩ BC = B and B → C, so B is a key of BC: AB ⋈ BC = ABC is lossless. ABC ∩ CD = C and C → D: lossless. Every FD lies inside one part (A → B in AB, B → C in BC, C → D in CD): dependency preserving. Lossless and preserving.

Same R and F, split AC, BD. AC ∩ BD = ∅: the join is a cross product. Lossy.

The whole chain

Problem Invention
A notice board repeats rules equivalent FD sets (F covers G both ways)
A useless condition, a repeated rule extraneous attributes, redundant FDs
Trim safely minimal / canonical cover (split, trim left, drop redundant); not unique
One big table repeats data decomposition
Join on name invents rows lossy decomposition, spurious tuples
Prove a split is safe common attributes are a key; the chase
A rule no table can check dependency preservation and its test

Common mistakes

Mistake What you get Why Fix
Dropping an FD because it "looks repeated" {B}+ shrinks from BC to B the meaning changed test with closure
Removing redundant FDs before trimming left sides a redundant FD survives trimming creates duplicates split, trim, then drop
Splitting the left side of an FD false FDs only right sides decompose keep AB together
"Lossy means rows are lost" 5 rows from 3 spurious rows are added lossy = information lost
Testing lossless on the sample rows only a split that fails later must hold for every legal table use the key test or the chase
Checking preservation against F only "C → A is lost" FDs in F+ also count use the closure-based test
Thinking lossless implies preserving lost CS → Z they are independent properties test both

Mini project: a decomposition checker

Combine the episode's functions into one tool: equivalent(F, G), minimal_cover(F), lossless(R, F, parts) (chase) and preserving(F, parts). Feed it a design for a train booking table (PNR, coach, seat, passenger, train_no, train_name, date) with your own FDs, try two different decompositions, and print a report: lossless? preserving? which FDs are lost?

Practice

1. Minimal cover of { AB → C, A → B, B → A, C → A }.

Solution

Step 1: right sides are already single. Step 2: AB → C: without A, {B}+ = B → A, then AB → C gives C, so A is extraneous: B → C. Step 3: test each FD without itself: B → A is redundant ({B}+ = B, C, then C → A gives A). The others are needed. Fc = { B → C, A → B, C → A } (the program in section 4 prints exactly this). Removing B instead of A in step 2 gives a different, equally valid minimal cover: { A → C, A → B, B → A, C → A } (nothing in it is redundant).

2. Are { A → B, B → C } and { A → BC, B → C } equivalent?

Solution

First covers second: {A}+ = ABC contains BC; B → C is in both. Second covers first: A → BC gives A → B by decomposition. Yes, equivalent.

3. R(A, B, C, D, E), F = { A → B, B → C, C → D }. Is the split AB, BCD, AE lossless?

Solution

AB ∩ BCD = B, and {B}+ = BCD: B is a key of BCD, so AB ⋈ BCD = ABCD is lossless. ABCD ∩ AE = A, and {A}+ = ABCD: A is a key of ABCD. Lossless.

4. R(A, B, C, D), F = { AB → C, C → D, D → A }. Is the split AB, BCD dependency preserving?

Solution

C → D lies in BCD: kept. AB → C: result = AB; (AB ∩ BCD)+ = {B}+ = B adds nothing: lost. D → A: (D ∩ AB) = ∅, {D}+ ∩ BCD = D adds nothing: lost. So it is not dependency preserving. (It is also lossy: AB ∩ BCD = B and {B}+ = B.)

5. R(A, B, C, D), F = { A → B, C → D }. Is AC, AB, CD lossless? Is it preserving?

Solution

AC ∩ AB = A, A → B: key of AB, so ABC is lossless. ABC ∩ CD = C, C → D: key of CD. Lossless. A → B is in AB and C → D in CD: preserving.

Quick quiz

-- R(A, B, C, D)
-- F = { A → B, C → D }
-- split R into two parts:

Which split is lossless? A. AB, CD B. AB, ACD C. AC, BD D. ABC, BD

Answer

B. AB, ACD. AB ∩ ACD = A and A → B, so A is a key of AB. Options A and C share nothing (cross products). In D the common attribute is B, and {B}+ = B determines neither part.

Interview questions

  1. When are two FD sets equivalent? When each covers the other: every FD of one is in the closure of the other.
  2. What is an extraneous attribute? One that can be removed from an FD without changing F+.
  3. What is a minimal (canonical) cover? How do you compute it? An equivalent set with single right sides, no extraneous attributes and no redundant FDs: split right sides, trim left sides, drop redundant FDs.
  4. Is the minimal cover unique? No; it depends on the order of tests.
  5. What is a lossless-join decomposition? One whose natural join always gives back exactly the original relation.
  6. What are spurious tuples? Rows created by joining a lossy decomposition that were not in the original.
  7. How do you test a two-way decomposition for losslessness? R1 ∩ R2 must determine R1 or R2.
  8. What is the chase? A tableau test for any number of parts: lossless if a row becomes all distinguished values.
  9. What is dependency preservation and why does it matter? Every FD can be checked inside one table, without joins on every insert.
  10. Can a decomposition be lossless but not preserving? Yes: (city, street, zip) into (street, zip), (city, zip).
  11. Which matters more? Lossless is mandatory; preservation is desirable.

Glossary

Term Meaning in plain words Example
FD set F The given rules of a relation {A → B, B → C}
F+ Every FD that follows from F
Attribute closure X+ Every attribute X determines {B}+ = BC
F covers G Every FD of G follows from F
Equivalent FD sets (F ≡ G) Each covers the other; same meaning {A→BC, B→C, A→B, AB→C} ≡ {A→B, B→C}
Extraneous attribute An attribute removable from an FD without changing F+ A in AB → C when B → C
Redundant FD An FD that follows from the others A → C given A → B, B → C
Minimal cover Equivalent set, single right sides, nothing extraneous or redundant {A → B, B → C}
Canonical cover A minimal cover, often with same-left-side FDs merged {A → B, B → C}
Decomposition Replacing R by smaller relations covering all its attributes (roll, name), (roll, course)
Projection A table's rows keeping only some columns (roll, name) from students
Natural join (⋈) Combine rows whose shared columns are equal R1 ⋈ R2
Legal instance Any table that satisfies all the FDs
Lossless-join decomposition Joining the parts always gives back exactly R split on roll
Lossy decomposition The join can give extra rows split on name
Spurious tuple A fake row created by a lossy join (1, Asha, OS)
Lossless-join test Common attributes determine one whole part roll → name
Chase / tableau test Row-per-part table of a/b symbols, apply FDs, look for an all-a row 5-part example
Distinguished value (a) A tableau value known to be in the original row
Dependency preservation (F1 ∪ ... ∪ Fn)+ = F+: every FD checkable inside one table
Projection of F on Ri (Fi) FDs in F+ that use only Ri's attributes C → B on BC
Lost dependency An FD only checkable by joining tables city, street → zip
dict.fromkeys Python: remove duplicates, keeping order
set <= set Python: subset test

Summary

  • Equivalent FD sets cover each other; test with attribute closures. Dropping an FD "by eye" changed {B}+ (live).
  • Minimal cover: split right sides, remove extraneous left attributes, remove redundant FDs. {A → BC, B → C, A → B, AB → C} becomes {A → B, B → C} (live). It is not unique (live).
  • A decomposition must be lossless; splitting on name created 2 spurious tuples (live).
  • Lossless test: the common attributes are a key of one part; for many parts, the chase (live: all-a row).
  • Dependency preservation: every FD checkable within one table; test with the closure loop. CS → Z was lost while the split stayed lossless (live).

Next episode: normalization 1: redundancy, insertion, update and deletion anomalies, 1NF, 2NF and 3NF.