Banner

 

SQL Divide

How it works

In addition to the existential quantifier that you have already encountered, formal logic has a universal quantifier; known as forall which is necessary for queries such as:

If a universal qualifier were supported by SQL, this query could be phrased as: "Select item names where forall sales, there exists a lineitem row recording that this item was sold." A quick inspection of Table 1 shows that one item satisfies this condition (itemno = 2).

While SQL does not directly support the universal qualifier, formal logic shows that forall can be expressed using exists. The query becomes "Find items such that there does not exist a sale in which this item does not appear." The equivalent SQL expression is:

SELECT itemno, itemname FROM item
   WHERE NOT EXISTS
      (SELECT * FROM sale
         WHERE NOT EXISTS
            (SELECT * FROM lineitem
               WHERE lineitem.itemno = item.itemno
               AND lineitem.saleno = sale.saleno))
itemno itemname
2 Pocket knife--Avon

You may be convinced that this query is correct by walking through it step by step using the data in Table 1 and examining the outcome of each step of the query (see Table 2).

Table 1: Condensed versions of sale, lineitem, and item
sale
saleno
1
2
3
4
5
lineitem  
lineno saleno itemno
1 1 2
1 2 6
2 2 16
3 2 19
4 2 2
1 3 4
2 3 2
1 4 4
2 4 9
3 4 13
4 4 14
5 4 3
6 4 2
1 5 10
2 5 11
3 5 12
4 5 13
5 5 2
item
itemno
1
2
3
...
Table 2: Results of the first 18 steps of the divide statement
Step itemno saleno SELECT * FROM lineitem WHERE lineitem.itemno = item.itemno AND lineitem.saleno = sale.saleno NOT EXISTS SELECT * FROM sale WHERE NOT EXISTS (SELECT * FROM lineitem WHERE lineitem.itemno = item.itemno AND lineitem.saleno =sale.saleno) NOT EXISTS
1 1 1 false true    
2 1 2 false true    
3 1 3 false true    
4 1 4 false true    
5 1 5 false true    
6         true false
7 2 1 true false    
8 2 2 true false    
9 2 3 true false    
10 2 4 true false    
11 2 5 true false    
12         false true
13 3 1 false true    
14 3 2 false true    
15 3 3 false true    
16 3 4 true false    
17 3 5 false true    
18         true false

Step 1.

The first row of item has itemno=1, and the first row of sale has saleno = 1.

The innermost query becomes

SELECT * FROM lineitem
   WHERE lineitem.itemno = 1
   AND lineitem.saleno = 1

Examination of the lineitem table shows this query returns false, which is negated by the NOT before the innermost EXISTS to give true.

Step 2.

We now advance to the second row of sale with saleno = 2, and execute the innermost query again. This query will also return false which will be negated to true.

Steps 3-5.

The results of these and other steps are summarized in Table 2.

Step 6.

The subquery
SELECT * FROM sale
	WHERE NOT EXISTS (... 

has now been executed for each value of saleno for the first value of itemno and returned true for each row. Thus this query returns true, and the NOT before the EXISTS of this query changes the true to false. Since the value returned is false, the current value of itemno is not reported.

Steps 7-11.

The results of these steps are shown in Table 2.

Step 12.

The subquery

SELECT * FROM sale
   WHERE NOT EXISTS (... 

has now been executed for each value of saleno for the second value of itemno and returned false for each row. Although this query returns false, the NOT before the EXISTS changes the false to true. Since the value returned is true, the current value of itemno is reported. Item 2 appears in all sales.

It will take you some time to step through this example to understand how the double NOT EXISTS works. Once you do, you will be convinced that the query does work.

 

This page is part of the promotional and support material for Data Management (sixth edition) by Richard T. Watson
For questions and comments please contact the author

Date revised: 19-Oct-2016