Re: A Logical Model for Lists as Relations
Date: Thu, 11 May 2006 21:08:06 +0200
Message-ID: <44638b8e$0$31656$e4fe514c_at_news.xs4all.nl>
Vadim Tropashko 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. >> >>But a list can be described as a relation.
In several ways, even. So - do we have to choose? If yes - is this choice consequential?
>>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.
Let's have a name for this way of describing a list as a relation.
Is "numbered items" ok?
>>Generalizing, we could
>>describe an n-ary list as a relation with an index attribute and
>>zero or more other attributes.
>
>
> This is one possibility. Formally, a list is a relation with extra
> integer attribute
>
> table EmpList (
> seq# integer,
> ... -- list element content
> )
>
> List concatenation, for example, can be expressed relationally as
>
> select * from EmpList1
> union
> select seq#+(select max(seq#) from EmpList1), ...
> from EmpList2
>
> The other possibility is to represent list with refereences like this:
>
> table EmpList (
> nodeId integer,
> nextNodeId integer,
> ... -- list element content
> )
Would "successive items" be a good one for this way? (I am asking because english is not my native language - I might overlook something completely obvious to native speakers.)
> List concatenation again can be expressed as amended relational union.
>
> It is clear what the mapping between these two relational implementaion
> is: given a list in one representation, we can convert it to the other
> representation. The list concatenation operation is consistent with
> this relational implementation mapping. We can concatenate lists in one
> representation and the other one, and the results would be the mappings
> of each other.
>
>>From this perspective list indeed looks like a worthful abstraction.
So, we have several ways to describing a list as a relation, at least "numbered items" and "successive items".
Do we have to choose? If yes - is this choice consequential? If it is, we have to consider what the consequences are each time we want to describe a list as a relation.
If it is'nt, it means we can think in lists and have (or for now assume) some translator/optimizer to figure out what the best relation description for this particular list in this particular operational context is.
No surprise I'ld prefer it if the latter would be possible. However, this would violate the flipside of the information principle.
- a short explanation. Information principle: The entire information content of a relational database is represented in one and only one way: namely, as attribute values within tuples within relations.
The flipside:
All attribute values within tuples within relations
in a relational database carry information content.
To me it isn't clear what discrete piece of information content is carried by an individual "number" or "successor" attribute.
OTOH:
1. All values of "number" or "successor" together do carry some content. 2. Nobody famous (AFAIK) stated that the flipside should hold. 3. It has allready been (severely) violated by you, Joe Celko and MikitoHarakiri when dealing hierarchies.
... so I guess it is allright :-) Received on Thu May 11 2006 - 21:08:06 CEST