pg.ddx.io pgsql-sql@postgresql.org mailing list archive
help / color / mirror / Atom feedretrieving all rows from a "tree" in one select - how ?
4+ messages / 4 participants
[nested] [flat]
* retrieving all rows from a "tree" in one select - how ?
@ 2002-08-09 21:36 h012@ied.com
0 siblings, 1 reply; 4+ messages in thread
From: h012@ied.com @ 2002-08-09 21:36 UTC (permalink / raw)
To: pgsql-sql
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/
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: retrieving all rows from a "tree" in one select - how ?
@ 2002-08-09 22:04 Adam Erickson <adamre@cox.net>
parent: h012@ied.com
0 siblings, 2 replies; 4+ messages in thread
From: Adam Erickson @ 2002-08-09 22:04 UTC (permalink / raw)
To: h012@ied.com; pgsql-sql
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
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: retrieving all rows from a "tree" in one select - how ?
@ 2002-08-09 22:15 Josh Berkus <josh@agliodbs.com>
parent: Adam Erickson <adamre@cox.net>
1 sibling, 0 replies; 4+ messages in thread
From: Josh Berkus @ 2002-08-09 22:15 UTC (permalink / raw)
To: Adam Erickson <adamre@cox.net>; h012@ied.com; pgsql-sql
Guys,
Check out Joe Celko's two chapters on tree structures in the 2nd edition of
"SQL for Smarties". It's pretty comprehensive.
--
-Josh Berkus
Aglio Database Solutions
San Francisco
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: retrieving all rows from a "tree" in one select - how ?
@ 2002-08-09 23:37 Oleg Bartunov <oleg@sai.msu.su>
parent: Adam Erickson <adamre@cox.net>
1 sibling, 0 replies; 4+ messages in thread
From: Oleg Bartunov @ 2002-08-09 23:37 UTC (permalink / raw)
To: Adam Erickson <adamre@cox.net>; +Cc: pgsql-sql
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
^ permalink raw reply [nested|flat] 4+ messages in thread
end of thread, other threads:[~2002-08-09 23:37 UTC | newest]
Thread overview: 4+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2002-08-09 21:36 retrieving all rows from a "tree" in one select - how ? h012@ied.com
2002-08-09 22:04 ` Adam Erickson <adamre@cox.net>
2002-08-09 22:15 ` Josh Berkus <josh@agliodbs.com>
2002-08-09 23:37 ` Oleg Bartunov <oleg@sai.msu.su>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox