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

On Wednesday 13 December 2000 18:05, Josh Berkus wrote:
> Frank, etc:
> > > create table Category (
> > > CategoryID int4 not null primary key,
> > > ParentCategoryID int4 not null REFERENCES Category (CategoryID),
> > > CategoryName varchar(100)
> > > );

I made a message board with a hierarchy for topics/boards under which
messages go into a post/reply hierarchy at www.comptechnews.com. I used the
parent_id idea like in the table above.

It's working OK and, yes, I can easily move nodes around without problems. I
can move/reparent Topic/boards and posts/replies (posts and replies are
treated nearly the same, just that a post has a parent-post-id of 0 while a
reply message's parent-post-id is non-zero). This arrangement combined with
the use of PL/pgSQL trigger functions can go a long way.

I did not use any foreign keys but just had the PL/pgSQL triggers do any
checks I wanted myself. So, its easy to make triggers that do things like
automatically delete an entire hierarchy when a node(message or topic) is
deleted. Like, if you delete a post, it deletes all its replies
automatically. If you delete a reply, it deletes any child/replies that it
might have etc. If you delete a topic/board, it deletes all messages that
were in that topic and any subtopics and messages in those subtopics
recursively. The PL/pgSQL can be used to RAISE EXCEPTION when something you
don't want to happen is attempted (like deleting the root topic!), which then
automatically ABORTs the transaction.

You will want to make heavy use of procedures in the database to ensure
integrity. You might be able to use FOREIGN KEY triggers also but with
careful use of BEFORE and AFTER PL/pgSQL triggers. In my case, I had somekind
of conflict between what my PL/pgSQL triggers where doing and what the
foreign key triggers were doing. The stuff my PL/pgSQL were doing caused
referential integrity violations sometimes. You have to be real careful what
goes into a BEFORE trigger and what goes into an AFTER trigger. Trying to
make a BEFORE trigger or an AFTER trigger do too much will end up in trouble
so you have to split what you want to do into two triggers for a table. The
CONSTRAINT TRIGGERs that get created automatically by FOREIGN KEYs are called
AFTER INSERT OR UPDATE|DELETE and are NOT DEFERRABLE and INITIALLY IMMEDIATE.
You have to keep that in mind in writing your procedures. In the end, I
judged the contraint triggers to interfere with what I wanted to do and
removed them.

>
> That was it. I also gave an example of a UNION query that would display
> the whole category tree in ASCII format:
>
> 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
>
> etc.
>
> 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:
>
> SELECT n1.unique_id, n1.label, n1.data, n1.node_level, n1.unique_id AS
> level1,
> 0 AS level2, 0 AS level3
> FROM sample_heirarchy n1
> WHERE n1.node_level = 1
> UNION ALL
> SELECT n2.unique_id, n2.label, n2.data, n2.node_level, n1.unique_id,
> n2.unique_id, 0
> FROM sample_heirarchy n2, sample_heirarchy n1
> WHERE n1.unique_id = n2.node_linkup
> AND n2.node_level = 2
> UNION ALL
> SELECT n3.unique_id, n3.label, n3.data, n3.node_level, n1.unique_id,
> n2.unique_id, n3.unique_id
> FROM sample_heirarchy n1, sample_heirarchy n2, sample_heirarchy n3
> WHERE n1.unique_id = n2.node_linkup AND
> n2.unique_id = n3.node_linkup
> AND n3.node_level = 3
> ORDER BY level1, level2, level3
>
> Should produce this output (pardon any parsing errors; I'm not at a
> PGSQL terminal right now):
>
> unique_id label data level level1 level2 level3
> 3 Node1 Node1 1 3 0 0
> 4 Node1.1 Node1.1 2 3 4 0
> 6 Node1.2 Node1.2 2 3 6 0
> 7 Node1.2.1 Node1.2.1 3 3 6 7
> 5 Node2 Node2 1 7 0 0
> etc.
>
> This sorts them in numerical (id) order, but one could just as easily
> substitute the labels or data for the various levels and sort them
> alphabetically (although you do need to allow for NULL sort order on
> your database, and any label duplicates).
>
> The advantages of this structure are:
> 1. It allows you to create, assign, and re-assign nodes freely all over
> the heirarchy ... just change the level and/or linkup.
> 2. Aside from the Union query above, the table structure allows for any
> number of levels, unlike a set or relationally linked tables.
> 3. Because the display query is entirely once table linking to itself on
> (hopefully) indexed fields, in my expreience it runs very, very fast.
> 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).
>
> -Josh Berkus

--
-------- Robert B. Easter reaster(at)comptechnews(dot)com ---------
- CompTechNews Message Board http://www.comptechnews.com/ -
- CompTechServ Tech Services http://www.comptechserv.com/ -
---------- http://www.comptechnews.com/~reaster/ ------------