Francisco Olarte <folarte@xxxxxxxxxxxxxx> 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
