Consider a simplified version of our usual suppliers and parts relvars in which suppliers have no attributes except SNO and CITY and parts have no attributes except PNO and CITY, thus:

S { SNO , CITY } KEY { SNO }
P { PNO , CITY } KEY { PNO }

Suppose also for the sake of the example that every supplier city is required to be a part city and vice versa—in other words, there’s a constraint in effect (actually an equality dependency once again) that looks like this:

CONSTRAINT ... S { CITY } = P { CITY } ;

In order to conform to this new requirement, let’s agree until further notice to drop the tuple for supplier S5 (city Athens) from our usual suppliers relation and the tuple for part P3 (city Oslo) from our usual parts relation.

Now let’s define the join of relvars S and P as a view SCP:

SCP { SNO , CITY , PNO } KEY { SNO , PNO }

Observe that the join here is indeed many to many, in the sense that (in general) every tuple in S joins to many tuples in P and vice versa. Nevertheless, we do have information equivalence, precisely because every tuple in either relvar does join to at least one tuple in the other. Sample values are shown in Figure 7-1.

Figure 7-1. Relvars S, P, and SCP—sample values

Here now are the predicates:^[93]

As usual, I’ll begin by considering what happens if all three relvars are base ones. If they are, what constraints hold? Well, first, the three relvars have {SNO}, {PNO}, and {SNO,PNO}, respectively, as their sole key (as already indicated). Second, we also clearly have:

CONSTRAINT ... SCP = S JOIN P ;
CONSTRAINT ... S   = SCP { SNO , CITY } ;
CONSTRAINT ... P   = SCP { PNO , CITY } ;

These constraints are, of course, all equality dependencies (EQDs), and together they ensure that the two designs—that consisting of just relvar SCP and that consisting of the combination of relvars S and P—are information equivalent, as previously claimed.

The following constraints—also EQDs—hold as well (actually they’re just logical consequences of the three just stated):

CONSTRAINT ... IDENTICAL { S { CITY } , P { CITY } , SCP { CITY } } ;
CONSTRAINT ... SCP = JOIN { SCP { SNO , CITY } , SCP { PNO , CITY } } ;

I want to elaborate somewhat on this last constraint, however. The fact that it holds means relvar SCP isn’t in fourth normal form (4NF), because the constraint in question is equivalent to the following join dependency (JD):

 { { SNO , CITY } , { PNO , CITY } }

And this JD in turn is equivalent to the following pair of multivalued dependencies (MVDs):

{ CITY } →→ { SNO }
{ CITY } →→ { PNO }

Or writing them as a “one liner”:

{ CITY } →→ { SNO } | { PNO }

These MVDs are neither trivial nor implied by the sole key {SNO,PNO} of SCP, and SCP is thus not in 4NF.^[94] Note: Informally, what these MVDs mean is this: If tuples (c, s, p) and (c, s’;, p’) appear in the relvar, then tuples (c, s, p’) and (c, s’, p) must appear as well (where c is a city, s and s’ are supplier numbers, and p and p’ are part numbers). By way of illustration of this point (with reference to Figure 7-1), take c as Paris, s and s’ as S2 and S3, respectively, and p and p’ as P2 and P5, respectively.

Of course, the fact that the foregoing MVDs hold in relvar SCP isn’t a fluke—it will always be the case with a many to many join that MVDs like those just shown hold. And the reason I mention all this is that relvars in which such MVDs hold (i.e., relvars not in 4NF) are of course subject to redundancy, and it’s generally true that relvars that are subject to redundancy can be awkward to update—as we’ll see later, in the case at hand.

While I’m on the subject of dependencies, let me also point out that the following functional dependencies (FDs) hold in relvar SCP as well:^[95]

{ SNO } → { CITY }
{ PNO } → { CITY }

These FDs are inherited from relvars S and P, respectively (where they certainly hold, because the determinant—the set of attributes on the left side—is a key in each case).

INSERT ( S9 , London ) INTO S ;

( S9 , London , P1 )
( S9 , London , P4 )
( S9 , London , P6 )

INSERT ( S9 , Madrid ) INTO S ;

INSERT ( S9 , Madrid ) INTO S ,
INSERT ( P8 , Madrid ) INTO P ;

( S9 , Madrid , P8 )

ON INSERT is INTO S , INSERT ip INTO P :
   INSERT ( P JOIN is ) INTO SCP ,
   INSERT ( S JOIN ip ) INTO SCP ;

DELETE ( S5 , Athens ) FROM S ,
DELETE ( P3 , Athens ) FROM P ;

DELETE ( S5 , Athens ) FROM S ;

ON DELETE ds FROM S , DELETE dp FROM P :
   DELETE ( SCP JOIN ds ) FROM SCP ,
   DELETE ( SCP JOIN dp ) FROM SCP ;

ON INSERT i INTO SCP :
   INSERT i { SNO , CITY } INTO S ,
   INSERT i { PNO , CITY } INTO P ;

ON DELETE d FROM SCP :
   DELETE ( ( S MATCHING d ) NOT MATCHING SCP ) FROM S ,
   DELETE ( ( P MATCHING d ) NOT MATCHING SCP ) FROM P ;

ON DELETE d FROM S :
   DELETE d { SNO , STATUS } FROM ST ,
   DELETE d { SNO , CITY } FROM SC ;

{ SNO } → { CITY }
{ PNO } → { CITY }

{ CITY } →→ { SNO } | { PNO }

CONSTRAINT ... SCP = JOIN { SCP { SNO , CITY } , SCP { PNO , CITY } } ;

ON INSERT i INTO SCP :
   INSERT ( SCP JOIN i { SNO , CITY } ) INTO SCP ,
   INSERT ( SCP JOIN i { PNO , CITY } ) INTO SCP ;

I’ve discussed the case in which S and P are base relvars and SCP is a view. To complete my examination of Example 1, I ought really to discuss the inverse situation also, in which SCP is a base relvar and S and P are views of that relvar. Of course, S and P would then be projection views specifically, and such a discussion thus logically belongs in Chapter 5. Rightly or wrongly, however, I felt Chapter 5 was complicated enough already, and so I decided to defer that discussion to the present chapter.

Actually I don’t think there’s all that much to be said. Recall from Chapter 5 that if DB1 contains just a single relvar R and DB2 contains just projections of R, then DB1 and DB2 are information equivalent only if those projections are obtained by decomposing R in accordance with some join dependency (JD) that holds in R. Well, the following JD does hold in SCP:

 { { SNO , CITY } , { PNO , CITY } }

As a direct consequence, SCP can be nonloss decomposed into its projections on {SNO,CITY} and {PNO,CITY}—in other words, into relvars S and P—and those relvars are necessarily updatable (just so long as SCP itself is updatable in the first place, which of course it is). The various compensatory actions are as previously discussed:

ON INSERT i INTO SCP :
   INSERT i { SNO , CITY } INTO S ,
   INSERT i { PNO , CITY } INTO P ;

ON DELETE d FROM SCP :
   DELETE ( ( S MATCHING d ) NOT MATCHING SCP ) FROM S ,
   DELETE ( ( P MATCHING d ) NOT MATCHING SCP ) FROM P ;

ON INSERT is INTO S , INSERT ip INTO P :
   INSERT ( P JOIN is ) INTO SCP ,
   INSERT ( S JOIN ip ) INTO SCP ;

ON DELETE ds FROM S , DELETE dp FROM P :
   DELETE ( SCP JOIN ds ) FROM SCP ,
   DELETE ( SCP JOIN dp ) FROM SCP ;

Let me now add that (of course) the relationship between views S and P is many to many. And although I didn’t discuss this specific example in Chapter 5, I did in fact discuss another example in that chapter involving projection views in a many to many relationship—namely, Example 3, which involved views ST (the projection of S on SNO and STATUS) and TC (the projection of S on STATUS and CITY). To spell the point out, the relationship in that example was indeed many to many, because the same STATUS value could be associated with many suppliers and many cities (STATUS value 30 is a case in point, given our usual sample values). However, that example involved a lossy decomposition, not a nonloss one. As a consequence, updates on the projection relvars didn’t always work terribly well.

Let’s get back to the case in which S and P are both base relvars. Suppose now that (as in our original suppliers-and-parts database, in fact) a city can be represented in base relvar S and not base relvar P or the other way around; in other words, some cities have suppliers but no parts or vice versa). Then the join SCP of S and P loses information, inasmuch as it’s no longer guaranteed that S and P are equal to the projections of that join on the corresponding attributes. In fact, of the constraints mentioned in the section before last, the only ones that still apply are the following (and this time I’ll give them in prose form instead of formal syntax):

(Certain inclusion dependencies hold too, but as with the second example in Chapter 6, I won’t bother to spell out the details here.)

A concrete example of a database value satisfying the foregoing conditions can be obtained by extending Figure 7-1 to reinstate the usual tuples for supplier S5 and part P3 (see Figure 7-2, and observe in particular that the relation shown as the current value of relvar SCP in that figure is the same as it was in Figure 7-1).

Figure 7-2. A revised version of Figure 7-1

Following on from the foregoing, let me now point out that, precisely because (as I’ve said) it loses information, the design consisting of relvar SCP alone is no longer information equivalent to the one consisting of relvars S and P taken together. (An example of a query on the latter that has no exact counterpart on the former is “Get supplier numbers for suppliers in a city in which there’s no part.”). More precisely, any information that can be represented by relvar SCP alone can certainly be represented by relvars S and P together, but the converse is false. As a consequence, it’s obvious that there are going to be certain updates that can be done on S and/or P that have no exact counterpart on SCP. An example is “Insert a tuple into S for a supplier with city Madrid,” without simultaneously inserting a tuple for that same city into P.

I don’t propose to investigate this example in any further detail here. Instead, I’m simply going to appeal to the analysis of Example 2 in Chapter 6; to be more specific, I’m going to claim that the detailed analysis of that example in that previous chapter applies to the present example also, mutatis mutandis. In other words, it’s my opinion that the rules developed earlier in the present chapter for updating a strict many to many join view can be taken, if desired, to apply to the present case as well. To paraphrase a remark from the discussions in Chapter 6, if we can agree on this position, then at least we’ll have agreed on a universal set of rules for updating many to many join views that do always work and do guarantee that joins are strictly many to many when they’re supposed to be—not to mention the point that the rules in question in fact work for all join views, regardless of whether the join in question is one to one, one to many, or many to many. What’s more, if those rules do sometimes give rise to consequences that are considered unpalatable for some reason, then there are always certain pragmatic fixes, such as using the DBMS’s authorization subsystem to prohibit certain updates, that can be adopted to avoid those consequences.

There’s one more point I want to make in connection with many to many joins. It has to do with the fact that—as is of course well known—cartesian product is a special case of many to many join. It follows that the rules for updating through a many to many join apply to cartesian product in particular (more precisely, they reduce to the rules for updating through a cartesian product, in the case where the join itself reduces to a cartesian product). To spell those rules out, let V be defined as A TIMES B and let HA and HB be the attributes of A and B, respectively, and let HA and HB have no attribute names in common. Then we have:

ON INSERT i INTO V :
   INSERT i { HA } INTO A ,
   INSERT i { HB } INTO B ;

ON DELETE d FROM V :
   DELETE ( ( A MATCHING d ) NOT MATCHING V ) FROM A ,
   DELETE ( ( B MATCHING d ) NOT MATCHING V ) FROM B ;

ON INSERT ia INTO A , INSERT ib INTO B :
   INSERT ( B TIMES ia ) INTO V ,
   INSERT ( A TIMES ib ) INTO V ;

ON DELETE da FROM A , DELETE db FROM B :
   DELETE ( V MATCHING da ) FROM V ,
   DELETE ( V MATCHING db ) FROM V ;