sqloraclerelational-algebrarelational-division

How to represent relational division(basic algebra expression) in terms of SQL


Query: Find names of sailors who have reserved all boats

This can be represented in relation algebra as:
1. πsname ( ((σsid,bid Reserves) / (σbid Boats)) ⋈ Sailors)

As per Relational algebra, Division can also be represented using basic algebra operator as follows:

  1. A/B= πx(A) - πx((πx(A) * B) - A )

Thus if I convert statement 1 as per Statement 2 then

  1. Reserves/Boats= πsid(Reserves) - πsid(( πbid(Reserves) * Boats) - Reserves )

How can i represent Statement 3 in terms of SQL in the same way as it is in Relation Algebra (i.e without using any operator other than minus/Except(-) and Cross join(*)).
I am trying to achieve it without the use of NOT EXISTS and EXISTS condition.

Schema of tables is as follows:
Sailors(sid: integer, sname: string, rating: integer, age: real)
Boats(bid: integer, bname: string, color: string)
Reserves(sid: integer, bid: integer, day: date)


Solution

  • Given this DDL for tables corresponding to your relevant relations:

    create table Boats(
      bid int,
      bname varchar(50),
      color varchar(50)
    );
    
    create table Reserves(
      sid int,
      bid int,
      day date
    );
    

    You can transliterate the division formula (3) into Oracle SQL syntax fairly straightforwardly, though it's verbose:

    -- All sailors who reserved at least one boat
    SELECT DISTINCT sid
    FROM Reserves
    
    MINUS 
    
    -- All sailors who reserved at least one boat, but not all of them
    SELECT sid
    FROM (
      -- all combinations of a sailor who reserved any boat with any boat
      -- available to be reserved:
      SELECT Reserves.sid, Boats.bid
      FROM
        Reserves
        CROSS JOIN
        Boats
    
      MINUS
    
      -- all combinations of sailor and boat for actual reservations made
      SELECT sid, bid
      FROM Reserves
    ) sids
    

    As specified, that uses only the CROSS JOIN and MINUS operations, so as to correspond directly to the relational algebra formula. In a real-world database application, however, one would surely obtain the same result via an altogether different query.

    Note also that SQL databases can and do violate the principle of formal relational algebra that relations do not contain duplicate tuples. That is the reason for SELECT DISTINCT in the first subquery. Distinct selection applied strategically elsewhere in the query might make it more efficient, but would not alter the result.