Functional Dependencies & Normalization Theory
Normalization is usually taught as a set of rules of thumb: "don't repeat data," "every column should depend on the key." Those rules are fine for everyday schema design, and the practical side, including when to deliberately break them, is covered in Normalization & Denormalization. This page is the theory underneath: a small amount of set algebra that turns "this table feels wrong" into a mechanical, checkable procedure.
That theory is worth learning for three reasons. First, it is what university DBMS courses, GATE and many CS-fundamentals interviews actually test: compute a closure, find all candidate keys, state the highest normal form, check whether a decomposition is lossless. Second, it gives you precise answers where intuition gives vague ones. "Is this schema in BCNF?" has a yes-or-no answer you can compute. Third, the algorithms are genuinely useful when you inherit a wide, messy table and need to split it without losing information.
Everything here builds on the vocabulary from The Relational Model & Relational Algebra: relations, tuples, superkeys, candidate keys, projection and natural join. If ER diagrams are how you design, ER Modeling & Schema Design shows how a good ER model already produces mostly normalized tables; this page explains why those tables are good.
Why Bad Schemas Hurt: Anomalies
Start with a single table that tries to hold everything about course enrolments:
| sid | sname | cid | ctitle | instructor | office | grade |
|---|---|---|---|---|---|---|
| 1 | Ada | CS101 | Intro to CS | Turing | B-12 | A |
| 1 | Ada | CS202 | Databases | Codd | C-03 | A |
| 2 | Linus | CS101 | Intro to CS | Turing | B-12 | B |
| 3 | Grace | CS202 | Databases | Codd | C-03 | A |
| 3 | Grace | CS303 | Compilers | Backus | B-07 | B |
The facts "CS101 is called Intro to CS," "Turing teaches CS101" and "Turing's office is B-12" are each stored once per enrolled student. That causes three classic problems:
| Anomaly | Example |
|---|---|
| Update anomaly | Turing moves to office B-20. You must update every CS101 row; miss one and the database contradicts itself |
| Insertion anomaly | A new course CS404 has no students yet. You cannot record its title without inventing a student (and sid is part of the key, so it cannot be NULL) |
| Deletion anomaly | Grace drops CS303, its only enrolment. Deleting her row also deletes the only record that Backus teaches CS303 and sits in B-07 |
All three come from the same root cause: the table stores several independent facts, and some of them are determined by part of the key or by a non-key column. Functional dependencies are the formal way to say exactly that.
Functional Dependencies
Definition
Let R be a relation schema and X, Y sets of its attributes. The functional dependency X → Y ("X functionally determines Y") holds on R if, in every legal instance of R, any two tuples that agree on X also agree on Y:
for all tuples t1, t2 in r: t1[X] = t2[X] implies t1[Y] = t2[Y]
X is the determinant (left-hand side, LHS) and Y the dependent (right-hand side, RHS).
In the enrolment table:
sid → sname
cid → ctitle, instructor
instructor → office
sid, cid → grade
Two points that trip people up:
- An FD is a statement about the schema, not about one instance. An instance can refute an FD (two rows with the same X and different Y), but it can never prove one. In the table above,
sname → sidhappens to hold today, but nothing stops a second student called Ada from enrolling. FDs come from the meaning of the data: business rules and requirements. - An FD says nothing about the reverse direction.
cid → instructordoes not implyinstructor → cid; one instructor may teach several courses.
Checking whether an instance violates an FD is a one-line query, useful when profiling a legacy table:
-- Does cid -> instructor hold in the current data? Any rows returned are violations.
SELECT cid, COUNT(DISTINCT instructor) AS n
FROM enrolment
GROUP BY cid
HAVING COUNT(DISTINCT instructor) > 1;
Trivial, Non-Trivial and Completely Non-Trivial
| Kind | Condition | Example |
|---|---|---|
| Trivial | Y ⊆ X | sid, cid → sid |
| Non-trivial | Y ⊄ X | sid, cid → sid, grade |
| Completely non-trivial | X ∩ Y = ∅ | sid, cid → grade |
Trivial FDs hold in every relation and carry no information. Normal form definitions only ever care about non-trivial ones.
Full, Partial and Transitive Dependencies
These three terms are what 2NF and 3NF are defined in terms of.
Full functional dependency. X → Y is full if removing any attribute from X breaks it: for every proper subset X' ⊂ X, X' → Y does not hold. sid, cid → grade is full, because neither sid alone nor cid alone determines a grade.
Partial dependency. X → Y is partial if some proper subset of X already determines Y. With key {sid, cid}, the dependency sid, cid → sname is partial, because sid → sname alone holds. In normalization the phrase "partial dependency" specifically means a non-prime attribute depending on a proper subset of a candidate key.
Transitive dependency. A → C is transitive if there is some B with A → B and B → C, where B does not determine A and C is not in A or B. With key cid in a Course(cid, instructor, office) table, cid → office is transitive via instructor. In normalization it specifically means a non-prime attribute depending on the key through another non-key attribute set.
flowchart LR
subgraph PART["Partial: sid alone determines sname"]
K1["sid, cid (key)"] --> G["grade"]
S["sid"] --> SN["sname"]
end
subgraph TRANS["Transitive: cid determines office via instructor"]
C["cid (key)"] --> I["instructor"]
I --> O["office"]
end
Armstrong's Axioms
Given a set F of FDs, other FDs follow logically. The set of all FDs implied by F is the closure F⁺. Armstrong's axioms (1974) are three inference rules that generate exactly F⁺.
| Axiom | Rule |
|---|---|
| Reflexivity | If Y ⊆ X, then X → Y |
| Augmentation | If X → Y, then XZ → YZ for any Z |
| Transitivity | If X → Y and Y → Z, then X → Z |
(XZ is shorthand for X ∪ Z.)
They are:
- Sound: every FD they derive really does hold in every relation satisfying F. You can check each rule directly from the definition. For transitivity: if t1[X] = t2[X], then t1[Y] = t2[Y] by X → Y, and therefore t1[Z] = t2[Z] by Y → Z.
- Complete: every FD that holds in every relation satisfying F can be derived with them. The proof constructs a two-tuple relation that agrees exactly on X⁺ and shows any FD not derivable is violated in it.
Derived Rules, With Proofs
Three more rules are used so often that they are taught alongside the axioms. Each follows from the three axioms.
Union. If X → Y and X → Z, then X → YZ.
1. X → Y given
2. X → XY augment (1) with X: XX → XY, and XX = X
3. X → Z given
4. XY → YZ augment (3) with Y
5. X → YZ transitivity on (2) and (4)
Decomposition. If X → YZ, then X → Y and X → Z.
1. X → YZ given
2. YZ → Y reflexivity (Y ⊆ YZ)
3. X → Y transitivity on (1) and (2)
(same argument for Z)
Pseudotransitivity. If X → Y and WY → Z, then WX → Z.
1. X → Y given
2. WX → WY augment (1) with W
3. WY → Z given
4. WX → Z transitivity on (2) and (3)
Union and decomposition together mean you can always rewrite FDs with a single attribute on the right-hand side and lose nothing, which is the first step of computing a canonical cover.
There is no "LHS decomposition"
X → Y lets you split the right side. It does not let you split the left. AB → C does not imply A → C. Likewise, A → C does not let you conclude anything about C → A. These two mistakes cause most wrong exam answers.
Worked derivation: from F = {A → B, B → C, CD → E}, derive AD → E
1. A → B given
2. B → C given
3. A → C transitivity (1), (2)
4. CD → E given
5. AD → E pseudotransitivity (3), (4) with W = D
Attribute Closure
Computing F⁺ directly is hopeless: it can contain exponentially many FDs. The practical tool is the closure of an attribute set X under F, written X⁺: the set of all attributes functionally determined by X.
The Algorithm
closure(X, F):
result := X
repeat
for each FD L → R in F:
if L ⊆ result:
result := result ∪ R
until result does not change
return result
It runs in at most |attributes| passes, each scanning F, so it is polynomial. A runnable version:
def closure(attrs, fds):
"""attrs: set of attribute names; fds: list of (lhs_set, rhs_set)."""
result = set(attrs)
changed = True
while changed:
changed = False
for lhs, rhs in fds:
if lhs <= result and not rhs <= result:
result |= rhs
changed = True
return result
F = [({'A'}, {'B'}), ({'A'}, {'C'}), ({'C', 'G'}, {'H'}),
({'C', 'G'}, {'I'}), ({'B'}, {'H'})]
print(sorted(closure({'A', 'G'}, F))) # ['A', 'B', 'C', 'G', 'H', 'I']
What Closure Answers
Attribute closure is the Swiss army knife of normalization. Each of these questions reduces to one closure computation:
| Question | Test |
|---|---|
| Does F imply X → Y? | Is Y ⊆ X⁺? |
| Is X a superkey of R? | Is X⁺ = R? |
| Is X a candidate key? | X⁺ = R and, for every attribute a in X, (X − a)⁺ ≠ R |
| Is attribute a extraneous in the LHS of XA → B? | Is B ⊆ X⁺ (computed under F)? |
| Is X → A redundant in F? | Is A ⊆ X⁺ computed under F − {X → A}? |
Worked Example 1
R(A, B, C, G, H, I) with F = { A → B, A → C, CG → H, CG → I, B → H }. Compute (AG)⁺.
| Step | FD applied | result |
|---|---|---|
| Start | {A, G} | |
| 1 | A → B | {A, B, G} |
| 2 | A → C | {A, B, C, G} |
| 3 | CG → H | {A, B, C, G, H} |
| 4 | CG → I | {A, B, C, G, H, I} |
(AG)⁺ = R, so AG is a superkey. Is it a candidate key? A⁺ = {A, B, C, H}, not R. G⁺ = {G}, not R. Neither proper subset works, so AG is a candidate key.
Worked Example 2
R(A, B, C, D, E) with F = { A → BC, CD → E, B → D, E → A }. Compute B⁺, (BC)⁺ and (CD)⁺.
- B⁺: start {B}; B → D gives {B, D}. Nothing else fires (CD needs C). B⁺ = {B, D}.
- (BC)⁺: {B, C} → B → D gives {B, C, D} → CD → E gives {B, C, D, E} → E → A gives {A, B, C, D, E}.
- (CD)⁺: {C, D} → CD → E gives {C, D, E} → E → A gives {A, C, D, E} → A → BC gives {A, B, C, D, E}.
So BC and CD are both superkeys, and since B⁺, C⁺ and D⁺ are not R, both are candidate keys.
Keys, Formally
| Term | Definition |
|---|---|
| Superkey | Any set X with X⁺ = R |
| Candidate key | A minimal superkey: no proper subset is a superkey |
| Primary key | The candidate key chosen as the main identifier |
| Prime attribute | An attribute that belongs to at least one candidate key |
| Non-prime attribute | An attribute in no candidate key |
Prime vs non-prime is the distinction that 2NF and 3NF turn on, so you must find all candidate keys before you can classify a schema. Finding just one is not enough: an attribute that looks non-prime may belong to a second key you missed.
Finding All Candidate Keys: a Systematic Method
Brute force (try all 2ⁿ subsets) works for small n but is slow by hand. The standard exam method prunes most of the search by classifying each attribute by where it appears in F:
| Attribute appears | Consequence |
|---|---|
| Only on the LHS of FDs (never on any RHS) | Nothing can determine it, so it is in every candidate key |
| In no FD at all | Same: in every candidate key |
| Only on the RHS (never on any LHS) | It is always determined by something else and never helps determine anything, so it is in no candidate key |
| On both sides | Might be in some keys; these are the ones to search over |
The procedure:
- Let CORE = attributes appearing only on the LHS, plus attributes appearing nowhere.
- Compute CORE⁺. If it equals R, CORE is the only candidate key. Stop.
- Otherwise, try adding attributes from the "both sides" group, one at a time, then two at a time, and so on. Whenever CORE ∪ S is a superkey and no smaller key you already found is a subset of it, record it as a candidate key.
- Skip any set that contains an already found key; it cannot be minimal.
flowchart TD
A["Classify each attribute:<br/>LHS-only, RHS-only, both, neither"] --> B["CORE = LHS-only plus neither"]
B --> C{"CORE+ = R?"}
C -->|"yes"| D["CORE is the unique candidate key"]
C -->|"no"| E["Try CORE + 1 attribute from 'both'"]
E --> F["Then CORE + 2, CORE + 3, ...<br/>skip supersets of found keys"]
F --> G["All minimal superkeys found<br/>= all candidate keys"]
Worked Example 3: Three Keys
R(A, B, C, D, E), F = { A → B, BC → E, ED → A }.
| Attribute | LHS? | RHS? | Class |
|---|---|---|---|
| A | yes (A → B) | yes (ED → A) | both |
| B | yes (BC → E) | yes (A → B) | both |
| C | yes | no | LHS-only |
| D | yes | no | LHS-only |
| E | yes (ED → A) | yes (BC → E) | both |
CORE = {C, D}. (CD)⁺ = {C, D}, nothing fires. Not a key.
Add one attribute from {A, B, E}:
- (ACD)⁺: A → B gives B; BC → E gives E. = {A, B, C, D, E}. Key.
- (BCD)⁺: BC → E gives E; ED → A gives A. = all. Key.
- (CDE)⁺: ED → A gives A; A → B gives B. = all. Key.
Any set of size 4 containing CD plus two of {A, B, E} contains one of these keys, so it is not minimal. Candidate keys: ACD, BCD, CDE. Every attribute is prime. Keep this example in mind: it reappears when we check normal forms.
Worked Example 4: Attributes That Appear Nowhere
R(A, B, C, D, E, H), F = { A → B, BC → D, E → C, D → A }.
- LHS-only: E. Appears nowhere: H. CORE = {E, H}.
- (EH)⁺ = {E, H, C}. Not a key.
- Both sides: A, B, C, D. Try each:
- (AEH)⁺ = {A, E, H} → C → B (A → B) → D (BC → D) = all. Key.
- (BEH)⁺ = {B, E, H, C} → D → A = all. Key.
- (CEH)⁺ = {C, E, H}. Not a key (C is already in (EH)⁺, so adding it changes nothing).
- (DEH)⁺ = {D, E, H, A, C, B} = all. Key.
Candidate keys: AEH, BEH, DEH. Prime attributes: A, B, D, E, H. Non-prime: C.
Counting Superkeys
A favourite numerical. If R has n attributes and a single candidate key K with k attributes, every superset of K is a superkey, so there are 2^(n−k) superkeys. With several candidate keys, use inclusion-exclusion over "contains K1," "contains K2," and so on, since a superset of K1 ∪ K2 is counted in both.
Two candidate keys K1, K2 in n attributes:
#superkeys = 2^(n − |K1|) + 2^(n − |K2|) − 2^(n − |K1 ∪ K2|)
Example: R(A, B, C, D) with candidate keys A and B: 2³ + 2³ − 2² = 8 + 8 − 4 = 12.
For R(A, B, C, D, E) with candidate keys A, E, BC, CD (worked example 2), inclusion-exclusion gives:
| Term | Sets fixed | Count |
|---|---|---|
| Singles | A: 2⁴, E: 2⁴, BC: 2³, CD: 2³ | 16 + 16 + 8 + 8 = 48 |
| Pairs | AE: 2³, A∪BC: 2², A∪CD: 2², E∪BC: 2², E∪CD: 2², BC∪CD: 2² | 8 + 4 + 4 + 4 + 4 + 4 = 28 |
| Triples | AE∪CD, AE∪BC, A∪BCD, E∪BCD: 2¹ each | 8 |
| All four | ABCDE: 2⁰ | 1 |
48 − 28 + 8 − 1 = 27 superkeys.
Canonical (Minimal) Cover
Different FD sets can say the same thing. A canonical cover (also called a minimal cover) Fc of F is an equivalent set with no redundancy:
- Every RHS is a single attribute.
- No LHS has an extraneous attribute: you cannot remove any attribute from any LHS without changing F⁺.
- No FD is redundant: you cannot remove any FD without changing F⁺.
(Some textbooks, such as Silberschatz, define the canonical cover with RHSs merged by union after minimizing, so that each LHS appears once. The two forms differ only in that last cosmetic step.)
The Algorithm
1. Decompose: replace each X → A1 A2 ... An by X → A1, X → A2, ..., X → An.
2. Remove extraneous LHS attributes:
for each FD XB → A with |XB| > 1:
if A ∈ X⁺ (closure under the CURRENT full set): replace with X → A
3. Remove redundant FDs:
for each FD X → A:
if A ∈ X⁺ computed under (current set − {X → A}): delete it
4. (Optional) Merge FDs with the same LHS using union.
Order matters: do step 2 before step 3. Removing an extraneous attribute can make another FD redundant, and doing it the other way round can leave redundancy behind.
Worked Example 5
F = { A → BC, B → C, A → B, AB → C }.
Step 1, decompose. { A → B, A → C, B → C, A → B, AB → C }. Drop the duplicate: { A → B, A → C, B → C, AB → C }.
Step 2, extraneous LHS. Only AB → C has a multi-attribute LHS.
- Is B extraneous? Compute A⁺ under the current set: A → B, A → C give {A, B, C}. C ∈ A⁺, so yes: replace AB → C with A → C, which is a duplicate.
Set is now { A → B, A → C, B → C }.
Step 3, redundant FDs.
- A → B: A⁺ without it = {A, C}. B ∉. Keep.
- A → C: A⁺ without it = {A, B} → B → C gives {A, B, C}. C ∈. Remove.
- B → C: B⁺ without it = {B}. Keep.
Fc = { A → B, B → C }.
Worked Example 6
F = { A → B, C → B, D → ABC, AC → D }.
Step 1. { A → B, C → B, D → A, D → B, D → C, AC → D }.
Step 2. AC → D: A⁺ = {A, B}, no D. C⁺ = {C, B}, no D. Neither is extraneous.
Step 3.
| FD | Closure of LHS without it | Contains RHS? | Action |
|---|---|---|---|
| A → B | A⁺ = {A} | No | Keep |
| C → B | C⁺ = {C} | No | Keep |
| D → A | D⁺ = {D, B, C} | No | Keep |
| D → B | D⁺ = {D, A, C, B} (via D → A, A → B) | Yes | Remove |
| D → C | D⁺ = {D, A, B} | No | Keep |
| AC → D | (AC)⁺ = {A, C, B} | No | Keep |
Fc = { A → B, C → B, D → A, D → C, AC → D }.
Canonical Covers Are Not Unique
The order in which you test FDs can change the result. Ullman's classic example, F = { AB → C, C → A, BC → D, ACD → B, D → EG, BE → C, CG → BD, CE → AG }, has (among others) both of these minimal covers:
Fc1 = { AB → C, C → A, BC → D, CD → B, D → E, D → G, BE → C, CG → D, CE → G }
Fc2 = { AB → C, C → A, BC → D, D → E, D → G, BE → C, CG → B, CE → G }
They have different sizes (9 and 8 FDs) yet are equivalent to F. "Minimal" means you cannot remove anything, not that it is the smallest possible. (In ACD → B, A is extraneous because C → A; in CE → AG, CE → A is redundant for the same reason.)
Equivalence of FD Sets
F and G are equivalent (F ≡ G) if F⁺ = G⁺. You never compute either closure. Instead:
- F covers G if every FD in G follows from F: for each X → Y in G, Y ⊆ X⁺ under F.
- F ≡ G if and only if F covers G and G covers F.
Worked Example 7
F = { A → C, AC → D, E → AD, E → H } and G = { A → CD, E → AH }. Are they equivalent?
Does F cover G?
- A → CD: A⁺ under F = {A, C} → AC → D gives {A, C, D}. CD ⊆. Yes.
- E → AH: E⁺ under F = {E, A, D, H} → A → C gives C. AH ⊆. Yes.
Does G cover F?
- A → C: A⁺ under G = {A, C, D}. Yes.
- AC → D: (AC)⁺ under G = {A, C, D}. Yes.
- E → AD: E⁺ under G = {E, A, H, C, D}. Yes.
- E → H: yes, same closure.
Both directions hold, so F ≡ G.
The Normal Forms
flowchart TB
subgraph N1["1NF: atomic values"]
subgraph N2["2NF: no partial dependency of non-prime attributes"]
subgraph N3["3NF: no transitive dependency of non-prime attributes"]
subgraph NB["BCNF: every determinant is a superkey"]
subgraph N4["4NF: every non-trivial MVD has a superkey LHS"]
N5["5NF / PJNF: every join dependency implied by keys"]
end
end
end
end
end
Each normal form is strictly stronger than the one outside it: every 5NF relation is in 4NF, every 4NF relation is in BCNF, and so on. The FD-based ones (2NF, 3NF, BCNF) are what most questions are about.
1NF
Definition. A relation is in First Normal Form if every attribute's domain contains only atomic (indivisible) values: no repeating groups, no lists, no nested relations.
Not in 1NF:
| sid | name | phones |
|---|---|---|
| 1 | Ada | 555-0100, 555-0199 |
| 2 | Linus | 555-0142 |
Fix: move the multivalued attribute into its own relation, keyed by the owner plus the value.
CREATE TABLE student (
sid integer PRIMARY KEY,
name text NOT NULL
);
CREATE TABLE student_phone (
sid integer REFERENCES student(sid),
phone text,
PRIMARY KEY (sid, phone)
);
"Atomic" depends on how the data is used: a date is atomic until you need to query by month, and PostgreSQL arrays or JSONB columns are allowed by the DBMS. The theory assumes atomicity so that FDs are well defined; the practical page discusses when nested types are worth it.
2NF
Definition. R is in Second Normal Form if it is in 1NF and no non-prime attribute is partially dependent on any candidate key. Equivalently, every non-prime attribute is fully functionally dependent on every candidate key.
A relation whose candidate keys are all single attributes is automatically in 2NF: there is no proper subset to depend on.
Worked decomposition. Enrolment(sid, sname, cid, ctitle, grade) with F = { sid → sname, cid → ctitle, sid cid → grade }.
- Candidate key: {sid, cid} (sid and cid are LHS-only). Non-prime: sname, ctitle, grade.
- sid → sname: sid ⊂ key, sname non-prime. Partial dependency. Same for cid → ctitle.
- Not in 2NF.
For each partial dependency, split off the determinant with what it determines:
Student(sid, sname) key sid
Course(cid, ctitle) key cid
Enrolment(sid, cid, grade) key {sid, cid}
Each FD now lives in one relation where its LHS is the key. The original can be rebuilt by joining on sid and cid.
3NF
Definition (Zaniolo's form, the one to use for exam checks). R is in Third Normal Form if for every non-trivial FD X → A that holds on R, at least one of these is true:
- X is a superkey of R, or
- A is a prime attribute.
Equivalent textbook form: R is in 2NF and no non-prime attribute is transitively dependent on a candidate key.
Condition 2 is the loophole that separates 3NF from BCNF: an FD whose RHS is part of some key is tolerated even if its LHS is not a superkey.
Worked decomposition. Course(cid, ctitle, instructor, office) with F = { cid → ctitle, cid → instructor, instructor → office }.
- Key: cid. Non-prime: ctitle, instructor, office. It is in 2NF (single-attribute key).
- instructor → office: instructor is not a superkey and office is not prime. Violates 3NF (transitive: cid → instructor → office).
Split on the offending FD:
Course(cid, ctitle, instructor) key cid
Instructor(instructor, office) key instructor
Both are now in 3NF (and BCNF).
BCNF
Definition. R is in Boyce-Codd Normal Form if for every non-trivial FD X → A that holds on R, X is a superkey of R.
That is 3NF minus the prime-attribute loophole. In BCNF, every fact is determined only by keys, so every redundancy that FDs can detect is gone.
When is a relation in 3NF but not BCNF? Only when there are multiple overlapping composite candidate keys and an FD from a non-superkey into a key attribute.
Worked example: the classic student-course-instructor schema. R(S, C, I): student S takes course C from instructor I. Rules: each student has one instructor per course (SC → I), and each instructor teaches exactly one course (I → C).
- Keys: S is LHS-only, so in every key. (SC)⁺ = {S, C, I}: key. (SI)⁺ = {S, I, C}: key. Candidate keys SC and SI. Every attribute is prime.
- I → C: I is not a superkey, but C is prime. Allowed by 3NF. R is in 3NF.
- I → C: I is not a superkey. R is not in BCNF.
The redundancy is real:
| S | C | I |
|---|---|---|
| Ada | Databases | Codd |
| Grace | Databases | Codd |
| Linus | Databases | Date |
"Codd teaches Databases" is stored once per student taking Databases from Codd.
BCNF decomposition on I → C:
R1(I, C) key I "which course each instructor teaches"
R2(S, I) key {S, I} "which instructor each student has"
Both are in BCNF and the join is lossless (I is common and I → C means I is a key of R1). But SC → I is no longer enforceable in either table: nothing in R1 or R2 stops Ada being assigned two instructors who both teach Databases. You would need a join or a trigger to enforce it. This is the fundamental trade-off covered below: BCNF is not always reachable without losing a dependency.
Testing the Highest Normal Form
To find the highest normal form of R under F:
flowchart TD
S["Find ALL candidate keys<br/>mark prime / non-prime"] --> B{"Every non-trivial FD<br/>has a superkey LHS?"}
B -->|"yes"| BC["BCNF"]
B -->|"no"| T{"For each violator X to A,<br/>is A prime?"}
T -->|"all yes"| N3["3NF"]
T -->|"no"| P{"Any non-prime attribute<br/>determined by a proper<br/>subset of a key?"}
P -->|"no"| N2["2NF"]
P -->|"yes"| N1["1NF"]
Check the FDs in F, but remember the definitions are over F⁺: an FD derived from F can also violate a normal form. For BCNF it is enough to check F itself (if every FD in F has a superkey LHS, every derived FD does too). For a decomposed fragment, you must check FDs projected onto it, which may not appear in F at all.
Apply this to worked example 3, R(A, B, C, D, E) with F = { A → B, BC → E, ED → A } and keys ACD, BCD, CDE:
- No LHS (A, BC, ED) is a superkey, so not BCNF.
- Every RHS (B, E, A) is prime, since all attributes are prime. So 3NF.
And worked example 4, R(A, B, C, D, E, H) with keys AEH, BEH, DEH and C the only non-prime attribute:
- E → C: E is a proper subset of key AEH and C is non-prime. Partial dependency. The highest normal form is 1NF.
Multivalued Dependencies and 4NF
FDs cannot express every kind of redundancy. Consider:
| course | teacher | book |
|---|---|---|
| Databases | Codd | Ullman |
| Databases | Codd | Silberschatz |
| Databases | Date | Ullman |
| Databases | Date | Silberschatz |
Rule: a course has a set of teachers and a set of recommended books, independently. Every teacher uses every book. There are no non-trivial FDs at all (course does not determine teacher), the only key is all three attributes, and the relation is in BCNF. Yet adding a third book means inserting one row per teacher: classic redundancy.
Multivalued dependency (MVD). X →→ Y holds on R if, whenever two tuples agree on X, there also exist tuples that swap their Y values: the set of Y values associated with an X value is independent of the remaining attributes Z = R − X − Y. Formally, for any t1, t2 with t1[X] = t2[X], there is a t3 with:
t3[X] = t1[X], t3[Y] = t1[Y], t3[Z] = t2[Z]
Here course →→ teacher and course →→ book.
Key facts about MVDs:
| Rule | Statement |
|---|---|
| Every FD is an MVD | If X → Y then X →→ Y |
| Complementation | If X →→ Y then X →→ R − X − Y |
| Trivial MVD | X →→ Y is trivial if Y ⊆ X or X ∪ Y = R |
| Fagin's theorem | R decomposes losslessly into (X ∪ Y) and (X ∪ (R − Y)) if and only if X →→ Y holds |
Definition. R is in Fourth Normal Form if for every non-trivial MVD X →→ Y that holds on R, X is a superkey.
Course-teacher-book violates 4NF (course is not a superkey). Decompose on course →→ teacher:
CourseTeacher(course, teacher) key {course, teacher}
CourseBook(course, book) key {course, book}
Lossless by Fagin's theorem. Adding a book is now one row.
MVDs usually come from bad ER mapping
A 4NF violation almost always means two independent many-to-many relationships were mapped into one table. A careful ER model maps each to its own table and never produces one. See ER Modeling & Schema Design.
Join Dependencies and 5NF
Some relations cannot be split into two without loss, yet can be split into three.
| agent | company | product |
|---|---|---|
| Smith | Ford | car |
| Smith | Ford | truck |
| Smith | GM | car |
| Jones | Ford | car |
Business rule: if an agent represents a company, and the agent sells a product type, and the company makes that product type, then the agent sells that product for that company. Under this rule the relation equals the join of its three binary projections:
AgentCompany(agent, company) AgentProduct(agent, product) CompanyProduct(company, product)
Check for this instance: Smith-GM, Smith-car and GM-car are all present, so (Smith, GM, car) must be in the join, and it is. Is there a GM-truck? No, so (Smith, GM, truck) is correctly excluded. Any two projections joined together produce spurious tuples, but all three together reproduce R exactly.
Join dependency. ⋈{R1, R2, ..., Rn} holds on R if every legal instance of R equals the natural join of its projections onto R1, ..., Rn. An MVD is the special case n = 2.
Definition. R is in Fifth Normal Form (Project-Join Normal Form) if every non-trivial join dependency that holds on R is implied by the candidate keys.
Without the business rule there is no join dependency and the three-column table is already 5NF. With it, decompose into the three projections. 5NF violations are rare in practice and hard to spot; they need a genuinely cyclic "if A-B and B-C and C-A then A-B-C" rule. Exams mostly test the definition and this example.
Normal Forms at a Glance
| Normal form | Condition (for every non-trivial dependency) | Eliminates |
|---|---|---|
| 1NF | Atomic values | Repeating groups |
| 2NF | No non-prime attribute depends on part of a candidate key | Partial dependencies |
| 3NF | X → A: X superkey or A prime | Transitive dependencies of non-prime attributes |
| BCNF | X → A: X superkey | All FD-based redundancy |
| 4NF | X →→ Y: X superkey | Independent multivalued facts in one table |
| 5NF | Every join dependency implied by keys | Cyclic join redundancy |
Decomposition Properties
Normalizing means replacing R with projections R1, R2, ..., Rn. Two properties decide whether a decomposition is any good.
Lossless Join
A decomposition of R into R1, ..., Rn is lossless (non-additive) if, for every legal instance r,
π_R1(r) ⋈ π_R2(r) ⋈ ... ⋈ π_Rn(r) = r
The join always contains r. A lossy decomposition produces extra, spurious tuples. "Lossy" is a misnomer: no rows are lost, but you lose the information about which combinations were real.
Lossy example. R(A, B, C) with F = { A → B }, decomposed into R1(A, B) and R2(B, C).
| A | B | C |
|---|---|---|
| 1 | x | p |
| 2 | x | q |
π_AB = {(1, x), (2, x)}, π_BC = {(x, p), (x, q)}. Joining on B gives four rows, including (1, x, q) and (2, x, p), which never existed.
The Binary Test (Common Attributes)
For a decomposition into two relations R1 and R2:
The decomposition is lossless if and only if (R1 ∩ R2) → R1 or (R1 ∩ R2) → R2 is in F⁺.
In words: the common attributes must be a superkey of at least one of the two pieces. Compute (R1 ∩ R2)⁺ and check whether it contains all of R1 or all of R2.
In the lossy example, R1 ∩ R2 = {B}, B⁺ = {B}: neither. Lossy. Decomposing into (A, B) and (A, C) instead: A⁺ = {A, B} ⊇ R1. Lossless.
The test also has to satisfy a basic precondition: R1 ∪ R2 = R (no attribute dropped).
For a multi-way decomposition built by repeated binary splits, apply the binary test at each split. For an arbitrary multi-way decomposition, use the chase.
The Chase (Tableau) Test
For R(A1, ..., Ak) decomposed into R1, ..., Rn:
- Build a table with one row per Ri and one column per attribute.
- In row i, column Aj: write the distinguished symbol a if Aj ∈ Ri, otherwise a unique symbol b_ij.
- Repeatedly, for each FD X → Y: find rows that agree on all X columns, and make them agree on each Y column. If one of the symbols is a, use a; otherwise pick one of the b's. Replace the symbol everywhere in that column.
- Stop when nothing changes. The decomposition is lossless if and only if some row is all a's.
Worked example 8. R(A, B, C, D, E), F = { A → C, B → C, C → D, DE → C, CE → A }. Decomposition: R1(A, D), R2(A, B), R3(B, E), R4(C, D, E), R5(A, E).
Initial tableau:
| A | B | C | D | E | |
|---|---|---|---|---|---|
| R1 (AD) | a | b12 | b13 | a | b15 |
| R2 (AB) | a | a | b23 | b24 | b25 |
| R3 (BE) | b31 | a | b33 | b34 | a |
| R4 (CDE) | b41 | b42 | a | a | a |
| R5 (AE) | a | b52 | b53 | b54 | a |
A → C. Rows R1, R2, R5 agree on A (all a). Equate their C: b13, b23, b53 → b13.
B → C. Rows R2, R3 agree on B (a). Equate C: b13, b33 → b13. Now R1, R2, R3, R5 all have C = b13.
C → D. Rows R1, R2, R3, R5 agree on C (b13). Their D values are a, b24, b34, b54 → a.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| R1 | a | b12 | b13 | a | b15 |
| R2 | a | a | b13 | a | b25 |
| R3 | b31 | a | b13 | a | a |
| R4 | b41 | b42 | a | a | a |
| R5 | a | b52 | b13 | a | a |
DE → C. Rows R3, R4, R5 agree on D (a) and E (a). Their C values are b13, a, b13 → a, and b13 is replaced by a everywhere in column C, so R1 and R2 also get C = a.
CE → A. Rows R3, R4, R5 agree on C (a) and E (a). Their A values are b31, b41, a → a.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| R1 | a | b12 | a | a | b15 |
| R2 | a | a | a | a | b25 |
| R3 | a | a | a | a | a |
| R4 | a | b42 | a | a | a |
| R5 | a | b52 | a | a | a |
Row R3 is all a's. The decomposition is lossless. Drop R5(A, E) and rerun: no row ever becomes all a's, so the four-way decomposition without R5 is lossy.
The intuition: an all-a row is a tuple that the FDs force to exist in R whenever the projections exist, which is exactly what "the join reproduces R" requires.
Dependency Preservation
The projection of F onto Ri, written F_Ri, is the set of FDs in F⁺ that mention only attributes of Ri. A decomposition is dependency preserving if
(F_R1 ∪ F_R2 ∪ ... ∪ F_Rn)⁺ = F⁺
Why it matters: if every FD can be checked inside a single table, the DBMS enforces it cheaply with a primary key or UNIQUE constraint on each insert. If an FD spans tables, enforcing it needs a join on every write, so in practice it goes unenforced.
-- R(S, C, I) with SC -> I is trivially enforced in one table:
CREATE TABLE teaches (s text, c text, i text, PRIMARY KEY (s, c));
-- After decomposing into (I, C) and (S, I), "one instructor per student per course"
-- can only be enforced with a trigger that joins the two tables on every insert.
The Test Without Computing F⁺
Computing projections of F⁺ is exponential. The standard polynomial test checks each FD X → Y in F directly:
preserved(X → Y):
result := X
repeat
for each fragment Ri:
t := (closure(result ∩ Ri, F)) ∩ Ri
result := result ∪ t
until result does not change
return Y ⊆ result
Each pass asks "what can fragment Ri alone tell me, given what I know so far?" The decomposition preserves dependencies if every FD in F passes.
The shortcut is only sufficient
If every FD in F has all its attributes inside some single fragment, the decomposition is certainly preserving. But an FD that sits in no single fragment may still be preserved through a chain of projected FDs. Always run the closure test before saying "not preserved."
Worked example 9: preserved, though it does not look it. R(A, B, C, D), F = { A → B, B → C, C → D, D → A }, decomposed into (A, B), (B, C), (C, D).
A → B, B → C and C → D each sit inside one fragment. D → A does not appear in any. Test it:
| Pass | Fragment | result ∩ Ri | closure ∩ Ri | result |
|---|---|---|---|---|
| start | {D} | |||
| 1 | (A, B) | ∅ | ∅ | {D} |
| 1 | (B, C) | ∅ | ∅ | {D} |
| 1 | (C, D) | {D} | D⁺ = ABCD, ∩ CD = {C, D} | {C, D} |
| 2 | (B, C) | {C} | C⁺ = ABCD, ∩ BC = {B, C} | {B, C, D} |
| 2 | (A, B) | {B} | B⁺ = ABCD, ∩ AB = {A, B} | {A, B, C, D} |
A ∈ result, so D → A is preserved. The projections contain the reverse FDs D → C, C → B and B → A, which chain back. The decomposition is dependency preserving.
Worked example 10: not preserved. R(A, B, C, D, E), F = { A → B, B → C, CD → E }, decomposed into (B, C), (A, B), (A, D, E).
Test CD → E: start {C, D}. (B, C): {C} ∩, C⁺ = {C}, adds nothing. (A, B): ∅. (A, D, E): {D} ∩, D⁺ = {D}, adds nothing. No change. E ∉ result. CD → E is lost.
3NF Synthesis vs BCNF Decomposition
Two algorithms take a schema and produce a normalized design. They make different guarantees.
| Property | 3NF synthesis | BCNF decomposition |
|---|---|---|
| Lossless join | Always | Always |
| Dependency preserving | Always | Not always |
| Result in BCNF | Not guaranteed (only 3NF) | Always |
| Result depends on order | Somewhat (cover chosen) | Yes, heavily |
| Input | A canonical cover | Any FD set |
3NF Synthesis (Bernstein's Algorithm)
1. Compute a canonical cover Fc of F.
2. For each FD X → A in Fc (or each group with the same LHS X, merged as X → A1...Ak),
create a relation schema (X ∪ A1 ... Ak).
3. If no schema created so far contains a candidate key of R,
add one schema consisting of any candidate key.
4. Remove any schema that is a subset of another.
Step 2 guarantees dependency preservation (every FD of the cover lives in its own table). Step 3 guarantees losslessness (the key schema ties all the pieces together).
BCNF Decomposition
result := {R}
while some Ri in result is not in BCNF:
find a non-trivial FD X → Y holding on Ri with X not a superkey of Ri
(use X⁺ to make it maximal: Y := (X⁺ ∩ Ri) − X)
replace Ri by: (X ∪ Y) and (Ri − Y)
Every split is lossless by the binary test, since the common part X is a key of (X ∪ Y). Checking "holding on Ri" must use FDs projected onto Ri, not just those in F.
flowchart TD
R["R(A, B, C, D, E)<br/>key AD"] -->|"A to B violates<br/>A+ = ABC"| R1["R1(A, B, C)"]
R -->|"R minus BC"| R2["R2(A, D, E)<br/>AD to E, BCNF"]
R1 -->|"B to C violates in R1"| R11["R11(B, C)<br/>BCNF"]
R1 --> R12["R12(A, B)<br/>BCNF"]
Worked Example 11: the Two Algorithms Side by Side
R(A, B, C, D, E), F = { A → B, B → C, CD → E }.
Keys. LHS-only: A, D. (AD)⁺ = {A, D, B, C, E} = R. AD is the only candidate key. Non-prime: B, C, E.
Normal form. A → B: A is a proper subset of the key and B is non-prime, so a partial dependency. The highest form is 1NF.
BCNF decomposition, splitting on A → B first (the tree above):
- A → B violates. A⁺ ∩ R = {A, B, C}. Split into R1(A, B, C) and R2(A, D, E).
- R1(A, B, C) has projected FDs A → B, B → C, A → C. Key A. B → C violates. Split into (B, C) and (A, B).
- R2(A, D, E) has projected FD AD → E (since A → B → C and CD → E). Key AD. BCNF.
Result: (B, C), (A, B), (A, D, E): BCNF and lossless, but as worked example 10 showed, CD → E is lost.
BCNF decomposition, splitting on CD → E first: (C, D, E) and (A, B, C, D). Then in (A, B, C, D), A → B violates: split into (A, B, C) and (A, D), then (B, C) and (A, B). Result: (C, D, E), (B, C), (A, B), (A, D): every FD preserved. The order of splits changed whether a dependency survived.
3NF synthesis:
- F is already a canonical cover: { A → B, B → C, CD → E }.
- Schemas: (A, B), (B, C), (C, D, E).
- None contains the key AD, so add (A, D).
- No subsets to remove.
Result: (A, B), (B, C), (C, D, E), (A, D): lossless, dependency preserving, and here also in BCNF.
The Trade-Off
For the SCI schema (SC → I, I → C), no BCNF decomposition preserves SC → I: any BCNF design must split on I → C, and SC → I spans both pieces. That is the core theorem behind the trade-off:
- A lossless, dependency-preserving decomposition into 3NF always exists (synthesis builds one).
- A lossless decomposition into BCNF always exists (the decomposition algorithm builds one).
- A lossless, dependency-preserving decomposition into BCNF does not always exist.
The usual engineering choice: aim for BCNF; if the only BCNF designs lose an important dependency, stop at 3NF and accept the small, controlled redundancy, or keep BCNF and enforce the lost FD with a trigger or an application check.
From Theory to Practice
Normalization theory tells you how to remove redundancy. It does not tell you whether you should: read-heavy analytics, reporting tables and caches often reintroduce redundancy on purpose to avoid joins. That decision, with join-cost analysis, materialized views and the patterns warehouses use, lives in Normalization & Denormalization and Dimensional Modeling. How the storage engine actually executes the joins a normalized schema needs is covered in How Databases Work and Query Planning & Optimization.
A pragmatic default for OLTP systems: design in BCNF (or 3NF where BCNF would lose a dependency), enforce every FD that survives with a primary key or UNIQUE constraint, and denormalize only with a measured reason and a plan for keeping the copies consistent.
A Verification Script
Every numerical on this page can be checked mechanically. This script computes closures, all candidate keys, the highest normal form and the dependency-preservation test. Use it to check your hand work, not to replace it.
from itertools import combinations
def parse(s):
"""'A->BC, CD->E' -> [({'A'}, {'B','C'}), ({'C','D'}, {'E'})]"""
out = []
for fd in s.split(','):
l, r = fd.split('->')
out.append((set(l.strip()), set(r.strip())))
return out
def closure(x, fds):
res, changed = set(x), True
while changed:
changed = False
for l, r in fds:
if l <= res and not r <= res:
res |= r
changed = True
return res
def candidate_keys(R, fds):
R, keys = set(R), []
for n in range(1, len(R) + 1):
for c in combinations(sorted(R), n):
if closure(c, fds) >= R and not any(k <= set(c) for k in keys):
keys.append(set(c))
return keys
def highest_nf(R, fds):
R = set(R)
keys = candidate_keys(R, fds)
prime = set().union(*keys)
# every non-trivial X -> a in F+ restricted to R (fine for small R)
deps = [(set(x), a) for n in range(1, len(R)) for x in combinations(sorted(R), n)
for a in closure(x, fds) & R - set(x)]
superkey = lambda x: closure(x, fds) >= R
if all(superkey(x) for x, _ in deps):
return 'BCNF'
if all(superkey(x) or a in prime for x, a in deps):
return '3NF'
if all(a in prime or not any(x < k for k in keys) for x, a in deps):
return '2NF'
return '1NF'
def preserved(fds, fragments):
lost = []
for x, y in fds:
res, changed = set(x), True
while changed:
changed = False
for ri in map(set, fragments):
t = closure(res & ri, fds) & ri
if not t <= res:
res |= t
changed = True
if not y <= res:
lost.append((x, y))
return lost
F = parse('A->B, BC->E, ED->A')
print(candidate_keys('ABCDE', F)) # [{'A','C','D'}, {'B','C','D'}, {'C','D','E'}]
print(highest_nf('ABCDE', F)) # 3NF
print(preserved(parse('A->B, B->C, CD->E'), ['BC', 'AB', 'ADE'])) # CD -> E lost
Common Misconceptions
| Misconception | Reality |
|---|---|
| An FD can be read off the current data | Data can refute an FD, never prove one. FDs come from business rules |
| AB → C implies A → C | Only the RHS can be split. LHS splitting is not a valid rule |
| Find one key, then classify attributes | You need all candidate keys; an attribute in a second key is prime |
| 3NF and BCNF are basically the same | They differ exactly when overlapping composite keys exist and some FD points into a key attribute |
| BCNF is always better | BCNF can lose dependencies that 3NF keeps; sometimes 3NF is the right stopping point |
| A lossy decomposition loses rows | It adds spurious rows to the join; what is lost is information |
| A relation in BCNF has no redundancy | It can still have MVD redundancy (4NF) or join-dependency redundancy (5NF) |
| The canonical cover is unique | Different orders of elimination can give different, equally minimal covers |
| A two-attribute relation can violate BCNF | It cannot: any non-trivial FD has a single-attribute LHS that determines the other attribute, so that LHS is a superkey |
Practice Problems
Problem 1. R(A, B, C, D, E, F) with F = { AB → C, C → D, D → E, E → F }. Find the candidate keys, the number of superkeys and the highest normal form.
Solution
A and B never appear on a RHS, so both are in every key. (AB)⁺ = {A, B, C, D, E, F} = R. AB is the only candidate key.
Superkeys: every superset of AB, so 2^(6−2) = 16.
Non-prime: C, D, E, F. Is there a partial dependency? No proper subset of AB determines anything (A⁺ = {A}, B⁺ = {B}), so 2NF holds. C → D has a non-superkey LHS and a non-prime RHS, so 3NF fails. Highest normal form: 2NF.
Problem 2. R(A, B, C, D) with F = { AB → CD, C → A }. Find all candidate keys and the highest normal form.
Solution
B is LHS-only, so in every key. D is RHS-only, so in no key. B⁺ = {B}.
- (AB)⁺ = {A, B, C, D}: key.
- (BC)⁺ = {B, C, A, D} (C → A, then AB → CD): key.
Candidate keys AB, BC. Prime: A, B, C. Non-prime: D.
AB → D and BC → D have superkey LHSs. C → A: C is not a superkey, but A is prime, so 3NF allows it. BCNF does not. Highest normal form: 3NF.
Problem 3. R(A, B, C, D, E) with F = { AB → C, C → D, B → E }. Highest normal form?
Solution
A and B are LHS-only. (AB)⁺ = {A, B, C, D, E}. Key AB. Non-prime: C, D, E.
B → E: B is a proper subset of the key and E is non-prime. Partial dependency, so not 2NF. Highest normal form: 1NF.
A 2NF decomposition: (B, E), (A, B, C, D). Then (A, B, C, D) has C → D, a transitive dependency, so for 3NF split further: (C, D), (A, B, C). Final: (B, E), (C, D), (A, B, C), which is also BCNF.
Problem 4. R(A, B, C, D, E, F, G, H) with F = { AB → C, AC → B, AD → E, B → D, BC → A, E → G }. Find all candidate keys.
Solution
F and H appear in no FD, so they are in every key. Nothing else is LHS-only: A, B, C, D, E appear on both sides, G is RHS-only. CORE = {F, H}, CORE⁺ = {F, H}.
Single additions: (AFH)⁺ = {A, F, H}; (BFH)⁺ = {B, D, F, H}; (CFH)⁺ = {C, F, H}; (DFH)⁺, (EFH)⁺ are small. None is a key.
Pairs:
- (ABFH)⁺: AB → C, B → D, AD → E, E → G gives all. Key.
- (ACFH)⁺: AC → B, then as above. Key.
- (BCFH)⁺: BC → A, then everything. Key.
- (ADFH)⁺ = {A, D, E, G, F, H}: no B or C. Not a key. Other pairs with D or E similarly fail.
Triples that do not contain a found key, such as ADEFH, also fail to reach B or C. Candidate keys: ABFH, ACFH, BCFH.
Problem 5. R(A, B, C, D, E) with candidate keys A and BC only. How many superkeys?
Solution
Contains A: 2⁴ = 16. Contains BC: 2³ = 8. Contains both A and BC: 2² = 4.
16 + 8 − 4 = 20.
Problem 6. What is the maximum number of superkeys of a relation with n attributes? The maximum number of candidate keys?
Solution
Superkeys: if every single attribute is a key, every non-empty subset is a superkey: 2ⁿ − 1.
Candidate keys: candidate keys form an antichain (no key contains another), and by Sperner's theorem the largest antichain in the subsets of an n-set has C(n, ⌊n/2⌋) members. It is achieved when every subset of size ⌊n/2⌋ is a key. For n = 4 that is C(4, 2) = 6.
Problem 7. Find a canonical cover of F = { A → BC, B → C, AB → D }.
Solution
Decompose: { A → B, A → C, B → C, AB → D }.
Extraneous LHS in AB → D: compute A⁺ under the current set. A → B and A → C give {A, B, C}; now AB ⊆ A⁺, so AB → D fires and A⁺ = {A, B, C, D}. D ∈ A⁺, so B is extraneous: AB → D becomes A → D.
Redundant: A → C follows from A → B and B → C. Remove it. A → B, B → C, A → D are each needed.
Fc = { A → B, B → C, A → D }, or merged, { A → BD, B → C }.
Problem 8. Are F = { A → B, B → C, C → A } and G = { A → BC, B → A, C → A } equivalent?
Solution
Under F, every attribute's closure is {A, B, C}. Under G, A⁺ = {A, B, C}, B⁺ = {B, A, C}, C⁺ = {C, A, B}.
F covers G: A → BC, B → A, C → A all follow since every closure under F is ABC. G covers F: A → B, B → C, C → A all follow for the same reason. Equivalent.
Problem 9. R(A, B, C, D) with F = { A → B, C → D }. Is the decomposition into (A, B) and (C, D) lossless? What about (A, B), (C, D), (A, C)?
Solution
(A, B) and (C, D) share no attributes; their join is a Cartesian product, so they are lossy (unless R happens to be a product). The binary test fails immediately: ∅⁺ = ∅.
Add (A, C), and do it as two binary steps. (A, C) ⋈ (A, B): common A, A → B, so lossless, giving (A, B, C). Then (A, B, C) ⋈ (C, D): common C, C → D, so lossless, giving R. Lossless. (A chase would end with the (A, C) row becoming all a's.)
Problem 10. R(A, B, C, D, E) with F = { A → B, B → C, C → D, D → E }. Check whether { (A, B), (B, C), (C, D, E) } is lossless and dependency preserving.
Solution
Lossless: (C, D, E) ⋈ (B, C): common C, C⁺ = {C, D, E} ⊇ CDE. Lossless, giving (B, C, D, E). Then ⋈ (A, B): common B, B⁺ = {B, C, D, E} ⊇ BCDE. Lossless. Lossless.
Preserving: A → B in (A, B), B → C in (B, C), C → D and D → E in (C, D, E). Every FD sits inside one fragment. Dependency preserving.
Problem 11. R(A, B, C) with F = { AB → C, C → B }. Is it in BCNF? Decompose it into BCNF and check dependency preservation.
Solution
A is LHS-only. (AB)⁺ = ABC, (AC)⁺ = ACB. Keys AB, AC. All attributes prime.
C → B: C is not a superkey, so not BCNF (but it is 3NF, since B is prime).
Split on C → B: (C, B) and (A, C). Lossless (C → B makes C a key of (C, B)).
Preservation of AB → C: start {A, B}. (C, B): {B}, B⁺ = {B}, nothing. (A, C): {A}, A⁺ = {A}, nothing. AB → C is lost. This is the SCI pattern again.
Problem 12. R(A, B, C, D, E, G) with F = { AB → C, C → A, BC → D, ACD → B, D → EG, BE → C, CG → BD, CE → AG }. Find a canonical cover.
Solution
Decompose: AB → C, C → A, BC → D, ACD → B, D → E, D → G, BE → C, CG → B, CG → D, CE → A, CE → G.
Extraneous LHS: in ACD → B, A is extraneous because C → A (so (CD)⁺ already contains A and then ACD → B fires). It becomes CD → B.
Redundant FDs: CE → A follows from C → A. Remove. Then, depending on order:
- Removing CG → B (it follows from CG → D and CD → B) gives Fc1 = { AB → C, C → A, BC → D, CD → B, D → E, D → G, BE → C, CG → D, CE → G }.
- Or keeping CG → B and instead removing CG → D (CG → B, then BC → D) and CD → B ((CD)⁺ gets A from C → A, G from D → G, then B from CG → B) gives Fc2 = { AB → C, C → A, BC → D, D → E, D → G, BE → C, CG → B, CE → G }.
Both are minimal and equivalent to F. This is the standard demonstration that canonical covers are not unique.
Problem 13. R(A, B, C, D, E) with F = { A → BC, CD → E, B → D, E → A }. Find the candidate keys and the highest normal form.
Solution
No attribute is LHS-only: A, B, C, D, E all appear on both sides. Search single attributes and pairs:
- A⁺ = {A, B, C, D, E}: key.
- E⁺ = {E, A, ...} = all: key.
- B⁺ = {B, D}, C⁺ = {C}, D⁺ = {D}: not keys.
- Pairs without A or E: BC⁺ = all (key), CD⁺ = all (key), BD⁺ = {B, D}: no.
Candidate keys A, E, BC, CD. Every attribute is prime.
B → D: B is not a superkey. D is prime, so 3NF is satisfied, BCNF is not. Highest normal form: 3NF. (Superkey count: 27, as computed earlier.)
Problem 14. R(P, Q, R, S) with F = { PQ → R, R → S, S → P }. Highest normal form, and a BCNF decomposition.
Solution
Q is LHS-only. Q⁺ = {Q}. (PQ)⁺ = PQRS: key. (QR)⁺ = {Q, R, S, P}: key. (QS)⁺ = {Q, S, P, R}: key. Keys PQ, QR, QS; all attributes prime.
R → S and S → P have non-superkey LHSs but prime RHSs: 3NF, not BCNF.
BCNF: split on S → P: (S, P) and (Q, R, S). In (Q, R, S), projected FDs include R → S (non-superkey) and QR → S, QS → R. Split on R → S: (R, S) and (Q, R). Result: (S, P), (R, S), (Q, R). Lossless. PQ → R is lost (no fragment can check it).
Problem 15. A relation Project(emp, skill, language) records that employees have skills and speak languages, independently. Which normal form does it violate, and how do you fix it?
Solution
There are no non-trivial FDs and the only key is all three attributes, so it is in BCNF. But emp →→ skill and emp →→ language hold (skills and languages are independent), and emp is not a superkey, so it violates 4NF. Decompose into EmpSkill(emp, skill) and EmpLanguage(emp, language), lossless by Fagin's theorem.
Problem 16. Run the chase on R(A, B, C, D) with F = { A → B, B → C, C → D } and decomposition (A, B), (B, C), (C, D).
Solution
Initial tableau:
| A | B | C | D | |
|---|---|---|---|---|
| AB | a | a | b13 | b14 |
| BC | b21 | a | a | b24 |
| CD | b31 | b32 | a | a |
B → C: rows AB and BC agree on B, so C becomes a in row AB. C → D: rows AB, BC, CD now agree on C (a), so D becomes a in rows AB and BC. Row AB is now (a, a, a, a). Lossless.
Interview Questions
1. What is a functional dependency, and can you discover one from data?
X → Y means any two tuples that agree on X must agree on Y, in every legal instance. Data can only refute an FD, never prove one; a pattern that holds in today's rows might be a coincidence. FDs come from business rules, though profiling queries (GROUP BY x HAVING COUNT(DISTINCT y) > 1) are useful for checking candidate rules against legacy data.
2. State Armstrong's axioms and prove the union rule. Reflexivity (Y ⊆ X gives X → Y), augmentation (X → Y gives XZ → YZ) and transitivity. Union: from X → Y augment with X to get X → XY; from X → Z augment with Y to get XY → YZ; transitivity gives X → YZ. The axioms are sound and complete.
3. How do you find all candidate keys of a relation? Attributes that never appear on a right-hand side (or appear in no FD) must be in every key. Attributes appearing only on right-hand sides are in no key. Start with the mandatory set, compute its closure, and if it is not everything, add the remaining "both sides" attributes in increasing combinations, skipping supersets of keys already found.
4. What is the difference between 3NF and BCNF? Give an example that is 3NF but not BCNF. BCNF requires every non-trivial FD's LHS to be a superkey. 3NF also allows FDs whose RHS is a prime attribute. Example: R(student, course, instructor) with student course → instructor and instructor → course. Keys are {student, course} and {student, instructor}, so course is prime and the relation is 3NF, but instructor is not a superkey, so it is not BCNF.
5. What is a lossless decomposition and how do you test it? Joining the projections gives back exactly the original relation, with no spurious tuples. For two pieces, it is lossless if and only if the common attributes functionally determine all of one piece. For more pieces, use the chase: build a tableau, apply FDs to equate symbols, and look for a row of all distinguished symbols.
6. Why might you prefer 3NF over BCNF? A lossless, dependency-preserving 3NF decomposition always exists; a dependency-preserving BCNF decomposition does not. If BCNF would split an important FD across tables, that rule can only be enforced with a join or a trigger. Stopping at 3NF keeps it enforceable with a single key constraint, at the cost of a little redundancy.
7. What is a canonical cover, and why do we compute it? A minimal equivalent FD set: single-attribute right-hand sides, no extraneous left-hand-side attributes, no redundant FDs. It is the input to 3NF synthesis, it minimizes the checks a DBMS must make on updates, and it makes key and normal-form analysis easier. It is not necessarily unique.
8. What is a multivalued dependency, and how does 4NF differ from BCNF? X →→ Y says the set of Y values for an X is independent of the other attributes. A relation with two independent multivalued facts about the same entity (an employee's skills and languages) has no non-trivial FDs and can be in BCNF while still being heavily redundant. 4NF requires every non-trivial MVD to have a superkey LHS, which forces those facts into separate tables.
9. How do you check dependency preservation without computing F⁺? For each X → Y in F, start with result = X and repeatedly, for every fragment Ri, add (closure(result ∩ Ri) ∩ Ri) to result. If Y ends up in result, the FD is preserved. This is polynomial and catches FDs preserved through chains of projected dependencies.
10. When would you deliberately denormalize? When reads dominate and the joins a normalized design requires are measurably too slow or too expensive: reporting tables, analytics star schemas, cached counters, search documents. The cost is that you now own keeping the copies consistent. See Normalization & Denormalization.
Summary
| Concept | One-line version |
|---|---|
| Functional dependency | Same X implies same Y, in every legal instance |
| Armstrong's axioms | Reflexivity, augmentation, transitivity: sound and complete |
| Attribute closure | X⁺ answers implication, superkey and extraneous-attribute questions |
| Candidate keys | LHS-only and unused attributes are in every key; RHS-only attributes in none |
| Prime attribute | Belongs to some candidate key |
| Canonical cover | Single-attribute RHS, no extraneous LHS attributes, no redundant FDs; not unique |
| 2NF | No non-prime attribute depends on part of a key |
| 3NF | Every FD has a superkey LHS or a prime RHS |
| BCNF | Every FD has a superkey LHS |
| 4NF / 5NF | Same idea for multivalued and join dependencies |
| Lossless join | Binary: common attributes determine one side. General: the chase |
| Dependency preservation | Each FD checkable within fragments; test with the iterative closure |
| The trade-off | 3NF: always lossless and preserving. BCNF: always lossless, not always preserving |
Where to Go Next
- Normalization & Denormalization: applying these ideas to real schemas, and when to undo them
- ER Modeling & Schema Design: designing schemas that come out normalized in the first place
- The Relational Model & Relational Algebra: keys, projection and join, the operators decompositions rely on
- SQL Fundamentals: declaring the keys and constraints that enforce surviving FDs
- Concurrency Control: the next theory topic, keeping concurrent transactions correct
- How Databases Work: what happens under the hood when a normalized schema is queried