Re: LinkedList

On Wed, 2006-04-26 at 11:09, Ray Madigan wrote:
> I have a table that I created that implements a linked list. I am not an
> expert SQL developer and was wondering if there are known ways to traverse
> the linked lists. Any information that can point me in the direction to
> figure this out would be appreciated. The table contains many linked lists
> based upon the head of the list and I need to extract all of the nodes that
> make up a list. The lists are simple with a item and a link to the history
> item so it goes kind of like:
>
> 1, 0
> 3, 1
> 7, 3
> 9, 7
> ...
>
> Any suggestions would be helpful, or I will have to implement the table
> differently.

You should be able to do this with a fairly simple self-join...

select a.id, b.aid, a.field1, b.field1
from mytable a
join mytable b
on (a.id=b.aid)

Or something like that.

I have a table that I created that implements a linked list. I am not an
expert SQL developer and was wondering if there are known ways to traverse
the linked lists. Any information that can point me in the direction to
figure this out would be appreciated. The table contains many linked lists
based upon the head of the list and I need to extract all of the nodes that
make up a list. The lists are simple with a item and a link to the history
item so it goes kind of like:

1, 0
3, 1
7, 3
9, 7
...

Any suggestions would be helpful, or I will have to implement the table
differently.

Thanks
Ray Madigan

Scott,

Thanks for your reply, I tried what you said, worked around a few things
but I am still stuck. The main reason is I didn't do an adequate job of
explaining the situation. The table implements many linked lists and I want
to traverse one of them given the end of the list.

Say the table contains

h | v | j
1 0 100
3 1 300
5 3 500
7 5 700

2 0 200
4 2 400
6 4 600
8 6 800

If I specify t.h = 8 I want to traverse the even part of the table
If I specify t.h = 7 I want to traverse the odd part of the table

If you can send me to a book to read I am willing

Thanks

-----Original Message-----
From: pgsql-sql-owner(at)postgresql(dot)org
[mailto:pgsql-sql-owner(at)postgresql(dot)org]On Behalf Of Scott Marlowe
Sent: Wednesday, April 26, 2006 8:59 AM
To: Ray Madigan
Cc: pgsql-sql(at)postgresql(dot)org
Subject: Re: [SQL] LinkedList

On Wed, 2006-04-26 at 11:09, Ray Madigan wrote:
> I have a table that I created that implements a linked list. I am not an
> expert SQL developer and was wondering if there are known ways to traverse
> the linked lists. Any information that can point me in the direction to
> figure this out would be appreciated. The table contains many linked
lists
> based upon the head of the list and I need to extract all of the nodes
that
> make up a list. The lists are simple with a item and a link to the
history
> item so it goes kind of like:
>
> 1, 0
> 3, 1
> 7, 3
> 9, 7
> ...
>
> Any suggestions would be helpful, or I will have to implement the table
> differently.

You should be able to do this with a fairly simple self-join...

select a.id, b.aid, a.field1, b.field1
from mytable a
join mytable b
on (a.id=b.aid)

Or something like that.

---------------------------(end of broadcast)---------------------------
TIP 2: Don't 'kill -9' the postmaster

decibel=# select * from t;
a | b
---+---
1 | 0
3 | 1
5 | 3
7 | 5
2 | 0
4 | 2
6 | 4
8 | 6
(8 rows)

decibel=# select * from t x join t y on(x.a=y.b) where y.a=7;
a | b | a | b
---+---+---+---
5 | 3 | 7 | 5
(1 row)

decibel=# select * from t x join t y on(x.a=y.b) where y.a=8;
a | b | a | b
---+---+---+---
6 | 4 | 8 | 6
(1 row)

decibel=#

As you can see, it selects the right data, but you'll need to step
through it somehow. You might be able to do it with a generate_series(),
or you can use a function. If we get WITH support/recursion in 8.2 you'd
use that.

I think that "SQL For Smarties" by Joe Celko might have an example of
how to do this without using a function. Even if it doesn't it's a book
any serious database developer should own.

On Wed, Apr 26, 2006 at 10:35:15AM -0700, Ray Madigan wrote:
> Scott,
>
> Thanks for your reply, I tried what you said, worked around a few things
> but I am still stuck. The main reason is I didn't do an adequate job of
> explaining the situation. The table implements many linked lists and I want
> to traverse one of them given the end of the list.
>
> Say the table contains
>
> h | v | j
> 1 0 100
> 3 1 300
> 5 3 500
> 7 5 700
>
> 2 0 200
> 4 2 400
> 6 4 600
> 8 6 800
>
> If I specify t.h = 8 I want to traverse the even part of the table
> If I specify t.h = 7 I want to traverse the odd part of the table
>
> If you can send me to a book to read I am willing
>
> Thanks
>
> -----Original Message-----
> From: pgsql-sql-owner(at)postgresql(dot)org
> [mailto:pgsql-sql-owner(at)postgresql(dot)org]On Behalf Of Scott Marlowe
> Sent: Wednesday, April 26, 2006 8:59 AM
> To: Ray Madigan
> Cc: pgsql-sql(at)postgresql(dot)org
> Subject: Re: [SQL] LinkedList
>
>
> On Wed, 2006-04-26 at 11:09, Ray Madigan wrote:
> > I have a table that I created that implements a linked list. I am not an
> > expert SQL developer and was wondering if there are known ways to traverse
> > the linked lists. Any information that can point me in the direction to
> > figure this out would be appreciated. The table contains many linked
> lists
> > based upon the head of the list and I need to extract all of the nodes
> that
> > make up a list. The lists are simple with a item and a link to the
> history
> > item so it goes kind of like:
> >
> > 1, 0
> > 3, 1
> > 7, 3
> > 9, 7
> > ...
> >
> > Any suggestions would be helpful, or I will have to implement the table
> > differently.
>
> You should be able to do this with a fairly simple self-join...
>
> select a.id, b.aid, a.field1, b.field1
> from mytable a
> join mytable b
> on (a.id=b.aid)
>
> Or something like that.
>
> ---------------------------(end of broadcast)---------------------------
> TIP 2: Don't 'kill -9' the postmaster
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 6: explain analyze is your friend
>

--
Jim C. Nasby, Sr. Engineering Consultant jnasby(at)pervasive(dot)com
Pervasive Software http://pervasive.com work: 512-231-6117
vcard: http://jim.nasby.net/pervasive.vcf cell: 512-569-9461

Ray,

There's a good introductory article on Sitepoint for doing this kind of thing:

http://www.sitepoint.com/article/hierarchical-data-database

The "Modified Preorder Tree Traversal" is quite a nice method that I
would expect to be a magnitude faster than recursive joins, although
does have some drawbacks.

Kind Regards,

Neil.

On 4/27/06, Jim C. Nasby <jnasby(at)pervasive(dot)com> wrote:
> decibel=# select * from t;
> a | b
> ---+---
> 1 | 0
> 3 | 1
> 5 | 3
> 7 | 5
> 2 | 0
> 4 | 2
> 6 | 4
> 8 | 6
> (8 rows)
>
> decibel=# select * from t x join t y on(x.a=y.b) where y.a=7;
> a | b | a | b
> ---+---+---+---
> 5 | 3 | 7 | 5
> (1 row)
>
> decibel=# select * from t x join t y on(x.a=y.b) where y.a=8;
> a | b | a | b
> ---+---+---+---
> 6 | 4 | 8 | 6
> (1 row)
>
> decibel=#
>
> As you can see, it selects the right data, but you'll need to step
> through it somehow. You might be able to do it with a generate_series(),
> or you can use a function. If we get WITH support/recursion in 8.2 you'd
> use that.
>
> I think that "SQL For Smarties" by Joe Celko might have an example of
> how to do this without using a function. Even if it doesn't it's a book
> any serious database developer should own.
>
> On Wed, Apr 26, 2006 at 10:35:15AM -0700, Ray Madigan wrote:
> > Scott,
> >
> > Thanks for your reply, I tried what you said, worked around a few things
> > but I am still stuck. The main reason is I didn't do an adequate job of
> > explaining the situation. The table implements many linked lists and I want
> > to traverse one of them given the end of the list.
> >
> > Say the table contains
> >
> > h | v | j
> > 1 0 100
> > 3 1 300
> > 5 3 500
> > 7 5 700
> >
> > 2 0 200
> > 4 2 400
> > 6 4 600
> > 8 6 800
> >
> > If I specify t.h = 8 I want to traverse the even part of the table
> > If I specify t.h = 7 I want to traverse the odd part of the table
> >
> > If you can send me to a book to read I am willing
> >
> > Thanks
> >
> > -----Original Message-----
> > From: pgsql-sql-owner(at)postgresql(dot)org
> > [mailto:pgsql-sql-owner(at)postgresql(dot)org]On Behalf Of Scott Marlowe
> > Sent: Wednesday, April 26, 2006 8:59 AM
> > To: Ray Madigan
> > Cc: pgsql-sql(at)postgresql(dot)org
> > Subject: Re: [SQL] LinkedList
> >
> >
> > On Wed, 2006-04-26 at 11:09, Ray Madigan wrote:
> > > I have a table that I created that implements a linked list. I am not an
> > > expert SQL developer and was wondering if there are known ways to traverse
> > > the linked lists. Any information that can point me in the direction to
> > > figure this out would be appreciated. The table contains many linked
> > lists
> > > based upon the head of the list and I need to extract all of the nodes
> > that
> > > make up a list. The lists are simple with a item and a link to the
> > history
> > > item so it goes kind of like:
> > >
> > > 1, 0
> > > 3, 1
> > > 7, 3
> > > 9, 7
> > > ...
> > >
> > > Any suggestions would be helpful, or I will have to implement the table
> > > differently.
> >
> > You should be able to do this with a fairly simple self-join...
> >
> > select a.id, b.aid, a.field1, b.field1
> > from mytable a
> > join mytable b
> > on (a.id=b.aid)
> >
> > Or something like that.
> >
> > ---------------------------(end of broadcast)---------------------------
> > TIP 2: Don't 'kill -9' the postmaster
> >
> >
> > ---------------------------(end of broadcast)---------------------------
> > TIP 6: explain analyze is your friend
> >
>
> --
> Jim C. Nasby, Sr. Engineering Consultant jnasby(at)pervasive(dot)com
> Pervasive Software http://pervasive.com work: 512-231-6117
> vcard: http://jim.nasby.net/pervasive.vcf cell: 512-569-9461
>
> ---------------------------(end of broadcast)---------------------------
> TIP 2: Don't 'kill -9' the postmaster
>

> I have a table that I created that implements a linked list. I am not an
> expert SQL developer and was wondering if there are known ways to traverse
> the linked lists. Any information that can point me in the direction to
> figure this out would be appreciated. The table contains many linked lists
> based upon the head of the list and I need to extract all of the nodes that
> make up a list. The lists are simple with a item and a link to the history
> item so it goes kind of like:

It may not be exactly suitable, but this one does only traversal (assuming
the list is not clsoed)

create table linkedlist(prevnode int, nextnode int, val int);
-- HEAD
insert into linkedlist values(null,1,0);
insert into linkedlist values(1,2,10);
insert into linkedlist values(2,3,20);
insert into linkedlist values(3,4,30);
insert into linkedlist values(4,5,40);
-- TAIL
insert into linkedlist values(5,null,50);

-- TRAVERSE
begin;
declare mc cursor for select * from linkedlist order by nextnode;
fetch 1 from mc;
fetch 1 from mc;
...
close mc;
commit;

which is nothing more than,
select * from linkedlist order by nextnode;

Regards,

Ben K.
Developer
http://benix.tamu.edu

On Thu, 2006-27-04 at 22:58 -0500, Ben K. wrote:
> > I have a table that I created that implements a linked list. I am not an
> > expert SQL developer and was wondering if there are known ways to traverse
> > the linked lists. Any information that can point me in the direction to
> > figure this out would be appreciated. The table contains many linked lists
> > based upon the head of the list and I need to extract all of the nodes that
> > make up a list. The lists are simple with a item and a link to the history
> > item so it goes kind of like:
>
> It may not be exactly suitable, but this one does only traversal (assuming
> the list is not clsoed)
>
> create table linkedlist(prevnode int, nextnode int, val int);
> -- HEAD
> insert into linkedlist values(null,1,0);
> insert into linkedlist values(1,2,10);
> insert into linkedlist values(2,3,20);
> insert into linkedlist values(3,4,30);
> insert into linkedlist values(4,5,40);
> -- TAIL
> insert into linkedlist values(5,null,50);
>
> -- TRAVERSE
> begin;
> declare mc cursor for select * from linkedlist order by nextnode;
> fetch 1 from mc;
> fetch 1 from mc;
> ...
> close mc;
> commit;
>
> which is nothing more than,
> select * from linkedlist order by nextnode;
>
>
> Regards,
>
> Ben K.
> Developer
> http://benix.tamu.edu

Bad example of a double linked list, you also need an id for
the current node and the values of prevnode and nextnode do not
need to be ordered or contiguous as the example shows.

create table linkedlist(node int,prevnode int, nextnode int, val int);

insert into linkedlist values(1,null,2,0);
insert into linkedlist values(2,1,3,10);
insert into linkedlist values(3,2,4,30);
insert into linkedlist values(4,3,5,20);
insert into linkedlist values(5,4,6,40);
insert into linkedlist values(6,5,null,50);

If we now wanted to reorder an item in the set you need
make some updates in a block, which I have not done before
but should be something like this:

Move node 4 between 2 and 3 so that the values from head
to tail are ordered.

BEGIN
update linkedlist set prevnode = '2',nextnode = '3' where node = '4';
update linkedlist set nextnode = '4' where node = '2';
update linkedlist set prevnode = '4' where node = '3';
COMMIT

I have never done linked lists in SQL but have done a lot of
work with bidirectional multi-dimensional linked lists in the
past in C and other programming languages. The concept is the
same.

A single linked list would be easier, but can only be traversed
in one direction :

create table linkedlist(node int,nextnode int, val int);

insert into linkedlist values(1,2,0);
insert into linkedlist values(2,3,10);
insert into linkedlist values(3,4,30);
insert into linkedlist values(4,5,20);
insert into linkedlist values(5,6,40);
insert into linkedlist values(6,null,50);

Again to order the val from head to tail:

BEGIN
update linkedlist set nextnode = '3' where node = '4';
update linkedlist set nextnode = '4' where node = '2';
COMMIT

On Fri, 28 Apr 2006, Guy Fraser wrote:

>> -- HEAD
>> insert into linkedlist values(null,1,0);
>> insert into linkedlist values(1,2,10);
>> insert into linkedlist values(2,3,20);
>> insert into linkedlist values(3,4,30);
>> insert into linkedlist values(4,5,40);
>> -- TAIL
>> insert into linkedlist values(5,null,50);

> Bad example of a double linked list, you also need an id for
> the current node and the values of prevnode and nextnode do not
> need to be ordered or contiguous as the example shows.

Wow. Interesting... I am willing to be corrected, but to me the "node"
field seems redundant, since it does not add any information. (Since each
item in the list is already uniquely identifiable without the "node".)
Certainly so, for traversing, which was the OP's intention.

It may save some steps in case of other operations but at the expense of
one more field. Please see below.

> create table linkedlist(node int,prevnode int, nextnode int, val int);
> insert into linkedlist values(1,null,2,0);
> insert into linkedlist values(2,1,3,10);
> insert into linkedlist values(3,2,4,30);
> insert into linkedlist values(4,3,5,20);
> insert into linkedlist values(5,4,6,40);
> insert into linkedlist values(6,5,null,50);

> If we now wanted to reorder an item in the set you need
> make some updates in a block, which I have not done before
> but should be something like this:
>
> Move node 4 between 2 and 3 so that the values from head
> to tail are ordered.
>
> update linkedlist set prevnode = '2',nextnode = '3' where node = '4';
> update linkedlist set nextnode = '4' where node = '2';
> update linkedlist set prevnode = '4' where node = '3';

If the intention is to change it from 0-10-30-20-40-50 to
0-10-20-30-40-50, it would have been (in my design) exchanging node 3 and
node 4 below.

null,1,0
1,2,10 <-- node 2
2,3,30 <-- node 3
3,4,20 <-- node 4
4,5,40
5,null,50

Now, it can be done by:

begin;
update linkedlist set prevnode=2 where prevnode=3; -- node 4 = (2,4,20)
update linkedlist set prevnode=3 where nextnode=3; -- node 3 = (3,3,30)
update linkedlist set nextnode=3 where prevnode=2; -- node 4 = (2,3,20)
update linkedlist set nextnode=4 where nextnode=3; -- node 3 = (3,4,30)
commit;

achieving the same.
...
2,3,20 <-- node 4, originally
3,4,30 <-- node 3, originally
...

"node" will be more cost efficient if we insert an item at the beginning
of a long list, for example insert
(2,3,100)
before node 3 (2,3,20), but at least the sql is simple;

update linkedlist set prevnode = prevnode + 1 where prevnode > 1;
update linkedlist set nextnode = nextnode + 1 where nextnode > 2;
and then do insert (2,3,xxx)

This method can also be used for reordering.

The usefulness of the "node" will depend on the economics of these update
operations over keeping one more field.

But I think this is more of an exercise, and functions would be the proper
way for complex operations.

Regards,

Ben K.
Developer
http://benix.tamu.edu

On Sat, 2006-29-04 at 01:50 -0500, Ben K. wrote:
> On Fri, 28 Apr 2006, Guy Fraser wrote:
>
> >> -- HEAD
> >> insert into linkedlist values(null,1,0);
> >> insert into linkedlist values(1,2,10);
> >> insert into linkedlist values(2,3,20);
> >> insert into linkedlist values(3,4,30);
> >> insert into linkedlist values(4,5,40);
> >> -- TAIL
> >> insert into linkedlist values(5,null,50);
>
>
>
> > Bad example of a double linked list, you also need an id for
> > the current node and the values of prevnode and nextnode do not
> > need to be ordered or contiguous as the example shows.
>
>
>
> Wow. Interesting... I am willing to be corrected, but to me the "node"
> field seems redundant, since it does not add any information. (Since each
> item in the list is already uniquely identifiable without the "node".)
> Certainly so, for traversing, which was the OP's intention.
>
> It may save some steps in case of other operations but at the expense of
> one more field. Please see below.
>

The problem is that your way, there is no indicated way to determine
which node is which. For instance is you update any of your nodes
then the node list would be out of order and your list would not
work.

After I posted the message I realized there is another way to
do this without adding an extra field, and it would be a closer
example to how it is done in C. If you assigned the OID of the
previous and next nodes rather than arbitrary integer, you could
access each node independent of the order they are listed.

I have not messed around much with OIDs. I am not sure if
OIDs change if an entry is updated.

In C you would use a pointer to storage location of previous
and next "node" which is similar to using the OID. In some
cases it can be necessary to use pointers to pointers when
accessing variable length relocatable data, but that goes way
past what this thread is about.

The example I provided, is still feasible and alleviates all
unknowns at the expense of 4 bytes of storage for one integer
used as a fixed address for each node.

>
>
> > create table linkedlist(node int,prevnode int, nextnode int, val int);
> > insert into linkedlist values(1,null,2,0);
> > insert into linkedlist values(2,1,3,10);
> > insert into linkedlist values(3,2,4,30);
> > insert into linkedlist values(4,3,5,20);
> > insert into linkedlist values(5,4,6,40);
> > insert into linkedlist values(6,5,null,50);
>
> > If we now wanted to reorder an item in the set you need
> > make some updates in a block, which I have not done before
> > but should be something like this:
> >
> > Move node 4 between 2 and 3 so that the values from head
> > to tail are ordered.
> >
> > update linkedlist set prevnode = '2',nextnode = '3' where node = '4';
> > update linkedlist set nextnode = '4' where node = '2';
> > update linkedlist set prevnode = '4' where node = '3';
>
>
>
> If the intention is to change it from 0-10-30-20-40-50 to
> 0-10-20-30-40-50, it would have been (in my design) exchanging node 3 and
> node 4 below.
>
> null,1,0
> 1,2,10 <-- node 2
> 2,3,30 <-- node 3
> 3,4,20 <-- node 4
> 4,5,40
> 5,null,50
>
> Now, it can be done by:
>
> begin;
> update linkedlist set prevnode=2 where prevnode=3; -- node 4 = (2,4,20)
> update linkedlist set prevnode=3 where nextnode=3; -- node 3 = (3,3,30)
> update linkedlist set nextnode=3 where prevnode=2; -- node 4 = (2,3,20)
> update linkedlist set nextnode=4 where nextnode=3; -- node 3 = (3,4,30)
> commit;
>
> achieving the same.
> ...
> 2,3,20 <-- node 4, originally
> 3,4,30 <-- node 3, originally
> ...
>
> "node" will be more cost efficient if we insert an item at the beginning
> of a long list, for example insert
> (2,3,100)
> before node 3 (2,3,20), but at least the sql is simple;
>
> update linkedlist set prevnode = prevnode + 1 where prevnode > 1;
> update linkedlist set nextnode = nextnode + 1 where nextnode > 2;
> and then do insert (2,3,xxx)
>
> This method can also be used for reordering.
>
> The usefulness of the "node" will depend on the economics of these update
> operations over keeping one more field.
>
> But I think this is more of an exercise, and functions would be the proper
> way for complex operations.
>

As long as it works in real world use. Without some way of addressing
each node, the idea of a linked list seems wrong, since a linked is
supposed to hold the address of the previous and or next item in the
list, assuming the data is always going to be correctly sorted so that
you can locate the next item by tupple number seems overly assumptive.
If it works for you great, your example may then be useful as a short
cut, but I don't believe in leaving things to chance when programming.

> The problem is that your way, there is no indicated way to determine
> which node is which. For instance is you update any of your nodes
> then the node list would be out of order and your list would not
> work.

I think the thinking is different here. The OP's list is ordered and has
prev-next only, and there can be lists that are read only and/or ordered
(like clickstream or a data stream out of multi-stream packets) and do not
require insert. That's why I mentioned it's for traverse-only in my
original post.

(But I disagree with you about not being able to determine a node - since
in sql it's possible to identify a row as long as it has unique values in
fields, however they are named)

> After I posted the message I realized there is another way to
> do this without adding an extra field, and it would be a closer
> example to how it is done in C. If you assigned the OID of the
> previous and next nodes rather than arbitrary integer, you could
> access each node independent of the order they are listed.
>
> I have not messed around much with OIDs. I am not sure if
> OIDs change if an entry is updated.

I understand oid doesn't change with update. But tables may or may not
have oids. (can be created "without oids") I also came to appreciate the
difference with C.

In sql, there is a way to identify a row like I did, but in C it'd not be
possible without the address (of course it's not like "impossible" but
...), so the linked list as in strict C-like sense would be perfect but
may carry a different value here. (Since we already have the added layer
of sql engines.) I agree your method would be better if we want to scale
when insert or delete is needed.

It'd be interesting to compare how the normal O() applies to sql - would
updating n rows with one sql statement be equivalent to O(n) in C? Maybe a
silly question but it came to my mind...

> In C you would use a pointer to storage location of previous
> and next "node" which is similar to using the OID. In some
> cases it can be necessary to use pointers to pointers when
> accessing variable length relocatable data, but that goes way
> past what this thread is about.
> The example I provided, is still feasible and alleviates all
> unknowns at the expense of 4 bytes of storage for one integer
> used as a fixed address for each node.

> As long as it works in real world use. Without some way of addressing
> each node, the idea of a linked list seems wrong, since a linked is
> supposed to hold the address of the previous and or next item in the
> list, assuming the data is always going to be correctly sorted so that
> you can locate the next item by tupple number seems overly assumptive.
> If it works for you great, your example may then be useful as a short
> cut, but I don't believe in leaving things to chance when programming.

Regards,

Ben K.
Developer
http://benix.tamu.edu