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
