An image relation is, loosely, the “image” within some relation of some tuple (usually a tuple within some other relation). For example, given the suppliers-and-parts database and our usual sample values, the following is the image within the shipments relation of the supplier tuple for supplier S4:
|
|
|
|
|
|
|
|
Clearly, this particular image relation can be obtained by means of the following Tutorial D expression
( SP WHERE SNO = 'S4' ) { ALL BUT SNO }Here’s a formal definition of image relations in general:
Definition: Let relations r1 and r2 be joinable (i.e., such that attributes with the same name are of the same type); let t1 be a tuple of r1; let t2 be a tuple of r2 that has the same values for those common attributes as tuple t1 does; let relation r3 be that restriction of r2 that contains all and only such tuples t2; and let relation r4 be the projection of r3 on all but those common attributes. Then r4 is the image relation (with respect to r2) corresponding to t1.
Here’s an example that illustrates the usefulness of image relations:
S WHERE ( !!SP ) { PNO } = P { PNO }Explanation:
First of all, the roles of r1 and r2 from the definition are being played by the suppliers relation and the shipments relation, respectively (where by “the suppliers relation” I mean the current value of relvar S, and similarly for “the shipments relation”).
Next, observe that the boolean expression in the WHERE clause involves an equality comparison between two relations (actually two projections). We can imagine that boolean expression being evaluated for each tuple t1 in r1 (i.e., each tuple in the suppliers relation) in turn.
Consider one such tuple, say that for supplier Sx. For that tuple, then, the expression !!SP—pronounced “bang bang SP” or “double bang SP”—denotes the corresponding image relation r4 within r2; in other words, it denotes the set of (PNO,QTY) pairs within SP for parts supplied by that supplier Sx.[95] The expression !!SP is an image relation reference.
The expression (!!SP){PNO}—i.e., the projection of the image relation on {PNO}—thus denotes the set of part numbers for parts supplied by supplier Sx.
The expression overall (i.e., S WHERE ...) thus denotes suppliers from S for whom that set of part numbers is equal to the set of all part numbers in the projection of P on {PNO}. In other words, it represents the query “Get suppliers who supply all parts” (speaking a little loosely).
Note: Since the concept of an image relation is defined in terms of some given tuple (t1, in the formal definition), it’s clear that an image relation reference can appear, not in all possible contexts in which relational expressions in general can appear, but only in certain specific contexts: namely, those in which the given tuple t1 is understood. WHERE clauses are one such context, as the foregoing example indicates, and we’ll see another in the section IMAGE RELATIONS bis, later in this chapter.
Aside: SQL has no direct support for image relations as such. Here for interest is an SQL formulation of the query “Get suppliers who supply all parts” (I show it for your consideration, but I’m not going to discuss it in detail, except to note that it can obviously (?) be improved in a variety of ways):
SELECT * FROM S WHERE NOT EXISTS ( SELECT PNO FROM SP WHERE SP.SNO = S.SNO EXCEPT CORRESPONDING SELECT PNO FROM P ) AND NOT EXISTS ( SELECT PNO FROM P EXCEPT CORRESPONDING SELECT PNO FROM SP WHERE SP.SNO = S.SNO )End of aside.
To get back to image relations as such, it’s worth noting that the “!!” operator can be defined in terms of MATCHING. For example, the example discussed above—
S WHERE ( !!SP ) { PNO } = P { PNO }—is logically equivalent to the following:
S WHERE
( SP MATCHING RELATION { TUPLE { SNO SNO } } ) { PNO } = P { PNO }Explanation: Again consider some tuple of S, say that for supplier Sx. For that tuple, then, the expression TUPLE {SNO SNO}—which is a tuple selector invocation—denotes a tuple containing just the SNO value Sx (the first SNO in that expression is an attribute name, the second denotes the value of the attribute of that name in the tuple for Sx within relvar S). So the expression
RELATION { TUPLE { SNO SNO } }—which is a relation selector invocation—denotes the relation that contains just that tuple. Hence, the expression
SP MATCHING RELATION { TUPLE { SNO SNO } }denotes a certain restriction of SP: namely, that restriction that contains just those shipment tuples that have the same SNO value as the supplier tuple for supplier Sx does. It follows that, in the context under consideration, the expression shown (“SP MATCHING ...”) is logically equivalent to the image relation reference “!!SP”, and the overall result follows.
By way of another example, suppose we’re given a revised version of the suppliers-and-parts database—one that’s simultaneously both extended and simplified, compared to our usual version—that looks like this (in outline):
S { SNO } /* suppliers */
SP { SNO , PNO } /* supplier supplies part */
PJ { PNO , JNO } /* part is used in project */
J { JNO } /* projects */Relvar J here represents projects (JNO stands for project number), and relvar PJ indicates which parts are used in which projects. Now consider the query “Get all (sno,jno) pairs such that sno is an SNO value currently appearing in relvar S, jno is a JNO value currently appearing in relvar J, and supplier sno supplies all parts used in project jno.” This is a complicated query!—but a formulation using image relations is almost trivial:
( S JOIN J ) WHERE !!PJ ⊆ !!SP
Exercise: Give an SQL analog of this expression.
Reverting now to the usual suppliers-and-parts database, here’s another example (“Delete shipments from suppliers in London”—and this time I’ll show an SQL analog as well):
For a given shipment, the relation denoted by the specified image relation reference (“!!(S WHERE ...”) is either empty, if the corresponding supplier isn’t in London, or contains exactly one tuple otherwise.
[95] As noted elsewhere in this book, in mathematics the expression “n!” (n factorial) is often pronounced “n bang”; hence my choice of pronunciation for the symbol “!!”.