Thread: retrieving all rows from a "tree" in one select - how ?

Hi,
 I realize that a relational database may not be ideal for storing (and 
retrieving) tree-like strucutres, but it looks like you guys are doing 
with PostgreSQL the impossible anyway.

Having table t of all nodes:

CREATE SEQUENCE nodeIDseq START 1;
CREATE TABLE t(id int PRIMARY KEY DEFAULT NEXTVAL('nodeIDseq'),parent int REFERENCES t,mydata int4);
INSERT INTO t VALUES (0,0);
I was wondering whether there is a known (and perhaps working) way to do 
things like:
-- select a tree starting with node 1234 and all its descendants:
SELECT * FROM t WHERE id=1234 OR ANCESTOR(t.parent) IS 1234;

and-- select the path from tree node 2345 to the root 
SELECT * FROM t WHERE id=2345 OR DESCENTANT(t.parent) IS 2345;

(I've seen some terse soutions at 
http://www.brasileiro.net/postgres/cookbook/view-recipes.adp?section_id=2&format=long 
but they don't seem to be complete.)

(Also I've looket at ltrees from GiST, but "ltree" seems to require that 
the ID attribute contains all ancestors.)
 Thanks,
   John

-- 
-- Gospel of Jesus is the saving power of God for all who believe --              ## To some, nothing is impossible. ##
                  http://Honza.Vicherek.com/
 

I'll be curious to see the responses to this.  I myself deal with this same
situation every day.  Although we're currently using MySQL but moving it to
postgres (which is why I'm on these lists..)

>  -- select a tree starting with node 1234 and all its descendants:
> SELECT * FROM t WHERE id=1234 OR ANCESTOR(t.parent) IS 1234;

I've seen some really weird solutions to this.  I'm not sure if a subselect
can do this or not.  I doubt it.  Since MySQL limits us greatly we resort to
a lookup field for each record in the node.

ie. (Forgive ASCII art please)

1 --> 2    --> 4    --> 5    --> 6       --> 8          --> 9 --> 3    --> 7       --> 10

The record for id=9 would have a field index='-1-2-6-8-x'

When we want all records under node id=6 we just use:
select * from t where index like "%-6-%";

We prefix with '-' for arbitrary level searches.  We suffix with -x for an
unknown (but good) reason.  My memory is leaving me.

>  -- select the path from tree node 2345 to the root
> SELECT * FROM t WHERE id=2345 OR DESCENTANT(t.parent) IS 2345;

With our lookup/index field this is trivial.  Unfortunately, it makes the
application responsible for parsing and is probably not what you're after.

Just my two cents.  It works very well for us (make the lookup field an
index btw) but their is probably a much better way in postgres.  I don't
remember if postgres allows regexes in the where clause (ie. rlike in mysql)
but with that you can "find all nodes 3 or more leaves down from node 123"
or even weirder stuff.  We have trees with 60,000 nodes 30-40 levels deep.
Queries on the tree take very little time at all.

Adam Erickson

Guys,

Check out Joe Celko's two chapters on tree structures in the 2nd edition of
"SQL for Smarties".  It's pretty comprehensive.

--
-Josh BerkusAglio Database SolutionsSan Francisco

folk,

have you looked at ltree ?
http://www.sai.msu.su/~megera/postgres/gist/ltree/

Regards,
Oleg

On Fri, 9 Aug 2002, Adam Erickson wrote:

> I'll be curious to see the responses to this.  I myself deal with this same
> situation every day.  Although we're currently using MySQL but moving it to
> postgres (which is why I'm on these lists..)
>
> >  -- select a tree starting with node 1234 and all its descendants:
> > SELECT * FROM t WHERE id=1234 OR ANCESTOR(t.parent) IS 1234;
>
> I've seen some really weird solutions to this.  I'm not sure if a subselect
> can do this or not.  I doubt it.  Since MySQL limits us greatly we resort to
> a lookup field for each record in the node.
>
> ie. (Forgive ASCII art please)
>
> 1 --> 2
>      --> 4
>      --> 5
>      --> 6
>         --> 8
>            --> 9
>   --> 3
>      --> 7
>         --> 10
>
> The record for id=9 would have a field index='-1-2-6-8-x'
>
> When we want all records under node id=6 we just use:
> select * from t where index like "%-6-%";
>
> We prefix with '-' for arbitrary level searches.  We suffix with -x for an
> unknown (but good) reason.  My memory is leaving me.
>
> >  -- select the path from tree node 2345 to the root
> > SELECT * FROM t WHERE id=2345 OR DESCENTANT(t.parent) IS 2345;
>
> With our lookup/index field this is trivial.  Unfortunately, it makes the
> application responsible for parsing and is probably not what you're after.
>
> Just my two cents.  It works very well for us (make the lookup field an
> index btw) but their is probably a much better way in postgres.  I don't
> remember if postgres allows regexes in the where clause (ie. rlike in mysql)
> but with that you can "find all nodes 3 or more leaves down from node 123"
> or even weirder stuff.  We have trees with 60,000 nodes 30-40 levels deep.
> Queries on the tree take very little time at all.
>
> Adam Erickson
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 1: subscribe and unsubscribe commands go to majordomo@postgresql.org
>
Regards,    Oleg
_____________________________________________________________
Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
Sternberg Astronomical Institute, Moscow University (Russia)
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83