Day 50: Relational Database Normalization – From Functional Dependencies to Normal Form Decomposition

Why study today

The series has already covered indexes, transactions and MVCC. Today’s focus moves further forward: how to design a relational table so that data duplication, contradictions and accidental deletions are avoided.

Example: a chaotic enrollment table

A university initially stores all information in one table:

选课总表( 学号, 姓名, 专业号, 专业名, 课程号, 课程名, 教师号, 教师名, 成绩 )

Business rules assumed for the example are:

One student ID maps to one student and one major.

One major code maps to one major name.

One course is taught by one teacher.

One teacher ID maps to one teacher.

A student can select many courses.

A course can be selected by many students.

A student has only one grade for a given course.

From these rules we can write the functional dependencies:

学号 → 姓名, 专业号
专业号 → 专业名
课程号 → 课程名, 教师号
教师号 → 教师名
(学号, 课程号) → 成绩

If the real world allowed multiple teachers per course, additional attributes such as teaching class or semester would be required; the dependencies above would no longer hold.

Relational model terminology

Relation – a two‑dimensional table (e.g., the enrollment table).

Tuple – a row, representing one enrollment record.

Attribute – a column, such as student ID or grade.

Domain – the set of permissible values for an attribute (e.g., grade 0‑100).

Mathematically a relation is a set of tuples, so duplicate rows are not allowed; SQL may return duplicates when DISTINCT is not used.

Keys: superkey, candidate key, primary key

In the enrollment table the attribute set (学号, 课程号) uniquely identifies a row, so it is a superkey. Adding a non‑essential attribute such as 姓名 still yields a superkey, but it is no longer minimal: (学号, 课程号, 姓名) Because the extra attribute does not contribute to uniqueness, (学号, 课程号) is the candidate key. From the candidate key we choose a primary key (the same set in this example).

Finding candidate keys with attribute closure

The closure X⁺ is the set of attributes that can be derived from X using the functional dependencies. To test whether (学号, 课程号) is a candidate key we compute its closure:

学号 → 姓名, 专业号 → 专业名
课程号 → 课程名, 教师号 → 教师名
(学号, 课程号) → 成绩

The closure contains all attributes of the original table, so the set is a superkey. Removing either 学号 or 课程号 makes the closure incomplete, confirming that the set is minimal and therefore a candidate key.

The test consists of two steps:

Check whether the closure covers every attribute.

Check whether any attribute can be removed while still covering all attributes.

Only when both steps succeed do we have a candidate key.

Functional dependencies – definitions and types

A functional dependency X → Y means that any two rows with the same X values must also have the same Y values.

For example, 学号 → 姓名 states that a student ID cannot be associated with two different names.

Important variants:

Full functional dependency : Y depends on the whole of X. Example: (学号, 课程号) → 成绩 – removing either part makes the dependency invalid.

Partial functional dependency : Y depends on only a part of a composite key. Example: 学号 → 姓名 and 课程号 → 课程名 are partial dependencies on the candidate key (学号, 课程号).

Transitive functional dependency : X → Z holds because X → Y and Y → Z. Example: 学号 → 专业号 → 专业名 yields the transitive dependency 学号 → 专业名.

Partial dependencies only appear when a candidate key contains more than one attribute; a single‑attribute candidate key cannot have a partial dependency.

Four anomalies caused by a non‑normalized table

Redundancy : Repeating the same major name or teacher name many times wastes space and can lead to inconsistent copies.

Update anomaly : Changing a major name requires updating every row that stores that name; missing a row creates contradictory data.

Insert anomaly : A new course cannot be entered without at least one student selecting it, because the course information is tied to the enrollment rows.

Delete anomaly : Deleting the last enrollment of a course also removes the course and teacher information.

In the example, deleting a single “enrollment fact” unintentionally deletes the associated “course fact” and “teacher fact”.

Normal forms – what each one fixes

1NF: each cell holds an indivisible value.
2NF: no non‑key attribute depends on only part of a composite key.
3NF: no non‑key attribute is transitively dependent on a key.
BCNF: for every non‑trivial functional dependency, the left side must be a superkey.
4NF: independent multi‑value facts must not be stored in the same table.

1NF

If a column stores multiple phone numbers like 联系电话 = "138xxxx, 139xxxx", it violates 1NF. Splitting into two tables fixes the problem:

学生(学号, 姓名)
学生电话(学号, 电话号码)

2NF

In the original enrollment table, non‑key attributes such as 姓名 and 课程名 depend only on part of the candidate key (学号, 课程号). Decomposing eliminates the partial dependencies:

学生暂表(学号, 姓名, 专业号, 专业名)
课程暂表(课程号, 课程名, 教师号, 教师名)
选课(学号, 课程号, 成绩)

3NF

The temporary student table still has a transitive dependency 学号 → 专业号 → 专业名. Splitting further yields:

学生(学号, 姓名, 专业号)
专业(专业号, 专业名)
课程(课程号, 课程名, 教师号)
教师(教师号, 教师名)
选课(学号, 课程号, 成绩)

BCNF

Consider the relation 授课(学生, 教师, 课程) with dependencies 教师 → 课程 and (学生, 课程) → 教师. The left side 教师 is not a superkey, so the relation violates BCNF. Decomposing gives:

教师课程(教师, 课程)
学生教师(学生, 教师)

BCNF rule: the determinant of any non‑trivial functional dependency must be a superkey.

4NF

When a table mixes independent multi‑value facts, such as an employee’s children and courses, the Cartesian product explodes. Splitting into separate tables removes the violation.

员工子女(员工, 子女)
员工课程(员工, 课程)

Putting the normal‑form checklist on one line

1NF: no multi‑value cells;
2NF: no attribute depends on only part of a composite key;
3NF: no attribute depends transitively on a key;
BCNF: every determinant must be a superkey;
4NF: independent multi‑value facts must be stored separately.

Lossless join and dependency preservation

A decomposition is lossless if natural joins of the sub‑tables reconstruct the original rows without spurious tuples. For a binary decomposition R → R1, R2 a sufficient condition is (R1 ∩ R2) → R1 or (R1 ∩ R2) → R2. Example:

学生(学号, 姓名, 专业号)
专业(专业号, 专业名)

Because 专业号 → 专业名, the join on 专业号 is lossless.

Dependency preservation means every original functional dependency can be enforced by checking constraints within the individual sub‑tables, without needing to join them first. In the final decomposition all original dependencies are preserved in the appropriate tables.

Denormalization – controlled redundancy for performance

After a schema is normalized, queries may require many joins. Introducing selective redundancy (denormalization) can improve read performance. Example from an order system:

订单项(订单号, 商品ID, 成交商品名, 成交单价, 数量)

Storing the product name and price at order time preserves a historical snapshot and avoids extra joins, but it costs extra storage and requires extra logic to keep the snapshot consistent.

Rule of thumb: normalize first, then denormalize only where measured performance gains outweigh the added maintenance cost.

Case‑study exam question and step‑by‑step answer

The exam asks to analyse the problems of the original enrollment table and propose a redesign. The solution follows the same steps presented earlier:

Identify business objects: student, major, course, teacher, enrollment.

Identify the candidate key: (学号, 课程号).

Write functional dependencies.

Locate anomalies (partial, transitive, redundancy, update/insert/delete).

Normalize into five tables (student, major, course, teacher, enrollment).

Check lossless join (foreign‑key relationships) and dependency preservation.

For high‑frequency statistics (e.g., daily enrollment per major) create a materialized summary table or view, updated by triggers or batch jobs.

Quick‑talk (three‑minute) summary

Relation = table, Tuple = row, Attribute = column, Domain = allowed values.

Superkey uniquely identifies a row; candidate key is a minimal superkey; primary key is the chosen candidate.

Use attribute closure to test candidate keys.

Full dependency = depends on whole key; partial = depends on part of a composite key; transitive = depends via another non‑key attribute.

Four anomalies: redundancy, update, insert, delete.

1NF eliminates multi‑value cells; 2NF removes partial dependencies; 3NF removes transitive dependencies; BCNF forces every determinant to be a superkey.

Lossless join guarantees data can be recombined; dependency preservation guarantees constraints stay enforceable locally.

Denormalization is a deliberate, performance‑driven trade‑off that adds controlled redundancy.