Relational algebra: obtaining the largest value


Posted by Diego Assencio on 2014.03.17 under Computer science (Relational algebra)

Using the basic operations of relational algebra (RA), it is possible to obtain the largest value assigned to a given attribute of a relation. This post shows how this can be done.

To start, consider the following operators of RA (below, $R$ and $S$ are relations):

$\sigma_{\theta}(R)$ select tuples (rows) from $R$ which satisfy the condition $\theta$, where $\theta$ consists of comparisons of attributes from $R$ using the following binary operators: $\lt$, $\leq$, $=$, $\geq$ and $\gt$
$\Pi_{a_1,\ldots,a_n}(R)$ extract attributes (columns) $a_1,\ldots,a_n$ from $R$ (duplicate tuples are discarded so each tuple in the resulting relation is unique)
$\rho_{a/b}(R)$ rename attribute $b$ from $R$ to $a$
$R \bowtie_{\theta} S$ $\theta$-join of $R$ and $S$: computes all combinations of tuples from $R$ and $S$ that satisfy the condition $\theta$ ($R \bowtie_{\theta} S = \sigma_{\theta}(R \times S)$, where $R \times S$ is the Cartesian product of $R$ and $S$)

Consider now the relation $P$ below:

NameAge
Peter21
Bob25
Alice32
John27

The maximum age of the people listed in $P$ can be retrieved as follows: $$ \max_{P}(\textrm{Age}) := \Pi_{\textrm{Age}} P - \Pi_{\textrm{Age}}\left[ P \underset{\textrm{Age} \lt \textrm{Age2}}{\bowtie} \left(\rho_{\textrm{Name2/Name}}\rho_{\textrm{Age2/Age}} P\right)\right] $$ In other words, we first obtain a relation $\Pi_{\textrm{Age}} P$ which contains a single column with all ages and subtract from it the set of all ages which are smaller than some other age. To clarify the second part, notice that: $$ P \underset{\textrm{Age} \lt \textrm{Age2}}{\bowtie} \left(\rho_{\textrm{Name2/Name}}\rho_{\textrm{Age2/Age}} P\right) $$ is a relation containing four columns ($\textrm{Name}$, $\textrm{Age}$, $\textrm{Name2}$, $\textrm{Age2}$) with each of its tuples satisfying $\textrm{Age} \lt \textrm{Age2}$. Applying $\Pi_{\textrm{Age}}$ to this relation gives us another relation with a single column ($\textrm{Age}$) containing all original age values from $P$ which are smaller than some other age value in $P$. Therefore, the relation $$ \Pi_{\textrm{Age}}\left[ P \underset{\textrm{Age} \lt \textrm{Age2}}{\bowtie} \left(\rho_{\textrm{Name2/Name}}\rho_{\textrm{Age2/Age}} P\right)\right] $$ contains all ages except the largest one, so removing these values from $\Pi_{\textrm{Age}} P$ yields a relation with a single age value: the largest one.

Comments

Maha on Nov 19, 2019:
what if I wanted for the final table to contain all the information for the maximum value holder, so in this case the name and the age, what are the differences i should make?
Diego Assencio on Nov 22, 2019:
@Maha: You would simply need to replace all occurrences of $\Pi_{\textrm{Age}}$ with $\Pi_{\textrm{Name}, \textrm{Age}}$ on equation (1). This would yield a relation with tuples (rows) representing all people having the maximum age.

If this does not seem obvious, notice that: $$ \Pi_{\textrm{Name}, \textrm{Age}}\left[ P \underset{\textrm{Age} \lt \textrm{Age2}}{\bowtie} \left(\rho_{\textrm{Name2/Name}}\rho_{\textrm{Age2/Age}} P\right)\right] $$ is a relation containing all people who are younger than someone else. By subtracting this relation from $\Pi_{\textrm{Name}, \textrm{Age}} P$, you obtain a relation containing only the people who are the oldest.

If you have additional attributes on your original relation $P$, change the projections accordingly to select the attributes you wish to keep at the end.
Bian Boyan on Feb 10, 2021:
Nice work! Thanks
Jaynam on Nov 03, 2022:
What if i wanted to select the second largest value only, how would you go about it?