How to Find the Maximum Value in Relational Algebra

1. Introduction

Relational algebra is the mathematical model of the query languages used in relational database systems. Its operations take relations as input and produce relations as output.

In this tutorial, we’ll learn how to find the maximum value in relational algebra.

2. Relational Algebra

The basic operations in relational algebra are:

Projection: $\boldsymbol{\pi}_{a_1, a_2, \ldots, a_n} R$ produces a new relation whose tuples have the coordinates that correspond to the columns $a_1, a_2, \ldots, a_n$ of relation . It works as the SELECT operator in SQL
Selection: $\boldsymbol{\sigma}_{\theta} R$ returns the subset of containing only the tuples for which the condition $\theta$ is true. We can think of it as the mathematical equivalent of the WHERE clause in SQL
Rename: we can change the name of a relation, some or all of its attributes, or both the name and attributes simultaneously. We’ll denote this operation as $\boldsymbol{\rho}$ .
Set operations: union, set difference ( $\boldsymbol{\setminus}$ ), intersection, and Cartesian product ( $\boldsymbol{\times}$ )

This set of operations is usually extended with join operators ( $\boldsymbol{\bowtie}$ ) and sometimes with aggregations ( $\boldsymbol{\gamma}$ ). The latter are equivalent to SQL aggregations, and in such extensions, finding the maximum is trivial, as MAX is a core operation of the algebra. Therefore, we’ll focus on implementing MAX using only the basic operations and joins.

3. Finding the Maximum

Let’s say we have a relation Tournament(id, points) in which we record how many points contestants scored in a tournament:

points

The task is to find the contestant with the most points.

To solve it using relational algebra, we’ll first talk about defining a set’s maximum value.

3.1. Maximum vs Greatest Element

In mathematics, we differentiate between the maximal and greatest elements of a set.

The greatest element of a set is the one that is greater than all the other elements of that set:

$[x = \mathrm{greatest of } A \iff (\forall y \in A: y \neq x) x > y]$

On the other hand, the maximal element is the one that is not less than any other element. Mathematically:

$[x = \max A \iff (\forall y \in A:) \neg (y > x)]$

We use the latter definition to implement MAX. We will do it in two steps:

Find all the contestants with a lower score than at least one other contestant (this is the part in the definition)
Find the contestants that are not among these

The second step finds those with maximal points because if a contestant isn’t found in the first step, then no other contestant has more points, which is the maximum’s definition.

3.2. Implementation

To find the contestants with fewer points than at least one other contestant, we’ll first compute the Cartesian product of Tournament with a renamed version of itself. Then, we’ll filter the product relation.

Let’s do the renaming and compute the product:

This is the resulting relation:

id1

id2

points1

points2

Now, let’s keep only the tuples in which points_1 < points_2 :

$[Temp_2 \leftarrow \boldsymbol{\sigma}_{points_1 < points_2} Temp_1]$

This gives us:

id1

id2

points1

points2

The first column contains the contestants who “lost” to at least one other contestant, so they can’t have the maximum number of points. Let’s do the projection:

$[Fewer \leftarrow \boldsymbol{\pi}_{id_1} Temp_2]$

Now, we have those IDs in this unary relation:

id1

The set difference of $\boldsymbol{\pi}_{id} Tournament$ and $\boldsymbol{\rho}_{id_1 \mapsto id}Fewer$ contains the IDs of the contestants with the maximum number of points. We rename the attribute id_1 of Fewer to so that the attribute names match:

$[(\boldsymbol{\pi}_{id} Tournament) \setminus (\boldsymbol{\rho}_{id_1 \mapsto id}Fewer) = \{A1, A2, A3, A4\} \setminus \{A1, A2\} = \{A3, A4\}]$

This is the correct result, as the contestants A3 and A4 have the same number of points, more than A1 and A2. As we see, there can be more than one maximum.

The same logic applies to finding the minimal values. We only have to replace points_1 < points_2 with points_1 > points_2 .

3.3. Using Joins

Filtering the Cartesian product is essentially a join operation:

$[R \boldsymbol{\bowtie}_{\theta} S = \boldsymbol{\sigma}_{\theta} (R \boldsymbol{\times} S)]$

So, we can streamline those two steps in the computation of maximum values:

$[\begin{aligned} Tournament_1 &\leftarrow \boldsymbol{\rho}_{Tournament_1(id_1, points_1)} Tournament \\ Tournament_2 &\leftarrow \boldsymbol{\rho}_{Tournament_2(id_2, points_2)} Tournament \\ Compared &\leftarrow Tournament_1 \boldsymbol{\bowtie}_{points_1 < points_2} Tournament_2 \\ Fewer &\leftarrow \boldsymbol{\pi}_{id_1} Compared \\ Result &\leftarrow (\boldsymbol{\pi}_{id} Tournament) \setminus (\boldsymbol{\rho}_{id_1 \mapsto id}Fewer) \end{aligned}]$

If another relation stores the contestants’ info, we can join the relations using the IDs to include those attributes in the result.

3.4. Showing the IDs and Maximal Values

If we want to see the maximal points in addition to the IDs, we should keep points_1 when applying the projection to Compared :

$[\begin{aligned} Fewer &\leftarrow \boldsymbol{\pi}_{id_1, points_1} Compared \\ Result &\leftarrow Tournament \setminus (\boldsymbol{\rho}_{id_1 \mapsto id, points_1 \mapsto points} Fewer) \end{aligned}]$

To get only the maximal number of points, we project points :

$[\boldsymbol{\pi}_{points} Result]$

4. Finding the Maximum per Group

What if the tournament is not all vs. all, but contestants compete within groups?

Let’s say the relation is Tournament(group, id, points) , where is the contestant’s ID*:*

group

points

We start the same way as before, by renaming the relations:

$[\begin{aligned} Tournament_1 &\leftarrow \boldsymbol{\rho}_{Tournament_1(group_1, id_1, points_1)} Tournament\\ Tournament_2 &\leftarrow \boldsymbol{\rho}_{Tournament_2(group_2, id_2, points_2)} Tournament\\ \end{aligned}]$

However, when joining, we include the condition that group_1=group_2 in addition to points_1 < points_2 . It means the comparisons will be performed only within groups:

$[Temp \leftarrow Tournament_1 \boldsymbol{\bowtie}_{group_1=group_2 \land points_1 < points_2} Tournament_2]$

This returns:

group1

id1

points1

group2

id2

points2

Now, we do the projection, keeping the attributes group_1 and points_1 in addition to id_1 :

$[Fewer \leftarrow \boldsymbol{\pi}_{group_1, id_1, points_1} Temp]$

Since relations are sets, all the tuples are unique. So, the duplicates are filtered out automatically:

group1

id1

points1

We rename the attributes of Fewer to match those of Tournament and find the set difference of and the renamed Fewer :

$[\begin{aligned} Fewer_{renamed} &\leftarrow \boldsymbol{\rho}_{group_1 \mapsto group, id_1 \mapsto id, points_1 \mapsto points} Fewer \\ Result &\leftarrow Tournament \boldsymbol{\setminus} Fewer_{renamed} \end{aligned}]$

This way, we get the contestants with maximum points per group:

group

points

5. Conclusion

In this article, we discussed how to find the maximum in relational algebra. The idea is to find the set of values that are less than at least one other value in the relation. The maximal values are those that aren’t in that set.

Persistence

REST

Security

1. Introduction

2. Relational Algebra

3. Finding the Maximum

3.1. Maximum vs Greatest Element

3.2. Implementation

3.3. Using Joins

3.4. Showing the IDs and Maximal Values

4. Finding the Maximum per Group

5. Conclusion