Do DBMSs Process Subqueries Correctly? (3)

The Problem is Bigger than Date Thought!

In his article, 'Beware of SQL EXISTS', C. J. Date warns of flaws in ANSI SQL's definition of EXISTS. An extended version of the example he used in the article is described in the prior section, The EXISTS Flaw. This example shows that the ANSI SQL EXISTS operator can produce wrong results, but the problems in SQL EXISTS are symptomatic of a larger problem.

Actually, the wrong results in the example query are not produced by EXISTS but by the WHERE clause within the EXISTS subquery. ANSI SQL defines the WHERE clause as returning True or False, a 2 valued result rather than a 3 valued result including Unknown. In the subquery,

(SELECT *
 FROM   sp spy
 WHERE  spy.sno = spx.sno
 AND    spy.sno = 'P1'
 AND    spy.qty = 1000)

The final sub-expression (spy.qty = 1000) produces an Unknown result if spy.qty is null, as when the variable spy is (S1,P1,NULL). This causes the result of the WHERE expression to be Unknown. Since the WHERE clause in ANSI SQL cannot return Unknown, it is transformed to False, causing S1 to be incorrectly included in the result set. The error is caused by the action of the WHERE clause, not the EXISTS!

Some ramifications of the larger problem are:

DBMSs do not process subqueries correctly. Because the definition of WHERE in ANSI SQL is the real problem, Date's first query using IN instead of EXISTS can be converted into an incorrect formulation (for ANSI SQL, at least!) by simple rearrangement (which actually simplifies Date's query):
```
SELECT DISTINCT sno
FROM   sp
WHERE  pno = 'P1'
AND    sno NOT IN
       ( SELECT sno
         FROM   sp
         WHERE  pno = 'P1'
         AND    qty = 1000) ;
```
This query exhibits the same error as the EXISTS query for ANSI SQL and most RDBMSs. In other words, virtually any SQL operation involving a subquery can have this flaw when columns can be null.
Even when query developers carefully avoid any incorrect formulations, the error may occur anyway. Many RDBMSs routinely perform transformations of queries during their query optimization phases. For example, Date's original query using IN could be transformed into the EXISTS query during optimization. Normally, this is a correct transformation (Date used the transformation since it is theoretically correct), but because of the error in the definition of WHERE in ANSI SQL it changes a correct query into an incorrect one. Even ostensibly correct queries can produce wrong results when subqueries are used.
The ANSI SQL definition of the HAVING clause has the same error. ANSI SQL defines HAVING as returning only True or False, like WHERE. Since some RDBMSs allow HAVING in views or in subqueries (FirstSQL allows HAVING in both), subqueries involving HAVING can also product incorrect results.

The flaw in SQL subquery processing is a major problem for users of relational systems. Though this problem is widespread, there are solutions. The FirstSQL implementation of subqueries shows none of the errors described above. A live demonstration of FirstSQL's correct implementation using DATE's queries is provided in the next section, How FirstSQL Solves the EXISTS and Other Problems.

Return to Contents Page: DBMSs Process Subqueries Correctly? Return to Issues Page