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 (Relational Algebra)

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 set of tuples based on the Cartesian product of multiple, possibly identical, domains.

Example:

$$phone\_book\subseteq \text{string}\times \text{string}\times \text{integer}$$

Link to original

Relation Schema

Definition

Schema (Relational Algebra)

A schema $\mathcal{R}$ or $\text{sch}(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:\text{string},street:\text{string},number:\text{integer})$$

Link to original

Arity

Arity

The number of attributes of a relation is called arity.

Attribute

Operations

Definition

Selection (Relational Algebra)

The selection operation ${\sigma }_F:\text{Relation}\to \text{Relation}$ performs a filter $F$ on a relation $R$ and maps it to a new filtered relation $R^{\prime }$, i.e.

$$R^{\prime }={\sigma }_F(R)=\{T\in R\mid F\text{ on }T\text{ evaluates to true}\}$$

Link to original

Projection

Definition

Projection (Relational Algebra)

The projection operation ${\pi }_{A_1,\dots ,A_k}:\text{Relation}\to \text{Relation}$ selects a subset of attribute $\{A_1,\dots ,A_k\}$ from a relation $R$ and maps it to a new relation $R^{\prime }$ containing only those attributes, i.e.

$$R^{\prime }={\pi }_{A_1,A_2,\dots ,A_k}(R)=\{T[A_1,A_2,\dots ,A_k]\mid T\in R\}$$

Where $T[A_1,A_2,\dots ,A_k]$ is a new tuple containing only the values from the attribute specified in the list $\{A_1,\dots ,A_k\}$ for a given tuple $T$. Since the resulting relation $R^{\prime }$ is a set, any duplicate tuple that arise from this operation are automatically eliminated.

Note that there’s also the possibility for extended projection, meaning specifying expressions instead of attributes, i.e.:

$${\pi }_{name,salary÷12}(instructors)$$

Link to original

Rename

Definition

Rename (Relational Algebra)

The rename operation, denoted by $\rho :\text{Relation}\to \text{Relation}$, modifies the schema of a relation $R$ without altering the data within its tuples. It produces a new relation $R^{\prime }$ with either a new name for the relation itself or new names for its attributes. It is used in two primary forms:

1. Renaming a Relation
   The expression ${\rho }_S(R)$ renames the relation $R$ to $S$. The new relation $S$ has the identical schema and contains the exact same set of tuples as $R$.

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

2. Renaming Attributes
   The expression ${\rho }_{A\leftarrow B}(R)$ produces a new relation $R^{\prime }$ where the attribute $B$ from $R$ is renamed to $A$. This can be extended to rename multiple attributes at once, e.g., ${\rho }_{A_1\leftarrow B_1,A_2\leftarrow B_2}(R)$.

   $$R^{\prime }={\rho }_{A\leftarrow B}(R)$$

The values and the number of tuples remain unchanged, only the attribute names in the schema are modified.

Link to original

Grouping and Aggregation

Definition

Grouping and Aggregation (Relational Algebra)

The grouping and aggregation operation, denoted by $\gamma$, is an operator that first partitions tuples of a relation $R$ into groups and then computes a single or multiple summary value for each group using an aggregate function.

This process involves two main steps:

1. Grouping: Tuples that have the same values for all attributes in a specified grouping list are placed into the same group.
2. Aggregation: An aggregate function (like SUM, COUNT, AVG, MIN, MAX) is applied to an attribute of the tuples within each group, producing a single value per group.

$${\gamma }_{L,F}(R)$$

where:

• $L$ is the list of attributes to group by
• $F$ is the aggregate function to be applied to each group. This also defines the new attribute for the aggregate value in the result schema (e.g., $F=\text{SUM}(\text{Price})\to \text{TotalValue}$)
• $R$ is the input relation

The resulting relation consists of the grouping attributes in $L$ and the new attribute(s) generated by the aggregate function(s) in $F$.

Link to original

Union

Definition

Union (Relational Algebra)

The union operation between two union compatible relations $R,S$ is the set of all tuples contained by $R$ or $S$, i.e.

$$R\cup S=\{T\mid T\in R\vee T\in S\}$$

Link to original

Intersection

Definition

Intersection (Relational Algebra)

The intersection operation between two union compatible relations $R,S$ is the set of all tuples contained by both $R$ and $S$, i.e.

$$R\cap S=\{T\mid T\in R\wedge T\in S\}$$

Link to original

Difference

Definition

Difference (Relational Algebra)

The difference operation between two union compatible relations $R,S$ is the set of all tuples that are in $R$ but not in $S$, i.e.

$$R-S=R\setminus S=\{T\mid T\in R\wedge T\notin S\}$$

Link to original

Join

Definition

Join (Relational Algebra)

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

Link to original

Division

Definition

Relational Division (Relational Algebra)

The relational division operation, denoted by $R÷S$, is typically used to answer queries that involve the phrase “for all”. It finds all tuples in one relation $R$ that are associated with every single tuple from another relation $S$.

The division operation can be expressed using projection, difference, and the Cartesian Product:

$$R÷S={\pi }_{(R-S)}(R)-{\pi }_{(R-S)}((({\pi }_{(R-S)}(R)\times S)-R))$$

---

Link to original

Joins

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

Theta Join

Definition

Theta Join (Relational Algebra)

The theta join $R{\bowtie }_{\theta }S$ combines two relations via a joining predicate $\theta$ by combining only tuples for which $\theta$ holds.

Link to original

Natural Join

Definition

Natural Join (Relational Algebra)

The natural join $R\bowtie S$ combines two relations via common attributes (same names and domains) by combining only tuples with the same values for common attributes.

Given two relations $R(A_1,\dots ,A_m,\underbrace{{{\mathbf{B}}_1,\dots {\mathbf{B}}_{\mathbf{k}}}_{}})$ and $S(\underbrace{{{\mathbf{B}}_1,\dots ,{\mathbf{B}}_{\mathbf{k}}}_{}},C_1,\dots ,C_n)$, the natural join can be expressed using projection, selection and the Cartesian Product:

$$R\bowtie S={\pi }_{A_1,\dots ,A_m,R.B_1,\dots ,R.B_k,C_1,\dots ,C_n}({\sigma }_{R.B_1=S.B_1\wedge \cdots \wedge R.B_k=S.B_k}(R\times S))$$

Link to original

Outer Joins

Definition

Outer Join

Outer joins deal with unmatched tuples without matching join partners in the other relation (“dangling tuples”).

Link to original

Left Outer Join

Definition

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$.

$$R⊐\bowtie S$$

Link to original

Right Outer Join

Definition

Right Outer Join (Relational Algebra)

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$.

$$R\bowtie ⊏S$$

Link to original

Full Outer Join

Definition

Full Outer Join (Relational Algebra)

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

$$R⊐\bowtie ⊏S$$

Link to original

Semi Joins

Definition

Semi Join (Relational Algebra)

A semi join finds all tuples in a relation for which there are matching tuples in the other relation.

Link to original

Left Semi Join

Definition

Left Semi Join (Relational Algebra)

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)$.

Link to original

Right Semi Join

Definition

Right Semi Join (Relational Algebra)

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)$.

Link to original