SQL and Relational Theory, 2nd Edition

EXAMPLE 4: CORRELATED SUBQUERIES

Consider the query “Get names of suppliers who supply both part P1 and part P2.” Here’s a logical formulation:

     { SX.SNAME } WHERE EXISTS SPX ( SPX.SNO = SX.SNO AND SPX.PNO = 'P1' )
                    AND EXISTS SPX ( SPX.SNO = SX.SNO AND SPX.PNO = 'P2' )

An equivalent SQL formulation is straightforward:

     SELECT DISTINCT SX.SNAME
     FROM   S AS SX
     WHERE  EXISTS ( SELECT *
                     FROM   SP AS SPX
                     WHERE  SPX.SNO = SX.SNO
                     AND    SPX.PNO = 'P1' )
     AND    EXISTS ( SELECT *
                     FROM   SP AS SPX
                     WHERE  SPX.SNO = SX.SNO
                     AND    SPX.PNO = 'P2' )

Here’s the result:

SNAME

Smith

Jones

As you can see, however, this SQL expression involves two correlated subqueries. (In fact, Example 3 involved a correlated subquery also. See Chapter 12 for further discussion.) But correlated subqueries are often contraindicated from a performance point of view, because—conceptually, at any rate—they have to be evaluated repeatedly, once for each row in the outer table, instead of just once and for all. The possibility of eliminating them thus seems worth investigating. Now, in the case at hand (where the correlated subqueries appear within EXISTS invocations), there’s a simple transformation that can be used to achieve precisely that effect. The resulting expression is:

     SELECT DISTINCT SX.SNAME
     FROM   S AS SX
     WHERE  SX.SNO IN ( SELECT SPX.SNO
                        FROM   SP AS SPX
                        WHERE  SPX.PNO = 'P1' )
     AND    SX.SNO IN ( SELECT SPX.SNO
                        FROM   SP AS SPX
                        WHERE  SPX.PNO = 'P2' )

More generally, the SQL expression

     SELECT sic    /* "SELECT item commalist" */
     FROM   T1 WHERE [ NOT ...