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

\{x |  \forall y S(x) \wedge S(y)  \to y \le x \}

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.


6 Responses to “Two Relational Algebra puzzles”

  1. Erwin Smout Says:


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

  2. Erwin Smout Says:

    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.

    • 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?

  3. Mukesh Ghildiyal Says:

    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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: