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.

Metatheory. Codd's theorem (1972) is the fundamental result: relational algebra, tuple relational calculus and domain relational calculus express exactly the same queries, provided the calculi are restricted to domain-independent formulas, since an unrestricted calculus expression can denote something depending on the underlying domain rather than on the database. That shared expressive power is first-order logic over finite structures, which fixes both what the algebra can and cannot do. Aho and Ullman (1979) showed transitive closure is not expressible; Ehrenfeucht–Fraïssé games and locality arguments give the same verdict for any query needing unbounded recursion, and Datalog is the standard repair. Complexity splits by parameter: data complexity is in AC⁰ and hence in LOGSPACE, while combined complexity is PSPACE-complete (Vardi 1982). Query equivalence is undecidable for the full algebra, but Chandra and Merlin (1977) proved containment and equivalence of conjunctive queries decidable and NP-complete, characterized by existence of a homomorphism — the theorem optimizers rest on.

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 — and once nulls are present the algebraic identities the optimizer relies on stop holding, since σ_p(R) ∪ σ_{¬p}(R) no longer recovers R. Set semantics differs from SQL's bag (multiset) semantics in practice, so duplicate elimination changes results that the algebra treats as equal. 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.

© 2026 Lingenic LLC