Converting aggregate operators from SQL to relational algebra

smcg picture smcg · Sep 30, 2011 · Viewed 9k times · Source

I have several SQL queries written that I want to convert to relational algebra. However, some of the queries use aggregate operators and I don't know how to convert them. Notably they use COUNT and GROUP BY.. HAVING operators.

Here is the schema:

Sailors(sid, sname, rating) Reserves(sid, bid, price) Boats(bid, bname)

Here is an example of what I'm doing: find the bids and bnames of all boats reserved by exactly 2 sailors.

SELECT B.bid, B.bname
FROM Boats B, Reserves R
WHERE B.bid = R.bid
GROUP BY R.bid
HAVING 2 = (SELECT COUNT(*)
FROM Reserves R2
WHERE R2.bid = B.bid);

Allowable relational algebra operations: selection, projection, join, conditional join, rename, union, intersection, cross-product, division

Answer

onedaywhen picture onedaywhen · Sep 30, 2011

This is only half an answer...

The relation "boats reserved by two or more sailors" can be found using conditional join and projection, which are both in your set of allowed operations:

SELECT DISTINCT R1.bid
  FROM Reserves AS R1 
       JOIN Reserves AS R2
          ON R1.bid = R2.bid
             AND R1.sid < R2.sid;

The relation "boats reserved by three or more sailors" can be found using conditional join (twice) and projection, which are both in your set of allowed operations:

SELECT DISTINCT R1.bid
  FROM Reserves AS R1
       JOIN Reserves AS R2
          ON R1.bid = R2.bid
             AND R1.sid < R2.sid
       JOIN Reserves AS R3
          ON R1.bid = R3.bid
          AND R2.sid < R3.sid;

If we had a minus operator e.g. EXCEPT in Standard SQL:

SELECT DISTINCT R1.bid
  FROM Reserves AS R1 
       JOIN Reserves AS R2
          ON R1.bid = R2.bid
             AND R1.sid < R2.sid
EXCEPT
SELECT DISTINCT R1.bid
  FROM Reserves AS R1
       JOIN Reserves AS R2
          ON R1.bid = R2.bid
             AND R1.sid < R2.sid
       JOIN Reserves AS R3
          ON R1.bid = R3.bid
          AND R2.sid < R3.sid;

If we had restriction (WHERE in SQL) and a semi difference (a.k.a. antijoin) operator (e.g. NOT IN in SQL):

SELECT DISTINCT R1.bid
  FROM Reserves AS R1 
       JOIN Reserves AS R2
          ON R1.bid = R2.bid
             AND R1.sid < R2.sid
 WHERE R1.bid NOT IN (
                      SELECT DISTINCT R1.bid
                        FROM Reserves AS R1
                             JOIN Reserves AS R2
                                ON R1.bid = R2.bid
                                   AND R1.sid < R2.sid
                             JOIN Reserves AS R3
                                ON R1.bid = R3.bid
                                AND R2.sid < R3.sid
                     );

...but your set of allowed operations does not include restriction, semi difference or minus :(