Previous Page
Next Page

10.4. SQL Universal and Existential Qualifiers

In SQL, "for all" and "for each" are the universal qualifiers, whereas "there exists" is the existential qualifier. As mentioned in the preceding section, SQL does not have a "for all" predicate; however, logically, the following relationship exists:

For all x, WHERE P(x) is true ...

which is logically the same as the following:

There does not exist an x, WHERE P(x) is not true.

A "for all" type SQL query is less straightforward than the other queries we have used, because it involves a double-nested, correlated subquery using the NOT EXISTS predicate. The next section shows an example.

10.4.1. Example 1

To show a "for all" type SQL query, we will use another table in our Student_course databasea table called Cap (for "capability"). This table has names of students who have multiple foreign-language capabilities. We begin by looking at the table by typing the following query:

SELECT *
FROM   Cap
ORDER BY name

This query produces the following output (18 rows):

NAME      LANGU
--------- -------
BRENDA    FRENCH
BRENDA    CHINESE
BRENDA    SPANISH
JOE       CHINESE
KENT      CHINESE
LUJACK    SPANISH
LUJACK    FRENCH
LUJACK    GERMAN
LUJACK    CHINESE
MARY JO   FRENCH
MARY JO   GERMAN
MARY JO   CHINESE
MELANIE   FRENCH
MELANIE   CHINESE
RICHARD   SPANISH
RICHARD   FRENCH
RICHARD   CHINESE
RICHARD   GERMAN
 
(18 row(s) affected)

Suppose that we want to find out which languages are spoken by all students (for which we would ask the question, "For each language, does it occur with all students?"). Although this manual exercise would be very difficult for a large table, for our practice table, we can answer the question by displaying and manually counting in the table ordered by language.

To see how to answer a question of the type--"Which languages are spoken by all students?"--for a much larger table where sorting and examining the result would be tedious, we will construct a query. After showing the query, we will dissect the result. Following is the query to answer our question:

SELECT  name, langu
FROM    Cap x
WHERE NOT EXISTS
             (SELECT 'X'
             FROM Cap y
             WHERE NOT EXISTS
                           (SELECT 'X'
                           FROM Cap z
                           WHERE x.langu = z.langu
                           AND y.name = z.name))

As you will see, all the for all/for each questions follow this double-nested, correlated NOT EXISTS pattern.


This query produces the following output (7 rows):

name      langu
--------- -------
BRENDA    CHINESE
RICHARD   CHINESE
LUJACK    CHINESE
MARY JO   CHINESE
MELANIE   CHINESE
JOE       CHINESE
KENT      CHINESE
 
(7 row(s) affected)

10.4.1.1. The way the query works

To SELECT a "language" spoken by all students, the query proceeds as follows:

  1. SELECT a row in Cap (x) (outer query).

  2. For that row, begin SELECTing each row again in Cap (y) (middle query).

  3. For each of the middle query rows, we want the inner query (Cap z) to be true for all cases of the middle query (remember that true is translated to false by the NOT EXISTS). As each inner query is satisfied (it is true), it forces the middle query to continue looking for a matchto look at all cases and eventually conclude false (evaluate to false overall). If the middle query is false, the outer query sees true because of its NOT EXISTS.

    To make the middle query (y) find false, all the inner query (z) occurrences must be true; that is, the languages from the outer query must exist with all names from the middle one (y) in the inner one (z). For an eventual "match," every row in the middle query for an outer query row must be false (that is, every row in the inner query is true).

These steps are explained in further detail in the next example, in which we use a smaller table, so that the explanation is easier to understand.

10.4.2. Example 2

Suppose that we have the simpler table Cap1 (see Table 10-1) when attempting to answer the question "Which languages are spoken by all students?"

Table 10-1. Cap1

Name         Language
------------ ------------
Joe          Hindi
Mary         Hindi
Mary         French
 
(3 row(s) affected)


The table Cap1 does not exist in the Student_course database. You will have to create it. Keep the column names and types similar to the table Cap.


The query will be similar to the one used in the previous section:

SELECT name, language
FROM   Cap1 x
WHERE NOT EXISTS
     (SELECT 'X'
       FROM Cap1 y
       WHERE NOT EXISTS
         (SELECT 'X'
              FROM   Cap1 z
              WHERE  x.language = z. language
              AND    y.name = z.name))
ORDER BY language

This query produces the following output:

name         language
------------ ------------
Joe          Hindi
Mary         Hind
 
(2 row(s) affected)

10.4.2.1. The way this query works

The following is a step-by-step explanation of how this query would work in Table 10-1 (Cap1):

  1. The row <Joe, Hindi> is SELECTed by the outer query (x).

  2. The row <Joe, Hindi> is SELECTed by the middle query (y).

  3. The row <Joe, Hindi> is SELECTed by the inner query (z).

  4. The inner query is true:

        X.LANGUAGE = Hindi
    Z.LANGUAGE = Hindi
    Y.NAME = Joe
    Z.NAME = Joe

  5. Because the inner query returns a row (is true), the NOT EXISTS of the middle query translates this to false and continues with the next row in the middle query. The middle query SELECTs <Mary, Hindi> and the inner query begins again with <Joe, Hindi> seeing:

         X.LANGUAGE = Hindi
     Z.LANGUAGE = Hindi
     Y.NAME = Mary
     Z.NAME = Joe

    This is false, so the inner query SELECTs a second row <Mary, Hindi>:

        X.LANGUAGE = Hindi
    Z.LANGUAGE = Hindi
    Y.NAME = Mary
    Z.NAME = Mary

    This is true, so the inner query is TRue. (Notice that the X.LANGUAGE has not changed yet; the outer query [X] is still on the first row.)

  6. Because the inner query returns a row (is true), the NOT EXISTS of the middle query translates this to false and continues with the next row in the middle query.

    The middle query now SELECTs <Mary, French> and the inner query begins again with <Joe, Hindi> seeing:

        X.LANGUAGE = Hindi
    Z.LANGUAGE = Hindi
    Y.NAME     = Mary
    Z.NAME     = Joe

    This is false, so the inner query SELECTs a second row <Mary, Hindi>:

        X.LANGUAGE = Hindi
    Z.LANGUAGE = Hindi
    Y.NAME     = Mary
    Z.NAME     = Mary

    This is true, so the inner query is true.

  7. Because the inner query is true, the NOT EXISTS of the middle query again converts this true to false and wants to continue, but the middle query is out of rows. Thus the middle query is false.

  8. Because the middle query is false, and because we are testing

    "SELECT distinct name, language
 FROM Cap1 x
 WHERE NOT EXISTS
    (SELECT 'X' FROM Cap1 y ...",

    the false from the middle query is translated to true for the outer query and the row <Joe, Hindi> is SELECTed for the result set. Note that "Hindi" occurs with both "Joe" and "Mary."

  9. The second row in the outer query will repeat the previous steps for <Mary, Hindi>. The value "Hindi" will be seen to occur with both "Joe" and "Mary" as <Mary, Hindi> is added to the result set.

  10. The third row in the outer query begins with <Mary, French>. The middle query SELECTs <Joe, Hindi> and the inner query SELECTs <Joe, Hindi>. The inner query sees the following:

       X.LANGUAGE = French
   Z.LANGUAGE = Hindi
   Y.NAME     = Joe
   Z.NAME     = Mary

    This is false, so the inner query SELECTs a second row, <Mary, Hindi>:

       X.LANGUAGE = French
   Z.LANGUAGE = Hindi
   Y.NAME     = Joe
   Z.NAME     = Mary

    This is false, so the inner query SELECTs a third row, <Mary, French>:

       X.LANGUAGE = French
   Z.LANGUAGE = French
   Y.NAME     = Joe
   Z.NAME     = Mary

    This is also false. The inner query returns no rows (fails). The inner query evaluates to false, which causes the middle query to returns rows (see TRue) because of the NOT EXISTS. Because the middle query sees true, it is finished and evaluated to true. Because the middle query evaluates to TRue, the NOT EXISTS in the outer query changes this to false and X.LANGUAGE = French fails because X.LANGUAGE = French did not occur with all the values of NAME.

Consider again the "for all" query presented in Example 2:

SELECT name, language
FROM   Cap1 x
WHERE NOT EXISTS
     (SELECT 'X'
       FROM Cap1 y
       WHERE NOT EXISTS
         (SELECT 'X'
              FROM    Cap1 z
              WHERE   x.language = z. language
              AND     y.name = z.name))
ORDER BY language

A clue as to what a query of this kind means can be found in the inner query where the outer query is tested. In the phrase that says WHERE x.language = z. language..., the x.language is where the query is testing which language occurs for all names.

This query is a SQL realization of a relational division exercise. Relational division is a "for all" operation just like that illustrated earlier. In relational algebra, the query must be set up into a divisor, dividend, and quotient in this pattern:

Quotient (B) Dividend(A, B) divided by Divisor (A).

If the question is "What language for all names?" then the Divisor, A, is names, and the Quotient, B, is language. It is most prudent to set up SQL like relational algebra with a two-column table (like Cap or Cap1) for the Dividend and then treat the Divisor and the Quotient appropriately. Our query will have the column for language, x.language, in the inner query, as language will be the quotient. We have chosen to also report name in the result set.

10.4.3. Example 3

Note that the preceding query is completely different from the following query, which asks, "Which students speak all languages?":

SELECT DISTINCT name, language
FROM   Cap1 x
WHERE NOT EXISTS
             (SELECT 'X'
             FROM Cap1 y
             WHERE NOT EXISTS
                     (SELECT 'X'
                          FROM     Cap1 z
                          WHERE    y.language = z.language
                          AND      x.name = z.name))
ORDER BY language

This query produces the following output:

name         language
------------ ------------
Mary         French
Mary         Hindi
 
(2 row(s) affected)

Note that the inner query contains x.name, which means the question was "Which names occur for all languages?" or, put another way, "Which students speak all languages?" The "all" goes with languages for x.name.


Previous Page
Next Page