CHAPTER 6

First of all, here are answers to a couple of exercises that were stated inline in the body of the chapter. The first asked what the difference was, given our usual sample data, between the expressions P JOIN (S{CITY}) and (P JOIN S){CITY}. Answer: The first yields full part details (PNO, PNAME, COLOR, WEIGHT, and CITY) for parts in the same city as at least one supplier, the second yields just CITY values for those same parts (speaking a trifle loosely in both cases).

The second exercise asked what the difference was between an equijoin and a natural join. Answer: Let the relations to be joined be r1 and r2, and assume for simplicity that r1 and r2 have just one common attribute, A. Before we can perform the equijoin, then, we need to do some renaming. For definiteness, suppose we apply the renaming to r2, to yield r3 = r2 RENAME {A AS B}. Then the equijoin is defined to be equal to (r1 TIMES r3) WHERE A = B. Note in particular that A and B are both attributes of the result, and every tuple in that result will have the same value for those two attributes. Projecting attribute B away from that result yields the natural join r1 JOIN r2.

6.1 a. The result has duplicate column names (as well as left to right column ordering). b. The result has left to right column ordering. c. The result has an unnamed column (as well as left to right column ordering). d. The result has duplicate rows (even though the SELECT clause explicitly specifies S.SNO, not SP.SNO, and SNO values are unique in table S). e. Compile time error: S NATURAL JOIN P has no column called S.CITY.[203] f. Nothing wrong (though it would be nice if CORRESPONDING were specified). g. The result has duplicate rows and left to right column ordering; it also has no SNO column, a fact that might come as a surprise.[204] h. The result has duplicate column names (as well as left to right column ordering). i. Compile time error: AS specification not allowed (because the expression “(S NATURAL JOIN P)” is neither a table name nor a table subquery—see Chapter 12). j. The result has duplicate column names (as well as left to right column ordering).

6.2 No! In particular, certain relational divides that you might expect to fail don’t. Here are some examples (which won’t make much sense until you’ve read the relevant section of Chapter 7):

  • Let relation z be of type RELATION {PNO CHAR} and let its body be empty. Then the expression

         SP { SNO , PNO } DIVIDEBY z { PNO }

    reduces to the projection SP{SNO} of SP on SNO.

  • Let z be either TABLE_DEE or TABLE_DUM. Then the expression

         r DIVIDEBY z

    reduces to r JOIN z. In other words, if z is TABLE_DEE, the result is just r; if z is TABLE_DUM, the result is the empty relation of the same type as r.

  • Let relations r and s be of the same type. Then the expression

         r DIVIDEBY s

    gives TABLE_DEE if r is nonempty and every tuple of s appears in r, TABLE_DUM otherwise.

  • Finally, r DIVIDEBY r gives TABLE_DUM if r is empty, TABLE_DEE otherwise.

6.3 The joining attributes are SNO, PNO, and CITY (each of which is a common attribute for exactly two of the relations to be joined, as it happens). The result predicate is: Supplier SNO is under contract, is named SNAME, has status STATUS, and is located in city CITY; part PNO is used in the enterprise, is named PNAME, has color COLOR and weight WEIGHT, and is stored in city CITY; and supplier SNO supplies part PNO in quantity QTY. Note that both appearances of SNO in this predicate refer to the same parameter, as do both appearances of PNO and both appearances of CITY. Given our usual sample values, the result looks like this:

SNO

SNAME

STATUS

CITY

PNO

QTY

PNAME

COLOR

WEIGHT

S1

Smith

20

London

P1

300

Nut

Red

12.0

S1

Smith

20

London

P4

200

Screw

Red

14.0

S1

Smith

20

London

P6

100

Cog

Red

19.0

S2

Jones

10

Paris

P2

400

Bolt

Green

17.0

S3

Blake

30

Paris

P2

200

Bolt

Green

17.0

S4

Clark

20

London

P4

200

Screw

Red

14.0

The simplest SQL formulation is just

     S NATURAL JOIN SP NATURAL JOIN P

(though it might be necessary to prefix this expression with “SELECT * FROM,” depending on context—see Chapter 12).

6.4 In 2-dimensional cartesian geometry, the points (x,0) and (0,y) are the projections of the point (x,y) on the X axis and the Y axis, respectively; equivalently, (x) and (y) are the projections into certain 1-dimensional spaces of the point (x,y) in 2-dimensional space. These notions are readily generalizable to n dimensions (recall from Chapter 3 that relations are indeed n-dimensional).

6.5 Throughout these answers, I show SQL expressions that aren’t necessarily direct transliterations of their algebraic counterparts but are, rather, “more natural” formulations of the query in SQL terms.

  1. SQL analog:

         SELECT DISTINCT CITY
         FROM   S NATURAL JOIN SP
         WHERE  PNO = 'P2'

    Predicate: City CITY is such that some supplier who supplies part P2 is located there.

    CITY

    London

    Paris

  2. SQL analog:

         SELECT *
         FROM   P
         WHERE  PNO NOT IN
              ( SELECT PNO
                FROM   SP
                WHERE  SNO = 'S2' )

    Predicate: Part PNO is used in the enterprise, is named PNAME, has color COLOR and weight WEIGHT, is stored in city CITY, and isn’t supplied by supplier S2.

    PNO

    PNAME

    COLOR

    WEIGHT

    CITY

    P3

    Screw

    Blue

    17.0

    Oslo

    P4

    Screw

    Red

    14.0

    London

    P5

    Cam

    Blue

    12.0

    Paris

    P6

    Cog

    Red

    19.0

    London

  3. SQL analog:

         SELECT CITY
         FROM   S
         EXCEPT CORRESPONDING
         SELECT CITY
         FROM   P

    Predicate: City CITY is such that some supplier is located there but no part is stored there.

    CITY

    Athens

  4. SQL analog:

         SELECT SNO , PNO
         FROM   S NATURAL JOIN P

    Note: There’s no need to do the preliminary projections (of S on {SNO,CITY} and P on {PNO,CITY}) in the Tutorial D version, either. Do you think the optimizer might ignore them?

    Predicate: Supplier SNO and part PNO are colocated.

    SNO

    PNO

    S1

    P1

    S1

    P4

    S1

    P6

    S2

    P2

    S2

    P5

    S3

    P2

    S3

    P5

    S4

    P1

    S4

    P4

    S4

    P6

  5. SQL analog:

         SELECT S.CITY AS SC , P.CITY AS PC
         FROM   S , P

    Predicate: Some supplier is located in city SC and some part is stored in city PC.

SC

PC

London

London

London

Paris

London

Oslo

Paris

London

Paris

Paris

Paris

Oslo

Athens

London

Athens

Paris

Athens

Oslo

6.6 Intersection and product are both special cases of join, so we can ignore them here. The fact that union and join are commutative is immediate from the fact that the definitions are symmetric in the two relations concerned. I now show that union is associative. Let t be a tuple. Using “≡” to stand for “if and only if” (or “is equivalent to”) and “∈” to stand for “appears in,” we have:

     tr UNION ( s UNION u )  ≡  tr OR t ∈ ( s UNION u )
                                ≡  tr OR ( ts OR tu )
                                ≡  ( tr OR ts ) OR tut ∈ ( r UNION s ) OR tut ∈ ( r UNION s ) UNION u

Note the appeal in the third line to the associativity of OR. The proof that join is associative is analogous. As for SQL, well, let’s first of all ignore nulls and duplicate rows (what happens if we don’t?). Then:

  • SELECT A, B FROM T1 UNION CORRESPONDING SELECT B, A FROM T2 and SELECT B, A FROM T2 UNION CORRESPONDING SELECT A, B FROM T1 aren’t equivalent, because they produce results with different left to right column orderings. Thus, union in general isn’t commutative in SQL (and the same goes for intersection).

  • T1 JOIN T2 and T2 JOIN T1 aren’t equivalent (in general), because they produce results with different left to right column orderings. Thus, join in general isn’t commutative in SQL (and the same goes for product).

The operators are, however, all associative.

6.7 RENAME is the only one—and even that one’s debatable! See the answer to Exercise 7.3 later in this appendix.

6.8 The product of a single table t is defined to be just t. But the question of what the product of t1 and t2 is if t1 and t2 both contain duplicate rows is a tricky one! See the answer to Exercise 4.4 earlier in this appendix for further discussion.

6.9 Tutorial D on the left, SQL on the right, as usual (the solutions aren’t unique, in general; note too that the Tutorial D solutions in particular could often be improved by using operators to be described in Chapter 7):

  1. image with no caption
  2. image with no caption
  3. image with no caption
  4. image with no caption
  5. image with no caption
  6. image with no caption
  7. image with no caption

    Note: The expression STATUS FROM (TUPLE FROM ...) in the Tutorial D solution here extracts the STATUS value from the single tuple in the relation that’s the TUPLE FROM argument (that relation must have cardinality one). By contrast, the SQL solution effectively does a double coercion: First, it coerces a table of one row to that row; second, it coerces that row to the single scalar value it contains.

  8. image with no caption

    Note the use of a relational comparison in the Tutorial D expression here. The SQL version uses EXISTS (see Chapter 10). A more elegant Tutorial D solution can be found as the answer to Exercise 7.9e later in this appendix.

  9. image with no caption
  10. image with no caption

    A more elegant Tutorial D solution can be found as the answer to Exercise 7.9f later in this appendix.

6.10 It’s intuitively obvious that all three statements are true. No further answer provided.

6.11 Union isn’t idempotent in SQL, because the expression SELECT * FROM T UNION CORRESPONDING SELECT * FROM T isn’t identically equal to SELECT * FROM T. That’s because if T contains any duplicates, they’ll be eliminated from the result of the union. (And what happens if T contains any nulls? Good question!)

Join is idempotent, and therefore so are intersection and cartesian product—in all cases, in the relational model but not in SQL, “thanks” again to duplicates and nulls.

6.12 As explained in the body of the chapter, the expression r{} denotes the projection of r on no attributes; it returns TABLE_DUM if r is empty and TABLE_DEE otherwise. The answer to the question “What’s the corresponding predicate?” depends on what the predicate for r is. For example, the predicate for SP{} is (a trifle loosely): There exists a supplier SNO, there exists a part PNO, and there exists a quantity QTY such that supplier number SNO supplies part PNO in quantity QTY. Note that this predicate is in fact a proposition; if SP is empty (in which case SP{} is TABLE_DUM) it evaluates to FALSE, otherwise (in which case SP{} is TABLE_DEE) it evaluates to TRUE.

The expression r{ALL BUT} denotes the projection of r on all of its attributes (in other words, it denotes the identity projection of r); it returns r. The corresponding predicate is identical to that for r.

6.13 So far as I know, DB2 and Ingres both perform this kind of optimization (DB2 refers to it as “predicate transitive closure”). Other products might do so too.

6.14 The expression means “Get suppliers who supply all purple parts.” Of course, the point is that (given our usual sample data values) there aren’t any purple parts. The expression correctly returns a relation identical to the current value of relvar S (i.e., all five suppliers, loosely speaking). For further explanation—in particular, for justification of the fact that this is indeed the correct answer—see Chapter 11.

6.15 For S{CITY} D_UNION P{CITY}, a rough equivalent in SQL might look like this:

     SELECT CITY
     FROM ( SELECT CITY FROM S
            UNION  CORRESPONDING
            SELECT CITY FROM P ) AS TEMP
     WHERE  NOT EXISTS
          ( SELECT    CITY FROM S
            INTERSECT CORRESPONDING
            SELECT    CITY FROM P )

This SQL expression isn’t precisely equivalent to the original, however. To be specific, if supplier cities and part cities aren’t disjoint, then the SQL expression won’t fail at run time but will simply return an empty result. Note: The CORRESPONDING specifications could safely be omitted in this example—why, exactly?—but it’s easier, and shouldn’t hurt, always to specify CORRESPONDING, even when it’s logically unnecessary. As for the AS TEMP specification, it’s required—on the subquery in the FROM clause but not on the subquery in the WHERE clause (where in fact it would be illegal!)—for reasons explained in Chapter 7.

Turning now to S{CITY} I_MINUS P{CITY}, a rough equivalent in SQL might look like this:

     SELECT CITY
     FROM ( SELECT CITY FROM S
            EXCEPT CORRESPONDING
            SELECT CITY FROM P ) AS TEMP
     WHERE  NOT EXISTS
          ( SELECT CITY FROM P
            EXCEPT CORRESPONDING
            SELECT CITY FROM S )

Again, however, this SQL expression isn’t precisely equivalent to the original, however. To be specific, if part cities aren’t a subset of supplier cities, then the SQL expression won’t fail at run time but will simply return an empty result.

6.16 Relations r1 and r2 are joinable if and only if attributes with the same name are of the same type (equivalently, if and only if the set theory union of their headings is a legal heading). That’s the dyadic case. Extending the definition to the n-adic case is easy: Relations r1, r2, ..., rn (n > 0) are joinable if and only if, for all i, j (1 ≤ in, 1

6.17 It’s possible to define n-adic versions of JOIN, UNION, and D_UNION because the operators (a) are all both commutative and associative and (b) all have a corresponding identity value.

SQL does effectively support (analogs of) n-adic join and union, though not for n < 2. For join, the syntax is:

     [ SELECT * FROM ] t1 NATURAL JOIN t2
                          NATURAL JOIN t3
                            ...........
                          NATURAL JOIN tn

For union, the syntax is:

     SELECT * FROM t1 UNION CORRESPONDING SELECT * FROM t2
                      UNION CORRESPONDING SELECT * FROM t3
                        ................................
                      UNION CORRESPONDING SELECT * FROM tn

An n-adic version of MINUS or I_MINUS makes no sense because MINUS and I_MINUS are neither commutative nor associative, nor do they have a corresponding identity value.

6.18 For a brief justification, see the answer to Exercise 6.12 above. A longer one follows. Consider the projection S{SNO} of (the relation that’s current value of) the suppliers relvar S on {SNO}. Let’s refer to the result of this projection as r; given our usual sample data values, r contains five tuples. Now consider the projection of that relation r on the empty set of attributes, r{}. As we saw in the answer to Exercise 3.16 earlier in this appendix, projecting any tuple on no attributes at all yields an empty tuple; thus, every tuple in r produces an empty tuple when r is projected on no attributes. But all empty tuples are duplicates of one another; thus, projecting the 5-tuple relation r on no attributes yields a relation with no attributes and one (empty) tuple, or in other words TABLE_DEE.

Now recall that every relvar has an associated predicate. For relvar S, that predicate looks like this:

Supplier SNO is under contract, is named SNAME, has status STATUS, and is located in city CITY.

For the projection r = S{SNO}, it looks like this:

There exists some name SNAME, there exists some status STATUS, and there exists some city CITY such that supplier SNO is under contract, is named SNAME, has status STATUS, and is located in city CITY.

And for the projection r{}, it looks like this:

There exists some supplier number SNO, there exists some name SNAME, there exists some status STATUS, and there exists some city CITY such that supplier SNO is under contract, is named SNAME, has status STATUS, and is located in city CITY.

Observe now that this last predicate is in fact a proposition: It evaluates to TRUE or FALSE, unequivocally. In the case at hand, r{} is TABLE_DEE and the predicate (proposition) evaluates to TRUE. But suppose no suppliers at all were represented in the database at this time. Then S{SNO} would yield an empty relation r, r{} would be TABLE_DUM, and the predicate (proposition) in question would evaluate to FALSE.

6.19 The expression returns the current value of table S—unless table P is currently empty, in which case it returns an empty result.



[203] It doesn’t really have a column called S.SNO, either (it has a column called SNO, unqualified, instead); however, there’s a bizarre syntax rule to the effect that the column can be referred to by that qualified name anyway, as in the case at hand. (When I say the rule is bizarre, I mean it’s extremely difficult to state precisely, as well as being both counterintuitive and logically incorrect.)

[204] In other words, although a column reference of the form “S.SNO” would be legal in the SELECT clause here—see part e. of the exercise—the expanded form of the expression “S.*” in that same context includes no such reference!

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.138.143.108