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

From: Frank Joerdens <frank(at)joerdens(dot)de>
To: pgsql-sql(at)postgresql(dot)org
Subject: Tree structure table normalization problem (do I need a trigger?)
Date: 2000-12-18 23:58:12
Message-ID: 3A3EA494.3682000B@joerdens.de
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-sql

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):

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

Responses

Browse pgsql-sql by date

  From Date Subject
Next Message jkakar 2000-12-19 01:11:34 Bounds checking on an alias
Previous Message Michael Fork 2000-12-18 22:30:09 Re: Problem with function...