in reply to Trees in SQL, adjacency lists and sorting.

The standard approach, despite the temptation to just use one table with an auto-foreign key, is:
CREATE TABLE node (node_name VARCHAR(32) NOT NULL)

CREATE TABLE node_node ( parent_fk VARCHAR(32) NOT NULL, child_fk VARC
+HAR(32) NOT NULL )

[download]
The next bit is DBMS specific but you also need to define the primary keys: (node.node_name) and (node_node.parent_fk, node_node.child_fk) and the foreign key constraints: node.node_name -> node_node.parent_fk and node.node_name -> node_node.child_fk.

The advantage of this over the single table solution is that it is normalised and can be extended into a multi-type, multi-tree model without having to keep adding foreign keys to the master table.

Replies are listed 'Best First'.
Re^2: Trees in SQL, adjacency lists and sorting.
by saberworks (Curate) on Jan 06, 2006 at 19:25 UTC
    The problem with this is that you can't do a single select query to get an entire branch of the tree in the correct order. You have to write something like a recursive function and you end up with one query per level of the tree.

    Someone above mentioned "nested set" - this is what I use and it's great for quick lookups, at the cost of expensive (relatively) inserts. I've never had a database big enough where inserts have been a problem.
[reply]

      Thats not really true. Assuming your nodes can be ordered, and assuming you store a root id, you grab everything from the tree on or later to the node you are interested in. Then filter out the noncompliant nodes when you read them. One query sufficies then. Admittedly at the cost of some client side processing, but if that isnt a problem then it should be fine.

      For the record this exactly what is doe in Recently Added Threads. We grab all the relevent nodes in two queries normally. (Roots then children as our roots arent the same type as the children).

      ---
      $world=~s/war/peace/g

[reply]
      You certainly can't do that with the single table solution either. Such a branch is iterative and therefore cannot be expressed as an RSE whichever RDBMS solution you choose.

      Everything but the troll

[reply]
        I beg to differ. In fact, here is an article about it: click
[reply]

In Section Seekers of Perl Wisdom