Re: recursing down a tree

Carl Meyer wrote:


> say i have a table with something like
>
> id,parent,description
>
> and parent points to an id of the very same table. now i have
> a specific id and i want to recurse down the tree to the root.
> is it in any way possible to do that without to doing a sql query
> for each level ? until today i always saved the parent and formulated
> a new query using it to get the next upper level. however, it seems to
> me that this might be quite some work given a tree of a larger size.
>
> thanks for your ideas
> carl


Well, this calls for recursive union support as per SQL '99. The
query would be

CREATE TABLE MyTree(id, parent, description);

WITH tmp(id) AS (
    SELECT parent FROM MyTree WHERE id=$myId
  UNION ALL

   SELECT MyTree.parent

     FROM tmp INNER JOIN MyTree ON tmp.id = MyTree.id

) SELECT *;

This is most powerful if you search for children though, since
then you get the full power of the recursive union join to find
more and more stuff:

WITH tmp(id) AS (
    SELECT id FROM MyTree WHERE id=$myId
  UNION ALL
    SELECT MyTree.id
      FROM tmp INNER JOIN MyTree ON MyTree.parent = tmp.id
) SELECT *;

Now, this is not supported in PostgreSQL, and I only know of DB2

implementing it actually. But it's way cool!

In the absence of this feature ... and even to speed some of such
queries up, you can use some tree representation in a special
field. There are many approaches. An interval method is theoretically
nice because it has a constant storage requirement regardless of
depth and fan-out of the tree. Oleg's GiST tree type is certainly
very nice here. If you don't want to use special data types, you
can use some path expression string, but the problem is you'll
have to have leading zeroes in each path step.

regards
-Gunther



--
Gunther Schadow, M.D., Ph.D.                    gschadow@regenstrief.org
Medical Information Scientist      Regenstrief Institute for Health Care
Adjunct Assistant Professor        Indiana University School of Medicine
tel:1(317)630-7960                         http://aurora.regenstrief.org