Re: A Logical Model for Lists as Relations

Bob Badour wrote:

> Jay Dee wrote:
> 
>> Marshall Spight wrote:
>>
>>> I am interested in the question of how best to handle lists in a
>>> relation-oriented world. I have considered various approaches,
>>> usually oriented around adding a list collection type.
>>
>>
>> Why not simply use a relation?

vc wrote:
> Jay Dee wrote:
> [..]
>
>>I think not. Relations are sets, lists aren't.
>
> Of course lists are sets plus the 'cons' operation.

I suspect we're stumbling into differing conventional definitions rather than fundamental differences. In my mind, a list may hold duplicates, while a set may not. [More follows.] Too, my reading of MS's post led me to think position in the list was significant.

Maybe that's covered in your theory of lists -- plus the 'cons' operation -- but not in mine.

>>The naturals -
>>which don't include zero, by the way - are a set,
>
> By the way in modern math, naturals do include zero (von Neumann
> numerals, abstract algebra, category theory) although N with or without
> zero distinction in many cases is unimportant.

Bad on me.

I've found domains of the naturals (excluding zero), zero, zero and the naturals, infinity, the naturals and infinity, zero minus all the previous, &c. are useful sets of integers. (No disjointedness is claimed.) And I vaguely recall some arm wrestling about zero...

> Besides, naturals can be regarded as a recursive data structure in a
> very much the same fashion as lists by substituting Nil and Cons for
> Zero and Succ.

See, I probably grok a successor operator, maybe a nil operator, but I'm not tracking cons and am not sure why zero and nil differ.

>>For lists, you need bunch theory, not set theory.
>
> What's 'bunch theory' ?

We speak of "SQL bags" without really defining them; based on what experience has taught us, we think we know what's in a bag. However, there is a formal description of bag-like things I know as bunches.

Bunch theory is one of a progression of consistent theories -- boolean, number, character, bunch, set, string, function, program -- that I thought might provide some useful insight into what MS was after.

It's formal - unlike bags - and has all the benefits that accrue. I'll try to track down a link...

Bob Badour wrote:
>
> Since it is relatively easy to write a query that extends a relation
> with a rank per any explicit order, I am not even sure the ordinal
> attribute is required.

True. I wasn't exactly sure what MS wanted to happen, for example, to the fourth element in a list when the second element is elided. Does it become the third? If so, your proposal is a good solution. But...

What if he envisions a list in which duplication of elements is significant? In that case - and I'm supposing that's what MS had in mind - a relation of element values wouldn't work.

"More requirements, please!"

In the end, though, I'm confident that the lists MS desires can be implemented in a relational design without inventing anything beyond what already exists. Received on Wed May 10 2006 - 23:55:05 CEST