Functional Dependencies and Normalization

Syllabus tag: Paper-II, Section-B, Topic IV.6 — Functional Dependencies and Normalization

Definition

A Functional Dependency (FD) A → B means that the value of attribute set A uniquely determines the value of attribute set B — for any two tuples with the same A value, the B value must also be the same. Normalization is the systematic process of decomposing relations to minimize redundancy and avoid insertion, update, and deletion anomalies.

Types of Functional Dependency

• Trivial FD: A → B where B ⊆ A (always holds, no information content)
• Non-trivial FD: A → B where B ⊄ A
• Full functional dependency: B depends on the whole of composite key A, not any proper subset
• Partial dependency: a non-key attribute depends on only part of a composite primary key
• Transitive dependency: A → B and B → C implies A → C, where B is not a candidate key (a non-key attribute determining another non-key attribute)

Armstrong's Axioms (inference rules for FDs)

1. Reflexivity: if B ⊆ A, then A → B
2. Augmentation: if A → B, then AC → BC for any C
3. Transitivity: if A → B and B → C, then A → C

• Derived rules: Union (A→B, A→C ⟹ A→BC), Decomposition (A→BC ⟹ A→B, A→C), Pseudotransitivity

Numerical — Attribute Closure & Candidate Key

Relation R(A, B, C, D, E) with FDs: A → BC, CD → E, B → D, E → A

• Find closure of A, written A⁺: start {A} → apply A→BC → {A,B,C} → apply B→D → {A,B,C,D} → apply CD→E → {A,B,C,D,E} = all attributes.
• Since A⁺ = R, A is a candidate key (a single attribute that functionally determines every other attribute).

Normal Forms

Numerical — Worked Decomposition Example

Enrollment(StudentID, CourseID, StudentName, CourseName, Grade) with FDs: StudentID → StudentName, CourseID → CourseName, (StudentID, CourseID) → Grade. Primary key = (StudentID, CourseID).

• StudentName depends only on StudentID (part of the key) → partial dependency → violates 2NF.
• CourseName depends only on CourseID (part of the key) → also a partial dependency → violates 2NF.
• Decompose to 2NF: Student(StudentID, StudentName), Course(CourseID, CourseName), Enrollment(StudentID, CourseID, Grade).
• Check 3NF: no non-key attribute determines another non-key attribute in any of the three tables → already in 3NF (and BCNF, since StudentID and CourseID are each the sole determinant in their tables).

Normalization Step-by-Step with Sample Tables (UNF → 5NF)

One running example carried through every normal form. In the exam, show the data before and after each step — FPSC awards marks for the visible anomaly being removed, not just the final schema.

Step 0 — Unnormalized Form (UNF)

StudentCourse(StudentID, StudentName, Dept, DeptHead, Courses) — the Courses cell holds a repeating group.

• Problem: one cell holds many values — it cannot be queried, sorted, joined, or indexed.

Step 1 — First Normal Form (1NF)

Rule: every attribute value is atomic; no repeating groups. Flatten the repeating group into separate rows. PK = (StudentID, CourseID).

• FDs holding here: StudentID → StudentName, Dept · Dept → DeptHead · CourseID → CourseName · (StudentID, CourseID) → Grade
• Anomalies still present:
  • Insertion: a new course with no enrolled student cannot be stored (StudentID is part of the PK and cannot be NULL).
  • Update: renaming DBMS means editing every row containing it — miss one and the data is inconsistent.
  • Deletion: deleting S2's only enrollment also erases the fact that EE's head is Dr. Malik.

Step 2 — Second Normal Form (2NF)

Rule: 1NF + no partial dependency (no non-key attribute may depend on only part of the composite key).

Violations: StudentName/Dept/DeptHead depend on StudentID alone; CourseName depends on CourseID alone.

Student

Course

Enrollment

• Fixed: a course can now exist with zero enrollments; a course name is stored once.

Step 3 — Third Normal Form (3NF)

Rule: 2NF + no transitive dependency (no non-key attribute determining another non-key attribute).

Violation: in Student, StudentID → Dept → DeptHead, so DeptHead depends on the key only transitively.

Student

Department

• Course and Enrollment are unchanged and already in 3NF.
• Fixed: a department can be created before any student joins it; changing a department head is a single-row update.

Step 4 — Boyce-Codd Normal Form (BCNF)

Rule: every determinant (left side of every FD) must be a candidate key. A relation can be in 3NF and still break BCNF when candidate keys overlap.

New mini-example: each student studies a subject under exactly one teacher, and each teacher teaches exactly one subject.

StudentTeacher

• FDs: (StudentID, Subject) → Teacher and Teacher → Subject
• Candidate keys: (StudentID, Subject) and (StudentID, Teacher) — so Subject and Teacher are both prime attributes, meaning there is no transitive dependency → the relation is in 3NF.
• But: Teacher → Subject has a determinant (Teacher) that is not a candidate key → violates BCNF.

Decomposition — Teaches

Decomposition — Studies

• Key trade-off (favourite follow-up question): this decomposition is lossless but not dependency-preserving — (StudentID, Subject) → Teacher can no longer be checked on any single table. 3NF decomposition is always both lossless and dependency-preserving; BCNF may have to give up dependency preservation.

Step 5 — Fourth Normal Form (4NF)

Rule: BCNF + no non-trivial multivalued dependency. An employee's skills and languages are independent facts, so storing them together forces every combination.

EmployeeSkillLanguage

• MVDs: EmpID →→ Skill and EmpID →→ Language. Four rows store what are really 2 + 2 independent facts; adding one new skill forces two more rows.

EmpSkill

EmpLanguage

Step 6 — Fifth Normal Form (5NF / Project-Join NF)

Rule: 4NF + no join dependency that is not implied by the candidate keys — i.e., the relation cannot be losslessly split into two relations, only into three or more.

Business rule: if supplier S supplies part P, and project J uses part P, and S supplies project J, then S supplies P to J.

SupplierPartProject (SPJ)

• The last row is implied by the other three under the business rule — pure redundancy. No decomposition into two tables is lossless, but decomposing into three binary projections is: SP(Supplier, Part), PJ(Part, Project), SJ(Supplier, Project). Joining all three reconstructs SPJ exactly.

Summary — one line per level

Multivalued Dependency (4NF) & Join Dependency (5NF)

• Multivalued dependency A →→ B: for each value of A, there is a set of values of B, independent of any other attribute C in the relation (e.g., an Employee with multiple Skills and multiple Languages, stored in one table, creates spurious combinations unless split into two tables).
• Join dependency: a relation can be losslessly reconstructed by joining more than two of its projections, even when no smaller (binary) decomposition is lossless — motivates 5NF.

Denormalization

• Deliberately introducing controlled redundancy (merging normalized tables back) to improve read performance in reporting/analytics systems, trading some update complexity for query speed.

MCQ Trap

• 2NF violations = partial dependency on a composite key (2NF is irrelevant if the primary key is a single attribute — a single-attribute-key relation in 1NF is automatically in 2NF).
• 3NF violations = transitive (non-key → non-key) dependency.
• BCNF is stricter than 3NF — every 3NF relation is not necessarily BCNF (only when candidate keys overlap on a common attribute).

CSS Exam Angle

• Normalization is a high-yield perennial topic (2017, 2023, 2024, 2025) — expect either a definition/short-note question or a "given this relation and its FDs, normalize to 3NF/BCNF" numerical.
• Always show FD closures or explicitly name which dependency (partial/transitive) is being removed at each step — FPSC awards marks for the reasoning trail, not just the final schema.

Likely Questions

1. What is Normalization? Discuss 1NF, 2NF, and 3NF with examples.
2. Distinguish full functional dependency, partial dependency, and transitive dependency.
3. Given a relation and its FD set, compute the closure of a given attribute set and identify all candidate keys.
4. Given an unnormalized relation, decompose it step-by-step to 3NF/BCNF, naming the anomaly removed at each step.
5. Differentiate BCNF from 3NF; give an example relation that is in 3NF but not BCNF.
6. Explain multivalued dependency and its role in 4NF.

---

📘 Enrichment — More Numericals (the ones FPSC can set)

Numerical 1 — Finding ALL Candidate Keys

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

Shortcut: an attribute that never appears on any right-hand side must be in every key. RHS attributes = {C, D, E, B} → A never appears → A is in every key.

• A⁺ = {A} → not a key alone.
• (AB)⁺: AB→C → {A,B,C}; C→D → +D; D→E → +E = all ✅ → AB is a key
• (AC)⁺: C→D, D→E, E→B → {A,C,D,E,B} ✅ → AC
• (AD)⁺: D→E, E→B, AB→C → all ✅ → AD
• (AE)⁺: E→B, AB→C, C→D → all ✅ → AE
• All are minimal (A alone fails) → Candidate keys = AB, AC, AD, AE.

Follow-up (normal form test): every attribute is prime (appears in some key), so no partial or transitive dependency on non-prime attributes exists → R is in 3NF. But C → D has a determinant (C) that is not a super key → R is not in BCNF. Perfect example of "3NF but not BCNF".

Numerical 2 — Minimal (Canonical) Cover

F = { A → BC, B → C, A → B, AB → C }

1. Split right sides into single attributes: A→B, A→C, B→C, A→B, AB→C → remove duplicate → {A→B, A→C, B→C, AB→C}
2. Remove extraneous left-side attributes: in AB→C, check A⁺ = {A, B, C} contains C → B is extraneous → AB→C becomes A→C (already present).
3. Remove redundant FDs: A→C follows from A→B and B→C (transitivity) → drop it.

• Minimal cover = { A → B, B → C }

Numerical 3 — Lossless-Join Test (binary decomposition)

Rule: decomposition of R into R1, R2 is lossless if the common attributes (R1 ∩ R2) form a super key of R1 or of R2.

• R(A, B, C), F = {A → B}. Decompose into R1(A, B), R2(A, C): common = A; A → AB so A is a key of R1 → lossless ✅
• Same R into R1(A, B), R2(B, C): common = B; B⁺ = {B} → not a key of either → lossy ❌ (joining back creates spurious tuples).

Spurious-tuple demonstration: R = {(1, x, p), (2, x, q)}. Projecting on (A,B) = {(1,x), (2,x)} and (B,C) = {(x,p), (x,q)}; joining on B gives 4 tuples, including the fake (1, x, q) and (2, x, p).

Numerical 4 — Dependency Preservation Test

R(A, B, C), F = {A → B, B → C}. Decompose into R1(A, B), R2(B, C): A→B lives in R1, B→C lives in R2 → dependency preserving ✅ (and lossless, since B is a key of R2).

Decompose instead into R1(A, B), R2(A, C): B→C cannot be checked in either table → not dependency preserving ❌ (though still lossless).

Numerical 5 — Highest Normal Form of a Relation

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

• D depends on part of the key (B) → partial dependency → only 1NF (not 2NF).
• Fix: R1(A, B, C) and R2(B, D) → both in BCNF.

3NF Synthesis Algorithm (Bernstein) — 4 lines to memorise

1. Find a minimal cover of F.
2. Create one relation for each FD group with the same left side (X → Y becomes R(X, Y)).
3. If no relation contains a candidate key of R, add one relation consisting of a candidate key.
4. Remove any relation that is a subset of another.

Result is always lossless and dependency-preserving — the reason 3NF is the practical target in industry.

Anomalies at a Glance (use in every normalization answer)

---

✍️ Model Answers — Likely Questions

Q1. What is normalization? Discuss 1NF, 2NF and 3NF with examples.

Definition: the process of decomposing relations, guided by functional dependencies, to remove redundancy and insertion/update/deletion anomalies while keeping decompositions lossless.

Answer plan (this earns full marks):

1. Show the UNF StudentCourse table (repeating group).
2. 1NF — atomic values; flatten; list the three anomalies still present.
3. 2NF — remove partial dependencies on (StudentID, CourseID) → Student, Course, Enrollment.
4. 3NF — remove transitive StudentID → Dept → DeptHead → Department table.
5. Summary table: form → removes → example.

Conclusion: normalization trades some join cost for integrity; for read-heavy reporting a controlled denormalization may be justified.

Q2. Distinguish full, partial and transitive dependency.

With key (StudentID, CourseID):

• Full: (StudentID, CourseID) → Grade — needs the whole key.
• Partial: StudentID → StudentName — depends on part of the key (violates 2NF).
• Transitive: StudentID → Dept and Dept → DeptHead, so StudentID → DeptHead via a non-key attribute (violates 3NF).

One-liner to remember: "The key, the whole key, and nothing but the key — so help me Codd." (1NF, 2NF, 3NF respectively).

Q3. Compute a closure and identify all candidate keys.

Use Numerical 1 above: show the "never on RHS" shortcut, compute closures of AB, AC, AD, AE step by step, confirm minimality, state keys = {AB, AC, AD, AE}, then identify prime attributes and the normal form (3NF not BCNF).

Q4. Decompose an unnormalized relation to 3NF/BCNF, naming the anomaly removed at each step.

Follow the UNF → 1NF → 2NF → 3NF → BCNF walkthrough with data tables. At each step write: rule → violating FD → decomposition → anomaly fixed. Finish by checking each final table for lossless join (common attribute is a key) and dependency preservation.

Q5. Differentiate BCNF from 3NF with an example in 3NF but not BCNF.

• 3NF: for every non-trivial X → A, X is a super key or A is prime.
• BCNF: for every non-trivial X → A, X is a super key (no exception).
• Example: StudentTeacher(StudentID, Subject, Teacher) with Teacher → Subject: in 3NF (Subject is prime) but not BCNF (Teacher is not a key). Decompose to Teaches(Teacher, Subject) and Studies(StudentID, Teacher).
• Trade-off: BCNF may lose dependency preservation; 3NF always keeps it. Hence BCNF is stricter, 3NF is safer.

Q6. Explain multivalued dependency and its role in 4NF.

X →→ Y holds when, for each X value, the set of Y values is independent of the other attributes. Example: EmpID →→ Skill and EmpID →→ Language in one table force every skill–language combination (2 skills × 2 languages = 4 rows). 4NF requires that every non-trivial MVD has a super key on its left; fix by splitting into EmpSkill and EmpLanguage (2 + 2 rows). Every FD is also an MVD, so 4NF ⊂ BCNF.

---

⚡ 60-Second Revision

• 1NF atomic · 2NF no partial · 3NF no transitive · BCNF every determinant a key · 4NF no MVD · 5NF no JD.
• Attribute never on RHS ⇒ in every candidate key.
• Lossless if common attributes are a key of one side.
• 3NF: always lossless + dependency-preserving. BCNF: always lossless, not always dependency-preserving.
• Minimal cover: split RHS → drop extraneous LHS → drop redundant FDs.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2017 · Paper-II · Q6(a) · 8 marks

Q. What is normalisation? Discuss 1NF, 2NF and 3NF with example(s).

Ans.

• Normalisation organises tables to remove redundancy and avoid insertion, update and deletion anomalies, by splitting tables according to dependencies.
• 1NF: every attribute holds a single, atomic value (no repeating groups or multi-valued cells). Example: a student with phone numbers "111, 222" in one cell must be split into separate rows.
• 2NF: in 1NF and no partial dependency: every non-key attribute depends on the whole primary key. Example: in Enrol(StudentID, CourseID, StudentName, Grade), StudentName depends only on StudentID. Move it to Student(StudentID, StudentName), keeping Enrol(StudentID, CourseID, Grade).
• 3NF: in 2NF and no transitive dependency: non-key attributes depend only on the key. Example: Employee(EmpID, DeptID, DeptName) becomes Employee(EmpID, DeptID) and Department(DeptID, DeptName).
• BCNF: every determinant is a candidate key.

2026 · Paper-II · Q6 · 20 marks

Q. Normalisation aims to improve schema quality. Discuss how violations of functional and multivalued dependencies lead to structural anomalies. Evaluate whether higher normal forms (3NF, BCNF, 4NF) always benefit large-scale OLTP database systems.

Ans.

• Functional dependency (FD) violations:
  • Partial dependency (violates 2NF): attributes tied to part of a composite key are repeated for every row.
  • Transitive dependency (violates 3NF): facts about a non-key attribute are repeated.
  • Determinant that is not a candidate key (violates BCNF).
  • Anomalies: an update anomaly (a fact stored in many rows must be changed in all), an insertion anomaly (a fact cannot be stored without unrelated data) and a deletion anomaly (deleting a row loses an unrelated fact).
• Multivalued dependency (MVD) violations: if X →→ Y and X →→ Z are independent in the same table, every combination must be stored. Example: CourseTeacherBook(Course, Teacher, Book) where teachers and books are independent. Adding a teacher requires a row for each book. The result is combinatorial redundancy and insert and delete anomalies. 4NF splits it into (Course, Teacher) and (Course, Book).
• Do higher normal forms always benefit large OLTP systems?
  • Benefits: less redundancy and storage, consistent data, simple and fast updates, better integrity. These matter for OLTP, which has many small, concurrent updates.
  • Costs: more tables mean more joins for reads, so read-heavy queries slow down, and the design is more complex. Over-normalisation (BCNF or 4NF with little practical anomaly) may add join cost with little gain. BCNF may lose some dependency preservation.
  • Practice: 3NF (or BCNF) is the usual target for OLTP. 4NF is applied when real independent multivalued facts exist. Selective denormalisation (duplicate stable columns, summary tables, caching) is used for hot read paths, after measuring.
• Verdict: higher normal forms generally help OLTP data integrity and update performance, but not always. The best design balances normalisation with query patterns and performance needs.

MCQs

2024 P-II · Q12. Boyce-Codd Normal Form:

• (A) Addresses a certain type of multivalued dependencies
• (B) Makes sure that data in each column is atomic
• (C) Makes sure that every determinant is a candidate key ✅
• (D) None of these
• Answer: (C).
• Why: a relation is in BCNF if, for every functional dependency X → Y, X is a candidate key (a superkey). Multivalued dependencies are the concern of 4NF, and atomic values are the requirement of 1NF.

2025 P-II · Q9. Which forms are based on the concept of functional dependency?

• (A) 1NF
• (B) 2NF
• (C) 3NF ✅ (best single choice)
• (D) 4NF
• Answer: (C) 3NF (2NF is also correct).
• Why: 2NF removes partial dependencies and 3NF removes transitive dependencies, so both are defined using functional dependencies (as is BCNF). 1NF only requires atomic values, and 4NF is based on multivalued dependencies.
• Note: the question has two valid options, (B) and (C). If a single answer must be chosen, 3NF is the safer pick.