Thread: LinkedList
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
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.
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@postgresql.org [mailto:pgsql-sql-owner@postgresql.org]On Behalf Of Scott Marlowe Sent: Wednesday, April 26, 2006 8:59 AM To: Ray Madigan Cc: pgsql-sql@postgresql.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 | 03 | 15 | 37 | 52 | 04 | 26 | 48 | 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@postgresql.org > [mailto:pgsql-sql-owner@postgresql.org]On Behalf Of Scott Marlowe > Sent: Wednesday, April 26, 2006 8:59 AM > To: Ray Madigan > Cc: pgsql-sql@postgresql.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@pervasive.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@pervasive.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@postgresql.org > > [mailto:pgsql-sql-owner@postgresql.org]On Behalf Of Scott Marlowe > > Sent: Wednesday, April 26, 2006 8:59 AM > > To: Ray Madigan > > Cc: pgsql-sql@postgresql.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@pervasive.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 +
1where 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