Received: from rakete.joerdens.de (rakete.joerdens.de [62.104.116.200]) by mail.postgresql.org (8.11.1/8.11.1) with ESMTP id eBIN1n624170 for ; Mon, 18 Dec 2000 18:01:49 -0500 (EST) (envelope-from frank@joerdens.de) Received: from joerdens.de (B3ebe.pppool.de [213.7.62.190]) by rakete.joerdens.de (8.9.3/8.9.3) with ESMTP id AAA15181 for ; Tue, 19 Dec 2000 00:21:34 +0100 Message-ID: <3A3EA494.3682000B@joerdens.de> Date: Tue, 19 Dec 2000 00:58:12 +0100 From: Frank Joerdens X-Mailer: Mozilla 4.75 [en] (Win95; U) X-Accept-Language: en MIME-Version: 1.0 To: pgsql-sql@postgresql.org Subject: Tree structure table normalization problem (do I need a trigger?) Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Archive-Number: 200012/203 X-Sequence-Number: 537 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