This is, yet again, another node displaying a misunderstanding of relational theory. These things are sets, which are inherently unordered. Ordering is provided as an additional feature, like triggers. It's not part of the relational theory and, in fact, violates relational theory. That said ...
  1. I'm assuming you're going to have a row that says "A | NULL | 0". You need to represent the root somewhere. Implicit representation is not going to cut it.
  2. This is going to be an absolute nightmare to update. For example, if you remove a node and promote one of the children (a common operation in red-black trees, for example), You're going to have to recalculate in your application every single depth. Furthermore, if your application code is wrong in any way, the database isn't going to help you catch your error, particularly in the depth area.
  3. Trees are ordered with respect to siblings. In your case, you're assuming that B comes before C and D comes before E. How are you planning on capturing that in your schema? You're storing depth (which is easily derived and doesn't really help improving select speed), but you're not storing sibling sort order (which isn't derivable because you cannot depend on the order the RDBMS will store the rows).
  4. Assuming you have all of that, let's see what your sort would look like in Perl: 
    my @nodes = map {
    $_->[0]
} sort {
    # What goes here??
} map {
    [ $_->{node_id}, $_->{depth}, $_->{sibling_order} ]
} $sth->fetchall_hashref();

    [download]

    If you wanted a level-order traversal, you'd use: 

        $a->{depth} <=> $b->{depth}
        ||
    $a->{sibling_order} <=> $b->{sibling_order}

    [download]
    Except, that gives you A-B-C-D-E-F-G, which isn't what you want.

    Take a look at Tree, particularly the traversal code I wrote in order to provide traversals as an iterator into the tree versus an array (which is what you're trying to do in an ORDER BY clause). The code is non-trivial, particularly in that it requires maintaining a stack to keep track of what comes next.

In short, you cannot do it with ANSI SQL-1992, SQL-1999, or even SQL-2003. You would have to use a vendor-specific extension that allows user-defined comparators for sorting. I recommend PostgreSQL as MySQL, Oracle, Sybase, and SQL*Server all don't provide this. SQLite definitely doesn't provide this.

My criteria for good software:
  1. Does it work?
  2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?

In reply to Re: Trees in SQL, adjacency lists and sorting. by dragonchild
in thread Trees in SQL, adjacency lists and sorting. by BUU

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.