F
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
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