Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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 email
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".

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

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}:

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

More DBMS notes