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 = 'London' OR CITY = 'Athens' )

Here then are some of the transformation laws we’ll be using in this chapter:

  • The implication law:

         IF p THEN q  ≡  ( NOT p ) OR q

    I did state this law in Chapter 10, but I didn’t have much to say about its use there. Take a moment (if you need to) to check the truth tables and convince yourself the law is valid. Note: The symbols p and q stand for arbitrary boolean expressions or predicates. In this chapter, I’ll favor the term boolean expression over predicate, since the emphasis throughout is on such expressions—i.e., on pieces of program text, in effect—rather than on logic per se. Logic in general, and predicates in particular, are more abstract than pieces of program text (or an argument can be made to that effect, at least). You can think of a boolean expression as a concrete representation of some predicate, if you like.

  • The double negation law (also known as the involution law):

        NOT ( NOT p ) ≡ p

    This law is obvious (but it’s important).

  • De Morgan’s laws:

         NOT ( p AND q ) ≡  ( NOT p ) OR  ( NOT q )

     NOT ( p OR q  ) ≡ ( NOT p ) AND ( NOT q )

    I didn’t discuss these laws in the previous chapter, but they make good intuitive sense. For example, the first one says, loosely, that if it’s not the case that p and q are both true, then it must be the case that either p isn’t true or q isn’t true (or both). Be that as it may, the validity of both laws follows immediately from the truth tables. Here, for example, is the truth table corresponding to the first law:

    image with no caption

    Since the columns for NOT (p AND q) and (NOT p) OR (NOT q) are identical, the validity of the first law follows. Proof of the validity of the second is analogous (exercise for the reader).

  • The distributive laws:

         p AND ( q OR  r ) ≡ ( p AND q ) OR  ( p AND r )

  p OR  ( q AND r ) ≡ ( p OR  q ) AND ( p OR  r )

    I’ll leave the proof of these two to you. Note, however, that (as in fact I did mention in passing) I was using the first of these laws in the SQL example near the beginning of this section. You might also note that these distributive laws are a little more general, in a sense, than the ones we saw in Chapter 6. In that chapter we saw examples of a monadic operator, such as restriction, distributing over a dyadic operator, such as union; here, by contrast, we see dyadic operators (AND and OR) each distributing over the other.

  • The quantification law:

         FORALL x ( p ( x ) ) ≡ NOT EXISTS x ( NOT p ( x ) )

    I discussed this one in the previous chapter. In fact, I hope you can see it’s really just an application of De Morgan’s laws to EXISTS and FORALL expressions specifically (recall from the previous chapter that EXISTS and FORALL are basically just iterated OR and iterated AND, respectively).

One further remark on these laws: Because De Morgan’s laws in particular will often be applied to the result of a prior application of the implication law, it’s convenient to restate the first of them, at least, in the following form (in which q is replaced by NOT q and the double negation law has been tacitly applied):

     NOT ( p AND NOT q ) ≡ ( NOT p ) OR q

Or rather (but it’s the same thing, logically):

     ( NOT p ) OR q ≡ NOT ( p AND NOT q )

Equivalently:

     IF p THEN q ≡ NOT ( p AND NOT q )

Most of the references to one of De Morgan’s laws in what follows will be to this restated formulation.

The remainder of this chapter offers practical guidelines on the use of these laws to help in the formulation of “complex” SQL expressions. I’ll start with some very simple examples and build up gradually to ones that are quite complicated.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
18.217.101.72