Integrity Constraints, Functional Dependencies and Normal Forms

Domain, key, entity and referential integrity constraints with cascading actions, update anomalies, functional dependencies and Armstrong's axioms, attribute closure and finding all candidate keys, minimal covers, the normal forms 1NF, 2NF, 3NF and BCNF (and 4NF), lossless-join and dependency-preserving decomposition, and the 3NF synthesis and BCNF decomposition algorithms.

Integrity constraints

Constraints are rules the DBMS enforces on every insert, update and delete.

Constraint	Meaning	SQL
Domain	values come from the attribute's type/range	types, `CHECK (age >= 18)`
Not null	value required	`NOT NULL`
Key (uniqueness)	no two tuples share the key	`PRIMARY KEY`, `UNIQUE`
Entity integrity	primary key attributes are never NULL	implied by `PRIMARY KEY`
Referential integrity	every foreign key value matches an existing referenced key (or is NULL)	`FOREIGN KEY ... REFERENCES`
General assertions / triggers	arbitrary conditions or actions	`CHECK`, `CREATE ASSERTION`, triggers

Referential actions when a referenced row is deleted or its key updated: RESTRICT/NO ACTION (reject), CASCADE (propagate), SET NULL, SET DEFAULT. Inserting a referencing row with a non-existent key is always rejected.

Why normalise? Anomalies

A badly designed table EmpDept(eid, ename, dept, dept_head) repeats dept_head for every employee of a department:

Update anomaly: changing a department head requires updating many rows (or the data becomes inconsistent).
Insertion anomaly: a new department cannot be recorded until it has an employee.
Deletion anomaly: deleting the last employee of a department loses the department's head.

Normalisation removes redundancy by decomposing relations using functional dependencies.

Functional dependencies

$X \to Y$ means: any two tuples that agree on $X$ also agree on $Y$ . It is trivial if $Y \subseteq X$ .

Armstrong's axioms (sound and complete):

Reflexivity: $Y \subseteq X \Rightarrow X \to Y$ .
Augmentation: $X \to Y \Rightarrow XZ \to YZ$ .
Transitivity: $X \to Y,\ Y \to Z \Rightarrow X \to Z$ .

Derived rules: union ( $X \to Y, X \to Z \Rightarrow X \to YZ$ ), decomposition ( $X \to YZ \Rightarrow X \to Y$ ), pseudo-transitivity ( $X \to Y, WY \to Z \Rightarrow WX \to Z$ ).

Attribute closure — the workhorse

$X^+$ = all attributes functionally determined by $X$ :

Python

def closure(X, F):                # F: list of (lhs, rhs) attribute strings
    result = set(X)
    changed = True
    while changed:
        changed = False
        for lhs, rhs in F:
            if set(lhs) <= result and not set(rhs) <= result:
                result |= set(rhs)
                changed = True
    return result

Uses: $X$ is a superkey iff $X^+$ contains all attributes; $X \to Y$ follows from $F$ iff $Y \subseteq X^+$ .

Finding candidate keys

Prime attribute: belongs to some candidate key.

Minimal (canonical) cover

An equivalent set of FDs with single attributes on the right, no extraneous attributes on the left, and no redundant FDs. Steps: split right-hand sides; remove extraneous left attributes (is $B$ in $(X - A)^+$ ?); drop FDs implied by the others.

Normal forms

Form	Requirement	Removes
1NF	atomic values, no repeating groups	multivalued cells
2NF	1NF + no partial dependency of a non-prime attribute on part of a candidate key	redundancy from composite keys
3NF	for every non-trivial $X \to A$ : $X$ is a superkey or $A$ is prime	transitive dependencies
BCNF	for every non-trivial $X \to Y$ : $X$ is a superkey	all FD-based redundancy
4NF	BCNF + every non-trivial multivalued dependency $X \twoheadrightarrow Y$ has $X$ a superkey	independent multivalued facts

BCNF ⊂ 3NF ⊂ 2NF ⊂ 1NF. Shortcuts: if every candidate key is a single attribute, a 1NF relation is automatically in 2NF; if every attribute is prime, the relation is automatically in 3NF; any relation with exactly two attributes is in BCNF.

Decomposition

Replacing $R$ by $R_1, \dots, R_k$ (projections) must satisfy:

Lossless join — joining the pieces gives back exactly $R$ (no spurious tuples). Binary test: $R_1 \cap R_2 \to R_1$ or $R_1 \cap R_2 \to R_2$ (the common attributes form a superkey of one side).

Dependency preservation — every FD can be checked within a single piece: $(F_1 \cup \dots \cup F_k)^+ = F^+$ .

Target	Lossless?	Dependency preserving?
3NF (synthesis from a minimal cover, plus a key relation if needed)	always	always
BCNF (repeatedly split on a violating FD $X \to Y$ into $XY$ and $R - Y + X$ )	always	not always

Integrity Constraints, Functional Dependencies and Normal Forms