SQL and Relational Theory, 3rd Edition

Chapter 11

Using Logic to Formulate SQL Expressions

There is science, logic, reason; there is thought verified by experience. And then there is California.¹

—Edward Abbey: A Voice Crying in the Wilderness (1989)

In Chapter 6, I described the process of expression transformation as it applied to expressions of the relational algebra; to be specific, I showed how one such expression could be transformed into another logically equivalent one, using various transformation laws. The laws I considered included such things as:

1. Restriction distributes over union, intersection, and difference

2. Projection distributes over union but not over intersection or difference

and several others. (As you might expect, analogous laws apply to expressions of the relational calculus also, though I didn’t say much about any such laws in Chapter 10.)

Now, the purpose of such transformations, as I discussed them earlier, was essentially optimization; the aim was to come up with an expression with the same semantics as the original one but better performance characteristics. But the concept of expression transformation—or query rewrite, as it’s sometimes (not very appropriately) known—has application in other areas, too. In particular, and very importantly, it can be used to transform precise logical expressions, representing queries and the like, into SQL equivalents. And that’s what this chapter is all about: It shows how to take the logical (i.e., relational calculus) formulation of, e.g., some query ...