Re: A simple notation, again

From: Brian Selzer <brian_at_selzer-software.com>
Date: Tue, 17 Jul 2007 05:36:27 GMT
Message-ID: <vzYmi.38447$YL5.34235@newssvr29.news.prodigy.net>

"paul c" <toledobythesea_at_oohay.ac> wrote in message news:4kWmi.125098$1i1.56624_at_pd7urf3no...

> Bob Badour wrote:

>> David Cressey wrote:
>>
>>> "Bob Badour" <bbadour_at_pei.sympatico.ca> wrote in message
>>> news:469bac76$0$8868$9a566e8b_at_news.aliant.net...
>>>
>>>> David Cressey wrote:
>>>>
>>>>
>>>>> Using the notation [A B C] for <NOT> (A <AND> B <AND> C), etc.
>>>>>
>>>>> The following [ A [B]] means "A implies B" for Boolean algebra.
>>>
>>>
>>> What is
>>>
>>>>> the corresponding thing for Relational Algebra?
>>>>>
>>>>> Also, I'm trying to come up with a bracket notation for a "literal
>>>>> relation", like literals for simple datatypes like numbers and
>>>
>>>
>>> character
>>>
>>>>> strings.
>>>>>
>>>>> I'm toying with this:
>>>>>
>>>>> [["David" "Cressey" 1]
>>>>> ["Marshall" "Spight" 2]
>>>>> ["Bob" "Badour" 3]
>>>>> ["Jan" Hidders" 4]]
>>>>>
>>>>>
>>>>>
>>>>> This would represent a relation of order 3 and cardinality 4.
>>>>>
>>>>>
>>>>> What I don't like about this is that the binding between attribute
>>>
>>>
>>> values
>>>
>>>>> and attribute names is
>>>>> by position rather than by name, and in fact the attribute names
>>>>> don't
>>>
>>>
>>> even
>>>
>>>>> appear here. That's unacceptably bad. The symmetry is appealing,
>>>>> but
>>>
>>>
>>> it
>>>
>>>>> clearly needs improvement.
>>>>
>>>>
>>>> You omitted names entirely. You would have to extend the syntax to
>>>> something like:
>>>> [[name="David" surname="Cressey" n=1]
>>>> [n=2 name="Marshall" surname="Spight"]
>>>> [surname="Badour" name="Bob" n=3]
>>>> [name="Jan" surname="Hidders" n=4]]
>>>
>>>
>>>
>>> Yeah, that'll do it, all right. To be consistent with the former
>>> notation,
>>> each attribute=value pair needs to be construed as a relation of order 1
>>> and
>>> cardinality 1.
>>>
>>> The extended <AND> of a single name, a single surname, and a single n,
>>> will
>>> be the cartesian extended product, which will be a relation of order 3
>>> and
>>> cardinality 1.
>>> Outside the inner bracket, what we have is the <NOT> of this, which
>>> I'll
>>> call the <NOT> of a <TUPLE>. Where <TUPLE> means a relation of
>>> cardinality
>>> one.
>>>
>>> We have four of these <NOT> of a <TUPLE>, connected by an extended <AND>
>>> .
>>> This time the extended <AND> resolves to the intersection of the
>>> operands,
>>> bercause all the operands have the same attributes.
>>>
>>> So inside the outer brackets we have the intersection of a collection of
>>> <NOT>s of <TUPLE>s.
>>> This is equivalent to the <NOT> of the union of the <TUPLE>s. Outside
>>> of
>>> the outer brackets, we have the <NOT> of the <NOT> of the union of the
>>> <TUPLE>s, This is the union of the <TUPLE>s, which is the desired
>>> relation.
>>>
>>> Does this make any sense at all, from a mathematical perspective? I am
>>> definitely in over my head, here.
>>
>>
>> Yeah, I followed it when you posted it. I will leave it for Jan or Vadim
>> to answer whether A UNION B = NOT( (NOT A) JOIN (NOT B))
>> ...

>
> I think I follow it too, at least as far as the D&D TTM-A algebra is 
> concerned and it gibes with any example I've ever tried to work through as 
> long as I followed the closed-world-assumption that D&D follow.
>
> ie. de Morgan's law applied with TTM-A means A <OR> B being true implies
> <NOT> ((<NOT> A) <AND> (<NOT> B)) being true and vice versa.  But why ask 
> the question using "UNION", "NOT" and "JOIN" unless they are defined 
> differently than D&D define them?
>
> Also, this gives me an excuse to mention one of my pet penchants again. 
> <NOT> (A <OR> B) is the complement of a union in D&D terms and when A <OR> 
> B is true, it implies that (<NOT> A) <AND> (<NOT> B) is false.  I find it 
> interesting to think about a relation's complement when thinking about 
> insert to "union".  When A and B have the same heading and we insert a 
> single tuple to a view that is A <OR> B, some people say inserting to one 
> or the other of A or B is just as logical as inserting to both A and B, so 
> we can't really decide what to do.  But it seems reasonable to me that the 
> complement of the view must also respect the complements of A and B, so 
> neither of those complements should contain the inserted tuple, which 
> means that both A and B would contain it after the insert.
>

I don't think this is quite right.

Suppose t is a tuple whose presence in A or in B would not violate any constraints. Then t must necessarily be an element of either A or its complement, and t must necessarily be an element of either B or its compliment. Now, if t does not appear in A union B, then t must necessarily be an element of both the complement of A and the complement of B. As a result, an insert of t into the view, A union B, does not map to any one of these operations: (1) an insert of t into A, (2) an insert of t into B, or (3) an insert of t into both A and B.

As an aside: if one adheres to the Principle of Orthogonal Design, then the individual represented by the tuple t can never* exemplify both A and B--that is, t would violate the predicate of A or of B, so an insert of t into the view, A union B, would necessarily be deterministic. (There is one exception, but it is trivial: when the keys of both A and B are composed of their entire headings and when an inclusion dependency is defined between A and B, then it is possible for t to exemplify both A and B, but it should be obvious that the view, A union B, would necessarily be composed of just those tuples that exist in whichever is the referenced relation, so it would be pointless to create such a view in the first place.)

> p Received on Tue Jul 17 2007 - 00:36:27 CDT