3

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)

Ankita Rane
  • 171
  • 1
  • 1
  • 12
  • 1
    It would be helpful if you'd build in [SQLFiddle](http://sqlfiddle.com/#!4) populated with the data you'd like to see used, and if you'd provide an idea of the results you expect. [See "How to Ask A Good Question"](http://stackoverflow.com/help/how-to-ask). Thanks. – Bob Jarvis - Слава Україні Sep 30 '15 at 14:34
  • 1
    https://www.simple-talk.com/sql/t-sql-programming/divided-we-stand-the-sql-of-relational-division/ – shawnt00 Sep 30 '15 at 16:16

2 Answers2

1

The query would be:

select 
  sailors.sname 
from (
  select r.sid 
    from reserves r 
   group by r.sid
   having count(distinct r.bid) = (select count(*) from boats) ) fullRes
join sailors 
on sailors.sid = fullRes.sid

You can test it here:

Example

dcieslak
  • 2,697
  • 1
  • 12
  • 19
1

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.

John Bollinger
  • 160,171
  • 8
  • 81
  • 157