Sorting a hierarchical table (SQL)

Discussion in 'Python' started by Frank Millman, Jan 30, 2013.

  1. 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
     
    Frank Millman, Jan 30, 2013
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Paul M

    SQL database table ot SQL schema

    Paul M, Dec 8, 2003, in forum: ASP .Net
    Replies:
    2
    Views:
    425
    Mythran
    Dec 8, 2003
  2. ecoolone
    Replies:
    0
    Views:
    797
    ecoolone
    Jan 3, 2008
  3. Masya
    Replies:
    0
    Views:
    524
    Masya
    Jan 7, 2009
  4. Steve
    Replies:
    4
    Views:
    397
    James Willmore
    Nov 28, 2003
  5. Replies:
    0
    Views:
    137
Loading...

Share This Page