The Relational Model

A relation is defined over a set of attributes $A_1, A_2, \ldots, A_n$, each attribute $A_i$ having an associated domain $D_i$ — the set of legal atomic values that attribute may take (e.g., integers, strings of length ≤ 20, dates). Formally, a relation $r$ is a subset of the Cartesian product of the domains:

Each element of this subset is a tuple $t = (v_1, v_2, \ldots, v_n)$, where $v_i \in D_i$ is the value of attribute $A_i$ in that tuple. Because $r$ is a set in the mathematical sense, two important consequences follow immediately: tuples are unordered (there is no "first row"), and there are no duplicate tuples (a set cannot contain the same element twice). This is a sharp, deliberate departure from a spreadsheet or a programming array, where row order and duplication are both meaningful. It is essential to separate two related but distinct notions. The relation schema specifies the structure: the relation's name, its attributes, and each attribute's domain — for example, `Student(ID: integer, name: varchar(30), dept: varchar(20), tot_cred: integer)`. The relation instance is the actual content at a given point in time — the current set of tuples satisfying that schema. A schema is defined once (via `CREATE TABLE` in SQL) and remains largely stable, while the instance changes constantly as rows are inserted, updated, and deleted. Confusing schema with instance is a common early mistake: the schema is the type, the instance is a value of that type. Each attribute must be atomic, meaning the domain contains indivisible values — a single integer, a single string — not sets, lists, or nested tuples. This atomicity requirement (part of what is informally called first normal form) is what makes relations simple to reason about mathematically and simple for a query language to manipulate uniformly: every operation on a relation produces another relation with the same kind of structure, which is what allows relational operators to be composed freely. A collection of relation schemas defines a relational database schema; the corresponding collection of instances, at some moment, is a relational database instance — the full state of the database.

The relational model is not a single algorithm but a representational discipline: any real-world entity or relationship is modeled as one or more relations, and every operation on data is expressed as an operation that maps relations to relations. The "mechanism" is best understood as the discipline of building and validating a schema, and the discipline of interpreting an instance against it.

Step 1 — Identify entities and relationships. Decide what real-world things need tracking (students, courses) and what facts connect them (enrollment, grade). Each becomes a candidate relation.

Step 2 — Define the schema. For each relation, list its attributes and their domains. Choose a candidate key — a minimal set of attributes whose values uniquely identify each tuple — and designate one as the primary key. (This is developed fully in Relations, Attributes, and Keys.)

Step 3 — Populate the instance. Insert tuples. The database system checks, on every insertion or update, that:

• every attribute value lies in its declared domain (domain constraint),
• no two tuples agree on the primary key (key constraint / entity integrity),
• foreign key references point to existing tuples in the referenced relation (referential integrity).

Step 4 — Query. Users express requests as expressions over relations (relational algebra or SQL), which the database evaluates by producing new relations as results — never by exposing internal storage. The pseudocode below formalizes the validation logic a database engine conceptually performs whenever the instance changes — this is the invariant-preservation machinery that keeps an instance a faithful, consistent model of the schema. ``` // Validate a proposed tuple insertion against a relation schema R function VALIDATE_INSERT(R, t): // R.attributes = [A_1, ..., A_n] with domains D_1, ..., D_n // R.instance = current set of tuples // R.primary_key = subset of attribute indices // R.foreign_keys = list of (attrs, referenced_relation, referenced_key) // 1. Domain check: every value must belong to its attribute's domain for i in 1..n: if t[i] not in R.attributes[i].domain: reject "domain violation on attribute " + R.attributes[i].name // 2. Entity integrity: primary key attributes cannot be null, // and must be unique across the current instance for k in R.primary_key: if t[k] is NULL: reject "primary key attribute cannot be null" for existing_t in R.instance: if projects_equal(existing_t, t, R.primary_key): reject "duplicate primary key value" // 3. Referential integrity: every foreign key value must // match an existing tuple's key in the referenced relation for (attrs, ref_relation, ref_key) in R.foreign_keys: fk_value = project(t, attrs) if fk_value is not NULL and fk_value not in { project(s, ref_key) for s in ref_relation.instance }: reject "referential integrity violation" // All checks passed: t may be safely added R.instance = R.instance ∪ { t } // set union — duplicates collapse automatically return "insert accepted" ``` The single line `R.instance = R.instance ∪ { t }` is where the set semantics of the model becomes operationally real: even without an explicit uniqueness check on the whole tuple, set union guarantees that inserting an already-present tuple has no effect, which is exactly the "no duplicate rows" property the mathematical definition promises.

Space. A relation instance with $r$ tuples over $n$ attributes requires $O(r \cdot n)$ space in the abstract model (before considering indexes, which trade extra space for faster lookups). This is a direct consequence of the definition: a tuple is a fixed-length vector of $n$ values, and the relation is simply $r$ such vectors.

Time for validation. The `VALIDATE_INSERT` procedure above costs, in the naive worst case:

• $O(n)$ for domain checks (constant per attribute, $n$ attributes),
• $O(r)$ for the primary-key uniqueness scan, since it may compare against every existing tuple,
• $O(m \cdot \bar{r})$ for referential integrity, where $m$ is the number of foreign keys and $\bar{r}$ is the size of each referenced relation, again in the naive linear-scan case.

So a single insertion costs $O(n + r + m\bar{r})$ in the worst case with no auxiliary structures — this is honestly poor for large $r$. Real systems avoid this by maintaining a B-tree or hash index on primary and foreign key attributes, reducing the uniqueness and referential checks to $O(\log r)$ or expected $O(1)$ respectively. This is precisely why physical data independence matters: the logical guarantee (uniqueness, referential integrity) is fixed by the model, while the physical mechanism enforcing it (linear scan vs. index lookup) is free to change without altering correctness or the schema visible to applications.

Correctness argument. The relational model's correctness rests on an invariant maintained across every state transition (insert, delete, update): > Invariant: At every point in time, the database instance satisfies all declared domain constraints, key constraints, and referential integrity constraints of its schema. The base case holds trivially for an empty database (vacuously satisfies all constraints). The inductive step is exactly what `VALIDATE_INSERT` (and its analogues for delete/update) enforces: a proposed transition is applied only if it preserves the invariant, and rejected otherwise. Because every mutation goes through such a check, and because the invariant holds initially, it holds after every subsequent operation by induction on the sequence of operations. This is the same style of reasoning used to prove loop invariants correct, applied here to a persistent data store rather than a single computation.

Tradeoffs. The rigor of the model — atomic values, set semantics, explicit constraints — is exactly what enables a small, closed query algebra with provable rewrite rules (used heavily by query optimizers). The cost is expressive friction: representing naturally hierarchical or repeating data (e.g., a student's list of phone numbers) requires decomposing it into separate relations rather than nesting it directly, which is why document/NoSQL models exist as an alternative for workloads dominated by nested, schema-flexible data.

Consider a small university database with two relations. ``` Student(ID, name, dept, tot_cred) Course(course_id, title, dept, credits) ``` Suppose the current instance of `Student` is:

Now trace three attempted operations through the validation logic.

Operation 1 — Insert (76543, "Levy", "Physics", 46).

• Domain check: `ID=76543` is an integer within range, `name` is a valid varchar, `dept="Physics"` valid, `tot_cred=46 ≥ 0`. Pass.
• Entity integrity: scan the 3 existing tuples for `ID=76543` — no match found. Pass.
• Referential integrity: none declared on `Student` in this simplified schema. Pass.
• Result: accepted. New instance has 4 tuples.

Operation 2 — Insert (12345, "Kim", "Physics", 15).

• Domain check passes (all values valid).
• Entity integrity: scan existing tuples — `ID=12345` already exists (Shankar's row).
• Result: rejected — duplicate primary key value. This is the entity-integrity rule preventing two distinct real-world students from colliding under one identifier.

Operation 3 — Insert (55555, "Patel", "Comp. Sci.", -10).

• Domain check: `tot_cred = -10` violates the declared domain `integer ≥ 0`.
• Result: rejected — domain violation on attribute tot_cred. Note this check fires before the key or referential checks even run, matching the order in the pseudocode — cheaper checks are evaluated first, a small but real optimization.

This trace demonstrates all three integrity mechanisms firing on realistic, non-symmetric inputs: one clean success, one key collision, and one domain violation — the three distinct failure modes a well-designed relational schema must guard against.

Every major relational database management system — PostgreSQL, MySQL, Oracle Database, Microsoft SQL Server, SQLite, IBM Db2 — implements the relational model as its logical data model, with SQL as the standard query interface built on top of relational algebra. Financial systems, airline reservation systems, hospital records, and e-commerce inventories all rely on the model's integrity guarantees (entity and referential integrity) to keep critical facts consistent even under heavy concurrent write load. Data warehousing and business intelligence tools issue analytical queries expressed as relational operations, trusting the query optimizer to exploit the algebra's mathematical equivalences to choose an efficient execution plan without the analyst ever specifying how to compute the answer. Even systems that reject strict relational structure — document stores, key-value stores, graph databases — are typically explained and compared against the relational baseline, since it remains the reference point for what a "table," a "key," and a "join" mean across the entire database field. The concepts introduced here — schema versus instance, atomic domains, set-based tuples — are the direct foundation for Relations, Attributes, and Keys (how uniqueness and constraints are formalized) and for The Relational Algebra (how queries are expressed and combined as operations on these very relations).

Ask the tutor: How does the relational model's mathematical set-based definition constrain and enable the design of the relational algebra's operators?