Re: A Logical Model for Lists as Relations

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

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
)

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.
Received on Wed May 10 2006 - 20:17:19 CEST