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$ is a relation):

$\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 the relation $R$ (duplicate tuples are discarded so each tuple in the resulting relation is unique)
$\rho_{a/b}(R)$ rename attribute $b$ from the relation $R$ to $a$
$R \bowtie_{\theta} S$ $\theta$-join of relations $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)$, with $R \times S$ being 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[ R \underset{\textrm{Age} \lt \textrm{Age2}}{\bowtie} \left(\rho_{\textrm{Name2/Name}}\rho_{\textrm{Age2/Age}} R\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: $$ R \underset{\textrm{Age} \lt \textrm{Age2}}{\bowtie} \left(\rho_{\textrm{Name2/Name}}\rho_{\textrm{Age2/Age}} R\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 $R$ which are smaller than some other age value in $R$. Therefore, the relation $$ \Pi_{\textrm{Age}}\left[ R \underset{\textrm{Age} \lt \textrm{Age2}}{\bowtie} \left(\rho_{\textrm{Name2/Name}}\rho_{\textrm{Age2/Age}} R\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

No comments posted yet.

Leave a reply

NOTE: A name and a comment (max. 1024 characters) must be provided; all other fields are optional. Equations will be processed if surrounded with dollar signs (as in LaTeX). You can post up to 5 comments per day.