Notes › DBMS
Keys and Normalization
Keys
Take this table:
Student(roll_no, email, name, phone, dept_id)
| Key | Meaning | Example |
|---|---|---|
| Super key | any set of columns that uniquely identifies a row | {roll_no}, {roll_no, name}, {email} |
| Candidate key | a minimal super key (remove any column and it stops being unique) | {roll_no}, {email} |
| Primary key | the candidate key you choose; unique and NOT NULL; one per table | roll_no |
| Alternate key | candidate keys not chosen as primary | |
| Composite key | a key made of 2+ columns | {student_id, course_id} in Enrollment |
| Foreign key | a column that refers to the primary key of another table | dept_id → Department(dept_id) |
| Surrogate key | an artificial id with no business meaning | auto-increment id, UUID |
Every candidate key is a super key, but not every super key is a candidate key.
CREATE TABLE Department (
dept_id INT PRIMARY KEY,
name VARCHAR(50) NOT NULL
);
CREATE TABLE Student (
roll_no INT PRIMARY KEY,
email VARCHAR(100) UNIQUE NOT NULL, -- alternate key
name VARCHAR(50),
dept_id INT,
FOREIGN KEY (dept_id) REFERENCES Department(dept_id) ON DELETE SET NULL
);
Referential integrity: a foreign key value must exist in the referenced table (or be NULL). ON DELETE CASCADE / SET NULL / RESTRICT decides what happens when the parent row is deleted.
Functional dependency (FD)
X → Y means: if two rows have the same X, they must have the same Y. "X determines Y".
- roll_no → name (one roll number has one name)
- dept_id → dept_name
| Type | Meaning |
|---|---|
| Trivial | Y ⊆ X, e.g. {a, b} → a |
| Full | Y depends on the whole key, not a part |
| Partial | Y depends on part of a composite key → violates 2NF |
| Transitive | X → Y → Z where Y is not a key → violates 3NF |
Attribute closure (finding candidate keys)
R(A, B, C, D) with A → B, B → C, C → D. A⁺ = {A, B, C, D} = all attributes → A is a candidate key. B⁺ = {B, C, D} — missing A → not a key. Trick: an attribute that never appears on the right side of any FD must be part of every candidate key.
Why normalize? The anomalies
One un-normalized table:
| student_id | name | course_id | course_name | instructor | instructor_phone |
|---|---|---|---|---|---|
| 1 | Aman | C1 | DBMS | Rao | 98xx |
| 1 | Aman | C2 | OS | Iyer | 97xx |
| 2 | Riya | C1 | DBMS | Rao | 98xx |
- Update anomaly: Rao's phone changes → must update many rows; miss one and data is inconsistent.
- Insert anomaly: can't add a new course until some student enrols.
- Delete anomaly: delete Riya (the only student in some course) and you lose the course itself. Normalization = splitting tables so each fact is stored once.
1NF — atomic values
Every cell holds one value; no lists or repeating groups.
| student | phones |
|---|---|
| Aman | 98xx, 97xx |
Fix: one row per phone, or a separate StudentPhone(student_id, phone) table.
2NF — no partial dependency
1NF and every non-key column depends on the whole primary key. Enrollment(student_id, course_id, name, course_name, grade), key = {student_id, course_id}:
- name depends only on student_id → partial ❌
- course_name depends only on course_id → partial ❌
- grade depends on both → fine ✅ Fix: split into
Student(student_id, name)
Course(course_id, course_name, instructor, instructor_phone)
Enrollment(student_id, course_id, grade)
A table whose key is a single column is automatically in 2NF.
3NF — no transitive dependency
2NF and no non-key column depends on another non-key column. In Course: course_id → instructor → instructor_phone. instructor_phone depends on the key through instructor ❌. Fix:
Course(course_id, course_name, instructor_id)
Instructor(instructor_id, name, phone)
Formal rule: for every FD X → A, either X is a super key or A is part of some candidate key (a prime attribute).
BCNF — Boyce-Codd Normal Form
Stricter 3NF: for every FD X → Y, X must be a super key. (No exception for prime attributes.)
Classic example: Teaches(student, subject, teacher), where each teacher teaches one subject (teacher → subject) and a student takes a subject from one teacher. Key = {student, subject}. teacher → subject, but teacher isn't a super key → in 3NF but not BCNF.
Fix: TeacherSubject(teacher, subject) and StudentTeacher(student, teacher).
BCNF decomposition is always lossless but may not preserve all dependencies; 3NF can always do both.
Summary
| Form | Rule | Removes |
|---|---|---|
| 1NF | atomic values | repeating groups |
| 2NF | 1NF + no partial dependency | duplication from part-key facts |
| 3NF | 2NF + no transitive dependency | non-key → non-key |
| BCNF | every determinant is a super key | remaining anomalies |
| 4NF / 5NF | no multi-valued / join dependencies | rare in practice |
Memory trick: "the key, the whole key, and nothing but the key".
Lossless join
A split is lossless if joining the parts gives back exactly the original table — no extra (spurious) rows. For R split into R1 and R2: lossless if the common columns are a key of R1 or of R2.
Denormalization
Deliberately adding redundancy for faster reads (fewer joins) — common in reporting, analytics and NoSQL designs. The price: more storage and harder updates. Normalize first, denormalize only for a measured performance problem.
Interview one-liners
- Candidate key = minimal super key; primary key = the chosen candidate key (unique, not null).
- 2NF removes partial dependencies; 3NF removes transitive ones; BCNF: every determinant is a super key.
- Normalization reduces redundancy and anomalies; denormalization trades them for read speed.
- Related: ER Model and Relational Schema Design, SQL Essentials and Joins.