How to implement intersect using where exists or not exists in mysql

Question

My tables are:

customer(cid,name,city,state)
orders(oid,cid,date)
product(pid,productname,price)
lineitem(lid,pid,oid,number,totalprice)

I want to select products bought by all the customers of city 'X'.It means I need to intersect products bought by all the customers living in city 'X'

Example:If there are 3 customers c1,c2 and c3 my answer is c1.product(intersect)c2.product(intersect)c3.product

I want to implement this only using where exists or where not exists because I need to write the relational calculus for the same in which where not in or where in is not available.My partial query is this:

select 
  * 
from 
  product p,
  lineitem l,
  customer c1 
where 
  exists(
   select 
      * 
   from 
     customer c,
     orders o 
   where 
    o.cid=c.cid and 
    c.city='X' and 
    l.oid=o.oid and 
    l.pid=p.pid and 
    c1.cid=c.cid)

The above query gives me the pid,cid,oid,lid,totalprice,city,productname of all the customers living in city X.Now I need to figure out how to select the product common to all customers.

Note:

I cant use any of the aggregate functions because it's not available in relational calculus.I have a working query using aggregate functions and that is

select 
   p.productname 
from 
   product p, 
   orders s, 
   lineitem l, 
   customer c 
where 
   l.pid=p.pid and
   l.oid=s.oid and 
   c.cid=s.cid and 
   c.city='X' 
group by 
   p.productname 
having 
   count(distinct c.cid)=(select count(*) from customer c1 where c1.city='X')

It's ok if someone can convert the above query in where exists or where not exists form without count and group by.

I am sure that it can be done because I can do that in relational algebra and according to Codd's theorom tuple relational calculus and relational algebra are logically equivalent and any query expressed in one can be expressed in other.As both relational algebra and relational calculus do not support aggregate functions the query can be expressed in sql without aggregrate functions.

Answer 1

This is my answer.

I created a sqlfiddle at http://www.sqlfiddle.com/#!2/f2fb85/1, so you can try it.

The query is:

SELECT p.*
FROM product p
WHERE NOT EXISTS (
    SELECT c.cid
    FROM customer c
    WHERE NOT EXISTS (
        SELECT l.lid
        FROM lineitem l
        JOIN orders o ON o.oid = l.oid
        WHERE l.pid = p.pid
        AND o.cid = c.cid
    )
    AND c.city = 'X'
) AND EXISTS (
    SELECT c.cid
    FROM customer c
    WHERE c.city = 'X' 
)

Answer 2

Based on your comments, I've replaced my previous answer with this one that doesn't make use of IN. This one makes use of multiple levels of correlated subqueries:

select p.* 
from product p
where exists (
  select *
  from customer c
  where c.city = 'x'
    and exists (
      select *
      from lineitem l
      where l.pid = p.pid
        and exists (
          select *
          from orders o
          where o.oid = l.oid
            and o.cid = c.cid
        )
    )
)
  and not exists(
    select *
    from customer c
    where c.city = 'x'
      and not exists (
        select *
        from lineitem l
        where l.pid = p.pid
          and exists (
            select *
            from orders o
            where o.oid = l.oid
              and o.cid = c.cid
          )
    )
  )

SQL Fiddle here.

Answer 3

ANSI-Sql lacks set theories universal quantifier, you need to use rewrite roles to get existential quantifier:

∀ Universal quantifier (For all . . .)
∃ Existential quantifier (There exists . . .)

Example:

(∀c ∈ CUSTOMER)
⇔ /*Add double negation */
¬¬(∀c ∈ CUSTOMER)
⇔ /*Bring one negation into the quantification, quantifier changes */
¬(∃c ∈ CUSTOMER)

Sql translation:

SELECT p.*
FROM product p
WHERE NOT EXISTS (
  SELECT c.cid
  FROM customer c
  WHERE  c.city = 'X'
  AND NOT EXISTS
  (
    SELECT o.oid
    FROM orders o
    JOIN lineitem l ON l.oid = o.oid
    WHERE l.pid = p.pid
    AND o.cid = c.cid
  )
)

Fiddle-Demo