Query 6: Find pairs of drinkers who frequent EXACTLY the same set of bars.

DRC - Initial Attempt

{X,Y | drinker(X) and drinker(Y) and X<Y and
       (forall B)(frequents(X,B) --> frequents(Y,B)) and
       (forall B)(frequents(Y,B) --> frequents(X,B)) }

DRC - Removing forall and -->

{X,Y | drinker(X) and drinker(Y) and X<Y and
       not ((exists B)(frequents(X,B) and not (frequents(Y,B)))) and
       not ((exists B)(frequents(Y,B) and not (frequents(X,B)))) }

DRC - Above query is not safe (inner sub-conjuncts have unlimited variables) - Add Predicates

{X,Y | drinker(X) and drinker(Y) and X<Y and
       not ((exists B)(frequents(X,B) and drinker(Y) and not (frequents(Y,B)))) and
       not ((exists B)(drinker(X) and frequents(Y,B) and not (frequents(X,B)))) }

DRC Expression Tree

Datalog Conversion at maximal sub-conjuncts

// Maximal sub-conjunct
// (exists B)(frequents(X,B) and drinker(Y) and not frequents(Y,B))
// produces following rule
temp1(X,Y) :- frequents(X,B), drinker(Y), not frequents(Y,B).

// Maximal sub-conjunct
// (exists B)(drinker(X) and frequents(Y,B) and not frequents(X,B))
// produces following rule
temp2(X,Y) :- drinker(X), frequents(Y,B), not frequents(X,B).

// Maximal sub-conjunct
// drinker(X) and drinker(Y) and X<Y and
// not ((exists B)(frequents(X,B) and not frequents(Y,B))) and
// not ((exists B)(frequents(Y,B) and not frequents(X,B)))
// produces following rule
answer(X,Y) :- drinker(X), drinker(Y), X<Y, not temp1(X,Y), not temp2(X,Y).

Since temp1(X,Y) is equivalent to temp2(Y,X), we can simplify the Datalog query to:

temp(X,Y) :- drinker(X), frequents(Y,B), not frequents(X,B).
answer(X,Y) :- drinker(X), drinker(Y), X<Y, not temp(X,Y), not temp(Y,X).

Relational Algebra (RA)

select[X<Y](
  rename[X](drinker)
  join
  rename[Y](drinker)
  join
  ((rename[X](drinker) times rename[Y](drinker))
     minus
   project[X,Y](rename[X,B](frequents) join rename[Y](drinker) join
                ((rename[Y](drinker) times project[B](rename[X,B](frequents)))
                 minus
                 rename[Y,B](frequents))
   )
  )
  join
  ((rename[X](drinker) times rename[Y](drinker))
     minus
   project[X,Y](rename[X](drinker) join rename[Y,B](frequents) join
                ((rename[X](drinker) times project[B](rename[Y,B](frequents)))
                 minus
                 rename[X,B](frequents))
   )
  )
);

OurSQL Solution

select x.dname, y.dname
from   drinker x, drinker y
where  x.dname < y.dname and
  not exists (
    select b.bname
    from   bar b, frequents f1
    where  f1.dname=x.dname and
           f1.bname=b.bname and
           not exists (
             select f2.dname
             from   frequents f2
             where  f2.dname=y.dname and
                    f2.bname=b.bname)) and
  not exists (
    select b.bname
    from   bar b, frequents f1
    where  f1.dname=y.dname and
           f1.bname=b.bname and
           not exists (
             select f2.dname
             from   frequents f2
             where  f2.dname=x.dname and
                    f2.bname=b.bname));