Re: Thinking about MINUS
Date: Sun, 07 Jan 2007 17:09:23 GMT
Message-ID: <7P9oh.41760$cz.613377_at_ursa-nb00s0.nbnet.nb.ca>
> Bob Badour wrote: >
>> paul c wrote:
>>
>>> Walt wrote:
>>>
>>>> The discussion over in "Curious SQL question" started me thinking
>>>> (after I
>>>> got over my embarassment at posting a wrong solution).
>>>>
>>>> Suppose you started with these two primitive concepts:
>>>>
>>>> A universal set, called U (whatever that is)
>>>>
>>>> and
>>>>
>>>> MINUS(A,B), a function that removes from set A any elements common
>>>> to A and
>>>> B.
>>>>
>>>> Can you derive the rest of it? Here's my first attempt:
>>>>
>>>> Infix notation: A MINUS B = MINUS (A,B). Just a notational
>>>> convenience
>>>> for me. This should be trivial. I apologize to any readers who find
>>>> this
>>>> inconvenient.
>>>>
>>>> Empty Set: PHI = U MINUS U. Note that PHI is somehow "bound" to U.
>>>> Whether the PHIs of different universes are or are not the same PHI is
>>>> something I'll let the rest of you discuss.
> > All this "boolean operations on sets" has me scratching my head. There > is, underneath it all, the presumption that one really means "is an > element of," right? I mean, what could the meaning of "NOT (strawberry > OR apple) AND grape" be?
Containment is inherent in sets. Given the definitions for U, A and B, A
and B are both subsets of U which means U contains both A and B.
If you wanted to, you could define predicates P and Q such that:
A = { x in U | P(x) }
The predicates P and Q would be eqivalent to "is an element of A" and
"is an element of B" respectively.
We could express the functions in terms of those predicates:
A MINUS B = { x in U | P(x) & ~Q(x) }
etc.
As Lennart already pointed out, the meaning of your expression above is:
The set of all things that are neither strawberries nor apples but are
grapes. Since no grape is a strawberry or an apple (at least in common
B = { y in U | Q(y) }
NOT B = U MINUS B = { x in U | 1 & ~Q(x) } = { x in U | ~Q(x) }
> Here's a good example >
>>>> NOT operator. NOT(A) = U MINUS A.
> > of something that requires significant presumptions that I don't think, > if I may invent a design on the fly, can be extended to expressions like > "NOT product" or "NOT order INTERSECT customer" or "product INTERSECT > NOT order INTERSECT customer."
> Sure, we can think of JOIN as an analog to AND and UNION as an analog to > OR, but they are very different operations.
Right now, we are at the level of using INTERSECT as an analog to AND. Join is an extension of INTERSECT, and I am not yet clear how our discussion extends to JOIN yet.
>>>> Left association. (A MINUS B) MINUS C = (A MINUS C) MINUS B (proof
>>>> omitted)
>>>>
>>>> INTERSECTION. A INTERSECT B = A MINUS (A MINUS B)
>>>> = B
>>>> MINUS
>>>> (B MINUS A)
>>>>
>>>> UNION. A UNION B = NOT (NOT (A) INTERSECT NOT (B))
>>>>
>>>> From here, it looks like we can bootstrap our way up to the rest of
>>>> set
>>>> theory and Boolean algebra.
>>>> Or am I seeing something wrong (again)?
>>>
>>> I guess NAND would then be U MINUS A MINUS B, and since NAND is said
>>> to be enough to "bootstrap" (I seem to remember), then I'd say you
>>> are right but where it leads as far as database is concerned, I don't
>>> know.
>>
>> NAND = U MINUS ( A MINUS ( A MINUS B ) )
>> = U MINUS ( B MINUS ( B MINUS A ) )
>>
>> NOR = ( U MINUS A ) MINUS B
Received on Sun Jan 07 2007 - 18:09:23 CET