10 — Relational Algebra: The Seven Primitives

Codd's 1970s paper defined seven primitives intended to express any query over a relational database (47:44).

• Caveat stated up front: this is not entirely true — the original set handles no sorting, aggregation, or GROUP BY. Those were added later (47:44).
• Operators chain: the input to any operator is either a base relation or the output of another operator (48:16, 48:29).

Quick reference

Operator	Symbol	Meaning	SQL equivalent
Select	σ	Filter tuples by a predicate	WHERE clause
Projection	π	Choose/reorder/transform output attributes	SELECT list
Union	∪	Concatenate two relations	UNION / UNION ALL
Intersection	∩	Tuples present in both	INTERSECT
Difference	−	Tuples in the first but not the second	EXCEPT
Cartesian product	×	All combinations of tuples	CROSS JOIN
Join	⋈	Matching tuples across relations	JOIN ... ON

1. Select (σ)

• First-order predicate logic identifying which tuples to keep; non-matching tuples are dropped, matches are emitted (48:29, 48:54).
• Predicates combine with conjunctions and disjunctions — e.g. a_id = 'a2' AND b_id > 102 (49:28).
• Mnemonic offered: lowercase σ (sigma) → S for Select (49:47).
• SQL: SELECT * FROM R WHERE <predicate> (49:47).

2. Projection (π)

• Defines what the output looks like: which attributes come through, in what order, and how they are transformed (50:10).
• Example: π(b_id − 100, a_id) applied to the output of σ(a_id = 'a2')(R) (50:10).
• Supports arithmetic, string functions, reordering — anything (51:06).
• SQL: the projection clause of a SELECT (51:06).

3. Union (∪)

• Concatenates R and S: takes R and puts S underneath it (51:20, 51:48).
• Requires identical attributes with identical types (51:48).
• Duplicate handling differs between theory and SQL (52:28):
  • Relational model: duplicates are removed.
  • SQL: UNION removes duplicates, UNION ALL keeps them — the default is set up so the system avoids the extra deduplication work when you don't need it.

Ordering is undefined

• The relational model and SQL leave result order undefined — tuples can come back in a different order than inserted (53:21).
• This is a feature: it opens up optimization opportunities, since the system need not preserve order (53:21).
• Concrete cause: a background garbage collector during transaction processing can reorder tuples arbitrarily (53:54).
• If order matters, use ORDER BY — which the original relational model did not have (53:54).

4. Intersection (∩)

• Tuples appearing in both relations; requires matching attributes (54:20).
• SQL: INTERSECT.

5. Difference (−)

• Tuples in the first relation but not the second — plain set theory (54:37).
• SQL: EXCEPT (54:37).

Union, intersection, and difference all require the same columns on both sides. Joins do not (55:33).

6. Cartesian product (×)

• Every tuple of R paired with every tuple of S (55:49).
• Real uses: generating all input combinations for experiments and testing (56:30).
• Theoretical importance: it is the basis of joins (56:48).
• SQL: SELECT * FROM R CROSS JOIN S, or the (not-recommended) comma-separated table list (57:06).

7. Join (⋈)

• Finds all matches between relations on the given attributes; unlike intersection, the two schemas need not be identical (57:28).
• Mechanically: mash the two tuples together, check that the matching attributes agree, then discard the duplicate attributes. Non-key attributes "come along for the ride" (57:57, 58:15).
• Joins are where DBMSs spend most of their query time — the single biggest optimization target, with a whole lecture devoted to them (58:32).

Natural join vs. explicit join

• NATURAL JOIN matches implicitly on identically named columns. Not recommended — it infers the join condition instead of stating it (58:47, 59:35).
• Prefer JOIN ... USING (...) or, best, JOIN ... ON R.a_id = S.a_id AND R.b_id = S.b_id — explicit, carries more information, and survives schema evolution without breaking application code (58:47, 59:35, 59:49).

Later additions (post-Codd)

Rename, assigning relations to variables, duplicate elimination, aggregation, sorting, and division. Most systems implement everything except division (59:49, 1:00:23).