These are the notes for CS Fundamentals for Placements, episode 48, the start of database design theory. We define the functional dependency (FD), its determinant and dependent, check FDs on real rows, separate trivial from non-trivial FDs, learn Armstrong's axioms (reflexivity, augmentation, transitivity) and the derived rules (union, decomposition, pseudo-transitivity), compare the closure of an FD set (F+) with attribute closure (X+), and build a method that finds all candidate keys, with prime and non-prime attributes and 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 the SyntaxPilot compiler's python3 (Python 3.13) on Linux x86-64 on 7 November 2026.
1. Some facts decide other facts
- PIN code 411001 always means Pune, but Pune has many PIN codes (411001, 411038, ...). PIN determines city; city does not determine PIN.
- A roll number always belongs to the same student: roll determines name.
A functional dependency X → Y (read "X functionally determines Y") holds in a relation if any two tuples that agree on X also agree on Y.
| Part | Name | Example |
|---|---|---|
| X (left side) | determinant | roll |
| Y (right side) | dependent | name |
X ↛ Y |
X does not determine Y | city ↛ pin |
X and Y can be sets of attributes: {roll, course} → room, written roll, course → room or RC → M. In exercises attributes are single letters and AB means the set {A, B}.
2. Checking FDs on rows
rows = [ # roll, name, course, instructor, room
(1, "Asha", "DBMS", "Rao", "L1"),
(1, "Asha", "OS", "Iyer", "L2"),
(2, "Ravi", "DBMS", "Rao", "L1"),
(3, "Neha", "CN", "Gupta", "L3"),
(3, "Neha", "OS", "Iyer", "L4")]
cols = ["roll", "name", "course", "instructor", "room"]
def holds(X, Y):
"""X -> Y holds if rows that agree on X also agree on Y"""
seen = {}
for r in rows:
x = tuple(r[cols.index(c)] for c in X)
y = tuple(r[cols.index(c)] for c in Y)
if seen.setdefault(x, y) != y:
return f"NO ({x} -> {seen[x]} and {y})"
return "yes"
for X, Y in [(["roll"], ["course"]), (["roll"], ["name"]),
(["course"], ["instructor"]), (["instructor"], ["room"]),
(["roll", "course"], ["room"])]:
print(f"{'+'.join(X):12} -> {'+'.join(Y):10}: {holds(X, Y)}")
Output:
roll -> course : NO ((1,) -> ('DBMS',) and ('OS',))
roll -> name : yes
course -> instructor: yes
instructor -> room : NO (('Iyer',) -> ('L2',) and ('L4',))
roll+course -> room : yes
roll → coursefails: roll 1 has DBMS and OS.instructor → roomfails: Iyer teaches in L2 and L4.roll → name,course → instructorandroll, course → roomhold in this data.
Data can disprove an FD, never prove one. Five rows without a clash don't guarantee tomorrow's rows won't clash. FDs are rules of the real world (the "business rules") that the designer learns from how the organisation works; sample data can only expose wrong ones. A key from episode 42 is exactly an FD: a key determines every attribute.
3. Trivial and non-trivial FDs
| Kind | Rule | Example |
|---|---|---|
| Trivial | Y ⊆ X (always true) | roll, name → name |
| Non-trivial | Y has at least one attribute not in X | roll → name |
| Completely non-trivial | X ∩ Y = ∅ | roll → name, city |
4. Armstrong's axioms
Given some FDs, which others must also hold? William W. Armstrong gave three rules in "Dependency Structures of Data Base Relationships" (IFIP Congress, 1974):
| Axiom | Rule | Example |
|---|---|---|
| Reflexivity | if Y ⊆ X then X → Y | roll, name → name |
| Augmentation | if X → Y then XZ → YZ | roll → name gives roll, course → name, course |
| Transitivity | if X → Y and Y → Z then X → Z | pin → city, city → state give pin → state |
- Sound: they never derive an FD that doesn't follow.
- Complete: every FD that follows can be derived with them.
Derived rules (provable from the axioms):
| Rule | Statement |
|---|---|
| Union (additivity) | X → Y and X → Z give X → YZ |
| Decomposition (projectivity) | X → YZ gives X → Y and X → Z |
| Pseudo-transitivity | X → Y and WY → Z give WX → Z |
| Composition | X → Y and Z → W give XZ → YW |
Proofs:
- Union: X → Y, augment with X: X → XY. X → Z, augment with Y: XY → YZ. Transitivity: X → YZ.
- Decomposition: YZ → Y by reflexivity; X → YZ and YZ → Y give X → Y by transitivity (same for Z).
- Pseudo-transitivity: X → Y, augment with W: WX → WY. With WY → Z, transitivity: WX → Z.
Caution: the left side does not decompose: AB → C does not give A → C.
5. F+ and attribute closure X+
- F: the FDs we are given. Running example: R(A, B, C, D, E), F = { A → B, BC → E, ED → A }.
- F+ (closure of F): every FD implied by F. It is exponentially large.
- X+ (attribute closure of X under F): every attribute X determines.
Algorithm for X+: start with result = X. Repeat: for each FD L → R in F, if L ⊆ result, add R to result. Stop when a full pass adds nothing.
from itertools import combinations
F = [("A", "B"), ("BC", "E"), ("ED", "A")] # A->B, BC->E, ED->A
def closure(X, show=True):
result, changed = set(X), True
while changed: # repeat until nothing new
changed = False
for lhs, rhs in F:
if set(lhs) <= result and not set(rhs) <= result:
result |= set(rhs) # lhs inside: add rhs
if show: print(f" {lhs}->{rhs}: now {''.join(sorted(result))}")
changed = True
return "".join(sorted(result))
for X in ["BC", "AC", "ACD"]:
print(f"{{{X}}}+ =", closure(X))
# F+ : every X -> Y with Y inside X+ (X, Y not empty)
n = sum(2 ** len(closure(X, False)) - 1
for k in range(1, 6) for X in combinations("ABCDE", k))
print("FDs in F+:", n, "from just", len(F), "in F")
Output:
BC->E: now BCE
{BC}+ = BCE
A->B: now ABC
BC->E: now ABCE
{AC}+ = ABCE
A->B: now ABCD
BC->E: now ABCDE
{ACD}+ = ABCDE
FDs in F+: 401 from just 3 in F
- Guess "BC → E, so BC is the key": wrong. {BC}+ = BCE lacks A and D.
- {AC}+ = ABCE (still no D). {ACD}+ = ABCDE: ACD is a super key.
- F+ already has 401 FDs (counting every X → Y with Y ⊆ X+, X and Y non-empty) from just 3 in F.
Uses of attribute closure
| Question | Test |
|---|---|
| Is X → Y implied by F? | Y ⊆ X+ |
| Is X a super key of R? | X+ = all attributes of R |
| Is X a candidate key? | X is a super key and no proper subset is |
| Are F and G equivalent? (episode 49) | every FD of each is implied by the other |
Same answer two ways: is AC → E implied? Axioms: A → B, augment with C: AC → BC; BC → E (given); transitivity: AC → E. Closure: {AC}+ = ABCE contains E. Is AC → D implied? D ∉ {AC}+, so no; the axioms are sound, so no derivation exists. Attribute closure is a mechanical way of applying the axioms.
6. Finding all candidate keys
from itertools import combinations
R, F = "ABCDE", [("A", "B"), ("BC", "E"), ("ED", "A")]
def closure(X):
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
rhs_all = set("".join(r for _, r in F))
lhs_all = set("".join(l for l, _ in F))
print("in every key (never on a right side):", sorted(set(R) - rhs_all))
print("in no key (only on right sides): ", sorted(rhs_all - lhs_all))
keys = []
for size in range(1, len(R) + 1):
for X in combinations(R, size):
if closure(X) == set(R) and not any(set(k) <= set(X) for k in keys):
keys.append("".join(X))
print("candidate keys:", keys)
print("prime attributes:", sorted(set("".join(keys))))
Output:
in every key (never on a right side): ['C', 'D']
in no key (only on right sides): []
candidate keys: ['ACD', 'BCD', 'CDE']
prime attributes: ['A', 'B', 'C', 'D', 'E']
Method, by hand:
- Attributes on no right side must be in every key (nothing else can determine them). Here: C, D.
- Attributes only on right sides are in no key (something else always determines them). Here: none.
- Compute the closure of the must-have set. {CD}+ = CD: not enough.
- Add the remaining attributes one at a time (then two at a time ...): {ACD}+, {BCD}+, {CDE}+ are all ABCDE.
- Never extend a set that already contains a key (it wouldn't be minimal).
Candidate keys: ACD, BCD, CDE. An attribute in at least one candidate key is prime; otherwise non-prime. Here all five are prime. (Prime/non-prime is the basis of 2NF and 3NF, episode 50.)
Numerical 2. R(A, B, C, D, E), F = { AB → C, C → D, B → E }. A and B are on no right side → in every key. {AB}+ = ABCDE. So AB is the only candidate key; prime: A, B; non-prime: C, D, E.
Numerical 3. R(A, B, C, D), F = { AB → C, C → D, D → A }. B is on no right side. {B}+ = B. Try AB: ABCD ✓. BC: C → D, D → A: ABCD ✓. BD: D → A, AB → C: ABCD ✓. Keys AB, BC, BD; all four attributes prime.
The whole chain
| Problem | Invention |
|---|---|
| A PIN fixes a city | functional dependency, determinant, dependent |
| Does it hold here? | check rows; data only disproves |
| Some FDs are always true | trivial vs non-trivial |
| What else follows? | Armstrong's axioms; union, decomposition, pseudo-transitivity |
| 401 FDs from 3 | attribute closure instead of F+ |
| BC looked like a key | {BC}+ = BCE: not a super key |
| Find every key | must-have attributes + closure; prime attributes |
Common mistakes
| Mistake | What you get | Why | Fix |
|---|---|---|---|
| "No clash in the data, so X → Y" | a false FD | data can't prove FDs | FDs come from rules |
| Splitting the left side: AB → C ⇒ A → C | a false FD | only the right side decomposes | keep AB together |
| Calling a determinant the key | BC as key | {BC}+ = BCE | compute the closure |
| Calling ACDE a candidate key | not minimal | ACD inside is a key | check proper subsets |
| Stopping at one key | missed keys | relations can have several | extend every must-have set |
| Forgetting attributes on no right side | wrong keys | they're in every key | start from them |
| Mixing up F+ and X+ | confusion | F+ is FDs; X+ is attributes |
Mini project: an FD toolkit
Write Python functions closure(X, F), implies(F, X, Y), is_superkey(R, F, X), candidate_keys(R, F) and prime_attributes(R, F), plus holds(rows, cols, X, Y) for data. Test them on R(ABCDE) with F = {A → B, BC → E, ED → A} (keys ACD, BCD, CDE), on the GATE quiz below, and on a table of your own (e.g. a train booking: PNR, coach, seat, passenger, train number, date).
Practice
1. Prove decomposition from the axioms.
Solution
Given X → YZ. Reflexivity: YZ → Y (Y ⊆ YZ). Transitivity with X → YZ: X → Y. Likewise YZ → Z gives X → Z.
2. Candidate keys of R(A, B, C, D), F = { AB → C, C → D, D → A }.
Solution
B is on no right side, so B is in every key; {B}+ = B. {AB}+ = ABCD, {BC}+ = BCDA, {BD}+ = BDAC. Keys: AB, BC, BD. All attributes are prime.
3. {B}+ for F = { A → B, B → C, CD → A }.
Solution
Start {B}. B → C: {B, C}. CD → A needs D: no. A → B: A not in set. {B}+ = BC.
4. Is AB → D implied by { A → C, BC → D }?
Solution
{AB}+: A → C gives ABC; BC → D gives ABCD. D ∈ {AB}+, so yes. (Axioms: A → C, augment with B: AB → BC; with BC → D, transitivity: AB → D. That's pseudo-transitivity.)
5. R(A, B, C, D, E, F) with F = { A → B, B → C, C → D, D → E }. Candidate keys and non-prime attributes?
Solution
A and F are on no right side. {AF}+ = ABCDEF. Only key: AF. Non-prime: B, C, D, E.
Quick quiz
-- R(A, B, C, D, E)
-- F = { A → BC, CD → E,
-- B → D, E → A }
Which is a candidate key? A. B B. CD C. BD D. AD
Answer
B. CD. {CD}+: CD → E, E → A, A → BC: ABCDE; neither C nor D alone gets there. {B}+ = {BD}+ = BD. AD is a super key, but A alone is a key ({A}+ = ABCDE), so AD is not minimal. All candidate keys: A, E, BC, CD.
Interview questions
- What is a functional dependency? X → Y: tuples agreeing on X agree on Y.
- Determinant vs dependent? Left side vs right side.
- Trivial FD? Y ⊆ X; always holds.
- State Armstrong's axioms. Reflexivity, augmentation, transitivity.
- What does sound and complete mean for them? Derive only implied FDs, and all of them.
- Can you split the left side of an FD? No; only the right side (decomposition).
- F+ vs X+? All implied FDs vs all attributes determined by X.
- How do you test if X is a super key? A candidate key? X+ = R; plus minimality.
- How do you find all candidate keys? Start with attributes on no right side, extend, test with closure, keep minimal ones.
- Prime attribute? One that belongs to some candidate key.
- Can data prove an FD? No, only disprove it.
- Relation between keys and FDs? A key K satisfies K → every attribute.
Glossary
| Term | Meaning in plain words | Example |
|---|---|---|
| Functional dependency (FD) | X → Y: equal X means equal Y | roll → name |
| Determinant | The left side of an FD | roll |
| Dependent | The right side of an FD | name |
↛ |
Does not determine | city ↛ pin |
| Business rule | A real-world rule FDs come from | one instructor per course |
| Trivial FD | Right side ⊆ left side | AB → A |
| Non-trivial FD | Right side has something new | A → B |
| Completely non-trivial | Sides share nothing | A → BC |
| Armstrong's axioms | Reflexivity, augmentation, transitivity | |
| Reflexivity | Y ⊆ X gives X → Y | |
| Augmentation | X → Y gives XZ → YZ | |
| Transitivity | X → Y, Y → Z give X → Z | |
| Sound | Derives only true consequences | |
| Complete | Derives all true consequences | |
| Union rule | X → Y, X → Z give X → YZ | |
| Decomposition rule | X → YZ gives X → Y, X → Z | |
| Pseudo-transitivity | X → Y, WY → Z give WX → Z | |
| F | The given set of FDs | {A → B, BC → E, ED → A} |
| F+ (closure of F) | All FDs implied by F | 401 FDs |
| X+ (attribute closure) | All attributes determined by X | {AC}+ = ABCE |
| Implied FD | Follows from F | AC → E |
| Super key | X with X+ = all attributes | ACD |
| Candidate key | Minimal super key | ACD, BCD, CDE |
| Minimal | No proper subset works | |
| Prime attribute | Member of some candidate key | C |
| Non-prime attribute | In no candidate key | E in R(AB→C, C→D, B→E) |
itertools.combinations |
Python: all subsets of a given size | |
setdefault |
Python dict: get a value, or store and return a default |
Summary
- An FD X → Y means equal X values force equal Y values; X is the determinant, Y the dependent.
- Checking rows found
roll ↛ courseandinstructor ↛ room(live); data can disprove FDs, never prove them. - Trivial FDs (Y ⊆ X) always hold.
- Armstrong's axioms (1974): reflexivity, augmentation, transitivity; sound and complete. Derived: union, decomposition, pseudo-transitivity. Never split the left side.
- F+ explodes (401 from 3, live); attribute closure X+ answers implication and key questions. {BC}+ = BCE exposed a wrong key guess.
- All candidate keys: start from attributes on no right side, extend, test closures, keep minimal sets: ACD, BCD, CDE (live). Prime = in some key.
Next episode: functional dependencies 2: minimal (canonical) cover, extraneous attributes, equivalence of FD sets, lossless-join and dependency-preserving decomposition.