Databases Reference

In-Depth Information

Before I try to answer this question, I want to offer a simpler illustration of the same point. With reference

again to Fig. 1.1, consider the six shipment (SP) tuples shown in that figure for supplier S1. Clearly, those tuples all

contain the subtuple (S1), of degree one. And those six appearances of that subtuple all mean the same thing:

2.

Supplier S1 supplies some part in some quantity.

We could even take the argument one step further and consider the fact that
every
SP tuple─in fact, every

possible tuple, no matter what attributes it has─always has the 0-tuple as a subtuple. Thus, the twelve

“appearances” (if you see what I mean!) of that subtuple in the shipments relation of Fig. 1.1 all represent the

following proposition:

3.

Some supplier supplies some part in some quantity.

So do we have redundancy on our hands here, or don't we? Well, let me observe now that the foregoing

propositions 1- 3 all involve some
existential quantification
. Here are slightly more formal versions of those

propositions:

1.

There exists some part PNO such that
supplier S1 supplies part PNO in quantity 100.

2.

There exists some part PNO such that there exists some quantity QTY
such that supplier S1 supplies part

PNO in quantity QTY.

3.

There exists some supplier SNO such that there exists some part PNO such that there exists some quantity

QTY
such that supplier SNO supplies part PNO in quantity QTY.

In these propositions, SNO in the third, QTY in the second and third, and PNO in all three aren't parameters

but what the logicians call
bound variables
, owing to the fact that they're all “existentially quantified” by the phrase

There exists some ... such that
.
Note:
If you're unfamiliar with these notions (viz., bound variables and existential

quantification), you can find a tutorial treatment in
SQL and Relational Theory
. However, I think the present

discussion should be easy enough to follow even if you don't have any prior knowledge of such matters.

In contrast to the foregoing, the propositions represented by tuples in the underlying relvar SP don't involve

any existential quantifiers. That's because they're all just instantiations of the relvar predicate (i.e., they're all

obtained just by substituting arguments for the parameters of that predicate), and that predicate in turn, which is as

follows, involves no such quantifiers either:

Supplier SNO supplies part PNO in quantity QTY.

To summarize to this point, then, it looks as if the following observations apply:

a.

What might be called the given propositions─the ones represented by tuples in the given relvars─are

quantifier free.

Aside:
It might not be quite true to say the given propositions are always quantifier free; consider, e.g., a

relvar with attributes WEIGHT and HEIGHT and predicate
Some person has weight WEIGHT and height

HEIGHT
. However, we can effectively eliminate the quantifiers in such a situation by a process known as

skolemization
(after the logician T. A. Skolem). In the example, that process involves replacing the original

predicate by a predicate of the form
Person p has weight WEIGHT and height HEIGHT
(where
p
denotes

some person or persons unknown). This latter predicate is quantifier free.
End of aside.