EXAMPLE 7: DEALING WITH AMBIGUITY

As we saw in Chapter 10, natural language is often ambiguous. For example, consider the following query: “Get suppliers such that every part they supply is in the same city.” First of all, notice the subtle (?) difference between this example and the previous one. Second, and more important, note that this natural language formulation is indeed ambiguous! For the sake of definiteness, I’m going to assume it means the following:

Get suppliers SX such that for all parts PX and PY, if SX supplies both of them, then PX.CITY = PY.CITY.

Observe that a supplier who supplies just one part will qualify under this interpretation. (So will a supplier who supplies no parts at all, incidentally.) Alternatively, the query might mean:

Get suppliers SX such that (a) SX supplies at least two distinct parts and (b) for all pairs of distinct parts PX and PY, if SX supplies both of them, then PX.CITY = PY.CITY.

Now a supplier who supplies just one part or no parts at all won’t qualify.

As I’ve said, I’m going to assume the first interpretation, just to be definite. But note that ambiguities of this kind are quite common with complex queries and complex business rules, and another advantage of logic in the context at hand is precisely that it can pinpoint and help resolve such ambiguities.

Here then is a logical formulation for the first interpretation:

     { SX } WHERE FORALL PX ( FORALL PY
          ( IF   EXISTS SPX ( SPX.SNO = SX.SNO AND SPX.PNO = PX.PNO )
            AND  EXISTS SPY ( SPY.SNO = SX.SNO AND SPY.PNO = PY.PNO )
            THEN PX.CITY = PY.CITY ) )

And here are the transformations (again I’ll leave it to you to decide just which law is being applied at each stage):

     { SX } WHERE FORALL PX ( FORALL PY
                ( IF exp1 AND exp2 THEN exp3 ) )

     { SX } WHERE NOT EXISTS PX ( NOT FORALL PY
                ( IF exp1 AND exp2 THEN exp3 ) )

     { SX } WHERE NOT EXISTS PX ( NOT ( NOT EXISTS PY ( NOT
                ( IF exp1 AND exp2 THEN exp3 ) ) ) )

     { SX } WHERE NOT EXISTS PX ( EXISTS PY ( NOT
                ( IF exp1 AND exp2 THEN exp3 ) ) )

     { SX } WHERE NOT EXISTS PX ( EXISTS PY ( NOT
                ( NOT ( exp1 AND exp2 ) OR exp3 ) ) )

     { SX } WHERE NOT EXISTS PX ( EXISTS PY ( NOT
                ( NOT ( exp1 ) OR NOT ( exp2 ) OR exp3 ) ) )

     { SX } WHERE NOT EXISTS PX ( EXISTS PY (
                ( exp1 AND exp2 AND NOT ( exp3 ) ) ) )

SQL equivalent:

     SELECT *
     FROM   S AS SX
     WHERE  NOT EXISTS
          ( SELECT *
            FROM   P AS PX
            WHERE  EXISTS
                 ( SELECT *
                   FROM   P AS PY
                   WHERE  EXISTS
                        ( SELECT *
                          FROM   SP AS SPX
                          WHERE  SPX.SNO = SX.SNO
                          AND    SPX.PNO = PX.PNO )
                   AND    EXISTS
                        ( SELECT *
                          FROM   SP AS SPY
                          WHERE  SPY.SNO = SX.SNO
                          AND    SPY.PNO = PY.PNO )
                   AND    PX.CITY <> PY.CITY ) )

By the way, I used two distinct range variables SPX and SPY, both ranging over SP, in this example purely for reasons of clarity; I could perfectly well have used the same one (say SPX) twice over—it would have made no logical difference at all. Anyway, here’s the result:

SNO

SNAME

STATUS

CITY

S3

Blake

30

Paris

S5

Adams

30

Athens

At this point, I’d like to remind you of another transformation law that’s sometimes useful: the contrapositive law (I mentioned this one in the previous chapter). Consider the implication IF NOT q THEN NOT p. By definition, this expression is equivalent to NOT (NOT q) OR NOT p—which is the same as q OR NOT p—which is the same as NOT p OR q—which is the same as IF p THEN q. So we have:

     IF p THEN q ≡ IF NOT q THEN NOT p

Note that this law does make intuitive sense: If the truth of p implies the truth of q, then the falsity of q must imply the falsity of p. For example, if “It’s raining” implies “The streets are wet,” then “The streets aren’t wet” must imply “It isn’t raining.”

In the example at hand, then, another possible way of stating the interpretation previously assumed (“Get suppliers SX such that for all parts PX and PY, if SX supplies both of them, then PX.CITY = PY.CITY”) is:

Get suppliers SX such that for all parts PX and PY, if PX.CITY ≠ PY.CITY, then SX doesn’t supply both of them.[159]

This perception of the query will very likely lead to a different (though logically equivalent) SQL formulation. I’ll leave the details as an exercise.



[159] Is it obvious that this version is equivalent to the previous one?

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

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