Relational Algebra

Origin. Edgar F. Codd introduced the relational model and relational algebra (1970) at IBM. Provided a mathematical foundation for database systems, replacing navigational models (hierarchical, network) with declarative queries. Basis for SQL. Turing Award 1981.

Models. Data as relations (tables). Queries as algebraic operations on relations. A relation is a set of tuples; operations combine relations to produce new relations. The algebra is closed: every operation takes relations in, produces a relation out. Core question: how to express and optimize data retrieval?

Formalism.

Relations: A relation R on attributes A₁, ..., Aₙ is a subset of dom(A₁) × ... × dom(Aₙ). Each row (tuple) assigns values to attributes. Relations are sets: no duplicate rows, order doesn't matter.

Primitive operations:

Selection (σ): σ_condition(R) — filter rows satisfying condition σ_{age>30}(Employees) — employees older than 30
Projection (π): π_attributes(R) — select columns π_{name,salary}(Employees) — just name and salary
Cartesian product (×): R × S — all combinations of rows
Union (∪): R ∪ S — rows in R or S (requires same schema)
Difference (−): R − S — rows in R but not S
Rename (ρ): ρ_{new←old}(R) — rename attributes

Derived operations:

Join (⋈): R ⋈_condition S — cross product filtered by condition
Natural join (⋈): R ⋈ S — join on common attribute names, no duplicates
Intersection (∩): R ∩ S = R − (R − S)
Division (÷): R ÷ S — tuples in R matching all tuples in S

Extended operations (for practical SQL):

Aggregation: sum, count, avg, min, max
Grouping: γ_{group-attrs, agg}(R)
Outer joins: preserve unmatched rows with nulls

Symbols.

Symbol	Unicode	Name	Meaning
σ	U+03C3	Selection	Filter rows
π	U+03C0	Projection	Select columns
×	U+00D7	Cartesian product	All row combinations
∪	U+222A	Union	Set union of rows
−	U+2212	Difference	Set difference
∩	U+2229	Intersection	Common rows
⋈	U+22C8	Join	Combine matching rows
ρ	U+03C1	Rename	Rename attributes
÷	U+00F7	Division	"For all" query pattern
γ	U+03B3	Grouping	Group and aggregate
⟕	U+27D5	Left outer join	Preserve left rows
⟖	U+27D6	Right outer join	Preserve right rows
⟗	U+27D7	Full outer join	Preserve all rows

Metatheory. Relational algebra is equivalent in expressive power to domain relational calculus and tuple relational calculus (Codd's theorem). All are captured by first-order logic over finite structures. Relational algebra is not Turing-complete: cannot express transitive closure (reachability) without recursion. Datalog extends with recursion. Query optimization: algebraic identities enable rewriting queries to equivalent but more efficient forms (push selections down, reorder joins).

Applies to. Database query languages (SQL is based on relational algebra). Query optimization. Data integration. Formal specification of data operations. Theoretical foundations of databases.

Limitations. Cannot express recursive queries (transitive closure, bill of materials) without extensions. No built-in support for nulls, which SQL adds with three-valued logic. Set semantics differs from SQL's bag (multiset) semantics in practice. Real databases have indexes, transactions, constraints — relational algebra is the query core, not the whole system. Schema evolution and data integrity constraints are outside the algebra. Performance depends on physical implementation, not algebraic form.