Relational Algebra: Select, Project & Join

Module Overview

While Structured Query Language (SQL) is a declarative language that specifies what data to retrieve, database engines convert declarative statements into Relational Algebra—a formal procedural query language. In this installment, we analyze the theoretical operators of relational algebra: fundamental unary and binary operators (Selection, Projection, Cartesian Product, Set Union, Difference), derived join operators (Theta, Natural, Outer Joins, Semijoins), Relational Division, and the algebraic transformation rules that power Cost-Based Optimizers.

1. Foundational Unary Operators

Unary operators operate upon a single input relation $R$ to produce a new relation $R'$. Because relations are closed under relational algebra, the result of any operation can serve as the input to another operation.

Selection ($\sigma$)

Horizontal filtering of tuples.

Denoted as $\sigma_{ heta}(R)$, it filters relation $R$ to retain only those tuples that satisfy propositional predicate $ heta$ (composed of comparison operators $=, eq, <, \le, >, \ge$ joined by logical connectives $\land, \lor, eg$).

text

123456

// Relational Algebra
σ_{salary > 90000 ∧ dept = 'Engineering'}(Employees)

-- Equivalent SQL
SELECT * FROM Employees 
WHERE salary > 90000 AND dept = 'Engineering';

Projection ($\pi$)

Vertical filtering of attributes.

Denoted as $\pi_{A_1, A_2, \dots, A_k}(R)$, it selects specified columns and eliminates duplicate tuples from the output relation (enforcing strict set semantics).

text

123456

// Relational Algebra
π_{first_name, email}(Employees)

-- Equivalent SQL
SELECT DISTINCT first_name, email 
FROM Employees;

2. Set Theoretic Binary Operators

For set operations—Union ($R \cup S$), Intersection ($R \cap S$), and Difference ($R - S$)—both relations must be union-compatible: they must have the same degree (number of attributes), and the corresponding attribute domains must be identical.

Cartesian Product ($ imes$)

Denoted as $R imes S$, it pairs every tuple $t_r \in R$ with every tuple $t_s \in S$. If relation $R$ contains $n_1$ tuples and degree $k_1$, and relation $S$ contains $n_2$ tuples and degree $k_2$, the cross product yields a relation of degree $k_1 + k_2$ containing exactly $n_1 imes n_2$ tuples.

3. Derived Join Operators

In practice, cross products generate massive intermediate tables. Joins combine a Cartesian product with a selection predicate to correlate matching records efficiently.

Theta Join ($\Join_ heta$) and Equi-Join

Formally defined as $R \Join_ heta S = \sigma_ heta(R imes S)$. When the condition $ heta$ involves only equality operators ($=$), it is termed an Equi-Join.

Natural Join ($\Join$)

An equi-join performed on all identically named attributes between $R$ and $S$, automatically projecting out duplicate join columns so each common attribute appears exactly once in the schema.

text

12345

// Relational Algebra
Employees ⨝ Departments

-- Equivalent SQL
SELECT * FROM Employees NATURAL JOIN Departments;

Outer Joins (Left ⟕, Right ⟖, Full ⟗)

Preserve tuples from one or both relations that have no matching records in the other relation, padding unmatched attribute positions with NULL values.

Semijoin ($\ltimes$) and Antijoin ($ hd$)

A Semijoin ($R \ltimes S = \pi_{ ext{attrs}(R)}(R \Join S)$) returns tuples from $R$ that match at least one tuple in $S$ without duplicating rows or widening the schema. An Antijoin ($R hd S$) returns tuples from $R$ that have no match in $S$ (equivalent to NOT EXISTS in SQL).

4. Relational Division ($\div$) for Universal Quantification

Relational division is used to solve queries requiring "for all" universal quantification—such as "Find all students who have enrolled in every required core course".

Given relation $R(A, B)$ and relation $S(B)$, the quotient $R \div S$ produces a relation with schema $(A)$ containing all values of $A$ that appear in $R$ associated with every value of $B$ present in $S$. Formally:

R ÷ S = π_A(R) - π_A((π_A(R) × S) - R)

5. Algebraic Query Optimization Rules

Query engines rewrite relational algebra expressions into algebraically equivalent trees that drastically minimize intermediate disk I/O and RAM usage:

Push Down Selections ($\sigma$): $\sigma_ heta(R \Join S) \equiv (\sigma_ heta(R)) \Join S$ (when $ heta$ references only attributes of $R$). Filtering rows early reduces the cardinality before expensive joins.
Push Down Projections ($\pi$): Discard unused attributes immediately after table scans to minimize tuple byte width in buffer pool pages.
Commutativity & Associativity of Joins: $R \Join S \equiv S \Join R$ and $(R \Join S) \Join T \equiv R \Join (S \Join T)$. Enables the optimizer to evaluate multiple join orders to select the least expensive execution plan.

Next in Curriculum

In Part 4: Database Normalization: From 1NF to BCNF and De-normalization Rules, we study functional dependencies and schema decomposition algorithms to eliminate data redundancy and anomalies.