Re: Thinking about MINUS

From: Bob Badour <bbadour_at_pei.sympatico.ca>
Date: Sun, 07 Jan 2007 21:46:24 GMT
Message-ID: <QSdoh.41900$cz.614470@ursa-nb00s0.nbnet.nb.ca>

J M Davitt wrote:

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

Both P(x) and Q(x) return values from that well-defined boolean domain, {0,1} (or {0,~0} if you prefer.) The domain of x is U, which seems defined well-enough for the current discussion.

   I suspect it's
> the tacit presumption that "you know what I mean" that I find > uncomfortable.

I said what I meant. You can examine what I said for yourself. Certainly, I presume your ability to correctly parse and interpret the syntax I used, and I presume our agreement on the semantics expressed by that syntax.

   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.

How is U ambiguous? How is the boolean domain {0,1} ambiguous?

P: U -> {0,1}
Q: U -> {0,1}

Each maps U onto the boolean domain.

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

I don't object to leading the thread into new territory--even so formidable a territory as the one in question.

> 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 don't know that we are devising anything that hasn't already been devised.

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

We are not inventing it again. We are merely playing with it. Isn't that what math is all about?

>>>>>> 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
Give the P and Q predicates far above and the expressions immediately above:

NAND(A,B) = { x in U | 1 & ~(P(x) & ~(P(x) & ~Q(x))) } // substitution

• { x in U | ~(P(x) & (~P(x) | Q(x))) } // demorgan
• { x in U | ~((P(x) & ~P(x)) | (P(x) & Q(x))) } // distrib.
• { x in U | ~(0 | (P(x) & Q(x))) } // mutual exclusion
• { x in U | ~(P(x) & Q(x)) } // identity element on |

NOR(A,B) = { x in U | (1 & ~P(x)) & ~Q(x) }  // substitution
          = { x in U | ~P(x) & ~Q(x) }        // identity element on &
          = { x in U | ~(~~P(x) | ~~Q(x)) }   // demorgan
          = { x in U | ~(P(x) | Q(x)) }       // double complement

Received on Sun Jan 07 2007 - 15:46:24 CST