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@comptechnews.com ---------
- CompTechNews Message Board   http://www.comptechnews.com/ -
- CompTechServ Tech Services   http://www.comptechserv.com/ -
---------- http://www.comptechnews.com/~reaster/ ------------