pg.ddx.io pgsql-sql@postgresql.org mailing list archive
help / color / mirror / Atom feedFW: Trees in SQL
12+ messages / 10 participants
[nested] [flat]
* FW: Trees in SQL
@ 1999-03-03 21:49 Jackson, DeJuan <djackson@cpsgroup.com>
0 siblings, 0 replies; 12+ messages in thread
From: Jackson, DeJuan @ 1999-03-03 21:49 UTC (permalink / raw)
To: pgsql-sql
-----Original Message-----
From: Jackson, DeJuan
Sent: Wednesday, March 03, 1999 1:18 PM
To: 'Bartek Teodorczyk'
Subject: RE: Trees in SQL
> I'm trying to implement set model of trees in SQL and I found
> a problem:
>
> How to find first level children of parent?
>
> For this structure:
>
> Jerry
> |
> -------------------
> | |
> Bert Chuck
> |
> ------------
> | |
> Donna Fred
>
> The question is: Who is first level child of Jerry?
> The answer should produce:
> Bert
> Chuck
>
> Maybe you know how to formulate the query?
>
> BarTeo
Assuming the above tree structure we have:
l | r | data
------------
1 |10 | Jerry
2 | 3 | Bert
4 | 9 | Chuck
5 | 6 | Donna
7 | 8 | Fred
What we need to do is find all children of Jerry that isn't a child of
anyone else who is a child of Jerry.
SELECT p1.*
FROM people p1, people p2
WHERE p2.l<p1.r AND p2.r>p1.r AND
p2.data = 'Jerry' AND
NOT EXISTS(SELECT 1 FROM people p3
WHERE p3.l<p1.r AND p3.r>p1.r AND
p2.l<p3.l AND p2.r>p3.r)
Results:
l|r|data
-+-+-----
2|3|Bert
4|9|Chuck
Hope this helps,
-DEJ
^ permalink raw reply [nested|flat] 12+ messages in thread
* Trees in SQL
@ 2002-05-24 18:08 Gregory Brauer <greg@wildbrain.com>
0 siblings, 6 replies; 12+ messages in thread
From: Gregory Brauer @ 2002-05-24 18:08 UTC (permalink / raw)
To: pgsql-sql
I hope this isn't an overly broad topic that ends up diverging into graph
theory, but I have a tree structure of identical items (analogous to a
filesystem directory tree) that I need to store in Postgres. The
"obvious" design is to give the table that will represent these objects
a field identifying its "parent" that is a relation to the same table.
However, this seems to make many common SQL queries rather difficult.
What sort of strategies are best for storing tree structures in a
relational database, and how would one structure SQL queries to find,
say, "all of the children anywhere under this node", or to represent
the condition "if this node is a child at any depth under this other
node"? Are there good strategies for preventing cycles?
I'd appreciate any insights anyone can give.
Thanks.
Greg Brauer
greg@wildbrain.com
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: Trees in SQL
@ 2002-05-24 18:34 Gregory Brauer <greg@wildbrain.com>
parent: Gregory Brauer <greg@wildbrain.com>
5 siblings, 1 reply; 12+ messages in thread
From: Gregory Brauer @ 2002-05-24 18:34 UTC (permalink / raw)
To: pgsql-sql
I guess this page answers many of my questions...
http://www.intelligententerprise.com/001020/celko1_1.shtml
Anybody have comments on working with nested sets?
Greg
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: Trees in SQL
@ 2002-05-24 18:41 Douglas Trainor <trainor@uic.edu>
parent: Gregory Brauer <greg@wildbrain.com>
5 siblings, 0 replies; 12+ messages in thread
From: Douglas Trainor @ 2002-05-24 18:41 UTC (permalink / raw)
To: Gregory Brauer <greg@wildbrain.com>; +Cc: pgsql-sql
If you're a book buyer, the one called "Joe Celko's SQL for Smarties: Advanced SQL Programming"
has a collection of tree/graph tricks. About 50 pages are devoted to these three sections:
Adjacency List Model of Trees
Nested Set Model of Trees in SQL
Graphs in SQL
Book distributors were trying to sell a preview edition of a book by
David Rozenshtein, et al called "Tree & Graph Processing in SQL" -- but something
fell through and the book apparently didn't come out.
Of course, it's more fun to not read a book and to try and implement a few toy tree/graph
things yourself.
douglas
Gregory Brauer wrote:
> I hope this isn't an overly broad topic that ends up diverging into graph
> theory, but I have a tree structure of identical items (analogous to a
> filesystem directory tree) that I need to store in Postgres. The
> "obvious" design is to give the table that will represent these objects
> a field identifying its "parent" that is a relation to the same table.
> However, this seems to make many common SQL queries rather difficult.
>
> What sort of strategies are best for storing tree structures in a
> relational database, and how would one structure SQL queries to find,
> say, "all of the children anywhere under this node", or to represent
> the condition "if this node is a child at any depth under this other
> node"? Are there good strategies for preventing cycles?
>
> I'd appreciate any insights anyone can give.
>
> Thanks.
>
> Greg Brauer
> greg@wildbrain.com
>
> ---------------------------(end of broadcast)---------------------------
> TIP 5: Have you checked our extensive FAQ?
>
> http://www.postgresql.org/users-lounge/docs/faq.html
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: Trees in SQL
@ 2002-05-24 19:28 Ron Peterson <ron.peterson@yellowbank.com>
parent: Gregory Brauer <greg@wildbrain.com>
0 siblings, 0 replies; 12+ messages in thread
From: Ron Peterson @ 2002-05-24 19:28 UTC (permalink / raw)
To: Gregory Brauer <greg@wildbrain.com>; +Cc: pgsql-sql
On Fri, May 24, 2002 at 11:34:41AM -0700, Gregory Brauer wrote:
>
> I guess this page answers many of my questions...
>
> http://www.intelligententerprise.com/001020/celko1_1.shtml
>
> Anybody have comments on working with nested sets?
Note that Joe Celko concludes this article by saying "Although this procedure
works, you might want to use a language that has arrays in it, instead of
trying to stick to pure SQL."
The operations required to maintain this type of structure are expensive.
You might like to take a look at:
http://cddb.sai.msu.su/~megera/postgres/gist/
I haven't had a chance to try this out yet, but it looks promising.
As an added bonus, if you're Russian, the documentation is in Russian.
Unfortunately, if you're not Russian, the documentation is in Russian.
Otherwise, for the time being, I'd recomend procedural code, rather than pure
SQL.
--
Ron Peterson -o)
87 Taylor Street /\\
Granby, MA 01033 _\_v
https://www.yellowbank.com/ ----
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: Trees in SQL
@ 2002-05-24 20:46 Oleg Bartunov <oleg@sai.msu.su>
parent: Gregory Brauer <greg@wildbrain.com>
5 siblings, 0 replies; 12+ messages in thread
From: Oleg Bartunov @ 2002-05-24 20:46 UTC (permalink / raw)
To: Gregory Brauer <greg@wildbrain.com>; +Cc: pgsql-sql
Check mailing list archive and try
http://www.sai.msu.su/~megera/postgres/gist/tree/
You'd need tree.tar.gz and test data to play with (dmoz catalog)
Unfortunately there is no doc in english :-(
Our approach is extremely fast for searching.
Oleg
On Fri, 24 May 2002, Gregory Brauer wrote:
>
> I hope this isn't an overly broad topic that ends up diverging into graph
> theory, but I have a tree structure of identical items (analogous to a
> filesystem directory tree) that I need to store in Postgres. The
> "obvious" design is to give the table that will represent these objects
> a field identifying its "parent" that is a relation to the same table.
> However, this seems to make many common SQL queries rather difficult.
>
> What sort of strategies are best for storing tree structures in a
> relational database, and how would one structure SQL queries to find,
> say, "all of the children anywhere under this node", or to represent
> the condition "if this node is a child at any depth under this other
> node"? Are there good strategies for preventing cycles?
>
> I'd appreciate any insights anyone can give.
>
> Thanks.
>
> Greg Brauer
> greg@wildbrain.com
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 5: Have you checked our extensive FAQ?
>
> http://www.postgresql.org/users-lounge/docs/faq.html
>
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] 12+ messages in thread
* Re: Trees in SQL
@ 2002-05-25 00:04 Christopher Kings-Lynne <chriskl@familyhealth.com.au>
parent: Gregory Brauer <greg@wildbrain.com>
5 siblings, 0 replies; 12+ messages in thread
From: Christopher Kings-Lynne @ 2002-05-25 00:04 UTC (permalink / raw)
To: Gregory Brauer <greg@wildbrain.com>; pgsql-sql
Try here maybe:
http://cddb.sai.msu.su/~megera/postgres/gist/
Look at their new 'tree' module...
Chris
----- Original Message -----
From: "Gregory Brauer" <greg@wildbrain.com>
To: <pgsql-sql@postgresql.org>
Sent: Friday, May 24, 2002 11:08 AM
Subject: [SQL] Trees in SQL
>
> I hope this isn't an overly broad topic that ends up diverging into graph
> theory, but I have a tree structure of identical items (analogous to a
> filesystem directory tree) that I need to store in Postgres. The
> "obvious" design is to give the table that will represent these objects
> a field identifying its "parent" that is a relation to the same table.
> However, this seems to make many common SQL queries rather difficult.
>
> What sort of strategies are best for storing tree structures in a
> relational database, and how would one structure SQL queries to find,
> say, "all of the children anywhere under this node", or to represent
> the condition "if this node is a child at any depth under this other
> node"? Are there good strategies for preventing cycles?
>
> I'd appreciate any insights anyone can give.
>
> Thanks.
>
> Greg Brauer
> greg@wildbrain.com
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 5: Have you checked our extensive FAQ?
>
> http://www.postgresql.org/users-lounge/docs/faq.html
>
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: Trees in SQL
@ 2002-05-27 12:00 Achilleus Mantzios <achill@matrix.gatewaynet.com>
parent: Gregory Brauer <greg@wildbrain.com>
5 siblings, 2 replies; 12+ messages in thread
From: Achilleus Mantzios @ 2002-05-27 12:00 UTC (permalink / raw)
To: Gregory Brauer <greg@wildbrain.com>; +Cc: pgsql-sql
On Fri, 24 May 2002, Gregory Brauer wrote:
I have exactly the same situation.
Some work (argued to have better performance than Celko's implementation)
has been done by Miguel Sofer. (see http://www.utdt.edu/~mig/trees.tar.gz)
One fast solution would be using pgsql arrays and the contrib/array
package.
However Oleg's and Theodor's contrib/tree solution looks the most
attractive.
I will ask my wife today to do a translation of the doc,
(hoping russian and yugoslavian are alike :)
>
> I hope this isn't an overly broad topic that ends up diverging into graph
> theory, but I have a tree structure of identical items (analogous to a
> filesystem directory tree) that I need to store in Postgres. The
> "obvious" design is to give the table that will represent these objects
> a field identifying its "parent" that is a relation to the same table.
> However, this seems to make many common SQL queries rather difficult.
>
> What sort of strategies are best for storing tree structures in a
> relational database, and how would one structure SQL queries to find,
> say, "all of the children anywhere under this node", or to represent
> the condition "if this node is a child at any depth under this other
> node"? Are there good strategies for preventing cycles?
>
> I'd appreciate any insights anyone can give.
>
> Thanks.
>
> Greg Brauer
> greg@wildbrain.com
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 5: Have you checked our extensive FAQ?
>
> http://www.postgresql.org/users-lounge/docs/faq.html
>
--
Achilleus Mantzios
S/W Engineer
IT dept
Dynacom Tankers Mngmt
tel: +30-10-8981112
fax: +30-10-8981877
email: achill@matrix.gatewaynet.com
mantzios@softlab.ece.ntua.gr
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: Trees in SQL
@ 2002-05-27 12:57 Rajesh Kumar Mallah. <mallah@trade-india.com>
parent: Achilleus Mantzios <achill@matrix.gatewaynet.com>
1 sibling, 0 replies; 12+ messages in thread
From: Rajesh Kumar Mallah. @ 2002-05-27 12:57 UTC (permalink / raw)
To: Achilleus Mantzios <achill@matrix.gatewaynet.com>; Gregory Brauer <greg@wildbrain.com>; +Cc: pgsql-sql
Hey Please post the translation back here !!
;-)
lot many others like would require it
despo.
regds
mallah.
On Monday 27 May 2002 05:30 pm, Achilleus Mantzios wrote:
> On Fri, 24 May 2002, Gregory Brauer wrote:
>
> I have exactly the same situation.
>
> Some work (argued to have better performance than Celko's implementation)
> has been done by Miguel Sofer. (see http://www.utdt.edu/~mig/trees.tar.gz)
>
> One fast solution would be using pgsql arrays and the contrib/array
> package.
>
> However Oleg's and Theodor's contrib/tree solution looks the most
> attractive.
>
> I will ask my wife today to do a translation of the doc,
> (hoping russian and yugoslavian are alike :)
>
> > I hope this isn't an overly broad topic that ends up diverging into graph
> > theory, but I have a tree structure of identical items (analogous to a
> > filesystem directory tree) that I need to store in Postgres. The
> > "obvious" design is to give the table that will represent these objects
> > a field identifying its "parent" that is a relation to the same table.
> > However, this seems to make many common SQL queries rather difficult.
> >
> > What sort of strategies are best for storing tree structures in a
> > relational database, and how would one structure SQL queries to find,
> > say, "all of the children anywhere under this node", or to represent
> > the condition "if this node is a child at any depth under this other
> > node"? Are there good strategies for preventing cycles?
> >
> > I'd appreciate any insights anyone can give.
> >
> > Thanks.
> >
> > Greg Brauer
> > greg@wildbrain.com
> >
> >
> > ---------------------------(end of broadcast)---------------------------
> > TIP 5: Have you checked our extensive FAQ?
> >
> > http://www.postgresql.org/users-lounge/docs/faq.html
--
Rajesh Kumar Mallah,
Project Manager (Development)
Infocom Network Limited, New Delhi
phone: +91(11)6152172 (221) (L) ,9811255597 (M)
Visit http://www.trade-india.com ,
India's Leading B2B eMarketplace.
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: Trees in SQL
@ 2002-05-27 18:24 Christopher Kings-Lynne <chriskl@familyhealth.com.au>
parent: Achilleus Mantzios <achill@matrix.gatewaynet.com>
1 sibling, 1 reply; 12+ messages in thread
From: Christopher Kings-Lynne @ 2002-05-27 18:24 UTC (permalink / raw)
To: Achilleus Mantzios <achill@matrix.gatewaynet.com>; Gregory Brauer <greg@wildbrain.com>; +Cc: pgsql-sql
> Some work (argued to have better performance than Celko's implementation)
> has been done by Miguel Sofer. (see http://www.utdt.edu/~mig/trees.tar.gz)
>
> One fast solution would be using pgsql arrays and the contrib/array
> package.
>
> However Oleg's and Theodor's contrib/tree solution looks the most
> attractive.
>
> I will ask my wife today to do a translation of the doc,
> (hoping russian and yugoslavian are alike :)
Well if she can - please post the docs back to Oleg & Teodor and the list
here!
Thanks,
Chris
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: Trees in SQL
@ 2002-05-27 20:06 Josh Berkus <josh@agliodbs.com>
parent: Gregory Brauer <greg@wildbrain.com>
5 siblings, 0 replies; 12+ messages in thread
From: Josh Berkus @ 2002-05-27 20:06 UTC (permalink / raw)
To: Gregory Brauer <greg@wildbrain.com>; pgsql-sql
Greg,
> What sort of strategies are best for storing tree structures in a
> relational database, and how would one structure SQL queries to find,
> say, "all of the children anywhere under this node", or to represent
> the condition "if this node is a child at any depth under this other
> node"? Are there good strategies for preventing cycles?
Joe Celko covers this extensively in his book "SQL for Smarties." You should
definitely buy it and read the two chapters on tree structures before going
any further.
I will be writing an article for Techdocs within the month on implementing
Celko's "Linear Nested Sets Model" of trees in PostgreSQL. If you can't
wait, buy the book, e-mail me, and I'll send you my notes.
--
-Josh Berkus
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: Trees in SQL
@ 2002-05-29 16:19 achill@matrix.gatewaynet.com
parent: Christopher Kings-Lynne <chriskl@familyhealth.com.au>
0 siblings, 0 replies; 12+ messages in thread
From: achill@matrix.gatewaynet.com @ 2002-05-29 16:19 UTC (permalink / raw)
To: Christopher Kings-Lynne <chriskl@familyhealth.com.au>; +Cc: Gregory Brauer <greg@wildbrain.com>; pgsql-sql
On Mon, 27 May 2002, Christopher Kings-Lynne wrote:
> > Some work (argued to have better performance than Celko's implementation)
> > has been done by Miguel Sofer. (see http://www.utdt.edu/~mig/trees.tar.gz)
> >
> > One fast solution would be using pgsql arrays and the contrib/array
> > package.
> >
> > However Oleg's and Theodor's contrib/tree solution looks the most
> > attractive.
> >
> > I will ask my wife today to do a translation of the doc,
> > (hoping russian and yugoslavian are alike :)
>
> Well if she can - please post the docs back to Oleg & Teodor and the list
> here!
The problem is that phrases like "the mask of the tree" dont make much
sense to her.
We've bought a greek-russian dictionary, and in 1-2 weeks i think
i will have it.
>
> Thanks,
>
> Chris
>
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 5: Have you checked our extensive FAQ?
>
> http://www.postgresql.org/users-lounge/docs/faq.html
>
^ permalink raw reply [nested|flat] 12+ messages in thread
end of thread, other threads:[~2002-05-29 16:19 UTC | newest]
Thread overview: 12+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
1999-03-03 21:49 FW: Trees in SQL Jackson, DeJuan <djackson@cpsgroup.com>
2002-05-24 18:08 Trees in SQL Gregory Brauer <greg@wildbrain.com>
2002-05-24 18:34 ` Gregory Brauer <greg@wildbrain.com>
2002-05-24 19:28 ` Ron Peterson <ron.peterson@yellowbank.com>
2002-05-24 18:41 ` Douglas Trainor <trainor@uic.edu>
2002-05-24 20:46 ` Oleg Bartunov <oleg@sai.msu.su>
2002-05-25 00:04 ` Christopher Kings-Lynne <chriskl@familyhealth.com.au>
2002-05-27 12:00 ` Achilleus Mantzios <achill@matrix.gatewaynet.com>
2002-05-27 12:57 ` Rajesh Kumar Mallah. <mallah@trade-india.com>
2002-05-27 18:24 ` Christopher Kings-Lynne <chriskl@familyhealth.com.au>
2002-05-29 16:19 ` achill@matrix.gatewaynet.com
2002-05-27 20:06 ` Josh Berkus <josh@agliodbs.com>
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