Re: How to represent a bi-directional list in db? - Mailing list pgsql-general

Francisco Olarte <folarte@peoplecall.com> writes:

>> Could you please elaborate? Suppose I have this table,
>> CREATE TABLE stages (
>>     id SERIAL PRIMARY KEY,
>>     name VARCHAR(80) NOT NULL,
>>     next_id INTEGER REFERENCE stages NULL,
>> );
>> What would be the backward query in that case? Forward is clear. This is
>> forward query,
>> SELECT name FROM stages WHERE next_id = 123;
>
> No. That is a BACKWARDS QUERY. You are in row 123, you go BACK to its
> preceedeing one.
> If you need a traversable list containing (ListID, id,name) = x,1,A;
> x,2,b; x,3;c ( I've added the ListId column to make it more
> interesting/reallistic, you normally do not have a single table)
> In sql you can build a (ListId, id, prev_id, name ) table ( PREV is
> easier, as when you insert a row, in a normal application, you know
> the previous one, but not the next one ) with the data
> (x,1,null,a),(x,2,1,b),(x,3,2,c) ( the last one is a synthetic
> sentinel and assumes nullable id), you can do it in a lot of ways.
>
> To traverse it forward you just querying "select id where listid=x and
> next_id is null" to locate the head (1), and then just go forward by
> selecting with prev_id = last got id until you hit zero results.
>
> To traverse backwards there are several ways. In the real cases I've
> used I always had a "list row" where I could store the node for the
> 1st stage. In that cases i linked them circularly, (id=1, prev=3), so
> bidirectional traversing was easy. Or you can use a special sentinel
> node ( with a marker, like name=null). The thing is you locate the
> last row, and then just query with id=last got prev_id. I do not
> remember the details, but probably your "stages" are stages of
> something which has a row, which can readily have a "first_stage_id"
> or something similar.
>
> Lists in tables are not the same as in C, where you directly store
> pointers which point outwards. In this case any unique data serves as
> a pointer, slow ( table scan ) by default, faster if you index the
> column.
>
> Anyway, unless you need the "linked list" functionality for something
> ( really heavy manipulation of large stage lists, splicing things
> around ), I've normally found it's easier, in sql, to model this kind
> of thing with a master-detail + order column.
> ( whatever = (id, ...., first_stage_id), stages=(id, order, .... ) )
>
Thanks a lot Francisco. This is great help.

My stages are stages of processes. So yes processes are also stored in a
table. I got the idea. I'll add another column in the processes table
which points to the first stage (first_stage_id). And quries

Forward pass:
1. select name from stages where id = <first_stage_id from
process table>
2. select name from stages where prev_id = <last fetched id>
3. repeat (2)

Backward pass:
1. select name from stages where prev_id = <first_stage_id from
process table>
2. select name from stages where id = <last fetched prev_id>
3. repeat (2)

This is assuming I also create a circular list. I can also store
last_stage_id in the process table if we don't want to create circular
list in db.

Regards.
-- 
Pankaj Jangid