Integrity Constraints

A relation schema specifies attribute names and domains, but by itself it permits any set of tuples over those domains, including tuples that make no sense in the application. An integrity constraint is a predicate over database states, declared once in the schema, that the DBMS checks and enforces on every insertion, deletion, and update. A database instance is called legal or consistent if it satisfies all declared constraints; the DBMS's job is to guarantee that only legal instances ever exist, by rejecting or repairing any operation that would produce an illegal one. Four constraint families form the foundation of relational integrity. A domain constraint restricts an attribute to a specific set of atomic values — an integer range, a fixed-length string, an enumerated set, or a `NOT NULL` requirement — and is checked independently, tuple by tuple, attribute by attribute. A key constraint (or uniqueness constraint) designates one or more attribute sets, called candidate keys, such that no two distinct tuples in the relation may agree on all attributes of that set; one candidate key is designated the primary key. Entity integrity is the rule that no attribute participating in the primary key may be `NULL` — because a `NULL` primary key value cannot uniquely identify a tuple, defeating the very purpose of a key. Referential integrity, enforced through foreign keys, requires that whenever a relation $R_1$ has an attribute set $\alpha$ declared as a foreign key referencing a candidate key of relation $R_2$, every non-null value of $\alpha$ in $R_1$ must appear as a value of that candidate key in $R_2$. These four families interact in a strict hierarchy of scope. Domain constraints are the narrowest, checked per-attribute-value. Key constraints operate within a single relation, comparing tuples against each other. Entity integrity is a special case tying keys to nullability. Referential integrity is the widest in scope: it is the only one of the four that spans two relations, and it is precisely the mechanism that lets a normalized schema — split into many small relations by Normalization Motivation and Anomalies — be reassembled correctly via joins, because the foreign key tells the query processor exactly which tuples in one relation "belong with" which tuples in another.

Domain constraints. A domain is declared with a base type (`INTEGER`, `VARCHAR(n)`, `DATE`, …) optionally refined by a `CHECK` clause and a nullability rule. The check is purely local: for a single attribute value $v$ being written into attribute $A$ of relation $R$, the DBMS evaluates the domain predicate $D_A(v)$ and rejects the write if it is false. Because the check needs no access to other tuples or other relations, it costs $O(1)$ per value (or $O(\text{length of value})$ for string-pattern checks) and is applied to every attribute of every inserted or updated tuple.

Key constraints. A candidate key $K \subseteq R$ requires: (1) uniqueness — no two distinct tuples $t_1 \neq t_2$ in any legal instance of $R$ have $t_1[K] = t_2[K]$; and (2) irreducibility (minimality) — no proper subset of $K$ also satisfies uniqueness. Uniqueness is what the DBMS actively enforces on writes; minimality is a design property checked once, at schema-creation time, by the designer (typically derived from functional-dependency analysis, foreshadowing normalization). Enforcement uses an index (commonly a B+-tree or hash index automatically built on $K$) so that a new tuple's key value can be looked up in $O(\log n)$ or $O(1)$ average time rather than scanning all $n$ existing tuples.

Entity integrity. This is a nullability restriction layered on top of the primary key: for the designated primary key $K_p$, every attribute $A \in K_p$ must be non-null in every tuple. It is checked at the same time and by the same mechanism as the key-uniqueness check, since a `NULL` value would need special-case comparison semantics (`NULL` is not equal to `NULL` under standard three-valued logic) that would make uniqueness itself ambiguous.

Referential integrity. Let $R_1$ (the referencing relation) declare a foreign key $\alpha$ that references a candidate key $\beta$ of $R_2$ (the referenced relation). The constraint requires:

in relational-algebra terms: every non-null projection of $R_1$ onto $\alpha$ must appear among the projections of $R_2$ onto $\beta$. This is checked on three kinds of operations: insertion into $R_1$ (the new $\alpha$ value must exist in $R_2$, or be null), update of $\alpha$ in $R_1$ (same check), and, crucially, deletion from $R_2$ or update of $\beta$ in $R_2$ — because removing or changing a referenced key value could orphan tuples in $R_1$ that still point to it. This last case is where a violation policy must be chosen: `NO ACTION`/`RESTRICT` (reject the delete/update if referencing tuples exist), `CASCADE` (propagate the delete/update into $R_1$), or `SET NULL` / `SET DEFAULT` (null out or default the referencing attribute in $R_1$).

Step-by-step enforcement algorithm

``` function VALIDATE_WRITE(operation, tuple_or_key, relation R):

# operation ∈ {INSERT, DELETE, UPDATE} if operation is INSERT or UPDATE: for each attribute A of R: v = new_value(tuple_or_key, A) if not DOMAIN_CHECK(A, v): reject "domain constraint violated on attribute A" for each attribute A in PrimaryKey(R): if new_value(tuple_or_key, A) is NULL: reject "entity integrity violated: primary key attribute A is null" for each candidate key K of R: if EXISTS tuple t' in R (t' != tuple_or_key) with t'[K] = tuple_or_key[K]: reject "key constraint violated: duplicate key value" for each foreign key alpha of R referencing (beta, R2): v = tuple_or_key[alpha] if v is not NULL and v NOT IN Project_beta(R2): reject "referential integrity violated: no matching key in R2" commit tuple if operation is DELETE or (UPDATE and key attributes changed): old_key_value = tuple_or_key[PrimaryKey(R)] # or the referenced candidate key for each relation R1 with foreign key referencing R: matches = { t1 in R1 : t1[foreign_key] = old_key_value } if matches is not empty: switch POLICY(R1, R): case RESTRICT: reject "referential integrity violated: referencing tuples exist" case CASCADE: if operation is DELETE: for t1 in matches: DELETE t1 from R1 # recursive call else: # UPDATE for t1 in matches: UPDATE t1.foreign_key = new_key_value case SET_NULL: for t1 in matches: UPDATE t1.foreign_key = NULL commit delete/update ``` The order matters: domain checks run first because they are the cheapest and most local (fail fast on a malformed value before doing any lookup). Key and entity-integrity checks run next since they only require a lookup within $R$ itself. Referential-integrity checks run last for inserts/updates because they require touching a second relation, and the deletion-side checks recurse across the whole graph of foreign-key dependencies, potentially touching many relations in a single `CASCADE`.

Domain constraint checking costs $O(1)$ time per attribute value for range/type checks, or $O(m)$ for a pattern/regex check of length $m$; space overhead is $O(1)$ beyond storing the value itself, since no auxiliary structure is needed. This is checked on every insert and every update to that attribute — $O(a)$ total per tuple write, where $a$ is the number of constrained attributes.

Key constraint checking, done naively, would require scanning all $n$ existing tuples to look for a duplicate — $O(n)$ per write. Real systems avoid this by maintaining an index on every declared key: a B+-tree gives $O(\log_B n)$ I/Os for the uniqueness lookup ($B$ the tree fan-out), and a hash index gives expected $O(1)$. Space cost is the index itself, typically $O(n)$ additional storage. This is a direct efficiency argument for why keys are always backed by indexes in practice, not just a modeling nicety.

Entity integrity adds no asymptotic cost — it is a single extra `NULL` test folded into the same tuple-write pass that checks key uniqueness, still $O(1)$ per attribute.

Referential integrity on insert/update into the referencing relation $R_1$ requires one lookup of the foreign-key value in the referenced relation's key index: $O(\log_B n_2)$ with a B+-tree over $R_2$'s $n_2$ tuples, again assuming (as SQL requires) that the referenced attribute set is indexed because it must be a candidate key of $R_2$. On delete/update of the referenced relation $R_2$, the DBMS must find all matching tuples in $R_1$; this requires an index on the foreign-key attribute in $R_1$ (not mandated by the relational model but essential in practice), giving $O(\log_B n_1 + k)$ where $k$ is the number of matching tuples, versus $O(n_1)$ with a full scan. `CASCADE` deletes can recurse through a chain of foreign keys; if the reference graph has depth $d$ and fan-out $f$ at each level, cascading touches up to $O(f^d)$ tuples in the worst case, which is why cyclic or deep cascade chains are a known operational hazard (see pitfalls below).

Correctness argument. The claim to prove is: if every write operation is validated by the algorithm above before being committed, then every reachable database state is legal (satisfies domain, key, entity-integrity, and referential-integrity constraints). This is an inductive invariant argument over the sequence of committed operations.

• Base case. The empty database (no tuples) vacuously satisfies all four constraint types, since there are no tuples to violate uniqueness, no null primary keys to find, and no dangling foreign-key values to detect.
• Inductive step. Assume the database is legal after $k$ committed operations. Consider operation $k+1$. The algorithm checks, before committing, exactly the predicate that defines each constraint: domain membership for every new value, non-null-ness for every primary-key attribute, absence of a duplicate key value among existing plus new tuples, and (for inserts/updates) presence of the foreign-key value in the referenced key's projection, or (for deletes/updates of the referenced side) absence of any orphaned referencing tuple once the chosen policy is applied. Since the pre-state was legal by the inductive hypothesis, and the algorithm only permits the operation to commit when the post-state predicate holds, the post-state is legal.
• Referential integrity's cross-relation subtlety is handled correctly because the algorithm treats `CASCADE`/`SET NULL` as part of the same atomic operation: the referencing tuples are fixed up (deleted, updated, or nulled) before the operation is considered committed, so the post-state never transiently violates the constraint from the perspective of any query that runs after the transaction completes. This is precisely why the DBMS must implement cascades as part of the same transaction as the triggering delete/update, not as an asynchronous cleanup — an important tie-in to Transactions and atomicity.

Honest tradeoffs. Enforcing constraints is not free: every insert pays the cost of index lookups for each key and each foreign key, and `CASCADE` chains can turn one delete into an unbounded cascade of deletes across the whole schema, which is a real risk to availability and to unintended data loss. Some high-throughput systems deliberately relax enforcement — deferring checks to end-of-transaction (`DEFERRABLE` constraints), or dropping foreign keys altogether in favor of application-level checks — trading correctness guarantees for write latency. This tradeoff is a live design decision in large-scale systems and is discussed further under Normalization Motivation and Anomalies, since denormalized schemas often shed foreign keys precisely to avoid this overhead.

Consider a simplified banking schema: ``` Branch(branch_name PK, branch_city, assets) Customer(customer_id PK, ssn UNIQUE, name NOT NULL) Account(account_number PK, branch_name FK→Branch, balance CHECK(balance >= 0)) Depositor(customer_id FK→Customer, account_number FK→Account, PRIMARY KEY(customer_id, account_number)) ``` Trace the following sequence of operations, showing which constraint (if any) is checked and whether the write is accepted:

Step 3 shows referential integrity failing in the insert direction (child references a non-existent parent). Steps 8–10 show the same underlying deletion attempt behaving completely differently depending on the declared violation policy — the constraint is fixed, but its enforcement consequence is a schema-design choice. Step 9's cascade illustrates the recursive fan-out from the complexity discussion: deleting one `Branch` tuple transitively removed a tuple in `Account` and a tuple in `Depositor`, two "hops" down the reference graph.

Integrity constraints are inseparable from the relational model itself: E. F. Codd introduced the notion that a database schema should carry declarative rules — checked by the system, not by application code — as a core part of his 1970 relational model, and he sharpened this further in later work explicitly proposing entity integrity and referential integrity as the two fundamental rules every relational database must obey.

Every production relational database — PostgreSQL, MySQL/InnoDB, Oracle, SQL Server, SQLite — implements domain, key, entity-integrity, and referential-integrity constraints as core engine features, typically backed by B+-tree indexes for efficient enforcement. Application frameworks (Django ORM, Rails ActiveRecord, Hibernate/JPA) expose these constraints as schema annotations (`unique=True`, `null=False`, `ForeignKey(on_delete=CASCADE)`) that generate the underlying SQL `DDL`. Data warehouses and ETL pipelines rely on referential-integrity checks to catch upstream data-quality problems before a broken foreign key propagates into a report. Financial and healthcare systems in particular depend on entity integrity and referential integrity as an automated, unbypassable line of defense — an accounting system simply cannot allow a debit against a nonexistent account, and a hospital system cannot allow a prescription record to reference a patient ID that was never created. These same constraints are exactly what makes it possible to reconstruct a fully normalized schema — split across many relations by Normalization Motivation and Anomalies — back into a coherent whole via joins guided by foreign keys, and they are the concrete artifact that Mapping ER to Relations produces when it turns entity-relationship diagrams into working table definitions.

Ask the tutor: How would you redesign the violation policy for a schema where a `CASCADE` delete on `Customer` currently risks wiping out years of `Order` history?