RE: How to represent a tree-structure in a relational database

[Josh Berkus]

> I've done this before for one project.  Here's what you do:
>
> CREATE TABLE sample_heirarchy (
>         unique_id       SERIAL CONSTRAINT PRIMARY KEY,
>         node_linkup     INT4,
>         node_level      INT2,
>         label           VARCHAR(30)
>         data            whatever
>         );
>
> Then you use the unique_id and node_linkup fields to create a heirarchy
> of data nodes, with an indefinite number of levels, where the
> node_linkup of each lower level equals the id of its parent record.  For
> example:
>
> id      linkup  level           label           data
> 3       0       1               Node1           Node1
> 4       3       2               Node1.1         Node1.1
> 6       3       2               Node1.2         Node1.2
> 7       6       3               Node1.2.1       Node1.2.1
> 5       0       1               Node2           Node2

I don't think I'd be comfortable with having the node_level column in the
table structure. First, because you can derive that value using a function,
it's duplicate data. Second, if you decide to take an entire segment of your
hierarchy and move it under another node (by changing the value of
node_linkup/ParentCategoryID), you'll need to recalculate all of those
node_level values. And all the node_level values underneath it.

> You can then access the whole heirarchy through moderately complex, but
> very fast-executing UNION queries.  The one drawback is that you need to
> know in advance the maximum number of levels (3 in this example), but
> I'm sure someone on this list can find a way around that:

I can think of another way to do this, though it would be a little complex
and would involve temp tables. Select all of your top level nodes into a
temp table. Create a new table with a new column for the new level. Select
the children of the top level nodes into the temp table, followed by those
top level nodes themselves, with a 0 in the new column and a flag indicating
not to expand again. Create a new temp table just like the last but with
another column for the new level, and repeat the above process from the
first temp table to the second, only expanding the latest children, but
copying all records over. Keep doing it until there are no more new
children.

Alternately, if you didn't need each level to have it's own column, but
didn't mind an x.x.x.x kind of notation, you could use one temp table, and
just append '.0' to the end of every copied-over parent node.

Basically, both methods are simulations of recursing the tree, but you get
to do each level all at once using an insert ... select. If you wanted, you
could even use a counter, to identify which level each node appeared in.

Clearly, this could also be done with cursors and recursive

> 4. My PHP developer has reprogrammed the easily available PHP Tree
> Control to uses this table structure (I don't know if he's giving it
> out, but he said it wasn't very difficult).

We've done a similar thing for Java. It was ridiculously easy to create a
TreeModel wrapped around this data. Almost too easy; it made me feel dirty.

Stuart Statman
Director of Software Development
Slam Media, Inc.