Re: Thinking about MINUS
Date: Sun, 07 Jan 2007 16:46:49 GMT
Message-ID: <Zt9oh.41743$cz.613288_at_ursa-nb00s0.nbnet.nb.ca>
Walt wrote:
> "paul c" <toledobythesea_at_oohay.ac> wrote in message
> news:ooZnh.560288$5R2.4691_at_pd7urf3no...
>
>>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.
>>>>>
>>>>>NOT operator. NOT(A) = U MINUS A.
>>>>>
>>>>>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
>>
>>Thanks and Oops, right you are (I think now). I should have say NOR
>>instead of NAND.
>>
>>p
> > Either NOR or NAND are enough to bootstrap to the rest of it, provided you > make one little extension to them: > > NOR or NAND with only one operand is NOT.
That's not really an extension. That's just the natural outcome of the functions themselves:
NOT A = A NAND A
NOT B = B NOR B
This derives from the identity:
A AND A = A
B OR B = B
> I don't know where it leads regarding database, either. Just a random > thought.
What I find interesting is we can express all of the base logical operations in the relational compromise for NOT.
Of course, so far, we are only looking at relations of the same type, and MINUS doesn't get us PROJECT or JOIN etc. I wonder whether one can define some reasonable extension to MINUS for relations of different types that gives us PROJECT and/or JOIN etc. Received on Sun Jan 07 2007 - 17:46:49 CET