Normalization: Functional Dependencies to BCNF and Beyond

What this lesson covers

Normalization is the process of organizing a relational schema so that each fact is stored once. It works by finding functional dependencies (rules such as "a roll number determines a student's name") and splitting tables whose structure lets the same fact appear many times. The payoff is fewer update bugs, less wasted space and clearer data. The cost is more tables and more joins, which is why real systems sometimes denormalize on purpose.

Normalization is the most numerical part of DBMS interviews and written tests (GATE-style questions are common in Indian placement tests). You will be asked to compute an attribute closure, list all candidate keys, find the highest normal form of a relation, compute a canonical cover, decompose into BCNF or 3NF, and check whether a decomposition is lossless and dependency preserving. Every one of those is worked step by step below, and every answer was double-checked with a small program.

Notation: attributes are single capital letters, a set like {A, B} is written AB, and a relation R(A, B, C, D) has those four attributes. X → Y is read "X determines Y".

Why normalize: the three anomalies

Here is a table a beginner might design for a college: one row per student per course.

enrollment
+-------+-------+--------+-------------+-----------+-------+
| sid   | sname | course | course_name | professor | grade |
+-------+-------+--------+-------------+-----------+-------+
| S1    | Asha  | C1     | DBMS        | Rao       | A     |
| S1    | Asha  | C2     | OS          | Menon     | B     |
| S2    | Ravi  | C1     | DBMS        | Rao       | A     |
| S3    | Meera | C1     | DBMS        | Rao       | C     |
+-------+-------+--------+-------------+-----------+-------+

Business rules: each student has one name; each course has one name and one professor; a student gets one grade per course. So the key is (sid, course).

The design stores "C1 is DBMS taught by Rao" three times and "S1 is Asha" twice. This redundancy causes three kinds of anomalies, meaning operations that go wrong or become impossible:

Update anomaly. Rao is replaced by Iyer for DBMS. You must update three rows. Miss one, and the table claims DBMS has two professors. The data is now inconsistent.

Insertion anomaly. The college adds course C3 "Networks" with professor Iyer, but nobody has enrolled yet. You cannot insert it: the key is (sid, course), and sid cannot be NULL. You cannot record a fact about a course until a student exists for it.

Deletion anomaly. Asha drops OS, and she was the only student in it. Deleting her row also deletes the only record that C2 is "OS" taught by Menon. Removing one fact destroyed an unrelated fact.

The root cause: the table mixes facts about three different things (students, courses, enrollments). Normalization separates them:

student(sid, sname)        course(course, course_name, professor)
enrollment(sid, course, grade)

Now each fact lives in one place: rename a professor in one row, add a course with no students, delete an enrollment without losing the course. The rest of this lesson makes that intuition precise, so you can do it for any relation, not just obvious ones.

Functional dependencies

A functional dependency (FD) X → Y on a relation R means: any two tuples that agree on all attributes in X must also agree on all attributes in Y. X is the determinant (left-hand side), Y the dependent (right-hand side).

In the enrollment table:

• sid → sname (a student id determines one name)
• course → course_name, professor
• sid, course → grade

An FD is a statement about every valid state of the relation, derived from business rules. You cannot prove an FD by looking at sample rows, but one counterexample in the data disproves it. In the table above, professor → course happens to hold, but if a professor may teach several courses, it is not an FD.

Trivial and non-trivial FDs

• Trivial: X → Y where Y is a subset of X, such as AB → A. It always holds and says nothing.
• Non-trivial: Y is not a subset of X, such as AB → C.
• Completely non-trivial: X and Y share no attributes, such as A → B.

Armstrong's axioms

Given some FDs, which others must also hold? Armstrong's axioms are three inference rules that are sound (they never derive a false FD) and complete (they derive every FD that logically follows).

1. Reflexivity: if Y ⊆ X, then X → Y. (Trivial FDs.)
2. Augmentation: if X → Y, then XZ → YZ for any Z.
3. Transitivity: if X → Y and Y → Z, then X → Z.

Useful rules derived from them:

1. Union: if X → Y and X → Z, then X → YZ.
2. Decomposition: if X → YZ, then X → Y and X → Z.
3. Pseudo-transitivity: if X → Y and WY → Z, then WX → Z.

Proof of union, as an example of using the axioms: from X → Y, augment with X to get X → XY. From X → Z, augment with Y to get XY → YZ. Transitivity on X → XY and XY → YZ gives X → YZ.

The set of all FDs implied by F is the closure of F, written F⁺. It can be exponentially large, so in practice we compute the closure of an attribute set instead.

Attribute closure

The closure of an attribute set X under F, written X⁺, is the set of all attributes that X determines. It is the single most useful tool in normalization:

• X → Y holds if and only if Y ⊆ X⁺.
• X is a super key of R if and only if X⁺ contains all attributes of R.

Algorithm

closure(X, F):
    result = X
    repeat
        for each FD  L -> R  in F:
            if L is a subset of result:
                result = result + R
    until result does not change
    return result

Worked example 1

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

Compute A⁺:

start          {A}
A -> B         {A, B}
A -> C         {A, B, C}
B -> E         {A, B, C, E}
CD -> E/F      needs D, not present
no change      A+ = {A, B, C, E}

A⁺ lacks D and F, so A is not a key. Compute (AD)⁺:

start          {A, D}
A -> B, A -> C {A, B, C, D}
CD -> E        {A, B, C, D, E}
CD -> F        {A, B, C, D, E, F}   all attributes

AD is a super key. Is it minimal? A⁺ = ABCE (not all) and D⁺ = D (no FD has D alone on the left), so neither part alone works. AD is a candidate key.

Finding all candidate keys

Testing every subset is slow for many attributes. Use this classification to cut the search:

• Attributes that appear on no right-hand side cannot be determined by anything else, so they must be in every candidate key. Call this set the core.
• Attributes that appear only on right-hand sides (never on a left) never help determine anything, so they are in no candidate key.
• Attributes on both sides may or may not be in a key.

Procedure:

1. Compute the core. If core⁺ = R, the core is the only candidate key.
2. Otherwise, add attributes from the "both sides" group to the core, smallest combinations first, and keep those whose closure is R and which do not contain an already found key.

Worked example 1 (continued)

F = {A → B, A → C, CD → E, CD → F, B → E} on ABCDEF.

• Right sides: B, C, E, F. Not on any right side: A, D. Core = AD.
• (AD)⁺ = ABCDEF. So AD is the only candidate key.

Worked example 2

R(A, B, C, D), F = {AB → C, C → D, D → A}.

• Right sides: C, D, A. Never on a right side: B, so B is in every key.
• B⁺ = B. Not a key. Try adding one attribute:
  • (AB)⁺: AB → C gives ABC; C → D gives ABCD. Key.
  • (BC)⁺: C → D gives BCD; D → A gives ABCD. Key.
  • (BD)⁺: D → A gives ABD; AB → C gives ABCD. Key.
• Any three-attribute set containing B contains one of these, so it is not minimal.

Candidate keys: AB, BC, BD. Prime attributes (those in some candidate key): A, B, C, D, which is all of them. Keep this in mind for normal forms.

Worked example 3

R(A, B, C, D, E), F = {A → B, BC → E, ED → A}.

• Right sides: B, E, A. Never on a right side: C, D. Core = CD.
• (CD)⁺ = CD. Not a key.
• Add one of A, B, E:
  • (ACD)⁺: A → B gives ABCD; BC → E gives ABCDE. Key.
  • (BCD)⁺: BC → E gives BCDE; ED → A gives ABCDE. Key.
  • (CDE)⁺: ED → A gives ACDE; A → B gives ABCDE. Key.

Candidate keys: ACD, BCD, CDE. Again every attribute is prime.

Worked example 4

R(A, B, C, D, E, H), F = {A → BC, CD → E, E → C, D → AEH, ABH → BD, DH → BC}.

• Right sides: B, C, E, A, H, D. Every attribute appears on some right side, so the core is empty. Search single attributes first.
• D⁺: D → AEH gives ADEH; A → BC gives ABCDEH. D is a key.
• A⁺: A → BC gives ABC; nothing else fires (CD needs D, ABH needs H). Not a key.
• Others alone: B⁺ = B, C⁺ = C, E⁺ = CE, H⁺ = H. Not keys.
• Pairs without D: (AH)⁺: A → BC gives ABCH; ABH → BD gives ABCDH; D → AEH gives ABCDEH. AH is a key.
• Check other pairs without D or A: (EH)⁺ = CEH, (BH)⁺ = BH, (CH)⁺ = CH, (BE)⁺ = BCE, and so on. None reach D. Any key without D must contain A and H (you need A to start ABH → BD, and H is only produced by D). So no other keys.

Candidate keys: D and AH. Prime attributes: A, D, H. Non-prime: B, C, E.

Canonical cover (minimal cover)

Different sets of FDs can say the same thing. A canonical cover Fc (also called a minimal cover) is a simplified set equivalent to F (same closure), where:

1. Every right side is a single attribute (for the minimal cover; the canonical cover then merges FDs with the same left side using union).
2. No left side has an extraneous attribute: you cannot remove any attribute from a left side and keep an equivalent set.
3. No FD is redundant: removing any FD changes the closure.

The canonical cover is used by the 3NF synthesis algorithm and to simplify dependency checks.

Algorithm

1. Split right sides:   X -> AB  becomes  X -> A, X -> B
2. Remove extraneous left attributes:
     for each FD  XA -> B: if B is in X+ (computed with full F),
     replace it by X -> B
3. Remove redundant FDs:
     for each FD  X -> A: if A is in X+ computed WITHOUT this FD,
     delete it
4. Optionally merge FDs with the same left side (union)

Do step 2 before step 3. The order matters for correctness.

Worked example 5

F = {A → BC, B → C, A → B, AB → C} on R(A, B, C).

1. Split: A → B, A → C, B → C, A → B, AB → C. Remove the duplicate: {A → B, A → C, B → C, AB → C}.
2. Extraneous attributes in AB → C: is B extraneous? A⁺ = ABC (via A → B, A → C), which contains C. So AB → C becomes A → C, already present. Now {A → B, A → C, B → C}.
3. Redundant FDs:
   • A → C: without it, A⁺ = A → B → C = ABC. C is still reachable, so A → C is redundant. Remove.
   • A → B: without it, A⁺ = A. Needed.
   • B → C: without it, B⁺ = B. Needed.

Fc = {A → B, B → C}.

Worked example 6

F = {A → B, AB → C, B → C, AC → D} on R(A, B, C, D).

1. Right sides are already single.
2. Extraneous attributes:
   • AB → C: A⁺ under F = A, B (A → B), C (B → C), D (AC → D) = ABCD. C ∈ A⁺, so B is extraneous: becomes A → C.
   • AC → D: A⁺ = ABCD contains D, so C is extraneous: becomes A → D.
   • Now {A → B, A → C, B → C, A → D}.
3. Redundant FDs:
   • A → C: without it, A⁺ = A, B, C (B → C), D = ABCD. Redundant. Remove.
   • A → B, B → C, A → D: each is needed (removing any one makes its right side unreachable).
4. Merge: Fc = {A → BD, B → C}.

A canonical cover is not always unique; different removal orders can give different, equally valid covers.

The normal forms

Each normal form is a condition on the FDs (and later, other dependencies) of a relation. Each is stricter than the one before:

 +-------------------------------------------+
 | 1NF                                       |
 |   +-----------------------------------+   |
 |   | 2NF                               |   |
 |   |   +---------------------------+   |   |
 |   |   | 3NF                       |   |   |
 |   |   |   +-------------------+   |   |   |
 |   |   |   | BCNF              |   |   |   |
 |   |   |   |   +-----------+   |   |   |   |
 |   |   |   |   | 4NF / 5NF |   |   |   |   |
 |   |   |   |   +-----------+   |   |   |   |
 |   |   |   +-------------------+   |   |   |
 |   |   +---------------------------+   |   |
 |   +-----------------------------------+   |
 +-------------------------------------------+

Two definitions are used throughout:

• A prime attribute belongs to at least one candidate key. A non-prime attribute belongs to none.
• A partial dependency is an FD where a non-prime attribute depends on a proper subset of a candidate key. A transitive dependency is key → X → A where X is not a super key and A is non-prime.

First normal form (1NF)

A relation is in 1NF if every attribute holds atomic (single, indivisible) values: no lists, no repeating groups, no nested tables.

Violation:

+-----+-------+-----------------+
| sid | sname | phones          |
+-----+-------+-----------------+
| S1  | Asha  | 98450, 99001    |
| S2  | Ravi  | 97000           |
+-----+-------+-----------------+

Searching "who has phone 99001?" needs string parsing, and you cannot constrain each number. The fix is to move the repeating values to their own table, one value per row:

student(sid, sname)          student_phone(sid, phone)
                              S1, 98450
                              S1, 99001
                              S2, 97000

Putting phones in columns phone1, phone2, phone3 is also a repeating group and a poor fix: it caps the count and leaves NULLs. By definition, the relational model assumes every relation is in 1NF. "Atomic" depends on use: a full address can be atomic if you never query its parts.

Second normal form (2NF)

A relation is in 2NF if it is in 1NF and no non-prime attribute is partially dependent on any candidate key. Every non-prime attribute must depend on the whole of every candidate key.

2NF only matters when a candidate key is composite. If every candidate key is a single attribute, a 1NF relation is automatically in 2NF.

Violation: the enrollment table. Key (sid, course). sid → sname makes the non-prime sname depend on part of the key. course → course_name, professor likewise.

Fix: move each partial dependency into its own relation, keyed by the part of the key it depends on.

student(sid, sname)                          sid -> sname
course(course, course_name, professor)       course -> ...
enrollment(sid, course, grade)               sid, course -> grade

Third normal form (3NF)

A relation is in 3NF if, for every non-trivial FD X → A, at least one of these holds:

1. X is a super key, or
2. A is a prime attribute.

Equivalently: it is in 2NF and no non-prime attribute is transitively dependent on a key.

Violation: employee(emp_id, name, dept_id, dept_name) with emp_id → name, dept_id and dept_id → dept_name. The key is emp_id. dept_id → dept_name has a left side that is not a super key and a non-prime right side. The chain emp_id → dept_id → dept_name is transitive, so the department name repeats for every employee in the department.

Fix:

employee(emp_id, name, dept_id)       department(dept_id, dept_name)

The second condition, "or A is prime", is what makes 3NF weaker than BCNF. It lets some redundancy remain to guarantee that a dependency-preserving decomposition always exists (more on that below).

Boyce-Codd normal form (BCNF)

A relation is in BCNF if, for every non-trivial FD X → A, X is a super key. No exceptions.

BCNF and 3NF differ only when a relation has overlapping composite candidate keys and an FD whose right side is prime.

Violation: teaches(student, course, instructor) with rules "a student takes a course from one instructor" (student, course → instructor) and "each instructor teaches only one course" (instructor → course).

• Candidate keys: {student, course} and {student, instructor} (since student, instructor → course via instructor → course).
• instructor → course: is instructor a super key? No. Is course prime? Yes. So it is in 3NF but not BCNF.
• The redundancy: "Rao teaches DBMS" repeats for every student of Rao.

Fix: decompose on the violating FD:

instructor_course(instructor, course)      instructor -> course
student_instructor(student, instructor)

This is lossless (shown later), but the FD student, course → instructor can no longer be checked inside a single table. That is the classic BCNF trade-off.

Summary of normal forms

Identifying the highest normal form: worked problems

Method:

1. Find all candidate keys and the prime attributes.
2. For each FD (after splitting right sides), check BCNF: is the left side a super key?
3. For each BCNF violation, check 3NF: is the right side prime?
4. For each 3NF violation, check 2NF: is the left side a proper subset of a candidate key (partial dependency on a non-prime attribute)?
5. The highest form is the strictest one with no violations. Assume 1NF unless told otherwise.

Problem 1

R(A, B, C, D), F = {AB → C, C → D}.

• Keys: A and B never appear on a right side, so AB is in every key. (AB)⁺ = ABCD. Key: AB. Prime: A, B. Non-prime: C, D.
• AB → C: AB is a super key. Fine.
• C → D: C is not a super key, so BCNF fails. D is non-prime, so 3NF fails. Is C a proper subset of key AB? No, so it is not a partial dependency; 2NF holds.

Highest normal form: 2NF. (A transitive dependency AB → C → D.)

Problem 2

R(A, B, C, D), F = {AB → CD, B → C}.

• Key: AB (A, B never on the right; (AB)⁺ = ABCD). Non-prime: C, D.
• B → C: B is part of key AB, and C is non-prime: a partial dependency. 2NF fails.

Highest normal form: 1NF.

Problem 3

R(A, B, C), F = {AB → C, C → B}.

• Keys: A is never on the right. (AB)⁺ = ABC, key. (AC)⁺ = ACB, key. A⁺ = A. Keys: AB, AC. All attributes are prime.
• C → B: C is not a super key, so not BCNF. B is prime, so 3NF holds.

Highest normal form: 3NF. (This is the same shape as the student-course-instructor example.)

Problem 4

R(A, B, C, D, E), F = {A → B, BC → E, ED → A} (example 3 above).

• Keys: ACD, BCD, CDE. All attributes prime.
• A → B: A is not a super key, so not BCNF. B is prime, so fine for 3NF.
• BC → E, ED → A: left sides are not super keys, but E and A are prime. Fine for 3NF.

Highest normal form: 3NF. Whenever every attribute is prime, the relation is at least in 3NF.

Problem 5

R(A, B, C, D), F = {A → BCD, BC → AD, D → B}.

• Keys: A⁺ = ABCD, key. (BC)⁺ = ABCD, key. D⁺ = DB, not a key. (CD)⁺: D → B gives BCD, BC → AD gives ABCD, key. Keys: A, BC, CD. All attributes prime.
• A → BCD, BC → AD: left sides are keys. Fine.
• D → B: D is not a super key, so not BCNF. B is prime, so 3NF holds.

Highest normal form: 3NF.

Problem 6

R(A, B, C, D, E, F), F = {A → B, A → C, CD → E, CD → F, B → E} (example 1).

• Key: AD. Non-prime: B, C, E, F.
• A → B: A is a proper subset of key AD and B is non-prime: partial dependency.

Highest normal form: 1NF.

Problem 7

R(A, B, C), F = {A → B, B → C, C → A}.

• A⁺ = ABC, B⁺ = BCA, C⁺ = CAB. Keys: A, B, C.
• Every FD has a key on the left.

Highest normal form: BCNF. A useful fact: a relation with only two attributes is always in BCNF.

Decomposition

To normalize, you decompose a relation R into smaller relations R1, R2, ..., Rn whose attributes together cover R. A good decomposition has two properties.

Property 1: lossless join

A decomposition is lossless (non-additive) if joining the pieces back always gives exactly the original relation, never extra rows. If the join can produce rows that were not in R, called spurious tuples, the decomposition is lossy, and you have lost information about which combinations were real.

A lossy split, tested in SQLite. The enrollment relation (student, course, instructor) has rows (Asha, DBMS, Rao), (Ravi, DBMS, Iyer) and (Asha, OS, Menon). Split it into (student, course) and (course, instructor), then join on course:

CREATE TABLE enroll (student TEXT, course TEXT, instructor TEXT);
INSERT INTO enroll VALUES
  ('Asha', 'DBMS', 'Rao'), ('Ravi', 'DBMS', 'Iyer'), ('Asha', 'OS', 'Menon');

CREATE TABLE r1 AS SELECT DISTINCT student, course FROM enroll;
CREATE TABLE r2 AS SELECT DISTINCT course, instructor FROM enroll;

SELECT r1.student, r1.course, r2.instructor
FROM r1 JOIN r2 ON r1.course = r2.course
ORDER BY 1, 2, 3;

student | course | instructor
--------+--------+-----------
Asha    | DBMS   | Iyer        <- spurious
Asha    | DBMS   | Rao
Asha    | OS     | Menon
Ravi    | DBMS   | Iyer
Ravi    | DBMS   | Rao         <- spurious

Five rows instead of three: the join cannot tell who learns from whom. Split instead into (student, instructor) and (instructor, course), join on instructor, and you get back exactly the original three rows, because instructor → course makes instructor a key of the second piece.

Binary lossless test. A decomposition of R into R1 and R2 is lossless if and only if the common attributes form a super key of at least one of them:

(R1 ∩ R2) -> R1   or   (R1 ∩ R2) -> R2      must be in F+

Check with closure: compute (R1 ∩ R2)⁺ and see whether it contains all of R1 or all of R2.

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

• R1(A, B), R2(A, C, D): common = A. A⁺ = AB ⊇ R1. Lossless.
• R1(A, B), R2(C, D): common = nothing. The empty set determines nothing. Lossy (the join is a Cartesian product).

Test for more than two pieces: the chase (tableau) method.

1. Build a table with one row per sub-relation and one column per attribute of R.
2. In row i, write a (distinguished) in the columns of attributes in Ri, and b (a unique placeholder) elsewhere.
3. Repeatedly, for each FD X → Y: if two rows agree on all X columns, make their Y columns equal (if one is a, both become a).
4. If some row becomes all a, the decomposition is lossless. If nothing more changes and no row is all a, it is lossy.

Example: R(A, B, C, D), F = {A → B, B → C, C → D}, decomposed into R1(A, B), R2(B, C), R3(C, D).

start          A    B    C    D
  R1(A,B)      a    a    b13  b14
  R2(B,C)      b21  a    a    b24
  R3(C,D)      b31  b32  a    a

B -> C: rows 1, 2 agree on B (a), so C becomes a in both
  R1           a    a    a    b14
  R2           b21  a    a    b24
  R3           b31  b32  a    a

C -> D: rows 1, 2, 3 all have C = a, and row 3 has D = a
  R1           a    a    a    a      <- all a: LOSSLESS
  R2           b21  a    a    a
  R3           b31  b32  a    a

With F = {A → B, C → D} instead, the same decomposition stays stuck (no two rows agree on A, and C → D only fills row 2's D), so it is lossy.

Property 2: dependency preservation

A decomposition preserves dependencies if every FD in F can be checked using only the FDs that hold inside individual sub-relations, without joining them. Formally, if Fi is the set of FDs of F⁺ that use only attributes of Ri, then (F1 ∪ F2 ∪ ... ∪ Fn)⁺ = F⁺.

Why it matters: if an FD is not preserved, enforcing it means joining tables on every insert or update, which is expensive, so in practice it goes unchecked.

Test for one FD X → Y without computing F⁺:

Z = X
repeat
    for each sub-relation Ri:
        Z = Z + ( closure(Z ∩ Ri, F) ∩ Ri )
until Z does not change
X -> Y is preserved if Y is a subset of Z

Example where it looks lost but is preserved. R(A, B, C), F = {A → B, B → C, C → A}, decomposed into R1(A, B), R2(B, C). The FD C → A mentions attributes in no single piece. Test it:

• Z = C. In R1, C ∩ AB is empty, nothing. In R2, C ∩ BC = C; C⁺ = CAB; ∩ BC = BC. Z = BC.
• In R1, BC ∩ AB = B; B⁺ = BCA; ∩ AB = AB. Z = ABC. A ∈ Z.

C → A is preserved (through C → B in R2 and B → A in R1, both implied by F).

Example where it is lost. The student-course-instructor relation: F = {SC → I, I → C}, decomposed into (I, C) and (S, I).

• Test SC → I: Z = SC. In (I, C): SC ∩ IC = C; C⁺ = C; nothing new. In (S, I): SC ∩ SI = S; S⁺ = S; nothing new. Z stays SC. I ∉ Z.

SC → I is not preserved. Nothing in either table stops a student from being given two instructors for the same course; you would need a join or a trigger to enforce it.

Decomposition algorithms

BCNF decomposition

result = {R}
while some Ri in result is not in BCNF:
    find a non-trivial FD  X -> Y  holding in Ri  with X not a super key of Ri
    replace Ri by  (X ∪ Y)  and  (Ri - Y)

Each split is lossless because the common attributes X determine all of X ∪ Y. The result is always lossless, but may not preserve dependencies.

Worked: R(A, B, C, D, E, F), F = {A → B, A → C, CD → E, CD → F, B → E}, key AD.

1. B → E violates BCNF (B⁺ = BE). Split into R1(B, E) and R2(A, B, C, D, F).
2. In R2, the FDs that hold (computed from closures on R2's attributes) include A → BC and CD → F; AD is the key. A → BC violates. Split into R3(A, B, C) and R4(A, D, F).
3. R1(B, E): key B, BCNF. R3(A, B, C): A⁺ = ABCE, so A → BC and A is the key; B⁺ ∩ ABC = B, nothing else. BCNF. R4(A, D, F): key AD; A⁺ ∩ ADF = A, D⁺ = D; only AD → F. BCNF.

Result: (B, E), (A, B, C), (A, D, F). Lossless (the chase confirms it). But CD → E and CD → F are not preserved: no table contains C and D together with E or F, and the preservation test fails for both. Choosing a different violating FD first can give a different, sometimes better, decomposition.

3NF synthesis

This algorithm always gives a decomposition that is both lossless and dependency preserving, which BCNF cannot guarantee.

1. Compute a canonical cover Fc.
2. For each FD  X -> Y  in Fc, create a relation (X ∪ Y).
3. If no relation contains a candidate key of R, add one
   relation that is a candidate key.
4. Remove any relation whose attributes are a subset of another.

Worked on the same R and F:

1. Fc: no right side splits, no extraneous left attributes (A alone cannot give E or F through CD; C or D alone cannot either), and no FD is redundant. Merging: {A → BC, CD → EF, B → E}.
2. Relations: R1(A, B, C), R2(C, D, E, F), R3(B, E).
3. Key AD is not contained in any of them. Add R4(A, D).
4. No relation is a subset of another.

Result: (A, B, C), (C, D, E, F), (B, E), (A, D). Every FD is preserved, and the chase shows it is lossless. Here each piece happens to be in BCNF as well, but the algorithm only promises 3NF.

3NF versus BCNF

Fourth normal form and multivalued dependencies

BCNF removes redundancy caused by FDs. Some redundancy comes from a different source: independent multi-valued facts stored in one table.

A course has several instructors and several textbooks, and any instructor may use any of the course's books. Instructors and books are independent of each other.

course_info
+--------+------------+----------+
| course | instructor | book     |
+--------+------------+----------+
| DBMS   | Rao        | Korth    |
| DBMS   | Rao        | Navathe  |
| DBMS   | Iyer       | Korth    |
| DBMS   | Iyer       | Navathe  |
+--------+------------+----------+

There are no non-trivial FDs at all: the only key is all three attributes, so the table is in BCNF. But adding a third book means adding two rows (one per instructor), and forgetting one creates an inconsistent state.

A multivalued dependency (MVD) X ↠ Y holds when, for each value of X, the set of Y values is independent of the values of the remaining attributes Z. Here course ↠ instructor and course ↠ book. Formally: if two tuples agree on X, then swapping their Y values must also give tuples in the relation. Every FD is also an MVD, but not the other way round.

A relation is in 4NF if, for every non-trivial MVD X ↠ Y, X is a super key. (An MVD is trivial if Y ⊆ X or X ∪ Y is all of R.)

Fix: split each independent fact into its own table.

course_instructor(course, instructor)   course_book(course, book)
  DBMS, Rao                              DBMS, Korth
  DBMS, Iyer                             DBMS, Navathe

The split on an MVD is lossless: a decomposition into (X ∪ Y) and (X ∪ Z) is lossless exactly when X ↠ Y holds.

Fifth normal form (brief)

Fifth normal form (5NF, also called project-join normal form) deals with join dependencies: cases where a relation can be rebuilt losslessly from three or more projections, but not from any two.

The textbook example is (agent, company, product) with the rule: "if an agent sells for 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 that rule, the relation equals the join of (agent, company), (agent, product) and (company, product), and storing the three-column table is redundant. Without the rule, the three-way split would create spurious tuples.

A relation is in 5NF if every join dependency is implied by its candidate keys. 5NF problems are rare in practice; recognizing the idea is usually enough for interviews.

Denormalization

Denormalization is deliberately reintroducing redundancy to make reads faster or simpler, after you have a normalized design.

Common forms:

• Duplicating a column to avoid a join, such as storing customer_name on orders for an order list page.
• Storing derived values, such as order_total or follower_count, instead of summing on every read.
• Pre-joined or summary tables and materialized views for reports.
• Star schemas in data warehouses, where dimension tables are kept wide and flat (see DBMS introduction).
• Embedding related data in documents in NoSQL databases.

Rules of thumb: normalize first (to 3NF or BCNF), measure, and denormalize only specific, proven hot paths. Keep the copies in sync with transactions, triggers, or an asynchronous pipeline, and decide how stale a copy may be. Some denormalized values are snapshots on purpose: an order's price_at_purchase must not change when the product's price changes later, so storing it is correct design, not redundancy.

Interview questions

Q1. What is normalization and why is it needed?

Normalization organizes a schema so that each fact is stored once, by decomposing relations based on functional and multivalued dependencies. It removes redundancy and the update, insertion and deletion anomalies that redundancy causes. The goal is a set of relations in a chosen normal form (usually 3NF or BCNF) that can be joined back losslessly.

Q2. Explain insertion, update and deletion anomalies with an example.

In a table with one row per student per course that also stores the course's professor: an update anomaly occurs when changing a professor requires updating many rows and missing one leaves conflicting data. An insertion anomaly occurs when you cannot add a new course until a student enrolls, because the key needs a student id. A deletion anomaly occurs when deleting the last student in a course also deletes the only record of that course.

Q3. What is a functional dependency? What makes it trivial?

X → Y means any two tuples that agree on X must agree on Y; it comes from business rules, not from sample data. It is trivial when Y is a subset of X, such as AB → A, because it always holds. Non-trivial FDs are the ones that drive normalization.

Q4. State Armstrong's axioms.

Reflexivity: if Y ⊆ X then X → Y. Augmentation: if X → Y then XZ → YZ. Transitivity: if X → Y and Y → Z then X → Z. They are sound and complete. Union, decomposition and pseudo-transitivity are derived from them.

Q5. How do you find the candidate keys of a relation?

Put attributes that never appear on a right side into every key, and leave out attributes that appear only on right sides. Compute the closure of the mandatory set; if it covers all attributes, it is the only key. Otherwise add the remaining attributes in increasing combinations, keeping minimal sets whose closure covers the relation.

Q6. What is the difference between 2NF and 3NF?

2NF forbids partial dependencies: a non-prime attribute depending on part of a composite candidate key. 3NF additionally forbids transitive dependencies: for every FD X → A, X must be a super key or A must be prime. For example, emp_id → dept_id → dept_name is in 2NF but not 3NF.

Q7. What is the difference between 3NF and BCNF? Give an example in 3NF but not BCNF.

3NF allows X → A when A is prime even if X is not a super key; BCNF does not. R(student, course, instructor) with student, course → instructor and instructor → course has keys {student, course} and {student, instructor}. instructor → course violates BCNF but satisfies 3NF because course is prime.

Q8. What is a lossless join decomposition and how do you test it?

It is a decomposition whose natural join always reproduces exactly the original relation, with no spurious tuples. For two pieces, it is lossless if the common attributes are a super key of at least one piece, checked by computing their closure. For more pieces, use the chase (tableau) method.

Q9. What is dependency preservation and why does it matter?

A decomposition preserves dependencies if every original FD can be enforced by checking FDs within individual tables, without joins. If an FD is lost, enforcing it requires joining tables on every change, so in practice it often goes unenforced. 3NF synthesis always preserves dependencies; BCNF decomposition may not.

Q10. What is a canonical cover?

A simplified set of FDs equivalent to the original, with no extraneous attributes on left sides and no redundant FDs, and with FDs that share a left side merged. Compute it by splitting right sides, removing extraneous left attributes using closures, then removing FDs that are implied by the rest. It is the starting point for 3NF synthesis.

Q11. Is a relation with all attributes prime always in 3NF? In BCNF?

It is always in 3NF, because every right side is prime, so the 3NF condition holds for every FD. It is not necessarily in BCNF: R(A, B, C) with AB → C and C → B has every attribute prime but C → B violates BCNF.

Q12. What is a multivalued dependency and 4NF?

X ↠ Y means the set of Y values for a given X is independent of the other attributes, like a course's instructors and its textbooks. Storing both in one table forces every combination to be stored. 4NF requires every non-trivial MVD to have a super key on the left, and is reached by splitting each independent fact into its own table.

Q13. When would you denormalize?

When a measured, frequent read path is too slow because of joins or aggregation, and the data changes rarely or can tolerate brief staleness. Examples are storing a follower count, copying a customer name onto orders for a listing page, or building a summary table for a dashboard. You accept extra write work and the risk of inconsistency, so you keep copies in sync with transactions, triggers or pipelines.

Q14. R(A, B, C, D) with AB → C and C → D: what is the highest normal form, and how do you fix it?

The key is AB. C → D has a non-super-key left side and a non-prime right side, so it violates 3NF; it is not a partial dependency, so the relation is in 2NF. Decompose into (A, B, C) and (C, D), which is lossless because C is the key of (C, D), preserves both FDs, and puts both pieces in BCNF.

Q15. Can every relation be decomposed into BCNF losslessly?

Yes. The BCNF decomposition algorithm always produces a lossless result, because each split is on an FD whose left side becomes a key of one piece. What cannot always be achieved is BCNF together with dependency preservation.

Key takeaways

• Redundancy causes update, insertion and deletion anomalies; normalization stores each fact once.
• An FD X → Y comes from business rules; Armstrong's axioms derive all implied FDs.
• Attribute closure answers "does X determine Y?" and "is X a key?"; use left-only and right-only attributes to find candidate keys fast.
• 1NF: atomic values. 2NF: no partial dependencies. 3NF: every X → A has X a super key or A prime. BCNF: every determinant is a super key.
• Identify the highest normal form by finding keys and prime attributes, then checking each FD from BCNF downward.
• Lossless join: common attributes must be a key of one side (binary), or use the chase.
• 3NF synthesis is always lossless and dependency preserving; BCNF decomposition is lossless but may lose FDs.
• 4NF handles independent multi-valued facts; 5NF handles join dependencies.
• Denormalize deliberately, for measured read paths, and keep copies consistent.

Next lesson

Continue with Indexing and B-trees.