Search code examples
sqlrelational-division

SQL nested not exist understanding

I want the SIDS of suppliers who supply every part. I have trouble understanding the query answer the book has given. 

Suppliers(sid: integer, sname: string, address: string)
Parts(pid: integer, pname: string, color: string)
Catalog(sid: integer, pid: integer, cost: real)

Suppose you're given a database as the following:

Table: Parts

PID
P1
P2
P3

Table : Catalog

SID  PID  
S1   P1
S1   P2
S1   P3
S2   P1

It should output S1, but I believe with the given query, it will output both S1 and S2. Wouldn't the last nested query satisfy the SID = 2 ? Because if C1.sid = S2 and C.sid = S2 and C1.pid = P1 and P.pid = P1 then it would satisfy the query.

The book answer is given as follows: SQL Translation : "C.Sid for which Does not exist the parts that are not supplied by C.Sid"

SELECT C.sid
FROM Catalog C
WHERE NOT EXISTS (SELECT P.pid
                  FROM Parts P
                  WHERE NOT EXISTS (SELECT C1.sid
                                    FROM Catalog C1
                                    WHERE C1.sid = C.sid
                                    AND C1.pid = P.pid)
                  )
Solution

  • A simple 'proof by contradiction' will demonstrate the query could never return S2.

    For the query to return S2, the first NOT EXISTS would demand the subquery on Parts to yield zero rows. Which is most certainly not the case, since that particular subquery returns all parts not supplied by S2 (i.e. P2 and P3).