Relational Algebra

🧩 Relational Algebra

Relational algebra is a procedural query language which takes instances of relations as input and yields instances of relations as output. It is the formal foundation upon which SQL and relational database engines are built.

---

🟢 1. Fundamental Operators

Selection ($\sigma$)

Selects tuples (rows) that satisfy a given predicate $p$. $\sigma_{p}(R)$ Example: $\sigma_{\text{salary} > 50000}(\text{Employees})$

Projection ($\pi$)

Selects specific attributes (columns) from a relation. $\pi_{a_1, a_2, \dots, a_n}(R)$ Example: $\pi_{\text{name, department}}(\text{Employees})$

Set Operations

• Union ($R \cup S$): Tuples in $R$ or $S$ (must be union-compatible).
• Difference ($R - S$): Tuples in $R$ but not in $S$.
• Intersection ($R \cap S$): Tuples in both $R$ and $S$.

---

🟡 2. Join Operations

Joins allow for the combination of related data from different relations.

Cartesian Product ($R \times S$)

Combines every tuple of $R$ with every tuple of $S$.

Natural Join ($R \Join S$)

A Cartesian product followed by a selection on common attributes, then a projection to remove duplicate columns. This is the most common way to link tables via foreign keys.

Outer Joins

• Left Outer Join ($R \Join^L S$): Keeps all tuples from $R$, filling with $NULL$ for missing matches in $S$.
• Right Outer Join ($R \Join^R S$): Keeps all tuples from $S$.
• Full Outer Join ($R \Join^F S$): Keeps all tuples from both relations.

---

🔴 3. Query Optimization

The real power of relational algebra lies in its Mathematical Identities, which allow a database engine to rewrite a query into a more efficient form.

Common Rewrite Rules

1. Pushing Selections: Perform $\sigma$ as early as possible to reduce the size of the relations being joined. $\sigma_p(R \Join S) \equiv (\sigma_p(R)) \Join S$
2. Pushing Projections: Perform $\pi$ early to reduce the width of the tuples.
3. Commutativity of Joins: $R \Join S \equiv S \Join R$. The optimizer chooses the order based on table statistics (cardinality).

Tip

When you run EXPLAIN on a SQL query, you are viewing the Logical Plan (Relational Algebra) and the Physical Plan (Algorithms like Hash Join or Nested Loop) chosen by the optimizer.