Relational Algebra

Introduction

• SQL is a declarative programming language.
• Relational Algebra is a more expressive language, a procedural programming language
  • meaning the query specifies exactly what operators to use and in what order
• Relation are sets of tuples (does not allow replication)

All of the operations in relational algebra take in a relation and output a relation.

Projection $(\pi )$

${\pi }_{name}(dogs)$ means SELECT name FROM dogs

The input parameters specify which tables to pull (like FROM key word)

Selection $(\sigma )$

Selection is used to filter rows, equivalent to SQL’s WHERE clause.

Both

${\sigma }_{age=12}({\pi }_{name,age}(dogs))$

and

${\pi }_{name,age}({\sigma }_{age=12}(dogs))$

are equivalent to

SELECT name, age FROM dogs WHERE age = 12 AND name='Timmy';

Union $(\cup )$

Same as SQL’s UNION. For example: ${\pi }_{name}(dogs)\cup {\pi }_{name}(cats)$

When union fails

• union 2-column-relation with 1-column-relation (columns number not match)
• union string column with int column (columns type not match)

Set Difference $(-)$

Same as SQL’s EXCEPT, ${\pi }_{name}(dogs)-{\pi }_{name}(cats)$

Intersection $(\cap )$

Same as SQL’s INTERSECT operator, ${\pi }_{name}(dogs)\cap {\pi }_{name}(cats)$

Cross Product $(\times )$

Perform a Cartesian product like the same in SQL.

Joins $(\bowtie )$

Put join condition in the subscript and put right operator on the right side.

• Theta Join $({\bowtie }_{\theta })$ : inner join. The $\theta$ refers to the join condition.
• Natural join $(\bowtie )$
• Example: $cats{\bowtie }_{cats.name=dogs.name}dogs$
  • This is a natural join, so to simplify: $cats\bowtie dogs$

Derived from cross product

Theta joins and natural joins are derived from cross product and conjunction of selections For example:

$cats{\bowtie }_{\theta }$ can be rewritten as ${\sigma }_{\theta }(cats\times dogs)$

and natural join $cats\bowtie dogs$ can be rewritten as

${\sigma }_{cats.col1=dogs.col1\wedge \cdots \wedge cats.colN=dogs.colN}(cats\times dogs)$

Rename $(\rho )$

The rename operator essentially accomplishes the same thing as aliasing in SQL.

$cats{\bowtie }_{name=dname}({\rho }_{name\to dname}(dogs))$: Renames the dogs relation’s name column to $dname$ first, so there’s no conflict in column names.

Group By / Aggregation $(\gamma )$

SELECT age, SUM(weight) FROM dogs GROUP BY age HAVING COUNT(*) > 5;

can be expressed as:

${\gamma }_{age,SUM(weight),COUNT(\ast )>5}(dogs)$