## Two Relational Algebra puzzles

### July 29, 2010

Here is couple of queries which are easily expressed in SQL, but are much more challenging in *Relational Algebra*

1. Find a maximum in a set

`select max(x) from S`

This query is expressed in *Relational Calculus* as

hence, it can be expressed in Relational Algebra as well. So, given unary relation `S(x)`

and binary relation `LE(x,y)`

, what relational algebra query outputs a maximal element of `S`

?

2. Sort a set

`select x from S order by x`

There is no concept of ordering in Relational Algebra, of course. Therefore, the query has to be reformulated a little. A list can be represented as binary relation with domain of non-negative integers as a first argument. For example, alphabetically ordered list `"a, b, c"`

becomes

`[position, value]`

0 a

1 b

2 c

Formally, given two unary relations `S`

(e.g numbers) and `R`

(e.g. strings) together with binary order relations `LES`

(e.g. numerical order) and `LER`

(e.g. alphabetical order) on their respective domains write a query that “matches” S and R. Leveraging previous problem we can express the query procedurally:

*“Find the maximal element in both S and R, match them together, and repeat this procedure with the S and R stripped off their respective maximums.”*

The problem is that Relational algebra doesn’t allow recursion/iteration, so the question is if this query is expressible by standard means.

September 29, 2010 at 12:56 pm

LE DIVIDEBY LE{x} ?

(Get me the y value that has ALL x’s)

October 1, 2010 at 4:10 pm

Little adjustments required:

`(S(x) join S(y) join LE(x,y)) divideby S(x)`

The detailed discussion is in the third section of

https://vadimtropashko.wordpress.com/relational-programming-with-qbql/udf/

September 29, 2010 at 1:59 pm

The other one about “matching S and R” is trivial insofar as it only involves finding the maxima from LES and LER (see previous solution).

These could be joined to get a pair such as {2147987654, “zzzzzzzzzzzzzz”}, and the MINUS/NOT operator could be applied to “remove” these maxima from the ‘working’ LES/LER.

It’s unclear to me how and where you want the recursion applied.

October 1, 2010 at 4:16 pm

By recursion I have meant that after one have matched

`0`

and`a`

, he applies the same method to smaller relations.This problem is difficult because the relations could mismatch in size. Then, what is the expected output?

February 12, 2013 at 7:48 pm

I think one can use rename operator to do this. However, a quick shortcut that I have seen while practicing the RA on the downloaded DUke project is:

\project_{max(columnName)} TableName;

Mukesh Ghildiyal

February 13, 2013 at 6:25 pm

Classic relational algebra is commonly understood not to include the extended projection (aka Tutorial D EXTEND).