On 2/17/06, SanjayK <[EMAIL PROTECTED]> wrote: > > > Dennis, > > I understand what you are saying. My problem is specific to only the > sorting. Given the tree: > > P1 > C1 > GC1 > C2 > GC2 > GC3 > C3 > P2 > C4 > C5 > GC4 > C6 > P3 > > This structure is perfect for my use. In fact, this is the way I want it. > The children at any level should immediately follow their parent in the > table. > > Now suppose, each of these items had a field "Size" and I want to sort > this > table such that the structure remains same but the siblings are sorted by > size. For example, the result of a sort might be: > > P1 > C2 > GC3 > GC2 > C3 > C1 > GC1 > ... > > Here, the position of the siblings changed according to sort but the > structure didn't break. I want to know the SQL for achieving this sort > using > the path and the size. For example, if I were to use the path as you > described and do an ORDER BY path, size, it will do this but the structure > of the table will break. Because the paths of the siblings would be same > and > hence they will become clubbed together and won't be separated by their > children as in the actual structure. > > If it is still unclear, I will make and post a real sample. > > > Sanjay,
You can get close to the depth first order of the first list by ordering by the full path to the nodes. select * from tree order by path || id || '/'; This is correct for this sample insert into tree (id, parent_id, data) values (NULL, NULL, 'P1'); insert into tree (id, parent_id, data) values (NULL, NULL, 'P2'); insert into tree (id, parent_id, data) values (NULL, NULL, 'P3'); insert into tree (id, parent_id, data) values (NULL, 1, 'C1'); insert into tree (id, parent_id, data) values (NULL, 1, 'C2'); insert into tree (id, parent_id, data) values (NULL, 1, 'C3'); insert into tree (id, parent_id, data) values (NULL, 2, 'C4'); insert into tree (id, parent_id, data) values (NULL, 2, 'C5'); insert into tree (id, parent_id, data) values (NULL, 2, 'C6'); insert into tree (id, parent_id, data) values (NULL, 4, 'GC1'); insert into tree (id, parent_id, data) values (NULL, 5, 'GC2'); insert into tree (id, parent_id, data) values (NULL, 5, 'GC3'); insert into tree (id, parent_id, data) values (NULL, 8, 'GC1'); Which displays as sqlite> select * from tree order by (path || id || '/'); 1 P1 / 4 1 C1 /1/ 10 4 GC1 /1/4/ 5 1 C2 /1/ 11 5 GC2 /1/5/ 12 5 GC3 /1/5/ 6 1 C3 /1/ 2 P2 / 7 2 C4 /2/ 8 2 C5 /2/ 13 8 GC1 /2/8/ 9 2 C6 /2/ 3 P3 / However, it will not always be correct because it uses a lexigraphic ordering which isn't quite right. If we change the query slightly to display the full path it is sorting on, we see. sqlite> select *, path || id || '/' as full from tree order by full; 1 P1 / /1/ 4 1 C1 /1/ /1/4/ 10 4 GC1 /1/4/ /1/4/10/ 5 1 C2 /1/ /1/5/ 11 5 GC2 /1/5/ /1/5/11/ 12 5 GC3 /1/5/ /1/5/12/ 6 1 C3 /1/ /1/6/ 2 P2 / /2/ 7 2 C4 /2/ /2/7/ 8 2 C5 /2/ /2/8/ 13 8 GC1 /2/8/ /2/8/13/ 9 2 C6 /2/ /2/9/ 3 P3 / /3/ Now if we arbitrarily change the id of C3 from 6 to 14 we will break the lexigraphic ordering. sqlite> update tree set id = 14 where id = 6; sqlite> select *, path || id || '/' as full from tree order by full; 1 P1 / /1/ 14 1 C3 /1/ /1/14/ 4 1 C1 /1/ /1/4/ 10 4 GC1 /1/4/ /1/4/10/ 5 1 C2 /1/ /1/5/ 11 5 GC2 /1/5/ /1/5/11/ 12 5 GC3 /1/5/ /1/5/12/ 2 P2 / /2/ 7 2 C4 /2/ /2/7/ 8 2 C5 /2/ /2/8/ 13 8 GC1 /2/8/ /2/8/13/ 9 2 C6 /2/ /2/9/ 3 P3 / /3/ This is because the string /1/1 (the first part of /1/14) sorts before the string /1/4. To solve this we need to create a custom collation function for the path that understands that the path ids can't be broken up. This should be possible using the sqlite3_create_collation API to create a tree_path collation, and then ordering using that collation. select * from tree order by path || id || '/' collate tree_path; I am going to write such a collation function to go along with the materialized path tree tables. As for sorting by size, that will take some more thought. The full path above is a complete ordering so it won' t do any good to also order by size. I think it will be necessary to create a size_path field that is much like the id path used for the tree. It would track the hierarchy of sizes. I think this can be done in an auxiliary table joined to the tree. I will let you know. I won' t get a chance to look at this for a few days as I will be away from home (i.e. no PC). HTH Dennis Cote
