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 → Yin 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:
- Split right sides (decomposition rule):
A → BCbecomesA → B,A → C. - Remove extraneous attributes from every left side.
- 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 }
- Split: A → B, A → C, CD → E, B → D, E → A.
- Only CD → E has two attributes on the left. {C}+ = C and {D}+ = D, neither contains E: nothing is extraneous.
- 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
- 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>). - 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. - Repeat until nothing changes.
- 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
- When are two FD sets equivalent? When each covers the other: every FD of one is in the closure of the other.
- What is an extraneous attribute? One that can be removed from an FD without changing F+.
- 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.
- Is the minimal cover unique? No; it depends on the order of tests.
- What is a lossless-join decomposition? One whose natural join always gives back exactly the original relation.
- What are spurious tuples? Rows created by joining a lossy decomposition that were not in the original.
- How do you test a two-way decomposition for losslessness? R1 ∩ R2 must determine R1 or R2.
- What is the chase? A tableau test for any number of parts: lossless if a row becomes all distinguished values.
- What is dependency preservation and why does it matter? Every FD can be checked inside one table, without joins on every insert.
- Can a decomposition be lossless but not preserving? Yes: (city, street, zip) into (street, zip), (city, zip).
- 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.