Dependencies, keys, and lossless normalization

Prerequisites: Relations, joins, keys, and sets.

Learning objectives

• Compute attribute closure and candidate keys.
• Identify a dependency that violates BCNF.
• Check a decomposition for lossless reconstruction.

A functional dependency X→Y is a claim about every permitted database state: rows agreeing on attributes X must agree on Y. It is not established by noticing a pattern in today's sample. If an employee belongs to exactly one department, Employee→Department is a business constraint. Department→Office is a separate constraint if each department has one office. Together they imply Employee→Office by transitivity.

For relation R(Employee,Department,Office), the closure of Employee begins with Employee, adds Department using the first dependency, then Office using the second. It contains every attribute, so Employee is a superkey. A candidate key is a superkey with no unnecessary attribute. Department is not a key because several employees can share a department. Write closures step by step rather than treating a familiar column name as proof of uniqueness.

Storing both facts in R repeats an office for every employee in a department. Updating one copy but not another creates a contradictory database state. Inserting a department without employees becomes awkward, and deleting its last employee can accidentally delete the office fact. These update, insertion, and deletion anomalies signal that one row is trying to represent facts with different determinants.

Boyce-Codd normal form requires every nontrivial functional dependency X→Y to have a superkey determinant X. Department→Office violates it here. Decompose into Employment(Employee,Department) and Departments(Department,Office). Their common attribute Department determines all of Departments, making this binary decomposition lossless under the given dependencies. Joining the projections reconstructs exactly the original valid relation, rather than inventing employee-office combinations.

Lossless does not mean every arbitrary split works. For R(A,B,C), decomposing into (A,B) and (B,C) without appropriate dependencies can create spurious rows. Original tuples (a1,b,c1) and (a2,b,c2) project into two pairs on each side; their join yields four tuples, including combinations absent originally. The join has forgotten which A belonged with which C.

Dependency preservation is a separate goal: can each original dependency be enforced using local checks on the decomposed tables, without joining them? BCNF decompositions can sacrifice that property. Third normal form allows certain dependencies involving prime attributes to preserve dependencies while still controlling redundancy. This is a design tradeoff requiring explicit constraints, not a contest to reach the highest named form.

Normalization concerns logical correctness. Query speed, indexes, and materialized summaries are later physical decisions. Deliberate denormalization should identify the duplicated fact, its authoritative owner, and how copies remain synchronized. A schema diagram alone cannot answer those questions; write the dependencies and reconstruction argument alongside it.

Practice problem

For R(Student,Course,Instructor,Room), assume (Student,Course)→Instructor, Course→Instructor, and Instructor→Room. Find a candidate key, identify a BCNF violation, and propose a lossless decomposition into three relations. Explain what must be enforced so that a department can change an instructor’s room without editing every enrollment, and why sample data with only one student per course does not prove Course is a key.

Worked solution

The closure of (Student,Course) contains Instructor and Room, and neither attribute alone determines the other, so it is a candidate key. Course→Instructor and Instructor→Room have non-key determinants in the original relation. Use Enrollment(Student,Course), Teaching(Course,Instructor), and Offices(Instructor,Room). First separate Offices using the Instructor determinant, then Teaching using Course; each binary step is lossless because the shared determinant is a key on the separated side. Enforce uniqueness of Course in Teaching and Instructor in Offices, with appropriate foreign keys. A room update now changes one office fact. One observed student per course is only sample coincidence, not a constraint over future states.

Check your understanding

R(A,B,C) has dependencies A→B and B→C, with no others except their consequences. Which statement follows?

• A is a candidate key, and B→C violates BCNF.
• R is in BCNF because A determines everything.
• Every pair of attributes is a minimal key.
• B is a candidate key.

Explanation

A’s closure is ABC. B determines only BC, so its nontrivial dependency has a non-superkey determinant.

R contains(a 1,b,c1) and(a 2,b,c2). Project to AB and BC, then join on B. With no further constraints, how many rows result?

• 3
• 4
• 1
• 2

Explanation

Each of the two A values combines with each of the two C values, producing two spurious combinations.

Primary reading

• Schema refinement, functional dependencies, and normalization: Carnegie Mellon University

Open the study and save your work →