On this page

The Relational Model & Relational Algebra

Every SQL query you have ever written is a sentence in a language that a mathematician designed in 1970. Edgar F. Codd, working at IBM, published A Relational Model of Data for Large Shared Data Banks and proposed something radical for the time: stop making programs navigate pointers between records, and describe data as sets of facts that you query by what you want rather than how to find it.

That one idea gave us SQL, query optimizers, declarative constraints, and fifty years of databases that still look the same from the outside. This page covers the theory underneath. It is the material university DBMS courses teach in the first few weeks and that CS-fundamentals interviews love to probe: what exactly a key is, why NULL = NULL is not true, what a relational algebra expression means, and how the operators map onto SQL.

If you want the practical side, how databases store and serve this data at scale, start with How Databases Work. If you want to write the queries, see SQL Fundamentals and Advanced SQL. This page sits between the two: the model that both of them assume.

The Vocabulary: Relations, Tuples, Attributes, Domains

The relational model has its own vocabulary. Practitioners use the informal words (table, row, column) and theory uses the formal ones. You need both, because exam questions and interviewers switch between them freely.

Formal termInformal termMeaning
RelationTableA set of tuples that all share the same attributes
TupleRow, recordOne fact: a mapping from each attribute to a value
AttributeColumn, fieldA named role a value plays in a tuple
DomainData type (plus constraints)The set of legal values for an attribute
Degree (arity)Number of columnsHow many attributes the relation has
CardinalityNumber of rowsHow many tuples the relation contains right now
Relation schemaTable definitionThe relation name plus its attributes and domains, e.g. Student(sid, name, major, year)
Relation instanceTable contentsThe set of tuples at a particular moment
Database schemaThe DDLThe set of all relation schemas plus constraints

A domain is more than a type. INTEGER is a type; "integers between 1 and 4 representing year of study" is a domain. In SQL you build a domain from a type plus constraints, and PostgreSQL even lets you name one:

CREATE DOMAIN study_year AS smallint
  CHECK (VALUE BETWEEN 1 AND 4);

CREATE TABLE student (
  sid    integer PRIMARY KEY,
  name   text NOT NULL,
  major  text,
  year   study_year NOT NULL
);

MySQL has no CREATE DOMAIN; you repeat the type and the CHECK on each column (and CHECK constraints are only enforced from MySQL 8.0.16 onward; earlier versions parsed and silently ignored them).

A Relation Is a Set, Not a Table

The mathematical definition matters because it has consequences. Given domains D1, D2, ..., Dn, a relation R is a subset of the Cartesian product D1 × D2 × ... × Dn. Each element of that subset is a tuple. Three properties fall out of "it's a set":

  1. No duplicate tuples. A set cannot contain the same element twice.
  2. No order among tuples. Sets are unordered. "The third row" is meaningless.
  3. No order among attributes (in the named-attribute formulation). A tuple maps names to values, so (sid: 1, name: 'Ada') and (name: 'Ada', sid: 1) are the same tuple.

A fourth property is a modelling rule rather than set theory:

  1. Every value is atomic. Each attribute holds a single value from its domain, not a list or a nested table. This is what First Normal Form means; see ER Modeling & Schema Design for the recap and Normalization & Denormalization for the full treatment.

SQL is not the relational model

SQL tables are bags (multisets), not sets. SELECT major FROM student happily returns 'CS' five times. Rows do have a physical order, but SQL promises nothing about it without ORDER BY. Columns have a positional order (SELECT *, INSERT ... VALUES without a column list). And SQL has NULL, which pure relational theory does not. When an interviewer asks "is SQL relational?", the honest answer is "mostly, with bag semantics and NULLs bolted on". SELECT DISTINCT and UNION (without ALL) are the places SQL switches back to set semantics.

The Running Example Schema

Every worked example on this page uses this small university database. Keep it in view.

erDiagram
  STUDENT ||--o{ ENROLLED : "takes"
  COURSE ||--o{ ENROLLED : "has"
  DEPARTMENT ||--o{ COURSE : "offers"
  DEPARTMENT ||--o{ STUDENT : "majors in"
  STUDENT {
    int sid PK
    text name
    text dept_code FK
    int year
  }
  COURSE {
    text cid PK
    text title
    text dept_code FK
    int credits
  }
  ENROLLED {
    int sid PK, FK
    text cid PK, FK
    text grade
  }
  DEPARTMENT {
    text dept_code PK
    text dept_name
  }

Student

sidnamedept_codeyear
1AdaCS3
2BrianMATH2
3ChenCS4
4DanaPHYS1
5EveNULL1

Course

cidtitledept_codecredits
CS101Intro to ProgrammingCS4
CS340DatabasesCS4
MA201Linear AlgebraMATH3
PH110MechanicsPHYS4

Enrolled

sidcidgrade
1CS101A
1CS340A
1MA201B
2MA201A
3CS101B
3CS340NULL
4PH110C

Department

dept_codedept_name
CSComputer Science
MATHMathematics
PHYSPhysics
BIOBiology

Notice the deliberate oddities: Eve has no department (NULL), Chen has no grade yet in CS340, and Biology offers no courses and has no students. Those edge cases are where outer joins, division and three-valued logic earn their keep.

CREATE TABLE department (
  dept_code text PRIMARY KEY,
  dept_name text NOT NULL UNIQUE
);

CREATE TABLE student (
  sid       integer PRIMARY KEY,
  name      text NOT NULL,
  dept_code text REFERENCES department (dept_code) ON DELETE SET NULL,
  year      smallint NOT NULL CHECK (year BETWEEN 1 AND 4)
);

CREATE TABLE course (
  cid       text PRIMARY KEY,
  title     text NOT NULL,
  dept_code text NOT NULL REFERENCES department (dept_code) ON DELETE RESTRICT,
  credits   smallint NOT NULL CHECK (credits > 0)
);

CREATE TABLE enrolled (
  sid   integer REFERENCES student (sid) ON DELETE CASCADE,
  cid   text    REFERENCES course (cid)  ON DELETE CASCADE,
  grade char(1) CHECK (grade IN ('A','B','C','D','F')),
  PRIMARY KEY (sid, cid)
);

Keys

Keys are the single most-tested concept in DBMS fundamentals, mostly because the terms nest inside each other and people mix them up. The definitions are precise; learn them precisely.

Superkey

A superkey is any set of attributes whose values uniquely identify a tuple. In Student, {sid} is a superkey. So is {sid, name}, and {sid, name, year}, and the set of all attributes. Adding attributes to a superkey always gives another superkey. The set of all attributes is always a superkey, because a relation has no duplicate tuples.

Candidate Key

A candidate key is a minimal superkey: remove any attribute and it stops being unique. {sid} is a candidate key of Student. {sid, name} is not, because you can drop name and still have uniqueness.

A relation can have several candidate keys. If every student also had a unique university email, {email} would be a second candidate key. A candidate key can be composite: in Enrolled, neither sid nor cid alone is unique, but {sid, cid} is, and it is minimal.

Minimal is not the same as smallest

"Minimal" means no proper subset is a superkey, not "has the fewest attributes". A relation can have a one-attribute candidate key and a three-attribute candidate key at the same time, and both are minimal. Interviewers like this trap.

Primary Key and Alternate Keys

The primary key is the one candidate key you choose to be the main identifier, the one other tables reference. Every other candidate key is an alternate key (sometimes "secondary key", though that phrase is also used for non-unique index columns, so avoid it). In SQL you declare the primary key with PRIMARY KEY and the alternates with UNIQUE NOT NULL:

CREATE TABLE student (
  sid    integer PRIMARY KEY,           -- primary key
  email  text NOT NULL UNIQUE,          -- alternate key
  name   text NOT NULL
);

Foreign Key

A foreign key is a set of attributes in one relation (the referencing or child relation) whose values must match a candidate key in another relation (the referenced or parent relation), or be NULL. Enrolled.sid is a foreign key referencing Student.sid. A foreign key need not reference the primary key; it can reference any UNIQUE column set. It also need not be named the same, and it can reference its own table:

CREATE TABLE employee (
  emp_id     integer PRIMARY KEY,
  name       text NOT NULL,
  manager_id integer REFERENCES employee (emp_id)  -- self-referencing FK
);

Composite Key

A composite key is any key made of more than one attribute. Enrolled's (sid, cid) is composite. Composite keys are common in junction tables for many-to-many relationships. A foreign key that references a composite key must itself be composite:

CREATE TABLE grade_appeal (
  appeal_id serial PRIMARY KEY,
  sid       integer NOT NULL,
  cid       text    NOT NULL,
  reason    text,
  FOREIGN KEY (sid, cid) REFERENCES enrolled (sid, cid)
);

Surrogate vs Natural Keys

A natural key is made of attributes that mean something in the real world: an ISBN, a country code, a national ID, an email. A surrogate key is a meaningless value the system generates purely to identify the row: an auto-increment integer, a UUID.

Natural keySurrogate key
Exampleisbn, country_code, emailid bigint GENERATED ALWAYS AS IDENTITY, uuid
MeaningBusiness meaning, human readableNone
StabilityCan change (people change emails, ISBN formats changed in 2007)Never needs to change
SizeOften wide (text, multi-column)Narrow (8 or 16 bytes)
JoinsWide join columns, copied into every childCheap joins
Duplicate protectionBuilt inNone unless you also add a UNIQUE on the natural key
Leaks informationCan (national ID in URLs)Sequential IDs leak row counts; UUIDs do not

The practical consensus: use a surrogate primary key for most entity tables, and declare the natural key as UNIQUE. The surrogate gives you stable, narrow foreign keys; the unique constraint keeps the real-world rule ("one account per email") enforced by the database rather than by hope.

CREATE TABLE customer (
  customer_id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,  -- surrogate
  email       text NOT NULL,
  CONSTRAINT customer_email_uk UNIQUE (email)                   -- natural key, still enforced
);

MySQL uses BIGINT AUTO_INCREMENT PRIMARY KEY instead of identity columns. Note that in InnoDB the primary key is the clustered index, so a random UUIDv4 primary key scatters inserts across the B+tree; prefer sequential keys or UUIDv7 there. See Indexing Deep Dive for why.

War Story (illustrative)

A team modelled users with email as the primary key, and orders.user_email as the foreign key. It was clean and readable until the day users were allowed to change their email address. Every change had to cascade into orders, payments, reviews, support tickets and three analytics pipelines that had copied the email into their own stores. The ON UPDATE CASCADE handled the database; nothing handled the copies. The migration to a surrogate user_id took a quarter. Natural keys are fine when they are truly immutable (ISO country codes); emails, phone numbers and usernames are not.

The Key Hierarchy at a Glance

flowchart TD
  SK["Superkeys: any unique attribute set"] --> CK["Candidate keys: minimal superkeys"]
  CK --> PK["Primary key: the one you choose"]
  CK --> AK["Alternate keys: the rest, declared UNIQUE"]
  PK --> FK["Foreign keys in other tables reference it"]
  AK --> FK

Worked example: finding all candidate keys. Consider R(A, B, C, D) with functional dependencies A → B, B → C, CD → A. (A functional dependency X → Y means "any two tuples that agree on X agree on Y".)

  1. Compute closures. D never appears on the right side of any dependency, so every candidate key must contain D.
  2. {D}+ = {D}. Not a key.
  3. {A, D}+: A gives B, B gives C, so {A, B, C, D}. Key. Is it minimal? {A}+ = {A, B, C} misses D, and {D}+ misses A. Yes, minimal.
  4. {B, D}+: B gives C, CD gives A, so {A, B, C, D}. Key, minimal.
  5. {C, D}+: CD gives A, A gives B, so all four. Key, minimal.
  6. Any other set containing D is a superset of one of these.

Candidate keys: {A, D}, {B, D}, {C, D}. Attributes appearing in some candidate key (A, B, C, D, here all of them) are called prime attributes, which matters for 2NF and 3NF.

Integrity Constraints

Constraints are rules the DBMS enforces on every write, so that no application bug, ad-hoc script or forgotten code path can put the database into an invalid state. They are the "C" in ACID: the database can only keep you consistent with respect to the rules you declared. See Transactions Basics for that angle.

ConstraintRuleSQL
DomainEach value comes from its attribute's domainColumn type, CHECK, CREATE DOMAIN
NOT NULLThe attribute must have a valueNOT NULL
Entity integrityNo primary-key attribute may be NULLPRIMARY KEY implies NOT NULL
Key (uniqueness)No two tuples share a candidate key valuePRIMARY KEY, UNIQUE
Referential integrityEvery foreign key value matches an existing parent key, or is NULLREFERENCES, FOREIGN KEY
CHECKAn arbitrary predicate on a single row holdsCHECK (expr)
General assertionsArbitrary predicates over many rows or tablesCREATE ASSERTION (in the SQL standard, implemented by almost no one)

Entity Integrity

The primary key identifies the tuple, so it must be fully present. If sid could be NULL, you would have a fact about "some student, we don't know which", which cannot be referenced or updated reliably. SQL enforces this automatically: every column in a PRIMARY KEY is implicitly NOT NULL.

Referential Integrity and ON DELETE Actions

Referential integrity says a child row may not point at a parent that does not exist. Inserting Enrolled(99, 'CS101', 'A') fails because student 99 does not exist. The interesting question is what happens when the parent changes. SQL gives you five referential actions, specified separately for ON DELETE and ON UPDATE:

ActionWhen the parent row is deleted (or its key updated)Typical use
NO ACTION (default)Reject the change if any child rows still reference it; checked at end of statement, so it can be deferredDefault safe choice
RESTRICTReject immediately; cannot be deferredSame as NO ACTION in practice for most uses
CASCADEDelete (or update) the child rows tooChildren that have no meaning without the parent: order lines, enrollments
SET NULLSet the child's foreign key columns to NULLOptional relationships: a student whose department is closed
SET DEFAULTSet the child's foreign key to its column defaultRare; "reassign to the Unassigned bucket"

On the running example:

-- Deleting a student removes their enrollments (CASCADE)
DELETE FROM student WHERE sid = 1;          -- also deletes 3 rows from enrolled

-- Deleting a department that still offers courses fails (RESTRICT on course)
DELETE FROM department WHERE dept_code = 'CS';
-- ERROR: update or delete on table "department" violates foreign key
--        constraint "course_dept_code_fkey" on table "course"

-- Deleting Physics would set Dana's dept_code to NULL (SET NULL on student)
-- ...but only if no course references PHYS. PH110 does, so this fails too.

CASCADE is a loaded gun

ON DELETE CASCADE is correct for true composition (an order and its lines), and dangerous anywhere else. A cascade can fan out through several levels: deleting a customer deletes their orders, which deletes their order lines, payments and shipment records. One mistaken DELETE on a top-level table can remove millions of rows in a single statement, all while holding locks. Prefer RESTRICT and explicit deletes for anything with audit or financial meaning, or use soft deletes.

Three details that come up in practice:

  • Index your foreign keys. PostgreSQL automatically indexes primary keys and unique constraints, but not the referencing column of a foreign key. Without an index on enrolled.cid, every delete from course does a sequential scan of enrolled to check for children. MySQL InnoDB creates the index automatically if one does not exist.
  • Deferrable constraints. PostgreSQL supports DEFERRABLE INITIALLY DEFERRED, which postpones the check to COMMIT. This lets you insert two rows that reference each other (a circular relationship) in one transaction. MySQL does not support deferrable constraints.
  • MySQL quirks. Only InnoDB enforces foreign keys (MyISAM parses and ignores them). SET DEFAULT is parsed but rejected by InnoDB. And SET foreign_key_checks = 0 disables enforcement for the session, which bulk loaders use and occasionally forget to undo.

CHECK, UNIQUE, NOT NULL

CREATE TABLE account (
  account_id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  owner_id   bigint NOT NULL REFERENCES customer (customer_id),
  currency   char(3) NOT NULL CHECK (currency ~ '^[A-Z]{3}$'),
  balance    numeric(14,2) NOT NULL DEFAULT 0 CHECK (balance >= 0),
  opened_at  date NOT NULL,
  closed_at  date,
  CHECK (closed_at IS NULL OR closed_at >= opened_at),   -- table-level CHECK
  UNIQUE (owner_id, currency)                             -- one account per currency
);

Rules worth memorizing:

  • A CHECK passes when its predicate is TRUE or UNKNOWN. CHECK (balance >= 0) accepts a NULL balance, because NULL >= 0 is unknown. That is why NOT NULL and CHECK are usually paired.
  • UNIQUE allows multiple NULLs in PostgreSQL and MySQL, because NULL is not equal to NULL. PostgreSQL 15+ lets you say UNIQUE NULLS NOT DISTINCT to allow only one. SQL Server, by contrast, allows only one NULL in a unique index.
  • CHECK can only see the current row. "The total enrolled credits per student must not exceed 20" spans many rows and needs a trigger, an exclusion constraint, or application logic with proper locking.

NULL and Three-Valued Logic

NULL is SQL's marker for "no value here". It can mean unknown (Chen's grade exists but hasn't been entered), inapplicable (a closed_at for an open account) or not yet known. SQL does not distinguish these; it has one NULL for all of them. Codd later proposed two different markers; nobody implemented them.

Because NULL is not a value, any comparison with it yields neither TRUE nor FALSE but a third truth value, UNKNOWN. SQL logic is therefore three-valued (3VL).

The Truth Tables

NOT

pNOT p
TRUEFALSE
UNKNOWNUNKNOWN
FALSETRUE

AND (UNKNOWN AND FALSE is FALSE, because FALSE wins regardless)

ANDTRUEUNKNOWNFALSE
TRUETRUEUNKNOWNFALSE
UNKNOWNUNKNOWNUNKNOWNFALSE
FALSEFALSEFALSEFALSE

OR (UNKNOWN OR TRUE is TRUE, because TRUE wins regardless)

ORTRUEUNKNOWNFALSE
TRUETRUETRUETRUE
UNKNOWNTRUEUNKNOWNUNKNOWN
FALSETRUEUNKNOWNFALSE

A good mental model: treat UNKNOWN as "could be either". If the answer is the same whichever way the unknown resolves, you get a definite result; otherwise UNKNOWN.

The Rule That Causes Every Bug

WHERE, JOIN ... ON and HAVING keep a row only if the predicate is TRUE. UNKNOWN is treated like FALSE. CHECK constraints reject a row only if the predicate is FALSE; UNKNOWN passes.

That asymmetry explains most NULL surprises:

-- Eve has dept_code NULL. Which students are NOT in CS?
SELECT name FROM student WHERE dept_code <> 'CS';
-- Brian, Dana.  Eve is missing: NULL <> 'CS' is UNKNOWN.

SELECT name FROM student WHERE dept_code <> 'CS' OR dept_code IS NULL;
-- Brian, Dana, Eve.

-- PostgreSQL (and the SQL standard) has a NULL-safe comparison:
SELECT name FROM student WHERE dept_code IS DISTINCT FROM 'CS';
-- MySQL equivalent: WHERE NOT (dept_code <=> 'CS')

The NOT IN Trap

This is the classic interview question about NULL:

-- Students whose department is not one of the departments of 3-credit courses
SELECT name FROM student
WHERE dept_code NOT IN (SELECT dept_code FROM course WHERE credits = 3);
-- Returns Ada, Chen, Dana (CS, CS, PHYS). Fine.

-- Now a course with a NULL dept_code sneaks in (imagine the column were nullable):
-- NOT IN ('MATH', NULL) expands to dept_code <> 'MATH' AND dept_code <> NULL
-- The second comparison is UNKNOWN for every row, so the AND is never TRUE.
-- Result: zero rows. Silently.

x NOT IN (list) is x <> a AND x <> b AND ...; one NULL in the list makes the whole thing UNKNOWN or FALSE for every row. NOT EXISTS does not have this problem, because it tests whether rows exist, not whether values compare:

SELECT s.name FROM student s
WHERE NOT EXISTS (
  SELECT 1 FROM course c WHERE c.credits = 3 AND c.dept_code = s.dept_code
);

The NULL cheat sheet

  • NULL = NULL is UNKNOWN. Use IS NULL, IS NOT NULL, IS [NOT] DISTINCT FROM.
  • Arithmetic with NULL is NULL: 5 + NULL is NULL. String concatenation with || is NULL in PostgreSQL; MySQL's CONCAT() returns NULL too, but CONCAT_WS() skips NULLs.
  • Aggregates ignore NULLs, except COUNT(*). COUNT(grade) on Enrolled is 6, COUNT(*) is 7. AVG divides by the non-NULL count.
  • SUM over zero rows (or all NULLs) is NULL, not 0. Wrap with COALESCE(SUM(x), 0).
  • GROUP BY, DISTINCT, UNION, INTERSECT and EXCEPT treat NULLs as equal to each other (they form one group). Comparisons do not. Yes, it is inconsistent.
  • ORDER BY: PostgreSQL sorts NULLs last ascending (as if larger than everything); MySQL sorts them first. Use NULLS FIRST / NULLS LAST in PostgreSQL to be explicit; MySQL has no such clause, so use ORDER BY x IS NULL, x.

Relational Algebra

Relational algebra is a procedural query language: a set of operators that each take one or two relations as input and produce a relation as output. Because the output is always a relation, operators compose into expressions, exactly as arithmetic operators compose into formulas. This closure property is the whole trick.

You will never type relational algebra into a database. But every SQL query is parsed into a tree of these operators, the optimizer rewrites that tree using algebraic equivalences, and the executor runs a physical version of each node. When you read an EXPLAIN plan, you are reading relational algebra. See Query Planning & Optimization for the physical side.

flowchart BT
  E["Enrolled"] --> J["⋈ on sid"]
  S["Student"] --> J
  J --> SEL["σ grade = 'A'"]
  SEL --> P["π name"]

The tree above is π_name(σ_grade='A'(Student ⋈ Enrolled)): names of students with at least one A. Data flows bottom to top.

The Operators at a Glance

OperatorSymbolTypeInput → OutputSQL equivalent
Selectionσ_condition(R)Unary, fundamentalFilters rowsWHERE
Projectionπ_attributes(R)Unary, fundamentalKeeps columns, removes duplicatesSELECT DISTINCT cols
Renameρ_S(A,B,...)(R)Unary, fundamentalRenames relation and/or attributesAS
UnionR ∪ SBinary, fundamentalTuples in eitherUNION
Set differenceR − SBinary, fundamentalTuples in R not in SEXCEPT (MySQL 8.0.31+), NOT EXISTS
Cartesian productR × SBinary, fundamentalEvery pairingCROSS JOIN, FROM R, S
IntersectionR ∩ SDerived: R − (R − S)Tuples in bothINTERSECT
Theta joinR ⋈_θ SDerived: σ_θ(R × S)Pairings satisfying θJOIN ... ON θ
Equi-joinR ⋈_(R.a = S.b) STheta join with only =JOIN ... ON R.a = S.b
Natural joinR ⋈ SDerivedEqui-join on all same-named attributes, one copy keptNATURAL JOIN, JOIN ... USING
Outer joins⟕ ⟖ ⟗ExtendedJoin plus unmatched tuples padded with NULLLEFT, RIGHT, FULL OUTER JOIN
DivisionR ÷ SDerivedValues of R related to all of SDouble NOT EXISTS
AssignmentT ← exprNotationNames an intermediate resultWITH t AS (...)

The six fundamental operators are σ, π, ρ, ∪, −, ×. Everything else can be built from them. A query language that can express everything those six can is called relationally complete; SQL is (and more, with aggregation and recursion).

Selection (σ)

σ_p(R) returns the tuples of R that satisfy predicate p. The predicate uses comparisons (=, ≠, <, ≤, >, ≥) combined with ∧ (and), ∨ (or), ¬ (not). Selection never changes the schema; it only removes rows. Its output cardinality is at most |R|.

Example: CS students in year 3 or later.

σ_(dept_code = 'CS' ∧ year ≥ 3)(Student)

sidnamedept_codeyear
1AdaCS3
3ChenCS4
SELECT * FROM student WHERE dept_code = 'CS' AND year >= 3;

Selection is commutative and cascades: σ_p(σ_q(R)) = σ_q(σ_p(R)) = σ_(p ∧ q)(R). That equivalence lets the optimizer push filters around freely.

Projection (π)

π_(A1, ..., Ak)(R) keeps only the listed attributes and, because the result is a set, removes duplicates. Output degree is k; output cardinality is at most |R|.

Example: Which departments do students belong to?

π_dept_code(Student)

dept_code
CS
MATH
PHYS
NULL

Ada and Chen are both CS, but the result has one CS row. SQL needs DISTINCT to match:

SELECT DISTINCT dept_code FROM student;    -- relational projection
SELECT dept_code FROM student;             -- bag projection: CS appears twice

(Pure relational algebra has no NULL; we include it here because SQL would.)

Rename (ρ)

ρ_S(B1, ..., Bn)(R) returns R with the relation named S and the attributes renamed to B1..Bn. It does nothing to the data. It exists because operators like × and ⋈ need unambiguous names, and because a self-join requires two copies of the same relation with different names.

Example: Pairs of students in the same department.

ρ_S1(Student) ⋈_(S1.dept_code = S2.dept_code ∧ S1.sid < S2.sid) ρ_S2(Student)

SELECT s1.name AS student_a, s2.name AS student_b
FROM student AS s1
JOIN student AS s2
  ON s1.dept_code = s2.dept_code AND s1.sid < s2.sid;
-- Ada, Chen

s1.sid < s2.sid removes both self-pairs (Ada, Ada) and mirror pairs (Chen, Ada).

Union, Difference, Intersection

These are ordinary set operations, with one requirement: the two relations must be union-compatible, meaning same degree and compatible domains attribute by attribute. You cannot union Student with Course.

Example: sids of students who either take CS340 or are in year 1.

π_sid(σ_cid='CS340'(Enrolled)) ∪ π_sid(σ_year=1(Student)) → {1, 3} ∪ {4, 5} = {1, 3, 4, 5}

Example (difference): sids of students not enrolled in anything.

π_sid(Student) − π_sid(Enrolled) → {1, 2, 3, 4, 5} − {1, 2, 3, 4} = {5}

Example (intersection): sids of students taking both CS101 and CS340.

π_sid(σ_cid='CS101'(Enrolled)) ∩ π_sid(σ_cid='CS340'(Enrolled)) → {1, 3} ∩ {1, 3} = {1, 3}

SELECT sid FROM enrolled WHERE cid = 'CS340'
UNION
SELECT sid FROM student WHERE year = 1;

SELECT sid FROM student
EXCEPT
SELECT sid FROM enrolled;

SELECT sid FROM enrolled WHERE cid = 'CS101'
INTERSECT
SELECT sid FROM enrolled WHERE cid = 'CS340';

UNION, INTERSECT and EXCEPT remove duplicates; the ALL variants keep them with bag semantics. MySQL added INTERSECT and EXCEPT only in 8.0.31; on older MySQL use IN/EXISTS and NOT EXISTS/LEFT JOIN ... IS NULL.

Union and intersection are commutative and associative. Difference is neither: R − S ≠ S − R.

Cartesian Product (×)

R × S pairs every tuple of R with every tuple of S. Degree is degree(R) + degree(S); cardinality is |R| × |S|. If attribute names collide, qualify them (Student.dept_code, Course.dept_code) or rename first.

Student × Course has 5 × 4 = 20 tuples, most of them meaningless (Ada paired with Mechanics). The product is rarely useful on its own; it is the building block that joins are defined on.

SELECT * FROM student CROSS JOIN course;   -- 20 rows
SELECT * FROM student, course;             -- same thing, old syntax

The accidental cross join

Forgetting the join condition in old comma syntax (FROM orders, customers WHERE orders.total > 100) produces a Cartesian product. On two tables of a million rows each, that is a trillion-row intermediate result. Explicit JOIN ... ON syntax makes a missing condition a syntax error instead.

Joins (⋈)

Theta join: R ⋈_θ S = σ_θ(R × S). Any condition θ.

Example: For each student, the courses worth more credits than their year of study (a silly but legal theta join).

Student ⋈_(Course.credits > Student.year) Course

SELECT s.name, c.cid FROM student s JOIN course c ON c.credits > s.year;

Equi-join: a theta join whose condition uses only equality. Both join columns appear in the output.

Natural join: R ⋈ S is an equi-join on all attributes with the same name, keeping only one copy of each. Formally: π_(attrs of R ∪ attrs of S)(σ_(R.a1 = S.a1 ∧ ...)(R × S)). If R and S share no attribute names, the natural join degenerates to the Cartesian product.

Worked example: Student ⋈ Enrolled. The only shared attribute is sid.

sidnamedept_codeyearcidgrade
1AdaCS3CS101A
1AdaCS3CS340A
1AdaCS3MA201B
2BrianMATH2MA201A
3ChenCS4CS101B
3ChenCS4CS340NULL
4DanaPHYS1PH110C

Eve vanishes: she has no matching Enrolled tuple. That is the defining behaviour of an inner join.

SELECT * FROM student NATURAL JOIN enrolled;
SELECT * FROM student JOIN enrolled USING (sid);              -- same, explicit
SELECT * FROM student s JOIN enrolled e ON s.sid = e.sid;     -- equi-join, sid appears twice

Now the trap. Student ⋈ Course shares dept_code, so the natural join pairs each student with every course in their department, which is not "courses they take". And Student ⋈ Enrolled ⋈ Course joins on sid and then on both cid and dept_code, silently dropping enrollments where a student takes a course outside their department (Ada's MA201).

Avoid NATURAL JOIN in production SQL

NATURAL JOIN joins on whatever columns happen to share names. Add a created_at or status column to two tables and every natural join between them silently changes meaning. Use JOIN ... USING (col) or JOIN ... ON, which name the join columns explicitly. Natural join is a theory and exam tool.

Join properties. Inner joins are commutative (R ⋈ S = S ⋈ R, up to column order) and associative ((R ⋈ S) ⋈ T = R ⋈ (S ⋈ T)). That freedom is why the optimizer can choose any join order, and why join ordering is the hardest part of query optimization: n tables have a huge number of possible orders.

Outer Joins (⟕, ⟖, ⟗)

Inner joins drop tuples with no partner. Outer joins keep them and pad the missing side with NULL.

  • Left outer join R ⟕ S: all of R, matched with S where possible.
  • Right outer join R ⟖ S: all of S.
  • Full outer join R ⟗ S: all of both.

Worked example: every department and its courses, including departments with none.

Department ⟕ Course (on dept_code)

dept_codedept_namecidtitle
CSComputer ScienceCS101Intro to Programming
CSComputer ScienceCS340Databases
MATHMathematicsMA201Linear Algebra
PHYSPhysicsPH110Mechanics
BIOBiologyNULLNULL
SELECT d.dept_code, d.dept_name, c.cid, c.title
FROM department d
LEFT JOIN course c ON c.dept_code = d.dept_code;

-- The anti-join pattern: departments with no courses
SELECT d.dept_code
FROM department d
LEFT JOIN course c ON c.dept_code = d.dept_code
WHERE c.cid IS NULL;                            -- BIO

Outer joins are not in the six fundamental operators and are not associative in general, which restricts how optimizers can reorder them. MySQL does not support FULL OUTER JOIN; emulate it with a LEFT JOIN UNION a RIGHT JOIN (using UNION ALL plus an IS NULL filter on the second half to avoid deduplicating legitimate duplicate rows).

ON vs WHERE in an outer join

LEFT JOIN course c ON c.dept_code = d.dept_code AND c.credits = 4 keeps every department and only attaches 4-credit courses. Moving c.credits = 4 to WHERE filters out the NULL-padded rows (NULL = 4 is UNKNOWN), turning your left join back into an inner join. Conditions on the optional side belong in ON.

Semi-Join and Anti-Join

Two operators you will see in EXPLAIN output, though textbooks often skip them:

  • Semi-join R ⋉ S: tuples of R that have at least one match in S, without S's columns and without duplicating R. Equivalent to π_(attrs of R)(R ⋈ S). SQL: WHERE EXISTS (...) or WHERE x IN (subquery).
  • Anti-join R ▷ S: tuples of R with no match in S. Equivalent to R − (R ⋉ S). SQL: WHERE NOT EXISTS (...).

PostgreSQL plans show these as Hash Semi Join and Hash Anti Join.

Division (÷)

Division answers "for all" questions: which students take every CS course? Which suppliers supply all parts? It is the operator people find hardest, and it is a favourite in exams.

Definition. Let R(A, B) and S(B). Then R ÷ S is the set of A values such that for every b in S, the tuple (a, b) is in R.

Worked example. Which students are enrolled in every CS course?

R = π_sid,cid(Enrolled)          S = π_cid(σ_dept_code='CS'(Course))

sid | cid                        cid
----+------                      -----
 1  | CS101                      CS101
 1  | CS340                      CS340
 1  | MA201
 2  | MA201
 3  | CS101
 3  | CS340
 4  | PH110

Check each sid: 1 has CS101 and CS340, so yes. 2 has neither. 3 has both, so yes. 4 has neither. R ÷ S = {1, 3}.

Division in terms of fundamental operators. The trick is to compute the students who fail and subtract them:

  1. All candidate students: T1 ← π_sid(R) = {1, 2, 3, 4}
  2. Every combination they should have: T2 ← T1 × S (8 tuples)
  3. Combinations that are missing: T3 ← T2 − R = {(2, CS101), (2, CS340), (4, CS101), (4, CS340)}
  4. Students with something missing: T4 ← π_sid(T3) = {2, 4}
  5. Answer: T1 − T4 = {1, 3}

So R ÷ S = π_A(R) − π_A((π_A(R) × S) − R).

SQL has no division operator. The two standard translations:

-- 1. Double NOT EXISTS: "there is no CS course that this student does not take"
SELECT s.sid, s.name
FROM student s
WHERE NOT EXISTS (
  SELECT 1 FROM course c
  WHERE c.dept_code = 'CS'
    AND NOT EXISTS (
      SELECT 1 FROM enrolled e
      WHERE e.sid = s.sid AND e.cid = c.cid
    )
);

-- 2. Counting: the student's CS course count equals the total CS course count
SELECT e.sid
FROM enrolled e
JOIN course c ON c.cid = e.cid
WHERE c.dept_code = 'CS'
GROUP BY e.sid
HAVING COUNT(DISTINCT e.cid) = (SELECT COUNT(*) FROM course WHERE dept_code = 'CS');

The double NOT EXISTS is a direct transcription of the logic "for all x, P(x)" ≡ "there is no x such that not P(x)". The counting version is often faster and easier to read, but it relies on the inner join restricting to exactly the divisor set; get the filter wrong and it silently counts the wrong things.

Division by an empty set

If there are no CS courses, then every student vacuously takes all of them. The double NOT EXISTS returns every student (correct by logic, surprising to humans). The counting version returns no one, since no student has any CS rows in the join. Decide which you mean.

Putting It Together: A Multi-Step Query

Question: names of students who got an A in some course offered by a department other than their own.

Step by step, using assignment:

  1. T1 ← σ_grade='A'(Enrolled)
  2. T2 ← T1 ⋈_(T1.cid = Course.cid) Course (attach the course's department)
  3. T3 ← T2 ⋈_(T2.sid = Student.sid ∧ Course.dept_code ≠ Student.dept_code) Student
  4. Result ← π_name(T3)

Brian's A in MA201 is in his own department (MATH). Ada's As are both in CS. Nobody qualifies: the result is empty. Change Ada's MA201 grade to A and she appears.

SELECT DISTINCT s.name
FROM enrolled e
JOIN course  c ON c.cid = e.cid
JOIN student s ON s.sid = e.sid
WHERE e.grade = 'A'
  AND c.dept_code <> s.dept_code;

Algebraic Equivalences the Optimizer Uses

Because each operator has well-defined semantics, a database can rewrite an expression into a cheaper but equivalent one. The most important rules:

RuleEquivalenceWhy it helps
Push selection below joinσ_p(R ⋈ S) = σ_p(R) ⋈ S, when p uses only R's attributesJoin fewer rows
Split conjunctionsσ_(p ∧ q)(R) = σ_p(σ_q(R))Lets each part be pushed separately
Push projection downπ_L(R ⋈ S) = π_L(π_(L1)(R) ⋈ π_(L2)(S)), keeping join attributesNarrower intermediate tuples
Join commutativityR ⋈ S = S ⋈ RPick the smaller side as the build side of a hash join
Join associativity(R ⋈ S) ⋈ T = R ⋈ (S ⋈ T)Join order search
Selection + product = joinσ_θ(R × S) = R ⋈_θ SNever actually build the product

The first rule, predicate pushdown, is the single biggest win in practice and the reason the logical order of your SQL clauses has little to do with the execution order.

Relational Calculus (Briefly)

Relational algebra says how to compute an answer, as a sequence of operations. Relational calculus says what the answer is, as a logical formula that tuples in the result must satisfy. SQL's surface syntax is closer to calculus: you describe the rows you want and the optimizer picks the operations.

Tuple relational calculus (TRC) uses variables that range over tuples:

{ t.name | t ∈ Student ∧ ∃ e ∈ Enrolled (e.sid = t.sid ∧ e.grade = 'A') }

"The names of student tuples t for which there exists an enrollment e with t's sid and grade A." Compare the SQL:

SELECT t.name FROM student t
WHERE EXISTS (SELECT 1 FROM enrolled e WHERE e.sid = t.sid AND e.grade = 'A');

Division becomes universal quantification:

{ t.sid | t ∈ Student ∧ ∀ c ∈ Course (c.dept_code = 'CS' ⇒ ∃ e ∈ Enrolled (e.sid = t.sid ∧ e.cid = c.cid)) }

SQL has no FOR ALL, which is exactly why you rewrite ∀ as ¬∃¬, producing the double NOT EXISTS.

Domain relational calculus (DRC) uses variables that range over attribute values instead of whole tuples: { ⟨n⟩ | ∃ s, d, y (⟨s, n, d, y⟩ ∈ Student ∧ d = 'CS') }. It is the basis of Query-By-Example (QBE), the grid-style query builders in tools like Microsoft Access.

Safety. A calculus expression like { t | ¬(t ∈ Student) } describes an infinite set: every possible tuple that is not a student. Such expressions are unsafe. Restricted to safe expressions (results drawn only from values that appear in the database or the query), Codd's theorem says relational algebra, safe TRC and safe DRC have exactly the same expressive power. That equivalence is what makes declarative SQL possible: any "what" you can write has a "how" the optimizer can find.

Relational algebraRelational calculus
StyleProcedural: a sequence of operationsDeclarative: a logical condition
Building blocksσ, π, ρ, ∪, −, ×Variables, ∧, ∨, ¬, ∃, ∀
Closest SQL featureJoins, UNION, the EXPLAIN planWHERE EXISTS, the query as written
Used byOptimizers and executorsQuery language design, QBE

What Algebra Cannot Do

Classic relational algebra cannot express aggregation (COUNT, SUM) or transitive closure (all ancestors of a node in a hierarchy, all reachable stops on a transit map). Extended algebras add a grouping operator γ (γ_(dept_code; COUNT(sid))(Student)), and SQL:1999 added recursive common table expressions for closure:

WITH RECURSIVE chain AS (
  SELECT emp_id, manager_id, 1 AS depth FROM employee WHERE emp_id = 42
  UNION ALL
  SELECT e.emp_id, e.manager_id, c.depth + 1
  FROM employee e JOIN chain c ON e.emp_id = c.manager_id
)
SELECT * FROM chain;    -- employee 42 and every manager above them

Advanced SQL covers recursive CTEs and window functions in depth.

Codd's Rules (Briefly)

By the mid-1980s, every vendor was calling its product "relational". In 1985 Codd published twelve rules (numbered 0 to 12, so thirteen in total) to define what that word should mean. No commercial system satisfies all of them; they are a yardstick, not a checklist anyone passed.

#RuleGist
0FoundationThe system must manage data entirely through its relational capabilities
1InformationAll information is represented as values in tables
2Guaranteed accessEvery value is reachable by table name + primary key + column name
3Systematic NULL treatmentA uniform representation for missing information, distinct from any value
4Active online catalogMetadata lives in tables, queryable with the same language (information_schema, pg_catalog)
5Comprehensive data sublanguageOne language for definition, manipulation, constraints and transactions
6View updatingAll theoretically updatable views are updatable by the system
7High-level insert, update, deleteSet-at-a-time operations, not just row-at-a-time
8Physical data independenceChanging storage or access methods does not break applications
9Logical data independenceChanging the logical schema (e.g. splitting a table) need not break applications, where possible
10Integrity independenceConstraints are defined in the catalog, not in application programs
11Distribution independenceApplications work the same whether data is centralized or distributed
12Non-subversionLow-level interfaces cannot bypass integrity rules

The ones that matter most in practice are 8 and 9, data independence. Rule 8 is why you can add an index, partition a table, or move to a new storage engine without changing a single query. Rule 9 is why views exist. Rule 12 is broken by every database that lets you disable foreign-key checks for bulk loads.

Why the Relational Model Won

Before 1970, databases were navigational. IBM's IMS (hierarchical) and CODASYL systems (network model) stored records linked by physical pointers. A program found data by walking those links: "find the customer, then follow the first-order pointer, then follow next-order until you reach the one you want". Every query was a hand-written traversal.

flowchart LR
  subgraph NAV["Navigational, 1960s"]
    direction TB
    C1["Customer record"] -->|"pointer"| O1["Order 1"]
    O1 -->|"next"| O2["Order 2"]
    O2 -->|"next"| O3["Order 3"]
  end
  subgraph REL["Relational, 1970+"]
    direction TB
    Q["SELECT * FROM orders WHERE customer_id = 7"] --> OPT["Optimizer picks access path"]
    OPT --> T["Tables + indexes"]
  end

The relational model won for reasons that are still the reasons to choose it today:

  1. Data independence. Applications describe what, not how. Add an index, the queries get faster; nothing else changes. In a navigational system, reorganizing storage meant rewriting programs.
  2. Ad-hoc queries. Any question expressible in the algebra can be asked, including ones nobody anticipated when the schema was designed. Navigational databases could only efficiently answer the questions their pointer structure was built for.
  3. A mathematical foundation. Set theory and first-order logic gave a precise semantics. Precise semantics enabled query optimization (provably equivalent rewrites), normalization theory and constraint theory.
  4. Declarative integrity. Keys and foreign keys are declared once, in the schema, and enforced for every program.
  5. The optimizer kept getting better. The early objection was "it'll be too slow". IBM's System R (1974–79) showed cost-based optimization could match hand-coded navigation, and Oracle (1979) and DB2 (1983) took it commercial. Every hardware improvement since has accrued to the optimizer, not to application code.
  6. SQL became a standard (ANSI 1986, ISO 1987). Skills, tools and drivers became portable.

Challengers came and mostly folded back in. Object databases (1990s) lost, but their ideas became JSON columns, arrays and user-defined types. NoSQL (2009 onward) traded joins and transactions for horizontal scale and flexible schemas; many of those systems have since added SQL-like query languages and transactions, and NewSQL systems brought the relational model to distributed storage. See Database Selection Guide and NewSQL.

Common Misconceptions

MisconceptionReality
"Relational" means the tables have relationshipsThe relation is the table itself (a mathematical relation). Relationships are modelled by foreign keys, but the name comes from set theory
A primary key must be a single columnIt can be composite. It must be minimal and non-null
A foreign key must reference a primary keyIt can reference any UNIQUE column set
UNIQUE means one NULL allowedIn PostgreSQL and MySQL, a UNIQUE column allows many NULLs
NOT IN is the opposite of INIt is, until the subquery returns a NULL; then NOT IN returns nothing
SQL follows the relational model exactlySQL uses bags, has NULLs, has column order, and allows tables without keys
Natural join means "the obvious join"It joins on every shared column name, which is often not what you meant

Interview Questions

1. What is the difference between a superkey, a candidate key and a primary key? A superkey is any attribute set that uniquely identifies tuples. A candidate key is a minimal superkey: no proper subset is unique. The primary key is the candidate key the designer chooses as the main identifier; the rest are alternate keys, declared UNIQUE NOT NULL.

2. Given R(A, B, C, D, E) with A → BC, CD → E, B → D, E → A, find the candidate keys. Compute closures. A+ = {A, B, C, D, E} (A gives BC, B gives D, CD gives E). So A is a key. E → A, so E is a key. CD gives E, so CD is a key. BC: B gives D, CD gives E, E gives A, so BC is a key. Check that B, C and D alone are not keys (B+ = {B, D}, C+ = {C}, D+ = {D}). Candidate keys: A, E, CD, BC.

3. Why does SELECT * FROM t WHERE x NOT IN (SELECT y FROM u) return no rows? Because some u.y is NULL. x NOT IN (a, NULL) means x <> a AND x <> NULL, and x <> NULL is UNKNOWN, so the predicate is never TRUE. Use NOT EXISTS or filter WHERE y IS NOT NULL in the subquery.

4. What is the difference between ON DELETE CASCADE, SET NULL and RESTRICT? When would you use each? CASCADE deletes children with the parent (order lines with an order). SET NULL detaches children from an optional parent (an employee whose manager left). RESTRICT or NO ACTION blocks deleting a parent that still has children (a customer with invoices), forcing an explicit decision.

5. Express "students enrolled in every CS course" in relational algebra and in SQL. π_(sid,cid)(Enrolled) ÷ π_cid(σ_(dept_code='CS')(Course)). In SQL, a double NOT EXISTS: students for whom there is no CS course they are not enrolled in. Alternatively, group by student and compare COUNT(DISTINCT cid) to the number of CS courses.

6. What are the six fundamental operators of relational algebra, and how is a join derived from them? Selection, projection, rename, union, set difference, Cartesian product. A theta join is σ_θ(R × S). A natural join additionally projects away the duplicate join columns, with renames where needed.

7. What does COUNT(*) vs COUNT(col) return when col has NULLs? COUNT(*) counts rows. COUNT(col) counts non-NULL values of col. Every aggregate except COUNT(*) ignores NULLs.

8. Surrogate or natural primary key? Usually a surrogate primary key for stable, narrow foreign keys, plus a UNIQUE constraint on the natural key to enforce the business rule. Use natural keys only when they are truly immutable and compact, like ISO currency codes.

9. Why can an optimizer reorder joins but not always outer joins? Inner joins are commutative and associative, so any order gives the same result. Outer joins are not associative in general (the NULL padding depends on what has been joined so far), so only certain reorderings are valid.

10. What is relational completeness, and is SQL relationally complete? A language is relationally complete if it can express every query relational algebra can. SQL is, and more: it adds aggregation, ordering, window functions and recursion, none of which classic algebra has.

Summary

ConceptOne-line version
RelationA set of tuples over named attributes with domains; SQL tables are bags
Candidate keyMinimal superkey; the primary key is the chosen one
Foreign keyReferences a candidate key in another (or the same) table, or is NULL
Entity integrityPrimary key attributes are never NULL
Referential integrityNo dangling foreign keys; ON DELETE decides what happens to children
Three-valued logicComparisons with NULL are UNKNOWN; WHERE keeps only TRUE
σ, π, ρ, ∪, −, ×The six fundamental operators; joins, intersection and division derive from them
Division"For all" queries; double NOT EXISTS in SQL
Relational calculusDeclarative counterpart, equally expressive (Codd's theorem)
Why it wonData independence, ad-hoc queries, a provable foundation, and optimizers

Where to Go Next