Re: Tree structure table normalization problem (do I need a trigger?)

On Tue, 19 Dec 2000, Frank Joerdens wrote:

> In a recent thread (How to represent a tree-structure in a relational
> database) I asked how to do a tree structure in SQL, and got lots of
> suggestions (thanks!), of which I chose the one below:
>
> create table Category (
> CategoryID int4 not null primary key,
> ParentCategoryID int4 not null REFERENCES Category (CategoryID),
> CategoryName varchar(100)
> );
>
> The one described in Joe Celko's article (the one with the worm that
> travels along the edge of the tree . . . ) seemed more evolved but
> requires fairly complex SQL stuff, I thought, for simple operations that
> are straighforward with the above model. However, I have a problem now
> which seems non-trivial: I am at some point in the tree, say 3 nodes
> down from the root, but I don't know where I am exactly (across which
> nodes would I travel along the shortest path to the top?) and would like
> to find out. This is, again, not really difficult if I know how deep
> into the tree I am, in which case I can simply do (I know that I am 3
> nodes from the root and that my current node number is x):

That's exactly what the 'worm' stuff is all about...
If you use the structure above, you have to use recursion in order to
find out the path, which is AFAIK missing from SQL (not counting some
DB2 feature which allows recursion, in a strange way, but we're talking
Postgres here). This solution also does not require any client-side
programming, since you only have to use one single statement,
regardless of which level you are on in the tree.

The SQL stuff of that nested set structure is fairly easy, I wrote some
quick'n'dirty plpgsql functions that will do inserts, updates, deletes
from the tree, display level number etc.
I can send it to you if you like (please allow a few days since I
have several exams at the university this week).

Zsolt Tulassay

>
> SELECT A1.CategoryID, A2.CategoryID, A3.CategoryID FROM Category AS A1,
> Category AS A2, Category AS A3 WHERE A3.CategoryID=x AND
> A3.ParentCategoryID=A2.CategoryID AND A2.ParentCategoryID=A1.CategoryID;
>
> (This is probably very expensive if the tree gets really deep, but I
> don't expect that to happen in my database anytime soon.)
>
> So I introduced a 'level' column into the above schema, where I store
> the information about how deep I am into the tree to have it readily
> available when I want to compute the path to the top. Unfortunately,
> this is dangerous because the information is already implicit in the
> original schema. The problem is that the only way I can see that you
> would get at the information is by walking up the tree step-by-step
> until you get a zero value (which is assigned to the root). This means
> you need a loop control structure which means you have to write a
> PL/pgSQL procedure (or some other procedure) that is run by a trigger to
> update the level column on insert or update, as in
>
> WHILE (CategoryID is not null) LOOP
> Run SQL statement to get the next higher-up node's CategoryID and
> increment a counter.
> END LOOP;
> Return counter and insert value into level column.
>
> This seems to feasible but not really as straightforward as one might
> hope. Is there an easier way?
>
> - Frank
>