SQL and Relational Theory, 2nd Edition

SOME TRANSFORMATION LAWS

Laws of transformation like the ones mentioned above are also known variously as:

• Equivalences, because they take the general form exp1 ≡ exp2 (recall from Chapter 10 and elsewhere that the symbol “≡” means “is equivalent to”).

• Identities, because a law of the form exp1 ≡ exp2 can be read as saying that exp1 and exp2 are “identically equal,” meaning they have identical semantics

• Rewrite rules, because a law of the form exp1 ≡ exp2 implies that an expression containing an occurrence of exp1 can be rewritten as one containing an occurrence of exp2 instead without changing the meaning

I’d like to expand on this last point, because it’s crucial to what we’re going to be doing in the present chapter. Let X1 be an expression containing an occurrence of x1 as a subexpression; let x2 be equivalent to x1; and let X2 be the expression obtained from X1 by substituting an occurrence of x2 for the occurrence of x1 in question. Then X1 and X2 are logically and semantically equivalent; hence, X1 can be rewritten as X2. By way of a simple example, consider the following SQL expression:

     SELECT  SNO
     FROM    S
     WHERE ( STATUS > 10 AND CITY = 'London' )
     OR    ( STATUS > 10 AND CITY = 'Athens' )

The boolean expression in the WHERE clause here is clearly equivalent (thanks to the distributivity of AND over OR—see later) to the following:

     STATUS > 10 AND ( CITY = 'London' OR CITY = 'Athens' )

Hence the overall expression can be rewritten as:

 SELECT SNO FROM S WHERE STATUS > 10 AND ( CITY = ...