The New Relational Database Dictionary

Examples: Let the symbols x and y denote integers. Then the following expressions are both predicates, and x appears as a free variable in both of them:

x < 7EXISTS y ( y > 3 ) AND x < 7

The first of these examples is self-explanatory. The second is a little more complicated, because it involves a quantified subexpression (in which y appears, twice, as a bound variable) as well as the free variable x.

Turning to a database example, the following is a query (“Get suppliers who supply at least one part”) on the suppliers-and-parts database, expressed in tuple calculus:

{ S } WHERE EXISTS SP ( SP.SNO = S.SNO )

The boolean expression following the keyword WHERE here is a predicate, and the reference to S in that predicate is free (by contrast, the references to SP are bound). Note, however, that in this particular example the symbols S and SP denote not only variables in the sense of logic but also variables in the conventional programming language sense—but that’s because we’ve indulged in a certain sleight of hand, as it were. Here’s an expanded version of the same example that should help clarify matters:

SX  RANGES OVER { S } ;SPX RANGES OVER { SP } ;{ SX } WHERE EXISTS SPX ( SPX.SNO = SX.SNO )

Here SX and SPX have been explicitly declared to be range variables (q.v.)—in other words, they’re variables in the sense of logic—ranging over (the current values of) relvars S and SP, respectively. Now it’s the reference to SX that’s free and the references to SPX that are bound (in the ...