Skip to content
Information Systems

Normalisation: functional dependencies, BCNF and third normal form

Update, insertion and deletion anomalies, functional dependencies and Armstrong's axioms, closure and the key test, Heath's theorem proved, BCNF, 3NF and denormalisation.

4 min read 0 comments

A table that mixes information about different objects works until it has to be modified: then repeated data must be updated everywhere, and sooner or later someone forgets. Normalisation is the theory that says when a schema is well made and how to fix it. In this lesson we look at anomalies with an example, functional dependencies and Armstrong’s axioms, the closure of a set of attributes and the key test, Heath’s theorem with proof, Boyce-Codd normal form and third normal form.

Anomalies

Consider the table Exams(number, name, code, title, mark), which records exams with the student’s name and the course title. A student’s name appears in every one of their exams, a course’s title in every exam of that course. Three anomalies arise:

  • update: to correct a course title hundreds of rows must be modified, and if one is skipped the data become inconsistent;
  • insertion: a new course cannot be recorded until someone has taken its exam, because the key (number, code) requires a student number;
  • deletion: deleting the last exam of a course also loses its title.

The cause is that the table represents three concepts (students, courses, exams) in one. The theory of functional dependencies makes this precise.

Functional dependencies

Given two sets of attributes X and Y of a relation, X \to Y (X determines Y) if two tuples equal on X are always equal on Y too. In the example: number → name, code → title, (number, code) → mark. Functional dependencies are rules of the real world, like the cardinalities of the E-R model, and a key K is exactly a set of attributes such that K \to all attributes, minimally.

From some dependencies others are deduced with Armstrong’s axioms:

  • reflexivity: if Y \subseteq X, then X \to Y;
  • augmentation: if X \to Y, then XZ \to YZ;
  • transitivity: if X \to Y and Y \to Z, then X \to Z.

They are sound (they deduce only true dependencies) and complete (they deduce all those following from the initial ones).

Closure and the key test

The closure X^+ of a set of attributes is the set of all attributes determined by X. It is computed starting from X^+ = X and adding, while possible, the right-hand side of every dependency A \to B whose left-hand side A is already contained in X^+. X is a superkey if and only if X^+ contains all the attributes.

In the example, \{number, code\}^+: start from {number, code}, add name (from number), title (from code), mark (from the third dependency): all attributes, so it is a superkey, and since neither number nor code alone suffices, it is a key.

Decomposing without losing information

Normalising means decomposing a relation into smaller relations. But the decomposition must be lossless: putting the parts back together with the natural join must give exactly the original relation, with no spurious tuples.

Lossless decomposition of a relation guided by a functional dependency
The relation with attributes X, Y, Z satisfies X determines Y. Split into the two relations with attributes X, Y and X, Z, it is reconstructed exactly by joining on X: each value of X corresponds to a single value of Y, so no false combinations arise.

Theorem (Heath). If a relation R(X, Y, Z) satisfies X \to Y, then the decomposition into R_1 = \pi_{XY}(R) and R_2 = \pi_{XZ}(R) is lossless: R_1 \bowtie R_2 = R.

Proof. *R \subseteq R_1 \bowtie R_2.* Every tuple (x, y, z) of R has projection (x, y) in R_1 and (x, z) in R_2, which combine again into (x, y, z). *R_1 \bowtie R_2 \subseteq R.* Let (x, y, z) be a tuple of the join. It comes from (x, y) \in R_1, projection of a tuple (x, y, z_1) of R, and from (x, z) \in R_2, projection of a tuple (x, y_2, z) of R. The two tuples of R are equal on X, so by the dependency X \to Y they are equal on Y: y_2 = y. Then (x, y_2, z) = (x, y, z) belongs to R. ∎

Without the dependency the decomposition can create false tuples: if x_1 corresponded to both y_1 and y_2, the join would combine every y with every z of x_1, even those never seen together.

Normal forms

A relation is in Boyce-Codd normal form (BCNF) if, for every non-trivial dependency X \to Y, X is a superkey. In words: every fact the table records depends on the key, the whole key and nothing else. The Exams table is not in BCNF, because number → name and number is not a superkey. Applying Heath’s theorem twice gives Students(number, name), Courses(code, title) and Exams(number, code, mark): all in BCNF, and the anomalies disappear. It is the same schema that E-R design would have produced directly (lesson on the E-R model).

Decomposition into BCNF is always possible without loss, but sometimes it loses a dependency: it can no longer be checked within a single table. The typical case: in Lessons(student, subject, teacher), each teacher teaches a single subject (teacher → subject) and each student has a single teacher per subject ((student, subject) → teacher). Bringing it to BCNF separates (teacher, subject) from (student, teacher), and the rule linking student and subject to the teacher can no longer be checked in one table. Third normal form (3NF) is somewhat more permissive: it allows X \to A even if X is not a superkey, provided A is part of a key. It can be proved that every schema can always be brought into 3NF losslessly while preserving all dependencies.

In practice one normalises up to 3NF or BCNF, and denormalises deliberately only where read speed is needed, as in data warehouses (lesson on distributed data), accepting redundancy in exchange for fewer joins.

Related articles

Subscribe
Notify of
guest
0 Comments
Oldest
Newest Most Voted
0
Would love your thoughts, please comment.x
()
x