Subject: Re: class difference

From: [email-masked] (Alfredo Sanchez)
Date: Mon, 6 Apr 92 11:18:02 -0700

>> how do i find the instances in A but not in B?

	>can you elaborate a little.  Right now I would say that
	>you are asking how to retrieve from class A instead of
	>from class B and that can't be what you are really asking.

	>Jeff Meredith

Actually, I needed something like the SQL minus operation.
I finally implemented it by creating a temporary class, and then
deleting the unwanted instances.

E.g. given

Class A
x  y
1  10
2  20
3  30

Class B
x  y
1  10
3  30

I wanted A - B = ({2,20}), so i did

retrieve into t unique (A.x, A.y) where A.x != B.x
delete t where t.x = B.x
(leaving the tuples i wanted in t)

Is there a better way to do it?

Thanks,

J Alfredo Sanchez H
-------------------
Hypermedia Research Lab
Department of Computer Science
Texas A&M University

---

From: postarch (Postgres Mailing Archive)
Date: Mon, 06 Apr 92 14:51:33 PDT

> (leaving the tuples i wanted in t)
While this works for your example, it is not correct in general.
Your first retrieve command will retrieve all unique tuples in A
such that there exists a tuple in B with a different x value.  This
will be most of the tuples in A (in your example, it's *all* of the tuples
in A).  So your first line doesn't do much more than make a copy of A.
This is not incorrect, but the qualification "where A.x != B.x" isn't helping
out very much.

Then your second delete command deletes *too many* tuples in general,
i.e. it deletes all the tuples in t for which there is a tuple in B with
*a matching x value.*  If (1,10) was not in B, but (1,20) was, you would still
get the final answer {(2,20)}, rather than the correct answer 
{(1,10), (2,20)}.

One reasonable correct scheme (see note on duplicates below for caveat)
would be to make a copy of A (i.e. "retrieve into tmp unique (A.all)")
and then remove from tmp all those tuples for which there is a tuple
in B that matches on *ALL* attributes.  For your example,
"delete tmp where tmp.x = B.x and tmp.y = B.y"
is the correct syntax.

> Is there a better way to do it?
One optimization is only to put the key columns of A into the where clause
of the delete command (if you know what the key columns are).
For instance, if you knew that y was a key of A, then you'd
get the correct result by saying
"delete tmp where tmp.y = B.y"

Otherwise, to express this in one command without a set difference
operator you need subqueries.
(e.g. in many versions of SQL you could say
SELECT DISTINCT A.* FROM A
WHERE NOT EXISTS (SELECT B.x1 FROM B
                   WHERE B.x1 = A.x1
                     AND B.x2 = A.x2
                     ...
                     AND B.xn = A.xn);
)

Postquel does not support subqueries, and there is no conversion of
the NOT EXISTS construct to join.  This is unfortunate, since your
hand-constructed "t" table is likely to be less efficient than an
internal scheme for processing the query.  That's a historical
decision that was made by the designers of Quel.  Note that
efficiently handling "correlated subqueries" like the SQL statment
above requires a lot of extra complexity, both in the language design and
the database code.

Note also that the semantics for the number of duplicates in the
output of set-difference are kind of tricky.  I believe SQL2 has two 
commands, "EXCEPT ALL" and "EXCEPT DISTINCT" (which is the default if you
just say "EXCEPT".)  The former does multi-set difference (i.e. the number 
of copies of a value in the output is equal to the max of 0 and the 
difference between the number of copies in the left and right inputs), 
while the latter removes duplicates from each input and then does set 
difference directly.  This can be rather confusing if you're not careful.  
The scheme we've discussed above does the latter semantics, which may or 
may not be what you want.  Doing the former semantics in Postquel sounds 
pretty yucky.

Joe Hellerstein