SQL and Relational Theory, 2nd Edition

SOME EQUIVALENCES

I’ll finish up this chapter with a few remarks regarding certain equivalences that might have already occurred to you (indeed, I’ve touched on some of them myself from time to time at earlier points). First of all, recall the IS_EMPTY operator, which I introduced in Chapter 3 and made heavy use of in Chapter 8. If the system supports that operator, then there’s no logical need for it to support the quantifiers, thanks to the following equivalences:

• EXISTS x ( p ) ≡ NOT ( IS_EMPTY ( X WHERE p ) )

• FORALL x ( p ) ≡ IS_EMPTY ( X WHERE NOT ( p ) )

(I’m assuming here that the variable x ranges over the set X.)

In fact, SQL’s support for EXISTS—and FORALL, such as it is—is based on exactly the foregoing equivalences. The fact is, SQL’s EXISTS isn’t really a quantifier, as such, at all, because it doesn’t involve any bound variables. Instead, it’s an operator, in the conventional sense of that term: a monadic operator of type BOOLEAN, to be precise. Like any monadic operator invocation, an invocation of the SQL EXISTS operator is evaluated by first evaluating the expression that denotes its sole argument, and then applying the operator per se—in this case EXISTS—to the result of that evaluation. Thus, given the expression EXISTS (tx), where tx is a table expression, the system first evaluates tx to obtain a table t; then it applies EXISTS to t, returning TRUE if t is nonempty and FALSE otherwise. (At least, that’s the conceptual algorithm; numerous optimizations are possible, ...