Relational Algebra – Complete Guide

Relational Algebra

A formal, procedural query language for the relational database model — the mathematical foundation behind SQL.

Relational algebra consists of operations that take one or two relations (tables) as input and produce a new relation as output. Because every operation returns a relation, operators can be nested and combined to build complex queries — exactly like SQL.

Core Operators at a Glance

Unary · Selection

Selection

Filters rows. Returns tuples that satisfy a Boolean condition. Think horizontal partition.

Unary · Projection

Projection

Filters columns. Keeps only selected attributes and auto-eliminates duplicates. Think vertical partition.

Unary · Rename

Rename

Renames elements. Changes a relation's name and/or its attribute names — essential for self-joins.

∪

Set · Union

Union

Combines sets. All tuples from either relation (duplicates removed). Relations must be union-compatible.

∩

Set · Intersection

Intersection

Finds commonalities. Only tuples appearing in both relations. Union-compatible required.

−

Set · Difference

Difference

Subtracts sets. Tuples in R but not in S. Not commutative: R − S ≠ S − R.

Binary · Cartesian Product

Cartesian Product

Pairs everything. Every tuple of R paired with every tuple of S. Result has n×m rows.

⋈

Binary · Join

Join

Matches records. Cartesian product + Selection condition. Only meaningful combinations survive.

Full Operator Reference

Operator	Symbol	Category	Purpose & Description
Selection Unary	σ	Row Filter	Filters rows by a Boolean condition. The output has the same columns as the input but fewer rows. Supports =, <, ≤, >, ≥, ≠ and AND (∧), OR (∨), NOT (¬).
Projection Unary	π	Column Filter	Keeps only specified attributes; automatically eliminates duplicate tuples because a relation is a set.
Rename Unary	ρ	Metadata	Changes the name of a relation and/or its attributes. Critical for self-joins and managing intermediate results.
Union Set	∪	Combine	Returns all tuples from R or S or both. Requires union-compatibility (same degree and matching domains). Duplicates eliminated.
Intersection Set	∩	Common	Returns only tuples that appear in both R and S. Requires union-compatibility.
Difference Set	−	Subtract	Returns tuples in R but not in S. Requires union-compatibility. Non-commutative.
Cartesian Product Binary	×	Combine All	Pairs every tuple of R with every tuple of S. If R has n rows and m cols, S has x rows and y cols → result has n×x rows and m+y cols.
Join Binary	⋈	Match	Cartesian product followed by selection on a join condition. Eliminates non-matching tuples. Has multiple variants (Theta, Equijoin, Natural).

1 — Unary Operations

These operators work on a single relation.

σ Selection (Sigma)

Purpose: Filters rows based on a specified Boolean condition. Returns a subset of tuples that satisfy the expression.
Visual metaphor: A horizontal cut through the table — keep some rows, discard others.
Characteristics: The result has the same number of columns (degree) as the original. Condition can use comparison operators (=, <, ≤, >, ≥, ≠) and logical connectives AND (∧), OR (∨), NOT (¬).

-- Retrieve all employees with salary > 30,000 σ_{salary > 30000}(EMPLOYEE) -- Multiple conditions: salary > 30,000 AND dept = 'IT' σ_{salary > 30000 ∧ dept = 'IT'}(EMPLOYEE)

π Projection (Pi)

Purpose: Selects specific columns (attributes) from a relation and discards the rest.
Visual metaphor: A vertical cut — keep some columns, drop others.
Characteristics: Because a relation is mathematically a set, projection automatically eliminates duplicate tuples in its result.

-- Return only name and salary for all employees π_{name, salary}(EMPLOYEE) -- Combine with selection: names of high earners π_name(σ_{salary > 30000}(EMPLOYEE))

ρ Rename (Rho)

Purpose: Changes the name of a relation, the names of its attributes, or both.
Characteristics: Indispensable for self-joins — lets you reference two copies of the same table with different names — and for managing intermediate query results.

-- Rename relation R to S; rename its attributes to B1 and B2 ρ_{S(B1, B2)}(R) -- Self-join example: find employees who earn more than their manager ρ_E1(EMPLOYEE) ⋈ ρ_E2(EMPLOYEE)

2 — Set Theory Operations

⚠️

Union-Compatibility Required: Union (∪), Intersection (∩), and Difference (−) all require the two participating relations to have the same number of attributes (degree) and matching domains (data types) for each corresponding attribute position.

∪ Union

Purpose: Returns all tuples appearing in relation R, relation S, or both.
Characteristics: Duplicate tuples are automatically eliminated. Commutative: R ∪ S = S ∪ R.

-- All students who are either CS majors or honor roll members π_{student_id}(σ_major='CS'(STUDENT)) ∪ π_{student_id}(HONOR_ROLL)

∩ Intersection

Purpose: Returns only tuples present in both R and S.
Characteristics: Commutative: R ∩ S = S ∩ R. Can be expressed using Difference: R ∩ S = R − (R − S).

-- Students who are BOTH CS majors AND on the honor roll π_{student_id}(σ_major='CS'(STUDENT)) ∩ π_{student_id}(HONOR_ROLL)

− Difference (Minus)

Purpose: Returns tuples in R that are not in S.
Characteristics: Not commutative — R − S ≠ S − R. Useful for "find all X that don't have a Y" queries.

-- CS students who are NOT on the honor roll π_{student_id}(σ_major='CS'(STUDENT)) − π_{student_id}(HONOR_ROLL)

3 — Binary Relational Operations

× Cartesian Product (Cross Product)

Purpose: Combines every tuple from R with every tuple from S.
Size: If R has n rows & m cols, and S has x rows & y cols → result has n×x rows and m+y columns.
Note: Does not require union-compatibility. On its own, generates many meaningless combinations; almost always followed by a Selection to filter meaningful pairs.

-- Raw cross product (rarely used alone) EMPLOYEE × DEPARTMENT -- More useful: cross product + selection = theta join σ_{EMPLOYEE.dept_id = DEPARTMENT.dept_id}(EMPLOYEE × DEPARTMENT)

⋈ Join

Purpose: Combines related tuples from two relations based on a matching condition. Tuples that don't satisfy the condition are discarded.
Formally: A Join = Cartesian Product followed by a Selection condition.

Variant	Symbol	Description
Theta Join	⋈_θ	Uses any comparison operator (≤, >, =, ≠, etc.) as the join condition.
Equijoin	⋈₌	A Theta Join where the condition uses only equality (=) comparisons. Produces duplicate join-attribute columns.
Natural Join	⋈ or ∗	Automatically joins on ALL attributes with the same name in both relations and removes redundant duplicate columns from the result.

-- Theta Join: employees whose salary exceeds their department budget EMPLOYEE ⋈_{salary > budget} DEPARTMENT -- Natural Join: auto-matches on shared attribute names EMPLOYEE ⋈ DEPARTMENT -- Equivalent using Cartesian Product + Selection σ_{EMPLOYEE.dept_id = DEPARTMENT.dept_id}(EMPLOYEE × DEPARTMENT)

Search This Blog

database management system