Relational algebra is a formal mathematical framework for querying and manipulating relations (tables) in a relational database. It provides a set of fundamental operations (such as selection, projection, join, and set operations) that take relations as input and produce a new relation as output, ensuring closure under the relational model. Developed by Edgar F. Codd as part of his relational data model, relational algebra serves as the theoretical basis for SQL and is a core topic in database theory and discrete mathematics.
1 Fundamental concepts
1.1 Relation as a set of tuples
A relation is a nonempty set of tuples, where each tuple represents an ordered list of attribute values. Tuples are unordered and duplicates are not allowed in the pure relational model; every relation is a set in the mathematical sense.
1.2 Schema and attribute naming
Each relation has a schema that defines its name and a set of attribute names (columns). Every attribute is associated with a domain (data type). The schema remains fixed for a given relation instance, though the set of tuples can change over time.
1.3 Closure property of operations
Every relational algebra operation takes one or more relations as input and produces a new relation as output. This closure property allows operations to be composed arbitrarily, forming complex queries by nesting or sequencing simple operations.
2 Basic unary operations
2.1 Selection (σ)
Selection filters tuples of a relation based on a predicate condition. It retains only those tuples for which the condition evaluates to true. The result has the same schema as the input relation.
2.1.1 Predicate conditions
A predicate can compare an attribute to a constant (e.g., salary > 50000) or compare two attributes (e.g., birth_year < hire_year). Comparisons use operators =, <, >, ≤, ≥, and ≠.
2.1.2 Boolean combinations (AND, OR, NOT)
Multiple conditions can be combined using logical AND (∧), OR (∨), and NOT (¬). For example, σ(age > 30 ∧ dept = 'Sales') selects employees older than 30 in the Sales department.
2.2 Projection (π)
Projection selects a subset of attributes (columns) from a relation. It removes all other attributes and, because the result is a set, eliminates duplicate tuples.
2.2.1 Attribute removal and ordering
The projection operation specifies which attributes to retain. The order of attributes in the result follows the order listed in the operation; attributes not listed are dropped.
2.2.2 Duplicate elimination
Since the output must be a set, any duplicate tuples arising from projecting onto a smaller set of columns are automatically removed. This contrasts with SQL’s default bag semantics.
2.3 Renaming (ρ)
Renaming changes the names of attributes or the relation itself without altering the data.
2.3.1 Renaming attributes
A rename operation ρ(new_attr1, new_attr2, … / old_attr1, old_attr2, …)(R) modifies the attribute names of relation R. This is useful for disambiguating attribute names in joins and for aligning schemas.
2.3.2 Renaming relations
A relation can be given a new name, e.g., ρ(S)(R) renames relation R to S. The tuple set remains unchanged.
3 Binary set operations
3.1 Union (∪)
The union of two relations R and S, denoted R ∪ S, contains all tuples that belong to either R or S (or both). Duplicate tuples appear only once.
3.1.1 Compatibility requirement (union-compatibility)
For R and S to be union-compatible, they must have the same number of attributes, and the corresponding attributes must be defined over the same domain (or compatible domains). The attribute names need not match, but the positional correspondence is assumed.
3.2 Intersection (∩)
The intersection R ∩ S contains tuples present in both R and S. It also requires union-compatibility.
3.3 Set difference (−)
The difference R − S contains all tuples that are in R but not in S. Again, the operands must be union-compatible.
3.4 Cartesian product (×)
The Cartesian product (or cross join) R × S combines every tuple of R with every tuple of S. The result relation has all attributes from R followed by all attributes from S.
3.4.1 Pairwise combination of tuples
If R has m tuples and S has n tuples, then R × S contains m × n tuples. Each tuple is the concatenation of one R‑tuple and one S‑tuple.
3.4.2 Handling attribute naming conflicts
When R and S share attribute names, the result must disambiguate them. Typically they are qualified by the original relation name (e.g., R.A, S.A) or automatically renamed. Some formalisms rename attributes to avoid duplicates.
4 Relational join operations
4.1 Theta join (⋈_θ)
A theta join is a Cartesian product followed by a selection with a condition θ. It combines tuples from two relations where the condition holds.
4.1.1 General condition join
The condition θ can involve any comparison (e.g., R.A < S.B). The result includes all attributes from both relations, with conflicting attribute names resolved as in the Cartesian product.
4.2 Equijoin
An equijoin is a theta join where the condition consists solely of equality comparisons (e.g., R.A = S.B). It is the most common form of join.
4.2.1 Natural join (⋈)
The natural join is an equijoin over all pairs of attributes with the same name in the two relations, and it eliminates one copy of each duplicate attribute. For example, if both relations have an attribute named "id", the natural join compares id = id and produces a result with a single id column.
4.3 Outer joins
Outer joins preserve tuples that do not satisfy the join condition by padding the missing side with null values.
4.3.1 Left outer join (⟕)
The left outer join includes all tuples from the left relation. When no matching tuple exists in the right relation, attributes from the right are filled with nulls.
4.3.2 Right outer join (⟖)
The right outer join includes all tuples from the right relation, padding the left side with nulls where no match occurs.
4.3.3 Full outer join (⟗)
The full outer join combines the effects of both left and right outer joins, preserving all tuples from both relations and inserting nulls where matches are missing.
4.4 Semijoin (⋉)
The semijoin R ⋉ S returns only the attributes of R for those R‑tuples that have at least one matching tuple in S based on the natural join condition. It is a weaker operation than a full join and is used in distributed query processing to reduce data transfer.
4.5 Antijoin (▷)
The antijoin R ▷ S returns those tuples of R that have no matching tuple in S (using natural join condition). It is equivalent to set difference after a semijoin but is often defined as a primitive in some algebraic systems.
5 Extended operations
5.1 Division (÷)
The division operator R ÷ S answers queries of the form “find all values that appear with every value in S.” It returns a relation whose tuples combine with every tuple of S to produce a tuple in R.
5.1.1 Quotient and remainder relation
If R has attributes A and B, and S has attribute B only, then R ÷ S yields a relation over A whose tuples, when joined with S, produce a subset of R. The remainder is the part of R that does not satisfy the division.
5.2 Generalized projection (π with aggregation)
Generalized projection extends the basic projection by allowing expressions that include aggregate functions. It can compute computed columns such as salary + bonus.
5.2.1 Aggregation functions (count, sum, avg, min, max)
Standard functions include COUNT (number of tuples), SUM (sum of values), AVG (average), MIN (minimum), and MAX (maximum). They operate on sets of attribute values and return a single scalar.
5.2.2 Grouping operator (G)
The grouping operator γ groups tuples by one or more attributes and applies aggregation functions within each group. For example, γ(dept, AVG(salary))(Employee) returns the average salary per department.
5.3 Outer union and disjunctive semantics
The outer union extends the union operation to relations that are not union‑compatible. Missing attributes in one relation are padded with nulls. It is sometimes used in integration scenarios and is related to the disjunctive semantics of natural joins in some database theories.
6 Equivalence and rewriting rules
6.1 Commutativity and associativity of operations
Several operations are commutative or associative. For example, union and intersection are both commutative (R ∪ S ≡ S ∪ R) and associative ((R ∪ S) ∪ T ≡ R ∪ (S ∪ T)). The Cartesian product and natural join are also commutative and associative. Selection is commutative under conjunction: σc1(σc2(R)) ≡ σc2(σc1(R)).
6.2 Distributive laws
Selection distributes over union, intersection, and set difference: σ(R ∪ S) ≡ σ(R) ∪ σ(S) (when the condition applies to both schemas). Projection distributes over union: π(R ∪ S) ≡ π(R) ∪ π(S) (provided the schemas are compatible).
6.3 Selection pushdown and pullup optimization
A key query optimization technique is to push selections as close as possible to the base relations, reducing the size of intermediate results. Conversely, pulling selections up can sometimes enable other rewrites. These rules are fundamental in cost‑based query optimizers.
6.4 Projection elimination and introduction
If an intermediate result is later projected to a subset of attributes, early projection can remove unnecessary columns. Conversely, introducing a projection (e.g., before a join) may reduce the number of attributes carried through computation. The transformation must respect equivalence under the overall query.
7 Relationship to SQL and practical databases
7.1 Mapping from relational algebra to SQL queries
Every relational algebra expression can be translated into an equivalent SQL query. For example, selection σcondition(R) corresponds to SELECT * FROM R WHERE condition; projection πattrs(R) to SELECT attrs FROM R; and join R ⋈ S to SELECT * FROM R JOIN S ON condition. Aggregation and grouping are expressed via GROUP BY and aggregate functions.
7.2 Limitations and extensions (bag semantics)
SQL operates on multisets (bags) rather than sets, so duplicates are preserved by default. Relational algebra’s set semantics can be extended to bag semantics (e.g., “bag projection” without duplicate elimination). Additionally, SQL supports null markers, outer joins, and ordering, which are not part of the classical relational algebra but have been formalized in extended algebras.
8 Historical context and theoretical significance
8.1 Codd’s original formulation (1970)
Edgar F. Codd introduced the relational model and relational algebra in his seminal 1970 paper “A Relational Model of Data for Large Shared Data Banks.” He defined eight operations: union, intersection, difference, Cartesian product, selection, projection, join, and division. This formal foundation separated the logical structure of data from physical storage.
8.2 Influence on relational database design
Relational algebra directly influenced the design of query languages such as SQL (originally SEQUEL), QUEL, and QBE. The algebra’s closure property enabled nested queries and modular query composition. It also provided a basis for query optimization through algebraic rewriting rules.
8.3 Connection to predicate logic and domain calculus
Relational algebra is equivalent in expressive power to the relational calculus (both tuple and domain variants), which are based on first‑order predicate logic. The equivalence was established by Codd’s theorem, demonstrating that any query expressible in the algebra can also be expressed in a safe subset of the calculus, and vice versa. This link rooted relational querying in formal logic.