Relational Algebra

relational-algebra

Definition

Relational Algebra

Relational algebra is a theory that uses algebraic structure for modeling data and defining queries on it with well founded semantics. It was introduced by Edgar Frank Codd.

Domain

A domain is a set of possible values for an attribute.

Relation

Definition

Relation

Let $D_1,D_2,\dots ,D_n$ be domains. A relation $R\subseteq D_1\times D_2\times \cdots \times D_n$ is a tuple based on the cartesian product of multiple, possibly identical, domains.

Example:

$$phone\_book\subseteq string\times string\times integer$$

Link to original

Relation Schema

Definition

Schema (Relational Algebra)

A schema $\mathcal{R}$ of a relation $R$ describes the structure of data in a relation $R$ and is denoted as $\mathrm{sch}(R)$ or as $\mathcal{R}$.

The notation is defined as follows:

$$R(A_1:D_1,A_2:D_2,\dots ,A_n:D_n)$$

where $A_i$ is an attribute of with domain $D_i$.

Example:

$$phone\_book(name:string,street:string,number:integer)$$

Link to original

Arity

Arity

The number of attributes of a relation is called arity.

Attribute

Operations

Selection

The unary selection operator ${\sigma }_{C_1,C_2,\dots ,C_k}(R)$ selects tuples of relation $R$ based on the given conditions $C_1,C_2,\dots ,C_k$ and maps them to a relation with the same schema but with only the selected tuples.

$${\sigma }_{C_1,C_2,\dots ,C_k}(R)$$

where $C_1,C_2,\dots ,C_k$ are conditions of which tuples (rows) are selected.

Projection

The unary project operator ${\Pi }_{A_1,\dots ,A_k}(R)$ takes all attributes of $R$ that are specified in the projection’s index, meaning $A_1,\dots ,A_k$.

$${\Pi }_{A_1,\dots ,A_k}(R)$$

Note that the projection operator allows simple arithmetic operations on attributes, e.g.:

$${\Pi }_{name,yearly\_salary÷12}(professors)$$

Rename

Renames the relation $R$ to $S$.

$$S\leftarrow {\rho }_S(R)$$

To select an attribute name of renamed relation S, we denote:

$${\sigma }_{S.name=\text{‘Lukas’}}(S)$$

Grouping

$${\gamma }_{A_1,A_2,\dots ,A_a;F_1,F_2,\dots F_f}(R)={\beta }_{L;F}(R)={\mathcal{G}}_{L;F}(R)$$

where $A_1,A_2,\dots ,A_a$ are the attributes to group by and $F_1,F_2,\dots ,F_f$ are the aggregation functions to apply per group.

Example: Given a relation $\text{students}$:

$$\text{students}(id:integer,name:string,semester:integer)$$

To retrieve the number of students per semester, we denote:

$${\gamma }_{semester,\mathrm{count}(\ast )}$$

Union

Union Compatibility

Two relations $R_1$ and $R_2$ are compatible if they have the same number of attributes with the same same domains, whereby the attribute names are not considered.

Intersection

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

Join

Joins are a way to associate two relations $R$ and $S$ based on certain conditions. See joins.

Division

Joins

Commutativity: $R\bowtie S\ne S\bowtie R$ due to different output schemas.

Theta Join

The theta join $R{\bowtie }_{\theta }S$ links two relations $R$ and $S$ based on the given condition $\theta$.

In theta joins, only tuples of both relations that can be joined are kept.

Notation:

$$R{\bowtie }_{\theta }S$$

Equi Join: A theta join is called equi join if the theta condition only checks for equality.

Natural Join

The natural join links two relations $R$ and $S$ based on equality of equally named attributes.

Notation:

$$R\bowtie S$$

In natural joins, only tuples of both relations that can be joined are kept.

Outer Joins

Outer joins are about how to handle tuples that cannot be joined.

Left Outer Join

In left outer joins $R⊐\bowtie S$, the left tuples of relation $R$ are kept even if they cannot be joined with the right tuples of relation $S$.

Notation:

$$R⊐\bowtie S$$

Right Outer Join

In right outer joins $R\bowtie ⊏S$, the right tuples of relation $S$ are kept even if they cannot be joined with the left tuples of relation $R$.

Notation:

$$R\bowtie ⊏S$$

Full Outer Join

In full outer joins $R⊐\bowtie ⊏S$, the tuples of relation $R$ and $S$ are kept even if they cannot be joined.

Notation:

$$R⊐\bowtie ⊏S$$

Semi Joins

Left Semi Join

The left semi join $R⋊S$ maps all tuples of $R$ that could be joined with at least a tuple in $S$.

The schema of $\mathrm{sch}(R⋊S)=\mathrm{sch}(R)$.

Right Semi Join

The right semi join $R⋊S$ maps all tuples of $S$ that could be joined with at least a tuple in $R$.

The schema of $\mathrm{sch}(R⋊S)=\mathrm{sch}(S)$.

Aggregation Functions

Count

Counts the number of elements per group.

Sum

Sums up the values of an attribute per group.

Min

Finds the minimum value of an attribute per group.

Max

Finds the maximum value of an attribute per group.

Avg

Calculates the average value of an attribute per group.