The Relational Model

A relation in the mathematical sense is a subset of a Cartesian product. If you have domains D₁, D₂, ..., Dₙ (each a set of possible values), then a relation R is a set of n-tuples where the i-th component of each tuple is drawn from Dᵢ.

Concretely: if D₁ = {strings} and D₂ = {integers}, then R ⊆ D₁ × D₂ might be:

{ ("Alice", 30), ("Bob", 25), ("Carol", 35) }

This is literally a mathematical set — which has two critical consequences that non-relational models lack:

1. No duplicate rows (sets have no repeated elements)
2. No ordering (sets are unordered — there is no "first" row)

Both of these feel like constraints, but they are actually freedoms for the database. Because there is no ordering, the database is free to return rows in any order it finds efficient. Because there are no duplicates (in the theory — SQL relaxes this with bags, which we'll address), equality testing is well-defined.

The database relation maps directly to this: a table in a relational database is a relation. The columns define the domains; each row is a tuple. The table is the extension (the actual set of tuples currently in the relation), while the schema defines the intension (what the relation is about).

-- In SQL, this CREATE TABLE statement defines the schema (intension):
CREATE TABLE Employee (
    emp_id   INTEGER,
    name     VARCHAR(100),
    dept_id  INTEGER,
    salary   NUMERIC(10,2)
);

-- The rows inserted constitute the extension (the actual relation):
INSERT INTO Employee VALUES (1, 'Alice', 10, 95000.00);
INSERT INTO Employee VALUES (2, 'Bob',   10, 88000.00);
INSERT INTO Employee VALUES (3, 'Carol', 20, 102000.00);

A tuple is a single row in a relation — an ordered list of values, one per attribute. An attribute is a named column with an associated domain (the set of legal values).

In the relational model, every attribute has a domain — an atomic type. Codd's First Normal Form (1NF) requires that every attribute value be atomic: it cannot be a list, set, or another relation. This is the formal statement of the intuition "no nested tables, no arrays as columns."

The arity (or degree) of a relation is the number of attributes. The cardinality is the number of tuples.

A critical subtlety: in the relational model, attribute access is by name, not by position. This matters because it means operations that rearrange columns still produce the same relation. The tuple (Alice, 30) under schema (name, age) is the same logical entity as a tuple retrieved in any column order — the names give meaning.

The special value NULL deserves its own discussion. Codd introduced NULL to represent missing or inapplicable information. It is NOT zero, NOT the empty string, NOT false. It is the absence of a value. This creates a three-valued logic: a comparison like salary > 50000 when salary is NULL returns UNKNOWN (not TRUE or FALSE). Most bugs in SQL come from not respecting this.

-- Domain constraint example: salary must be positive
CREATE TABLE Employee (
    emp_id  INTEGER     NOT NULL,
    name    VARCHAR(100) NOT NULL,
    salary  NUMERIC(10,2) CHECK (salary > 0),  -- domain constraint
    dept_id INTEGER      -- nullable: department may be unassigned
);

-- Three-valued logic with NULL:
SELECT name FROM Employee WHERE dept_id = 10;  -- NULL rows excluded
SELECT name FROM Employee WHERE dept_id != 10; -- NULL rows ALSO excluded!
SELECT name FROM Employee WHERE dept_id IS NULL; -- correct way to find them

The schema of a relation is its name, the list of attribute names, and their domains. The schema is the intension — the meaning, the template, the contract. It changes rarely (when the application evolves).

The instance (or extension) of a relation is the actual set of tuples at a particular moment. It changes constantly — every INSERT, UPDATE, DELETE changes the instance.

This distinction is fundamental: the schema is a description of what the world is like; the instance is a snapshot of the world's current state.

A database schema is the collection of all relation schemas together with any integrity constraints. A database instance is the collection of all current relation instances that satisfies those constraints.

Formally, a relation schema R(A₁:D₁, A₂:D₂, ..., Aₙ:Dₙ) defines a relation where each tuple t satisfies t[Aᵢ] ∈ Dᵢ for all i. The notation t[A] means "the value of attribute A in tuple t."

# Representing schema and instance in Python
from dataclasses import dataclass
from typing import Optional, Set, Tuple

# Schema: describes the structure
schema = {
    "Employee": {
        "attributes": ["emp_id", "name", "dept_id", "salary"],
        "domains":    [int,      str,    int,         float]
    }
}

# Instance: the actual tuples right now
# (using frozenset to reflect that it's a set — no duplicates, no order)
employee_instance: Set[Tuple] = {
    (1, "Alice", 10, 95000.0),
    (2, "Bob",   10, 88000.0),
    (3, "Carol", 20, 102000.0),
}

A superkey of a relation R is any set of attributes K such that no two distinct tuples in any valid instance of R have the same values for all attributes in K. In other words, K uniquely identifies each tuple.

A candidate key is a minimal superkey — a superkey from which no attribute can be removed while still guaranteeing uniqueness. Every relation has at least one candidate key (in the worst case, the set of all attributes is a superkey).

The primary key is the candidate key the designer designates as the "official" identifier. SQL enforces this with the PRIMARY KEY constraint (which implicitly adds NOT NULL).

A foreign key is a set of attributes in relation R that references the primary key of another relation S. It is a referential integrity constraint: every non-null value in R's foreign key must appear as a primary key value in S. This is how the relational model represents relationships between entities.

The intuition for why keys matter: the relational model gives each tuple no intrinsic identity (no memory address, no pointer). The only identity a tuple has is its content. Keys are how we refer to specific tuples from other relations — they are the relational equivalent of a pointer, but based on value, not location. This is the foundation of data independence.

Surrogate vs. Natural keys: A natural key is a key drawn from real-world attributes (e.g., SSN, ISBN). A surrogate key is a synthetic attribute added purely for identification (e.g., auto-increment integer, UUID). Surrogate keys avoid the problem of natural keys changing over time (e.g., a person changes their name).

CREATE TABLE Department (
    dept_id   INTEGER     PRIMARY KEY,  -- candidate key, chosen as PK
    dept_name VARCHAR(50) UNIQUE NOT NULL  -- another candidate key
);

CREATE TABLE Employee (
    emp_id   INTEGER      PRIMARY KEY,     -- surrogate key
    name     VARCHAR(100) NOT NULL,
    email    VARCHAR(150) UNIQUE,          -- candidate key (natural)
    dept_id  INTEGER      REFERENCES Department(dept_id)  -- foreign key
    -- every dept_id here must exist in Department, or be NULL
);

-- Composite primary key example:
CREATE TABLE Enrollment (
    student_id INTEGER REFERENCES Student(student_id),
    course_id  INTEGER REFERENCES Course(course_id),
    grade      CHAR(2),
    PRIMARY KEY (student_id, course_id)  -- composite PK
);

An integrity constraint is a condition that every valid database instance must satisfy. Constraints are part of the schema — they capture real-world rules about the data. The database enforces them automatically, rejecting any modification that would violate them.

The main types in the relational model:

1. Domain constraints: Each attribute value must lie in its declared domain (e.g., salary must be a number, age must be non-negative). Implemented via column types, CHECK constraints, NOT NULL.

2. Key constraints: The values of the key attributes must be unique across all tuples. Implemented via PRIMARY KEY and UNIQUE.

3. Entity integrity: No attribute of a primary key can be NULL. Rationale: if a primary key could be NULL, we couldn't reliably identify tuples, and foreign key references would be ambiguous.

4. Referential integrity (foreign key constraints): Every foreign key value either is NULL or matches a primary key value in the referenced relation. This prevents "dangling references" — orphaned tuples that point to entities that don't exist.

5. General constraints: Application-specific business rules expressed as CHECK constraints or triggers (e.g., CHECK (end_date > start_date), CHECK (salary BETWEEN 0 AND 1000000)).

The beauty of declaring constraints in the schema is that they serve double duty: the database enforces them at write time (keeping data consistent), and the query optimizer can exploit them at read time (e.g., knowing a foreign key is always valid allows certain join optimizations).

CREATE TABLE Project (
    proj_id    INTEGER      PRIMARY KEY,
    title      VARCHAR(200) NOT NULL,
    start_date DATE         NOT NULL,
    end_date   DATE,
    budget     NUMERIC(12,2) CHECK (budget >= 0),
    -- General constraint: end must be after start
    CONSTRAINT valid_dates CHECK (end_date IS NULL OR end_date > start_date)
);

CREATE TABLE Assignment (
    emp_id   INTEGER REFERENCES Employee(emp_id) ON DELETE CASCADE,
    proj_id  INTEGER REFERENCES Project(proj_id) ON DELETE RESTRICT,
    role     VARCHAR(50) NOT NULL,
    hours    INTEGER     CHECK (hours > 0 AND hours <= 168),
    PRIMARY KEY (emp_id, proj_id)
);
-- ON DELETE CASCADE: if an employee is deleted, their assignments vanish too
-- ON DELETE RESTRICT: cannot delete a project that has assignments

Relational algebra is a formal query language for the relational model. It defines six fundamental operations that take relations as input and produce a relation as output — making it closed under composition. Every SQL query can be expressed in relational algebra (with some extensions for aggregation), and query optimizers work by transforming algebraic expressions.

The six operations:

1. Selection σ (sigma) — Filters rows. σ_condition(R) returns all tuples in R satisfying the condition. Like the WHERE clause.

2. Projection π (pi) — Filters columns. π_{A₁,A₂,...}(R) returns only the named attributes (and removes duplicates, since the result is a set). Like SELECT DISTINCT with named columns.

3. Union ∪ — R ∪ S returns all tuples in R or S (or both). R and S must be union-compatible: same number of attributes with compatible domains.

4. Set Difference − — R − S returns tuples in R that are not in S. Again requires union-compatibility.

5. Cartesian Product × — R × S returns all combinations of one tuple from R and one from S. If R has m tuples and S has n, the result has m×n tuples. This is the raw material of joins.

6. Rename ρ (rho) — ρ_{new_name}(R) renames a relation (or its attributes). Necessary for self-joins and avoiding ambiguity.

From these six, you can derive the intersection (R ∩ S = R − (R − S)), and most importantly, the natural join and theta join that are the workhorses of real queries.

The theta join R ⋈_θ S = σ_θ(R × S): Cartesian product followed by selection. The natural join R ⋈ S: theta join on equality of all same-named attributes, with duplicate columns removed.

-- Selection: σ_{salary > 90000}(Employee)
SELECT * FROM Employee WHERE salary > 90000;

-- Projection: π_{name, salary}(Employee)
SELECT DISTINCT name, salary FROM Employee;

-- Cartesian product then selection = theta join:
-- Employee ⋈_{Employee.dept_id = Department.dept_id} Department
SELECT * FROM Employee, Department
WHERE Employee.dept_id = Department.dept_id;
-- or equivalently:
SELECT * FROM Employee JOIN Department
  ON Employee.dept_id = Department.dept_id;

-- Natural join (join on matching column names automatically):
SELECT * FROM Employee NATURAL JOIN Department;
-- Note: NATURAL JOIN is rarely used in practice due to fragility
-- (adding a column with the same name to a table silently changes query)

-- Union (requires same schema):
SELECT name FROM Employee
UNION
SELECT name FROM Contractor;
-- UNION removes duplicates (set semantics); UNION ALL keeps them (bag semantics)

Several extremely useful operations are not primitive but can be expressed in terms of the six core operations. Understanding them as derived operations reveals what SQL is really doing.

Intersection: R ∩ S = R − (R − S). All tuples in both R and S. SQL: INTERSECT.

Natural join: R ⋈ S. Let the common attributes be {A₁,...,Aₖ}. The natural join selects all tuples from R × S where the shared attributes are equal, then projects away duplicates:

R ⋈ S = π_{all attributes, deduped}(σ_{R.A₁=S.A₁ ∧ ... ∧ R.Aₖ=S.Aₖ}(R × S))

Division: R ÷ S is the trickiest operation. If R(A, B) and S(B), then R ÷ S returns all values of A that appear paired with every value in S. This expresses "for all" queries. Example: "Find all students who have taken every course in the 'required' list."

Formally: R ÷ S = π_A(R) − π_A((π_A(R) × S) − R)

This reads: take all A values, remove those for which there exists some B in S that A is NOT paired with.

The division operation is how you express universal quantification in relational algebra — and why SQL has no direct FOR ALL but instead uses double negation (NOT EXISTS ... NOT EXISTS ...) to simulate it.

Outer joins: The natural join is an inner join — tuples with no match are dropped. An outer join preserves unmatched tuples, padding with NULLs. SQL has LEFT OUTER JOIN, RIGHT OUTER JOIN, FULL OUTER JOIN. These are not in core relational algebra (they require NULL) but are essential in practice.

-- Division example: "Find employees assigned to ALL projects in dept 10"
-- R = Assignment(emp_id, proj_id), S = {proj_id : dept_id = 10}

-- Step 1: projects in dept 10
WITH dept10_projects AS (
    SELECT proj_id FROM Project WHERE dept_id = 10
),
-- Step 2: employees who are MISSING at least one dept-10 project
missing AS (
    SELECT e.emp_id
    FROM Employee e
    CROSS JOIN dept10_projects d
    WHERE NOT EXISTS (
        SELECT 1 FROM Assignment a
        WHERE a.emp_id = e.emp_id AND a.proj_id = d.proj_id
    )
)
-- Step 3: all employees minus those with any gap
SELECT emp_id FROM Employee
WHERE emp_id NOT IN (SELECT emp_id FROM missing);

-- Outer join: keep all employees, even those with no department
SELECT e.name, d.dept_name
FROM Employee e
LEFT OUTER JOIN Department d ON e.dept_id = d.dept_id;
-- Employees with no dept get NULL for dept_name

A relational algebra expression can be represented as a tree where leaves are base relations and internal nodes are operations. This algebraic representation is exactly what a SQL query optimizer builds internally (called the logical query plan).

The optimizer applies algebraic equivalences — proven laws about relational algebra — to rewrite the tree into an equivalent but cheaper form. Key equivalences:

1. Cascading selections: σ_{A∧B}(R) = σ_A(σ_B(R)) — split a conjunction into two nested selections.

2. Pushing selections down (crucial!): σ_condition(R ⋈ S) ≡ σ_condition(R) ⋈ S if the condition only references R's attributes. This is called predicate pushdown: filter early, join less data.

3. Commutativity of join: R ⋈ S = S ⋈ R (result is the same set of tuples, modulo column order)

4. Associativity of join: (R ⋈ S) ⋈ T = R ⋈ (S ⋈ T) — enables the query optimizer to reorder joins.

5. Pushing projections down: π_A(R ⋈ S) — if A only covers R's attributes, push projection before the join.

The optimizer generates multiple equivalent plans and estimates the cost of each (using statistics like table sizes and index availability), then picks the cheapest one. This is possible only because relational algebra is formal — the equivalences can be proven correct, not just hoped to work.

The difference between a naive plan (Cartesian product of all tables, then filter) and an optimized plan (push selections, use indexes, reorder joins) can be 6-8 orders of magnitude in performance on real queries.

-- This SQL query:
SELECT e.name, d.dept_name
FROM Employee e, Department d, Assignment a
WHERE e.emp_id = a.emp_id
  AND a.proj_id = 42
  AND e.dept_id = d.dept_id;

-- Naive plan (bad): compute E × D × A first, then filter
-- Optimized plan: push σ_{proj_id=42} before the join
--
-- Algebraic rewrite:
-- Original: σ_{conditions}(E × D × A)
-- Step 1 (push selection on A):
--   σ_{e.emp_id=a.emp_id ∧ e.dept_id=d.dept_id}(E × D × σ_{proj_id=42}(A))
-- Step 2 (replace Cartesian products + selections with joins):
--   E ⋈_{emp_id} (σ_{proj_id=42}(A)) ⋈_{dept_id} D
--
-- The optimizer might then use:
--   - Index scan on Assignment.proj_id (if indexed)
--   - Hash join or nested-loop join depending on table sizes
--   - Reorder joins based on cardinality estimates

-- EXPLAIN shows the physical query plan PostgreSQL chose:
EXPLAIN ANALYZE
SELECT e.name, d.dept_name
FROM Employee e
JOIN Assignment a ON e.emp_id = a.emp_id
JOIN Department d ON e.dept_id = d.dept_id
WHERE a.proj_id = 42;

Relational algebra is procedural — it specifies a sequence of operations to compute a result. Codd also defined relational calculus — a declarative notation that specifies what the answer should contain without specifying how to compute it.

There are two variants:

Tuple relational calculus (TRC): Queries have the form {t | P(t)} — "the set of tuples t such that predicate P(t) is true." For example, "employees with salary > 90000" is: {t | t ∈ Employee ∧ t[salary] > 90000}.

Domain relational calculus (DRC): Variables range over individual attribute values (domains). The query "get names of employees earning more than 90000" is: {⟨n⟩ | ∃i, d, s: Employee(i, n, d, s) ∧ s > 90000}.

Codd's Theorem (the foundational result): Relational algebra and safe relational calculus are expressively equivalent — any query expressible in one can be expressed in the other. This is the formal reason SQL (which descends from relational calculus) and the algebraic query planning underneath it (relational algebra) are interchangeable.

SQL itself is essentially relational calculus with syntactic sugar. The SELECT-FROM-WHERE structure maps directly to DRC: SELECT = projection (which attributes), FROM = which relations and what they contain, WHERE = the predicate.

The calculus formulation is important because it separates specification from implementation — you describe the answer, the DBMS figures out how to compute it. This is the essence of declarative programming.

-- Domain Relational Calculus: "Names of employees in dept 10 earning > 80000"
-- DRC: { <n> | ∃id, s: Employee(id, n, 10, s) ∧ s > 80000 }
--
-- Direct SQL translation:
SELECT name
FROM Employee
WHERE dept_id = 10 AND salary > 80000;

-- DRC: "Departments that have at least one employee"
-- { <dn> | ∃did: Department(did, dn) ∧ ∃id, n, s: Employee(id, n, did, s) }
SELECT dept_name
FROM Department
WHERE EXISTS (
    SELECT 1 FROM Employee WHERE Employee.dept_id = Department.dept_id
);

-- TRC: "Pairs of employees in the same department"
-- { <t1, t2> | t1 ∈ Employee ∧ t2 ∈ Employee
--              ∧ t1[dept_id] = t2[dept_id] ∧ t1[emp_id] < t2[emp_id] }
SELECT e1.name, e2.name
FROM Employee e1, Employee e2
WHERE e1.dept_id = e2.dept_id AND e1.emp_id < e2.emp_id;

Pure relational algebra operates on sets — no duplicate tuples, no ordering. SQL, for practical performance reasons, operates on bags (also called multisets) — duplicates are allowed unless you explicitly remove them.

This is why SELECT name FROM Employee may return duplicates if multiple employees share a name, while the theoretically pure π_{name}(Employee) would not. SQL uses SELECT DISTINCT to force set semantics.

This design choice was deliberate: eliminating duplicates requires sorting or hashing the entire output, which is expensive. For many applications (e.g., computing an average salary, counting rows), duplicates are needed anyway. So SQL defaults to bags and makes set behavior opt-in.

The bag algebra has its own set of equivalences, and importantly, some algebraic laws that hold for sets do NOT hold for bags. For example:

• Set: R ∪ R = R (idempotent). Bag: R UNION ALL R ≠ R (doubles every row).
• Set: R − R = ∅. Bag: R EXCEPT ALL R = ∅ (this one holds).
• Bag union distributes over bag intersection (this is more subtle).

Query optimizers must track whether they are operating under set or bag semantics because an optimization valid for sets may be incorrect for bags. This is a subtle but real source of bugs in database implementations.

The practical rule: use DISTINCT explicitly when you need set semantics; use UNION (not UNION ALL) when merging result sets where duplicates are meaningful duplicates.

-- Set vs bag semantics illustrated:

-- Returns duplicate dept_ids (bag semantics):
SELECT dept_id FROM Employee;
-- dept_id
-- 10
-- 10
-- 20

-- Returns unique dept_ids (set semantics, like π in relational algebra):
SELECT DISTINCT dept_id FROM Employee;
-- dept_id
-- 10
-- 20

-- UNION eliminates duplicates (set union):
SELECT name FROM Employee
UNION
SELECT name FROM Contractor;

-- UNION ALL preserves duplicates (bag union, much faster):
SELECT name FROM Employee
UNION ALL
SELECT name FROM Contractor;

-- Practical: to count distinct departments that have employees:
SELECT COUNT(DISTINCT dept_id) FROM Employee;
-- NOT: SELECT COUNT(dept_id) FROM Employee -- that counts rows

A functional dependency (FD) X → Y on a relation R means: for any two tuples t₁ and t₂ in R, if t₁[X] = t₂[X] then t₁[Y] = t₂[Y]. In English: knowing X determines Y.

For example, in Employee: emp_id → name, salary, dept_id (the employee ID determines everything else). In a combined table: dept_id → dept_name (knowing the department ID tells you the name).

Functional dependencies are the theoretical foundation for normalization — the process of decomposing relation schemas to eliminate redundancy and update anomalies. The normal forms (1NF through BCNF/3NF/4NF/5NF) are defined entirely in terms of FDs.

Anomalies from redundancy: If you store dept_name in the Employee table directly (not via a foreign key), you get:

• Update anomaly: change a department name → must update every employee row
• Insertion anomaly: can't record a department until it has an employee
• Deletion anomaly: delete the last employee → department info vanishes

Normalization eliminates these by decomposing the "bad" relation into smaller, well-structured ones. Boyce-Codd Normal Form (BCNF): for every FD X → Y in R, X must be a superkey. If it isn't, decompose.

Normalization is covered in depth in its own module; the key insight here is that FDs, keys, and normalization are all connected: a candidate key is precisely the set of attributes X such that X → {all attributes}.

-- Bad design: storing dept_name redundantly in Employee
CREATE TABLE Employee_Denormalized (
    emp_id    INTEGER PRIMARY KEY,
    name      VARCHAR(100),
    dept_id   INTEGER,
    dept_name VARCHAR(50),  -- redundant! determined by dept_id
    salary    NUMERIC(10,2)
);
-- FD violation: dept_id -> dept_name, but dept_id is not a key
-- This violates BCNF

-- BCNF decomposition: separate the FD into its own table
CREATE TABLE Department (
    dept_id   INTEGER PRIMARY KEY,
    dept_name VARCHAR(50) NOT NULL
);

CREATE TABLE Employee (
    emp_id  INTEGER PRIMARY KEY,
    name    VARCHAR(100) NOT NULL,
    dept_id INTEGER REFERENCES Department(dept_id),
    salary  NUMERIC(10,2)
);
-- Now dept_id -> dept_name lives in Department, with dept_id as PK
-- No redundancy, no anomalies