Relational Algebra

While database developers use SQL to interact with databases, SQL is a declarative language—you declare what you want, but you don't tell the database how to get it.

Relational Algebra is a procedural query language. It consists of a set of operations that take one or two relations (tables) as input and produce a new relation as their result. When you submit an SQL query, the DBMS internal query optimizer automatically translates your SQL into a Relational Algebra expression to figure out the most efficient execution plan.

1. Fundamental Operations

There are six fundamental operations in relational algebra.

1. Select (σ)

The select operation selects tuples (rows) that satisfy a given predicate (condition).

• Notation: σ_P(R) where P is the propositional logic formula and R is the relation.
• Example: σ_(salary > 80000)(Instructor)
• SQL Equivalent: The WHERE clause.

2. Project (π)

The project operation returns its argument relation, with certain attributes (columns) left out. Since a relation is a mathematical set, any duplicate rows are eliminated from the result.

• Notation: π_(A1, A2, ..., Ak)(R)
• Example: π_(name, salary)(Instructor)
• SQL Equivalent: The SELECT column_names clause.

3. Union (∪)

The union operation combines two relations into one. For a union operation to be valid, the two relations must be union-compatible (they must have the same number of attributes, and the domains of corresponding attributes must be compatible).

• Notation: R ∪ S
• SQL Equivalent: The UNION operator.

4. Set Difference ($-$)

The set-difference operation allows us to find tuples that are in one relation but are not in another. The relations must be union-compatible.

• Notation: $R - S$
• SQL Equivalent: The EXCEPT or MINUS operator.

5. Cartesian Product ($\times$)

The Cartesian-product operation allows us to combine information from any two relations. If $R$ has $n_1$ tuples and $S$ has $n_2$ tuples, the result will have $n_1 \times n_2$ tuples.

• Notation: $R \times S$
• SQL Equivalent: A CROSS JOIN (or selecting from two tables without a WHERE clause).

6. Rename ($\rho$)

The results of relational-algebra expressions do not naturally have a name. The rename operator allows us to name the resulting relation.

• Notation: ρ_X(E) returns the result of expression E under the name X.
• SQL Equivalent: The AS alias keyword.

2. Additional Operations

These operations do not add any new computational power to the algebra (they can all be defined in terms of the fundamental six), but they simplify common queries.

Set Intersection ($\cap$)

Returns tuples that are present in both relations.

• $R \cap S = R - (R - S)$

Natural Join ($\bowtie$)

The Natural Join is extremely common. It forms a Cartesian product of its two arguments, performs a selection forcing equality on those attributes that appear in both relation schemas, and finally removes duplicate attributes.

• Notation: $R \bowtie S$
• SQL Equivalent: The NATURAL JOIN or an INNER JOIN on equality of commonly named columns.