Databases Reference
In-Depth Information
context. I refer here to the point, explained in Chapter 2, that compensatory actions aren't driven
by the arbitrary choice of syntax in which the pertinent update happens to have been formulated.)
More recently, however, I began to wonder whether it might perhaps not be valid after all, or at
best only partly valid. The reasons for this shift in attitude on my part are explained in the next
couple of sections, but what they boil down to is this: It's all too easy to find examples where—
on the face of it, at least—such a principle simply doesn't seem to hold up. What's more, the
machinations that one has to go through in attempts to make it hold up after all get increasingly
baroque (epicycles upon epicycles, as it were). All of which makes the following quote from
Enrico Bombieri
2
(one of my favorite quotes, incidentally) increasingly germane: “When things
get too complicated, it sometimes makes sense to stop and wonder: Have I asked the right
question?”
Now read on ...
SOME WELL KNOWN TAUTOLOGIES
In logic, a tautology is something that's unconditionally true; more precisely, it's a predicate
whose every possible invocation is guaranteed to yield TRUE, regardless of what arguments are
substituted for its parameters if any. For example,
p
OR NOT
p
, where
p
is an arbitrary
proposition, is a tautology, and so is 1+1 = 2. (This latter is in fact a proposition, of course, and
it doesn't actually have any parameters.)
Now, tautologies of the form
exp1
≡
exp
(where
exp1
and
exp2
are arbitrary expressions
and the symbol “≡” denotes logical equivalence)
3
are particularly important, because they allow
an expression containing an occurrence of
exp1
to be rewritten as one containing an occurrence
of
exp2
instead. To spell the point out, let
X1
be an expression containing an occurrence of
exp1
as a subexpression; let
exp2
be logically equivalent to
exp1
; and let
X2
be the expression
obtained from
X1
by substituting an occurrence of
exp2
for the occurrence of
exp1
in question.
Then
X1
and
X2
are logically equivalent in turn; hence,
X1
can be rewritten as
X2
.
By way of illustration, I remind you of Example 1 from the previous section. In that
example, I was effectively appealing to the fact that the expression
( S WHERE CITY = 'London' OR CITY = 'Paris' )
≡
( ( S WHERE CITY = 'London' ) UNION ( S WHERE CITY = 'Paris' ) )
is a tautology.
Note:
Of course, I'm sure you're familiar with all of these ideas, since they form
the basis of one of the important things that relational optimizers are supposed to do: namely,
expression transformation
, sometimes known as “query rewrite.” See
SQL and Relational
Theory
for further discussion.
2
Fields Medalist and IBM von Neumann professor of mathematics at the Princeton Institute for Advanced Study, New Jersey.
3
Expressions
exp1
and
exp2
are logically equivalent if and only if each can be derived from the other in accordance with the
rules of inference of the logical system in effect.
