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.
