Re: Thinking about MINUS

From: J M Davitt <jdavitt_at_aeneas.net>
Date: Sun, 07 Jan 2007 19:23:37 GMT
Message-ID: <ZMboh.21700$Ye5.8137@tornado.ohiordc.rr.com>

Bob Badour wrote:
> J M Davitt wrote:
>

>> 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) }
> B = { y in U | Q(y) }
>
> 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) }
> NOT B = U MINUS B = { x in U | 1 & ~Q(x) } = { x in U | ~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
> understanding of those words), the expression simplifies to the "set of
> all grapes."

I guess it's the "set of all things" bit that gives me pause. Booleans operate on and return values from a well-defined domain. I suspect it's the tacit presumption that "you know what I mean" that I find uncomfortable. On the other hand, if the domains on which these operations are defined are unambiguous - implicit or not - then I don't have any reason to be uncomfortable.

>> 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."

>
>
> I don't see why it would need any extension at all. You have simply
> omitted a concrete specification for U. However, I don't see how that
> even constrains us much. Given our previous discussion, product, order
> and customer are all subsets of some universe and the universe is some
> superset of product, order and 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.

You're right; I didn't mean to lead the thread into new territory.

My point is that we don't have to devise operations on sets that have the same operators as booleans just because they're analogous operations.

I may have read too much into this discussion. After all, there are already alternate systems - both boolean and relational - that have settled upon different sets of fundamental operations and don't contradict each other. Which left me wondering, "Why would one try to invent MINUS again?"

>>>>> 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 - 13:23:37 CST