Relational Algebra and Calculus
Relational algebra and relational calculus are the theoretical query languages of the relational model. Algebra is procedural—it specifies step-by-step operations—while calculus is declarative—it describes desired results. Both are equivalent in expressive power and underlie SQL.
Selection (σ)
The selection operator σp(R) returns the tuples of R that satisfy predicate p. For example, σAge > 20(Students) selects students older than 20. Predicates may combine comparisons with AND, OR, and NOT.
Projection (π)
The projection operator πA1, A2, ...(R) produces the relation containing only the specified attributes. Because relations contain no duplicates, projection automatically eliminates duplicate tuples. The combination π of σ implements the classic SELECT-WHERE pattern.
Set Operations
Relations are sets, so union (∪), intersection (∩), and difference (−) apply between union-compatible relations—relations with the same number of attributes and compatible domains. These operators give the algebra a set-theoretic foundation.
Cartesian Product (×)
R × S produces every combination of a tuple from R with a tuple from S. On its own the product is rarely useful; it becomes powerful when combined with selection to produce joins.
Join Operations
The theta-join R ⋈θ S selects tuples of R × S satisfying predicate θ. The natural join joins on equality of attributes with the same name and removes duplicate columns. Outer joins—left, right, and full—preserve unmatched tuples by padding with nulls. Joins are the workhorse of relational queries.
Division
The division operator R ÷ S answers queries of the form "find tuples in R associated with every tuple in S". It is the algebraic analogue of universal quantification and is used to express queries such as "students who have taken every required course".
Rename and Assignment
The rename operator ρ changes attribute names, which is sometimes necessary to avoid ambiguity in self-joins. The assignment operator stores intermediate results in named relations, improving readability of complex queries.
Tuple Relational Calculus
Tuple relational calculus expresses queries of the form { t | P(t) }, where t is a tuple variable and P is a predicate. For example, { t | t ∈ Students ∧ t.Age > 20 } returns students older than 20. Quantifiers ∀ and ∃ support powerful queries. Expressions must be safe (yielding finite results).
Domain Relational Calculus
Domain relational calculus uses domain variables rather than tuple variables: { (n, a) | ∃ t ∈ Students (t.Name = n ∧ t.Age = a ∧ a > 20) }. QBE (Query-By-Example) is a graphical interface based on this formalism.
Equivalence and Completeness
Relational algebra and (safe) calculus are equivalent in expressiveness: any query expressible in one can be expressed in the other. A query language that can express all queries in relational algebra is called relationally complete. SQL achieves this while adding practical features like aggregation, grouping, and procedural extensions.
Summary
Algebra and calculus give a rigorous foundation for understanding database queries. Every SQL query compiles to an algebra expression internally, and understanding these operators is essential for writing correct queries and understanding query optimization.