Re: A Logical Model for Lists as Relations

From: Bob Badour <bbadour_at_pei.sympatico.ca>
Date: Fri, 12 May 2006 19:05:45 GMT
Message-ID: <d059g.6861$A26.173500@ursa-nb00s0.nbnet.nb.ca>

JOG wrote:

> Marshall Spight wrote:
>

>>JOG wrote:
>>
>>>Marshall  Spight wrote:
>>>
>>>>But a list can be described as a relation. Most simply, an infinite
>>>>list is a relation from the natural numbers to the target set,
>>>>and a finite list is a relation from some finite contiguous subset
>>>>[0..n] of the naturals to the target set. Generalizing, we could
>>>>describe an n-ary list as a relation with an index attribute and
>>>>zero or more other attributes.
>>>
>>>Do you not find this unsatisfying though?
>>
>>Actually, I find it quite satisfying, since it means I can, for
>>example,
>>use the full power of the relational algebra for selection on lists.
>>
>>
>>>By doing this one is altering
>>>information that is ordinal in nature to being cardinal.
>>
>>I don't understand this statement. Can you expand?

>
>
> "The order of the primeministers were Blair, major, thatcher" =
> "Blair was prime minister after Major."
> "Major was prime minister after Thatcher."
>
> Hence A satisfying relation (to me ;) representing this list is:
> { (Blair, Major), (Major, Thatcher) }
>
> This ordinal representation does not need to include cardinal indeces,
> and to my eyes that's a good thing as where did they exist in the
> original propositions?

You will run into problems when you get to things like:

{ (MacDonald, Laurier), (Laurier, MacDonald), (MacDonald, Laurier) }

Unless of course you want to record only the order in which Prime Ministers were first elected.

>>>Given one is
>>>modelling assertions, these indexes come from the aether - they seem
>>>rather implementational in nature, a physical workaround to the issue
>>>of ordering.
>>
>>I don't see it that way. I don't see anything implementational to these
>>equalities:
>>
>>   "abc" = ['a', 'b', 'c'] = { (0,'a'), (1, 'b'), (2, 'c') }

>
> well, yes that is array indexing, but that seems to me very much like
> an implementation approach. Perhaps our views of lists are conceptually
> different - I see ['a', 'b', 'c'] as { (a,b) , (b,c) }, a transitive
> representation as per a hasse diagram.

And what of "ababa" ?

>>Rather, they simply provide me a way to work with lists in a
>>set-theoretic way, rather than in the recursive, or worse, the customary iterative
>>way. It also means I don't have to introduce a new container type to handle
>>ordered data, which maintains closure and keeps the number of generic
>>containers small (= 1).

>
> Don't get me wrong, I totally see where you're coming from and I'm not
> objecting to your preference for using relations over list datatypes.
> (Just something about array indexing doesn't sit well with me in terms
> of the information itself, it seems brittle - apologies, at the moment
> I don't think I have cogent arguments to express it better than that).

Your method does not work in the general case. Whether one uses predecessors and successors or whether one uses an ordered index, one still needs to consider the requirement for at least one candidate key. Received on Fri May 12 2006 - 14:05:45 CDT