Core CS · DBMS

One fact, stored in exactly one place

Q: What is a functional dependency?

X → Y means any two rows that agree on X must agree on Y . In the enrolment table SID → Name holds, because one student ID can never carry two different names. It is a rule about every legal row, so you confirm it from what the data means, not by checking a sample.

Normalisation is not a ritual to memorise. It is a repair procedure: find a fact the table stores more than once, give it a table where it is the key, and a whole class of bugs stops being possible.

Split a messy table, step by step →

Every rule from 1NF to BCNF is the same sentence applied to a different kind of dependency: a fact belongs in the table whose key determines it.

01 The idea

Redundancy is not a space problem

Students are told normalisation saves disk. It barely does. The table in this lesson shrinks from 35 cells to 34 when you normalise it fully — one cell saved. What actually changes is that after the split, no two rows can disagree with each other, because no fact is written twice.

Every rule works on one idea: the functional dependency. Written X → Y, it says that any two rows agreeing on X must agree on Y. A student ID determines a name. A course code determines a course title. An instructor determines the room they sit in. Once you can list those arrows for a table, normalisation stops being a set of definitions to recite and becomes a checklist: for each arrow, ask whether its left-hand side is the key of the table it sits in. If it is not, that arrow is telling you where the next table goes.

If two rows can ever disagree about the same fact, the schema is wrong. Find the column that determines that fact, and move the fact into a table where that column is the key.

Functional dependencyWritten X → Y. Two rows that agree on X must agree on Y. It is a rule about all legal data, not something you confirm by eyeballing five sample rows.

Candidate keyThe smallest set of columns that identifies a row. Remove any column from it and rows start colliding. A table can have more than one.

AnomalyAn insert, update or delete that the schema either blocks outright or lets you get half-right. Removing anomalies is the entire point of normalising.

02 Worked example

One enrolment table, and the three things it gets wrong

Three students, three courses, five enrolments. The table is already flat — one value per cell — so it is in 1NF. Its key is the pair {SID, CID}: S1 appears on two rows and C1 appears on two rows, so neither column identifies a row alone, and the five pairs are all distinct. Amber marks a cell that repeats something an earlier row already said.

SID	Name	CID	Course	Instructor	Room	Marks
S1	Asha	C1	DBMS	Rao	R101	78
S1	`Asha`	C2	OS	Iyer	R204	65
S2	Ravi	C1	`DBMS`	`Rao`	`R101`	71
S3	Meera	C2	`OS`	`Iyer`	`R204`	82
S3	`Meera`	C3	Networks	Rao	`R101`	90

Nine amber cells out of thirty-five. The dependencies that produce them are SID → Name, CID → Course, Instructor and Instructor → Room. Only {SID, CID} → Marks uses the whole key, and Marks is the only non-key column that never restates something an earlier row already said. Now watch what those nine cells cost.

Insertion anomaly — a fact you cannot recordA new course is approved: C4, Compilers, taught by Nair in R310. No student has enrolled in it yet. There is nowhere to put it, because every row needs a SID and SID is half the primary key.INSERT (SID = null, Name = null, C4, Compilers, Nair, R310, Marks = null) → rejected: no part of a primary key may be null

Update anomaly — a fact you can get half-rightRao moves office from R101 to R308. His room is written on rows 1, 3 and 5. Change two and miss one, and the table now claims Rao is in two rooms at once. No constraint can catch it, because the database does not know those three cells are the same fact.UPDATE Room = 'R308' WHERE Instructor = 'Rao' → 3 rows must change together, or the table contradicts itself

Deletion anomaly — a fact you lose by accidentMeera withdraws from Networks, so row 5 goes. Row 5 was the only place the database recorded that C3 is Networks, taught by Rao. Deleting an enrolment deleted a course.DELETE WHERE SID = 'S3' AND CID = 'C3' → the only row saying C3 is Networks, taught by Rao, goes with it

✓

One cause behind all threeThis table stores three different kinds of fact: who a student is, what a course is, and who scored what. Give each kind its own table and all three anomalies stop being expressible.STUDENT(SID, Name) COURSE(CID, Course, Instructor) INSTRUCTOR(Instructor, Room) ENROLMENT(SID, CID, Marks)

UNFa cell holds a list — nothing can be indexed or joined

→

1NFone value per cell; 3 rows became 5, key grows to {SID, CID}

→

2NFno partial dependency — kills the insert and delete anomalies

→

3NFno transitive dependency — kills the update anomaly on Room

Read the arrows, not the table. Each one is named by its left-hand side. SID → Name hangs off half the key, so it forces a table out at 2NF. Instructor → Room hangs off a non-key column, so it forces one out at 3NF. Repeated cells fall 9 → 7 → 1 → 0 as you go, while the number of distinct facts stays at 16 the whole way — nothing was dropped, which is why the four tables rejoin to exactly the original five rows.

03 Mechanics

Four tests, and the split each one forces

Each normal form is one test applied to one dependency. Run them in order, because each assumes the one before it has already passed. The right-hand column is what the test costs you when you skip it — that is the part interviewers push on.

Normal form	The test	What failed here	The split it forces
1NF	`one value per cell`	`Courses held "C1, C2"`	one row per (SID, CID) pair — 3 rows became 5
2NF	`nothing depends on part of a composite key`	`SID → Name`	STUDENT(SID, Name)
2NF	`nothing depends on part of a composite key`	`CID → Course, Instructor`	COURSE(CID, Course, Instructor, Room)
3NF	`no non-key column determines another`	`Instructor → Room`	INSTRUCTOR(Instructor, Room)
BCNF	`every determinant is a candidate key`	`nothing — all four pass`	no further split needed

Before — one table

ENROLMENT  SID          * key  Name           -- SID → Name  CID          * key  Course         -- CID → Course  Instructor     -- CID → Instructor  Room           -- Instructor → Room  Marks          -- {SID,CID} → Marks-- 5 rows · 35 cells · 9 repeated

After — four tables in 3NF

STUDENT(SID*, Name)COURSE(CID*, Course, Instructor)INSTRUCTOR(Instructor*, Room)ENROLMENT(SID*, CID*, Marks) COURSE.Instructor    → INSTRUCTORENROLMENT.SID        → STUDENTENROLMENT.CID        → COURSE-- 13 rows · 34 cells · 0 repeated

SID → Name forced the STUDENT table. Name depended on half the key, so it was rewritten once per course the student took. In STUDENT, SID is the whole key, so the name is stored exactly once and SID stays behind in ENROLMENT as a foreign key.

CID → Course, Instructor forced the COURSE table. Same partial dependency, other half of the key. Room travels with them at this stage: it depends on CID too, just not directly, and it has nothing to do with a student's mark.

Instructor → Room forced the INSTRUCTOR table. After the 2NF split, COURSE still wrote R101 twice, because CID determines Instructor and Instructor determines Room. Room reached the key only through a non-key column, which is what "transitive" means.

Nothing forced a fourth split. A determinant is the left side of an arrow. In the four tables above every determinant — SID, CID, Instructor, {SID, CID} — is the key of the table it sits in, so the schema is already in BCNF. That is the usual outcome; a 3NF table that is not in BCNF needs two overlapping candidate keys, which is rare.

05 Cheat sheet

Four forms, four tests, four costs

Normal form	Test to apply	What ignoring it costs you
1NF	`one atomic value per cell, no repeating group`	You cannot index, join or constrain a list stuffed into a cell.
2NF	`no non-key column depends on only part of a composite key`	Insertion and deletion anomalies on whatever that part describes. Free if the key is a single column.
3NF	`no non-key column depends on a non-key column`	Update anomalies on the chained fact — the same value in many rows.
BCNF	`every determinant is a candidate key`	Rarely anything, and reaching it can cost you a dependency you can no longer check inside one table.

Reaching 3NF does not mean every trace of redundancy is gone. It removes exactly the redundancy that partial and transitive dependencies cause — which in our table happened to be all of it. A 3NF table with two overlapping candidate keys can still repeat a fact on every row; that is the BCNF case. Independent multi-valued facts crammed into one table repeat too, and neither 3NF nor BCNF says anything about them — that is 4NF, a separate rule. "Zero repeated cells" was a measurement of this schema, not a promise from the form.

Lossless joinA decomposition is lossless if joining the pieces gives back exactly the original rows — no fewer, no extra. Split on a dependency so that its determinant becomes the key of one piece and stays as a foreign key in the other, and it always is. Our four tables rejoin to the same five enrolments.

Dependency preservationYou also want every dependency checkable inside a single table, with no join. Every schema has a 3NF decomposition that is both lossless and dependency-preserving. BCNF is only guaranteed lossless — that is the one thing 3NF has over it.

Joins are the billFour tables means a query that once read one row now joins four. Normalisation buys write-time safety with read-time work. On a system that writes constantly that is the right trade; on a report scanning millions of rows it may not be.

06 Where & why

Where 3NF is the default, and where it is deliberately abandoned

Normalisation is not a virtue you apply everywhere. It is a trade you make once you know the workload: a normalised schema is cheap to write and expensive to read, and a denormalised one is the reverse. Real systems pick per workload, and they pick knowingly.

PostgreSQL · MySQL

3NF is the default for anything that writes

An orders schema keeps customers, addresses, products and line items in separate tables. A customer changes their phone number in one row, and every order ever placed shows the new number because none of them copied it.

Snowflake · BigQuery

Warehouses denormalise on purpose

A star schema repeats product name and category on every row of a wide dimension table. That is redundancy, and it is accepted: data arrives in controlled batch loads rather than ad-hoc updates, so nobody can update two of three copies.

MongoDB · DynamoDB

Embedding is a normalisation decision

An order document that embeds its line items is a repeating group by 1NF's standard. It is the right call when the items are only ever read with the order, and the wrong one the moment you need to query items on their own.

Materialised views

Keep 3NF as the truth, denormalise a copy

A materialised view or nightly summary table holds the flat, pre-joined shape reports want. The normalised tables remain the single source of each fact, so a wrong copy is a refresh bug you can rebuild away, not corrupted data.

Denormalise deliberately, after measuring a read that is genuinely too slow, and record which table is the source of truth. What you cannot do is denormalise a schema you never normalised — without the dependencies written down, you are not making a trade, you are just guessing.

07 Interview questions

What they actually ask

Normalisation is the most asked DBMS topic in placement interviews and the most commonly recited without understanding. Expect to be handed a table and asked to name its key, its dependencies and its normal form, in that order.

What is normalisation, in one line?

Splitting a table so that every fact is stored in exactly one place. You do it by listing the functional dependencies and giving each determinant a table where it is the key. The goal is not saving disk — our example goes from 35 cells to 34 — it is making it impossible for two rows to disagree.

What is a functional dependency?

X → Y means any two rows that agree on X must agree on Y. In the enrolment table SID → Name holds, because one student ID can never carry two different names. It is a rule about every legal row, so you confirm it from what the data means, not by checking a sample.

How do you find the candidate key of a table?

Take the smallest column set whose values are unique across all legal rows, and check that removing any column from it breaks uniqueness. Here it is {SID, CID}: S1 is on two rows and C1 is on two rows, so neither works alone, and the five pairs are distinct. Formally you compute the attribute closure of a column set and check it reaches every column.

What are the three anomalies, with an example of each?

Insertion: you cannot record course C4 because the key needs a SID and no student has enrolled yet. Update: Rao’s room sits on three rows, so changing two leaves the table claiming two rooms. Deletion: removing Meera’s Networks enrolment removes the only record that Networks exists. All three are the same disease — one table holding several kinds of fact.

What is 1NF, and what does it cost you?

Every cell holds a single indivisible value and there is no repeating group of columns. Our original row stored C1, C2 in one cell; flattening turned 3 rows into 5. The cost is that the key grows: SID identified a row before, and {SID, CID} is needed after, which is precisely what makes 2NF violations possible.

What is 2NF, and what is a partial dependency?

2NF is 1NF plus no non-key column depending on only part of a composite key. SID → Name is partial because SID is half of {SID, CID}, so the name is rewritten once per course the student takes. The fix is STUDENT(SID, Name). If the key is a single column there is no proper part, so any 1NF table with a one-column key is automatically in 2NF.

What is 3NF, and what is a transitive dependency?

3NF is 2NF plus no non-key column determining another non-key column. In the 2NF COURSE table, CID → Instructor and Instructor → Room, so Room reaches the key only through Instructor. Splitting out INSTRUCTOR(Instructor, Room) stores each instructor’s room once instead of once per course they teach — R101 sat on two of the three COURSE rows, and on three of the five original rows.

3NF versus BCNF — what is the actual difference?

BCNF demands that every determinant be a candidate key, with no exceptions. 3NF lets a determinant off the hook if the column it determines is itself part of some candidate key, which is why a table can be in 3NF and not in BCNF. The trade matters: every schema has a lossless, dependency-preserving 3NF decomposition, while BCNF sometimes forces you to give a dependency up.

A table has a single-column primary key. Which forms does it get for free?

2NF, provided it is already in 1NF. A partial dependency means depending on part of the key, and a one-column key has no proper part, so the test cannot fail. It buys you nothing beyond that: a one-column key does not stop one non-key column from determining another, so 3NF and BCNF still have to be tested by hand, and 1NF is a precondition you have to check rather than a prize.

How do you know a decomposition did not lose data?

Hard

TEACHES(Student, Subject, Teacher) records that a student studies a subject under a teacher. Each teacher teaches exactly one subject, and a student takes any given subject from only one teacher. Show the table is in 3NF, show it is not in BCNF, give the BCNF decomposition, and name the dependency it can no longer enforce.

Follow-up

The usual 3NF hunt — find a non-key column that determines another — comes up empty here, and BCNF fails anyway. This is the one case where going a form further costs you something real, so the last part of the question is not a trick.

Show the hint

List both candidate keys first, then check each determinant against them. The determinant that is not a candidate key is the violation, and the dependency you lose is the one whose left-hand side ends up split across the two new tables.