Sorting a hierarchical table (SQL)

[Frank Millman]

Hi all

This is not really a python question, but I am hoping that some of you 
can offer some suggestions.

I have a SQL table with hierarchical data. There are two models that can 
be used to represent this - Adjacency Lists and Nested Sets. Here is a 
link to an article that discusses and compares the two approaches -

http://explainextended.com/2009/09/24/adjacency-list-vs-nested-sets-postgresql/

A feature of the Nested Sets model is that a SELECT returns the rows by 
following the links in the structure - root first, followed by its first 
child, followed by *its* first child, until the bottom is reached, then 
any siblings, then up one level to the next child, and so on, until the 
entire tree is exhausted.

I am looking for a way to emulate this behaviour using Adjacency Lists. 
It is not that easy.

The article above shows a way of doing this using an Array. 
Unfortunately that is a PostgreSQL feature not available in all 
databases, so I want to avoid that. Here is the best I have come up with.

For each row, I know the parent id, I know the level (depth in the 
tree), and I know the sequence number - every row has a sequence number 
that is unique within any group of siblings within the tree, always 
starting from zero.

I create a string to be used as a sort key, consisting of the parent's 
sort key, a comma, and the row's sequence number. So the root has a key 
of '0', the first child has '0,0', its first child has '0,0,0', etc.

If there could never be more than 10 siblings, that would work, but if 
it goes over 10, the next key would contain the substring '10', which 
sorts earlier than '2', which would be incorrect.

Therefore, on the assumption that there will never be more that 10000 
siblings, I zero-fill each element to a length of 4, so the first key is 
'0000', the next one is '0000,0000', then '0000,0000,0000', etc.

All this is done in SQL, as part of a complicated SELECT statement.

It works, and it would be unusual to have a tree with a depth of more 
than 4 or 5, so I can live with it.

However, it is not pretty. I wondered if anyone can suggest a more 
elegant solution.

Thanks

Frank Millman