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 $R$ . It works as the SELECT operator in SQL
Selection: $\boldsymbol{\sigma}_{\theta} R$ returns the subset of $R$ 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:

id	points
A1	67
A2	78
A3	85
A4	85

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 $y > x$ 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
A1	A1	67	67
A1	A2	67	78
A1	A3	67	85
A1	A4	67	85
A2	A1	78	67
A2	A2	78	78
A2	A3	78	85
A2	A4	78	85
A3	A1	85	67
A3	A2	85	78
A3	A3	85	85
A3	A4	85	85
A4	A1	85	67
A4	A2	85	78
A4	A3	85	85
A4	A4	85	85

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
A1	A2	67	78
A1	A3	67	85
A1	A4	67	85
A2	A3	78	85
A2	A4	78	85

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
A1
A2

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 $id$ 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 $id$ is the contestant’s ID:

group	id	points
G1	A1	67
G1	A2	78
G1	A3	85
G2	B1	50
G2	B2	65
G2	B3	65

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
G1	A1	67	G1	A2	78
G1	A1	67	G1	A3	85
G1	A2	78	G1	A3	85
G2	B1	50	G2	B2	65
G2	B1	50	G2	B3	65

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
G1	A1	67
G1	A2	78
G2	B1	50

We rename the attributes of $Fewer$ to match those of $Tournament$ and find the set difference of $Tournament$ 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	id	points
G1	A3	85
G2	B2	65
G2	B3	65

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.

id1	id2	points1	points2
A1	A1	67	67
A1	A2	67	78
A1	A3	67	85
A1	A4	67	85
A2	A1	78	67
A2	A2	78	78
A2	A3	78	85
A2	A4	78	85
A3	A1	85	67
A3	A2	85	78
A3	A3	85	85
A3	A4	85	85
A4	A1	85	67
A4	A2	85	78
A4	A3	85	85
A4	A4	85	85

group1	id1	points1	group2	id2	points2
G1	A1	67	G1	A2	78
G1	A1	67	G1	A3	85
G1	A2	78	G1	A3	85
G2	B1	50	G2	B2	65
G2	B1	50	G2	B3	65

id1	id2	points1	points2
A1	A1	67	67
A1	A2	67	78
A1	A3	67	85
A1	A4	67	85
A2	A1	78	67
A2	A2	78	78
A2	A3	78	85
A2	A4	78	85
A3	A1	85	67
A3	A2	85	78
A3	A3	85	85
A3	A4	85	85
A4	A1	85	67
A4	A2	85	78
A4	A3	85	85
A4	A4	85	85

group1	id1	points1	group2	id2	points2
G1	A1	67	G1	A2	78
G1	A1	67	G1	A3	85
G1	A2	78	G1	A3	85
G2	B1	50	G2	B2	65
G2	B1	50	G2	B3	65

Learn Java Collections

Learn Spring

Learn Maven

View All Courses

Core Concepts

Operating Systems

Neural Networks

Graph Theory

Latex

Full Archive

About Baeldung