ON DATE'S "THIRD GREAT BLUNDER"

From: KS
To: Editor

The comment is about Date's AN INTRODUCTION TO DATABASE SYSTEMS. I want to send a comment to the author of the book. Help me in sending these comments to C.J. Date, I do not know who receives this feedback form.

I know people won't believe this. But given a counter example calms every one. I found a big blunder in the book of Mr. Date regarding a SQL query. Let us call it as "Third Great Blunder" as the author himself reserves the words "First Great Blunder" and "Second Great Blunder" in his book (p. 237). It is regarding the SQL equivalent of A=B, where A and B are relvars. The author writes the equivalent query as

NOT EXISTS(SELECT *
           FROM a
           WHERE(NOT EXISTS (SELECT *
                &nbs p;            FROM b
                &nbs p;            WHERE a-row = b-row));

I will give you a counter example that this SQL equivalent query is a big blunder:

Let relvar A be instance of table:

CREATE TABLE A (one integer,PRIMARY KEY(one));

Let relvar B be instance of table:

CREATE TABLE B(two integer,PRIMARY KEY(two));

Let A={a1,a2,a3} at a particular instant

Let B={a1,a2,a3,a4} at a particular instant

Then the query to check A=B at the specified instance values be written as [sic]

The output of the query should be

2
------------
2

if A=B is true

As per Date ( the query is tested using Oracle SQL)

SELECT 2
FROM dual
WHERE NOT EXISTS(SELECT *
                 FROM a
                 WHERE NOT EXISTS(SELECT *
                &nbs p;                 FROM b
                &nbs p;                 WHERE one = two));

Answer is:

2
---------
2

Now the same query is written as (to test B=A)

SELECT 2
FROM dual
WHERE NOT EXISTS(SELECT *
                 FROM a
                 WHERE NOT EXISTS(SELECT *
                &nbs p;                 FROM a
                &nbs p;                 WHERE one = two));

Answer is:

no rows selected

The above two conflicting results are enough to show the blunder in the book by Mr. Date.

In fact the solution is:

SELECT 2
FROM dual
WHERE NOT EXISTS(

(SELECT * a
   MINUS
SELECT *
FROM b)
UNION
  (SELECT *
   FROM b
    MINUS
   SELECT *
   FROM a));

Answer is:

no rows selected

So the equivalent of A=B (or B=A in RDBMS) is

NOT EXISTS(

(SELECT *
FROM a
   MINUS
  SELECT *
  FROM b)
  UNION
(SELECT *
FROM b
   MINUS
  SELECT *
  FROM a));

and not as given in the book.

Hope you will correct the "Third Great Blunder" as early as possible

Chris Date Responds: Thanks to KS for pointing out an error in my book AN INTRODUCTION TO DATABASE SYSTEMS, p. 237. My text currently reads:

"For example, the comparison

A = B

(where A and B are relvars) can be simulated by the SQL expression

NOT EXISTS(SELECT *
           FROM a
           WHERE NOT EXISTS(SELECT *
                &nbs p;           FROM b
                &nbs p;           WHERE a-row = b-row));

(where A-row and B-row are <row constructor>s--see Appendix A--representing an entire row of A and an entire row of B, respectively)."

What it should have said is as follows:

"For example, the comparison

A = B

(where A and B are relvars) can be simulated by the SQL expression

NOT EXISTS(SELECT *
           FROM a
           WHERE NOT EXISTS(SELECT *
                &nbs p;           FROM b
                &nbs p;           WHERE a-row = a-row))
AND
NOT EXISTS(SELECT *
           FROM b
           WHERE NOT EXISTS(SELECT *
                &nbs p;           FROM a
                &nbs p;           WHERE b-row = b-row))

(where A-row and B-row are <row constructor>s--see Appendix A-- representing an entire row of A and an entire row of B, respectively)."

I'm on record as suggesting (in the THIRD MANIFESTO) that any logical mistake is a big mistake, so I might agree the mistake under discussion was a blunder! (I can explain exactly how the blunder occurred, too--it's a little subtle--but it probably isn't very interesting.) However, we shouldn't call it, as KS suggests, the "Third Great Blunder", because (a) it has nothing to do with the First and Second Great Blunders and (b) in any case, I fear the book in question contains many more than just two logical mistakes.

Anyway, KS suggests an alternative formulation:

SELECT 2
FROM dual
WHERE NOT EXISTS(

(SELECT * a
   MINUS
SELECT *
FROM b)
UNION
  (SELECT *
   FROM b
    MINUS
   SELECT *
   FROM a));

(I've replaced KS's MINUSes by EXCEPTs in order to conform to the SQL standard.) This formulation is correct, too, but in context. I prefer my corrected original, because it appeared in a chapter that was concerned primarily with the relational calculus, not the relational algebra. But it's not a big deal.

I note in passing that KS's suggested replacement formulation relies, rather more than my (corrected) version does, on SQL's nonrelational notion of there being a left-to-right ordering to the columns of a table. I note too that neither my corrected version nor KS's suggested replacement works properly if A or B is allowed to contain duplicates ... Taking care of duplicates properly is left as a nasty exercise for the reader.

Posted 03/14/02

[ABOUT] [QUOTES] [LINKS]