Aggregate Relational Algebra (Maximum)

Question

I am currently working on a homework assignment that requires a selection to occur that pulls out an element containing a specific attribute of maximum value compared to all other records. I've read a number of sources online that reference an "aggregate" relational algebra function called maximum, but they don't describe how it works using the basic operators. How does one select the attribute containing a maximum value?

Answer 1

You can very well express aggregate functions with only basic operators. It's a pretty neat thing.

Suppose we have a table T, and we'd like to find the maximum of its "value" field. First, we should take the cartesian product of T with itself -- or rather with a copy of itself, T2. Then we select the rows where T.value is smaller than T2.value: this nets us all the unwanted rows, whose value is less than the value of some other row. To get the maximal values, we should subtract these unwanted rows from the set of all rows. And that's it. At least that's the basic idea, we also need to use projections to get the dimensions right.

Unfortunately I have no idea how to insert Latex here, but using relational algebra notation, it'd be something like this:

π(T.a1...Tan, T.value)(T)
    -
π(T.a1...Tan, T.value)(
    σ(T.value<T2.value)( ρ(T, T2) x T )
)

where π is the projection operator, - is the set difference, σ is the selection operator and ρ is the rename operator.

SQLishly:

SELECT T.* FROM T
    MINUS
SELECT T.* FROM T, T as T2 WHERE T.value<T2.value

And more practically:

SELECT T.* FROM T LEFT JOIN T as T2 ON T.value<T2.value WHERE T2.value IS NULL

Of course, all this is mostly only of academic interest, i.e. that it shows that the relational algebra works.