Integrity Constraints & Normal Forms

Normalisation looks like a list of rules to memorise, and understanding why it is not saves a great deal of effort.

The organising fact is that every update anomaly traces to a functional dependency whose determinant is not a key. If a non-key attribute determines something, that something is stored redundantly, once per row sharing the determinant, and the copies can disagree.

Each normal form is therefore a statement about which dependencies are permitted to exist, and the forms get stronger by permitting fewer of them. Boyce-Codd normal form is the limiting case: every determinant must be a superkey.

The second organising fact is that decomposition must not lose information, and the test for that is purely mechanical. A binary decomposition is lossless exactly when the shared attributes determine one of the two halves.

The third is a trade-off that cannot be escaped. Third normal form is always achievable with both losslessness and dependency preservation. Boyce-Codd normal form is always achievable losslessly, but sometimes only by giving up a dependency.

1. Functional Dependencies

A functional dependency $X\to Y$ says that any two tuples agreeing on $X$ must agree on $Y$.

It is a statement about every legal instance, not about the rows currently present. A dependency that happens to hold in the sample data is not necessarily a dependency of the schema.

A trivial dependency has $Y$ contained in $X$ and holds automatically.

Armstrong's axioms are sound and complete, meaning they derive exactly the dependencies logically implied by a given set.

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$.

Three derived rules save time. Union combines $X\to Y$ and $X\to Z$ into $X\to YZ$. Decomposition splits $X\to YZ$ into $X\to Y$ and $X\to Z$. Pseudotransitivity turns $X\to Y$ and $WY\to Z$ into $WX\to Z$.

Decomposition applies only to the right side. From $XY\to Z$ one may not conclude $X\to Z$, and assuming otherwise is the single most common error in this topic.

2. Attribute Closure and Candidate Keys

The closure $X^{+}$ is the set of all attributes functionally determined by $X$.

The algorithm is simple. Start with $X$. Repeatedly, if some dependency's left side is contained in the current set, add its right side. Stop when nothing changes.

$X$ is a superkey exactly when $X^{+}$ contains every attribute of the relation.

Finding candidate keys uses two shortcuts that turn a search into an inspection.

Any attribute appearing on no right side must belong to every candidate key, because nothing else can determine it.

Any attribute appearing on no left side and on some right side belongs to no candidate key, because it determines nothing.

The procedure is therefore: collect the attributes that must be in every key, take their closure, and if that is everything, it is the unique candidate key. Otherwise extend it with one attribute at a time from the remaining pool.

A prime attribute is one belonging to some candidate key. Non-prime attributes are the ones normalisation is mostly about.

3. Canonical Cover

A canonical cover is a minimal set of dependencies equivalent to the original.

Three conditions define it. Every right side is a single attribute. No dependency is redundant, meaning removing it changes the closure of nothing. No left side has a redundant attribute.

The computation proceeds in that order. Split all right sides. Then, for each dependency, test whether its left side still determines its right side without it. Then, for each left side attribute, test whether it can be dropped.

Order matters and the result is not unique, so different valid canonical covers exist for the same set, and an exam answer is judged on the checks rather than on matching a particular list.

The canonical cover is what the 3NF synthesis algorithm consumes, which is why it is worth computing correctly.

4. Anomalies and the Normal Forms

Three anomalies motivate the whole subject.

Insertion anomaly: a fact cannot be recorded because another, unrelated fact is unknown.

Deletion anomaly: removing one fact silently removes another.

Update anomaly: a fact stored in many rows must be changed in all of them, and a partial update leaves the database inconsistent.

First normal form requires atomic attribute values, with no repeating groups or nested relations. It is a condition on the data model rather than on dependencies.

Second normal form forbids a partial dependency, meaning a non-prime attribute determined by a proper subset of some candidate key. It matters only when a candidate key is composite.

Third normal form requires that for every non-trivial dependency $X\to A$, either $X$ is a superkey or $A$ is prime.

The second clause is what makes 3NF weaker than BCNF, and it exists precisely so that dependency preservation is always achievable.

Boyce-Codd normal form requires that for every non-trivial dependency $X\to A$, $X$ is a superkey. There is no escape clause.

A relation with only two attributes is always in BCNF, which is a useful sanity check.

5. Decomposition

A decomposition is lossless if joining the pieces recovers exactly the original relation, with no spurious tuples.

For a binary decomposition into $R_1$ and $R_2$, the test is that $R_1\cap R_2\to R_1$ or $R_1\cap R_2\to R_2$.

In words: the shared attributes must be a key of at least one piece.

Dependency preservation asks whether every original dependency can be checked on a single piece, without a join.

The union of the projected dependency sets must be equivalent to the original set, which is tested by checking each original dependency against the closure computed from the union.

Losing a dependency is not a correctness failure but an enforcement cost. The constraint still holds logically; it simply cannot be verified without joining, which is expensive enough that systems typically stop enforcing it.

The 3NF synthesis algorithm builds one relation per dependency in the canonical cover, adds a relation containing a candidate key if none of the pieces contains one, and removes any relation contained in another. It guarantees 3NF, losslessness and dependency preservation together.

BCNF decomposition is analytical rather than synthetic. Find a violating dependency $X\to Y$, split the relation into $XY$ and $X$ plus the remaining attributes, and repeat. It guarantees losslessness but not preservation.

6. Multivalued Dependencies and 4NF

A multivalued dependency, written $X$ double-arrow $Y$, says that the set of $Y$ values associated with an $X$ value is independent of the remaining attributes.

It captures redundancy that no functional dependency can. A relation recording a course's instructors and its textbooks, where any instructor may use any textbook, must store every instructor-textbook pair, and no functional dependency is violated.

Every functional dependency is a multivalued dependency, but not conversely.

Fourth normal form requires that for every non-trivial multivalued dependency $X$ double-arrow $Y$, $X$ is a superkey.

The fix is the same shape as before: split the relation so each independent set lives with its determinant.

Fifth normal form, or project-join normal form, handles join dependencies that only a decomposition into three or more pieces resolves, and appears rarely in examinations.

Constraints the Schema Enforces Directly

Normalisation removes redundancy; declared constraints enforce validity, and the two are separate concerns that the chapter title joins.

A domain constraint restricts an attribute's permitted values, either through its declared type or through a CHECK clause on the column.

A key constraint declares uniqueness, and a primary key adds the prohibition on nulls that entity integrity requires.

A referential constraint declares a foreign key and specifies what happens on delete or update: cascade, set null, or restrict.

An assertion states a condition over the whole database rather than one table, and is the only declarative way to express constraints spanning relations, though few systems implement it, leaving triggers as the practical mechanism.

7. Worked Examples

Example 1. Find all candidate keys of $R(A,B,C,D,E)$ with dependencies $A\to BC$, $CD\to E$, $B\to D$, $E\to A$.

First classify the attributes.

Right sides contain $B$, $C$, $E$, $D$ and $A$. Every attribute appears on some right side, so no attribute is forced into every key by that test.

Left sides contain $A$, $C$, $D$, $B$ and $E$, so every attribute appears on some left side too, and none is excluded.

Both shortcuts fail, so compute closures of single attributes.

$A^{+}$: start with $A$; add $BC$ from $A\to BC$; add $D$ from $B\to D$; now $CD$ is present so add $E$. The closure is $ABCDE$, so $A$ is a candidate key.

$B^{+}$: $B$, then $D$ from $B\to D$. That is $BD$ only, so $B$ is not a key.

$E^{+}$: $E$, then $A$ from $E\to A$, then everything $A$ gives. The closure is $ABCDE$, so $E$ is a candidate key.

$C^{+}$ is just $C$ and $D^{+}$ is just $D$.

Now try pairs involving $B$, $C$ and $D$.

$C{D}^{+}$: $CD$, add $E$, then $A$, then $BC$. That is everything, so $CD$ is a candidate key.

$B{C}^{+}$: $BC$, add $D$ from $B\to D$, now $CD$ gives $E$, then $A$. Everything, so $BC$ is a candidate key.

$B{D}^{+}$ is $BD$ only. Not a key.

Check minimality: $CD$ and $BC$ are both minimal since no single attribute among them is a key.

The candidate keys are $A$, $E$, $BC$ and $CD$, and the prime attributes are $A$, $B$, $C$, $D$ and $E$, which is all of them.

Example 2. Determine the highest normal form of that relation.

Every attribute is prime, which was the conclusion above.

Check 3NF. The condition is that for each dependency $X\to A$, either $X$ is a superkey or $A$ is prime.

$A\to BC$: $A$ is a candidate key, so this passes on the first clause.

$CD\to E$: $CD$ is a candidate key, passes.

$E\to A$: $E$ is a candidate key, passes.

$B\to D$: $B$ is not a superkey, since $B^{+}$ is only $BD$. But $D$ is prime, being part of $CD$. So it passes on the second clause.

The relation is in 3NF.

Check BCNF. Every determinant must be a superkey, with no escape clause.

$B\to D$ violates it, since $B$ is not a superkey.

So the relation is in 3NF but not BCNF, which is exactly the situation the second clause of 3NF was designed to permit.

Example 3. Test whether decomposing $R(A,B,C,D)$ with $A\to B$ and $C\to D$ into $R_1(A,B)$ and $R_2(C,D)$ is lossless.

Compute the shared attributes. $R_1\cap R_2$ is empty.

The test requires the intersection to determine one of the halves. An empty set determines only attributes that everything determines, which here is nothing.

The decomposition is lossy.

A concrete counterexample makes it vivid. Suppose $R$ holds two tuples, $(a_1,b_1,c_1,d_1)$ and $(a_2,b_2,c_2,d_2)$.

$R_1$ holds $(a_1,b_1)$ and $(a_2,b_2)$. $R_2$ holds $(c_1,d_1)$ and $(c_2,d_2)$.

Their natural join, with no common attribute, is a Cartesian product giving four tuples, two of which never existed.

The repair is to include a connecting attribute. Decomposing into $R_1(A,B)$ and $R_2(A,C,D)$ gives intersection $A$, and since $A\to B$ means $A$ determines all of $R_1$, the decomposition is lossless.

Example 4. Decompose $R(A,B,C)$ with $AB\to C$ and $C\to B$ into BCNF, and show which dependency is lost.

First find the candidate keys.

$A{B}^{+}$ is $ABC$, so $AB$ is a key. $A{C}^{+}$: $AC$, add $B$ from $C\to B$, giving $ABC$, so $AC$ is a key.

$A^{+}$ is $A$, $B^{+}$ is $B$, $C^{+}$ is $BC$. So the candidate keys are $AB$ and $AC$, and the prime attributes are $A$, $B$ and $C$.

Check 3NF. $AB\to C$ has a superkey determinant. $C\to B$ has a non-superkey determinant, but $B$ is prime. So the relation is in 3NF.

Check BCNF. $C\to B$ violates it, since $C^{+}$ is $BC$, not everything.

Decompose on the violating dependency. Put $C$ and its closure together as $R_1(C,B)$, and keep $C$ with the remaining attributes as $R_2(A,C)$.

Verify losslessness. The intersection is $C$, and $C\to B$ means $C$ determines all of $R_1$. Lossless.

Now check dependency preservation.

$C\to B$ is checkable on $R_1$ alone.

$AB\to C$ is checkable on neither. $R_1$ lacks $A$ and $R_2$ lacks $B$, so verifying it requires joining the two pieces.

The dependency is lost.

This is the standard illustration that BCNF and dependency preservation can conflict, and no other BCNF decomposition of this relation preserves it either.

The practical consequence: a system using this decomposition cannot enforce $AB\to C$ cheaply, so two rows could be inserted that jointly violate it, and only a periodic join would detect the problem. Designers often stop at 3NF for exactly this reason.

Example 5. Compute a canonical cover for $A\to BC$, $B\to C$, $A\to B$, $AB\to C$.

Step one: make all right sides single attributes.

This gives $A\to B$, $A\to C$, $B\to C$, $A\to B$ again, and $AB\to C$.

Removing the literal duplicate leaves $A\to B$, $A\to C$, $B\to C$, $AB\to C$.

Step two: remove redundant attributes from left sides.

Consider $AB\to C$. Is $B$ redundant? Compute $A^{+}$ using the current set: $A$, then $B$, then $C$. Since $A^{+}$ contains $C$, $B$ is redundant and the dependency becomes $A\to C$.

That duplicates an existing dependency, so the set is now $A\to B$, $A\to C$, $B\to C$.

Step three: remove redundant dependencies.

Test $A\to C$. Remove it and compute $A^{+}$ from $\{A\to B,B\to C\}$: $A$, then $B$, then $C$. $C$ is still reachable, so $A\to C$ is redundant.

Remove it, leaving $A\to B$, $B\to C$.

Test $A\to B$. Removing it leaves only $B\to C$, and $A^{+}$ would be just $A$. Not redundant, so keep it.

Test $B\to C$. Removing it leaves only $A\to B$, and $B^{+}$ would be just $B$. Not redundant, so keep it.

The canonical cover is $\{A\to B,B\to C\}$.

Example 6. A relation Course(cid, instructor, textbook) records that any instructor of a course may use any textbook of that course. Identify the dependency and normalise.

No functional dependency is violated. The key is all three attributes, since no attribute determines any other.

The relation is therefore in BCNF, trivially, because the only determinant is the full key.

Yet the redundancy is obvious. A course with 3 instructors and 4 textbooks needs 12 rows, and adding a fifth textbook requires 3 new rows rather than 1.

The dependency present is multivalued. Course double-arrow instructor holds, because the set of instructors for a course does not depend on which textbook the row mentions.

Course double-arrow textbook holds symmetrically, and in fact the two always come in pairs within a relation.

4NF is violated, since cid is not a superkey.

Decompose into CourseInstructor(cid, instructor) and CourseTextbook(cid, textbook).

Now the course needs 3 plus 4, which is 7 rows instead of 12, and adding a textbook costs exactly one row.

The decomposition is lossless because the intersection cid multidetermines each half, which is the multivalued analogue of the functional test.

The general lesson is that BCNF is not the end of the story. A relation can satisfy every functional dependency requirement and still store the cross product of two independent facts.

Summary

Every anomaly traces to a dependency whose determinant is not a key, and each normal form restricts which dependencies may exist.

A functional dependency constrains every legal instance, not just the current rows. Armstrong's axioms are reflexivity, augmentation and transitivity, and are sound and complete. Decomposition applies to right sides only.

Attribute closure decides superkeys. An attribute on no right side is in every candidate key; one on no left side but some right side is in none.

A canonical cover has single-attribute right sides, no redundant dependency and no redundant left-side attribute, and it is not unique.

1NF requires atomic values. 2NF forbids partial dependencies and matters only with composite keys. 3NF requires each determinant to be a superkey or each determined attribute to be prime. BCNF drops the second clause.

A binary decomposition is lossless exactly when the intersection determines one of the halves. Dependency preservation asks whether every dependency is checkable without a join.

3NF synthesis from a canonical cover gives 3NF, losslessness and preservation together. BCNF decomposition gives losslessness but may lose a dependency, and the classic example is $R(A,B,C)$ with $AB\to C$ and $C\to B$.

Multivalued dependencies capture redundancy no functional dependency can, and 4NF requires their determinants to be superkeys. A relation can be in BCNF and still store a cross product of independent facts.

Separately from normalisation, the schema declares domain, key and referential constraints directly, while conditions spanning several relations need an assertion or, in practice, a trigger.