1 Introduction to Databases 2 2 Basic Relational Data Model 11

Figure 7-4 Product and Transaction relations with associated tuple variables

Consider, for example, the Product and Transaction relations in Figure 7 -4, with tuple variables P ranging over the former and T over the latter. The rule

P.Pname: T (T.P# = P.P# And T.C# = 1)

is interpreted as the query to find values of the free variable P such that there exists at least one value of the bound variable T satisfying the formula “T.P# = P.P# And T.C# = 1”. As before, evaluation of the expression is in the context of some instantiations of the variables. All possible values of P must be considered, but for each we need only find one value of T to satisfy expression. Once we have done that, other possible values of T, if any, may be ignored. For example, with P instantiated to the first tuple of Product, we consider in turn tuples of Transaction as values of T. We will find in fact that the first already satisfies the expression and we may therefore ignore the others. With P set to the second tuple, however, we will find no value for T to satisfy the expression. The result for this example therefore is only one value for P, with P.Pname=CPU.

As another example, consider the relations in Figure 7 -5 with associated tuple variables as shown. Suppose, we are interested in finding the names of customers who bought the product CPU. That is, our target is the value X.Cname, but only if X is a customer who has bought the product CPU. In other words, there must exist a Y such that “X.C# = Y.C#”. This would establish that X bought a product, denoted by Y.P# (the product number). Furthermore, this product must be a CPU, ie. there must exist a Z such that “Y.P# = Z.P#” and “Z.Pname = CPU”. Thus, the rule corresponding to our query is

X.Cname: Y Z ( X.C# = Y.C# & Y.P# = Z.C# & Z.Pname = CPU )

T
he reader can verify that the answer satisfying this query is {Codd, Martin}.

Figure 7-5 Product, Customer and Transaction relations with associated tuple variables

Using again the relations in Figure 7 -5, let’s look at a more complex query: get the names of customers who bought the product CPU and VDU. At first glance, this seems a simple extension of the above query:

X.Cname: Y Z ( X.C# = Y.C# & Y.P# = Z.C# &

Z.Pname = CPU & Z.Pname = VDU )

But the reader who remembers a similar example in section 6.1 would have noted a problem. Specifically, the subexpression “Z.Pname = CPU & Z.Pname = VDU” can never be true for a given value of Z—a field of a given tuple can only hold one value, so only one or the other can be true but not both! Of course what we mean to specify is that the customer purchased at least one product which is a CPU, and another which is a VDU. Since a tuple variable can hold only one value at a time, this clearly cannot be done using only one tuple variable. The solution, therefore, is to introduce additional distinct variables to range over the same relation when more than one tuple is to be considered at a time (note that relational calculus places no restriction on the number of distinct variables that can range over a relation). For this particular example, we need only introduce one additional variable each for the relations Transaction and Product respectively, as shown in Figure 7 -6. This will allow us to consider two separate purchases at one time. The correct formulation, therefore, is:

X.Cname: T1 T2 P1 P2 ( X.C# = T1.C# & X.C# = T2.C# &

Figure 7 -6
additionally shows particular values of these variables that satisfy our query.

Figure 7-6 Multiple variables ranging over a relation

Let’s turn now to the universal quantifier. Informally, the formula “x ( )” asserts that for every value of x (from among its range of values) is true. Like the existential quantifier, the truth of an existentially quantified expression is not a function of the quantified variable(s). Consider, for example, the unquantified expression

x < y | y < 12

and suppose x ranges over {4,15} and y over {7,14}. The truth table for the expression is:

x	y	x
4	7	true
4	14	true
15	7	true
15	14	false

Now consider the same expression but with x universally quantified:

x (x < y | y < 12)

In a sense, like the existentially quantified variable, we don’t care what the values of x are, as long as every one of them makes the expression true for any given y. Thus its truth table is:

y	x (x
7	true
14	false

“get the names of customers who bought every type of product”

Assume the relations as in Figure 7 -5. The phrase “every type of product” clearly means every tuple of the Product relation. However, the Product relation does not record purchases, which are found only in the Transaction relation, ie. a product is purchased (by someone) if there is a transaction recording its purchase. In other words, a customer (ie. X) satisfies this query if for every product (ie. Z) there is a transaction (ie. Y) recording its purchase by the customer. This can now be quite simply rewritten in the calculus:

X.Cname: Z Y (X.C# = Y.C# & Y.P# = Z.P#)

Note that the different types of quantifiers can be mixed. But note also that their order is significant, ie. x y ( ) is not the same as y x ( ). For example,

x y ( y is the mother of x)

asserts that everyone has a mother. Whereas,

y x ( y is the mother of x)

asserts that there is a single individual (y) who is the mother of everyone!