pg.ddx.io pgsql-sql@postgresql.org mailing list archive
help / color / mirror / Atom feedtree structures in sql - my point of view (with request of comment from joe celko)
6+ messages / 6 participants
[nested] [flat]
* tree structures in sql - my point of view (with request of comment from joe celko)
@ 2002-09-03 13:22 Hubert depesz Lubaczewski <depesz@depesz.pl>
0 siblings, 2 replies; 6+ messages in thread
From: Hubert depesz Lubaczewski @ 2002-09-03 13:22 UTC (permalink / raw)
To: pgsql-sql
hi
i recently spent some time on tree-structures in sql.
i started with simple id/parent_id approach, used by nearly everyone,
then i stopped at joe celko's nested sets, but i found it not very
usable.
then i found my own (maybe someone wrote it before, but i haven't read
it, so idea is mine) way.
in my way we have two tables:
create table data (id serial, name text);
create table structure (parent_id int8, child_id int8, depth int8);
structure table represents all paths in tree.
for example for this tree:
sql
/ \
postgresql oracle-----__
| / | \
linux sco linux windows
/ \
glibc1 glibc2
(sorry for used data - it is just template, and personally i don't like
oracle).
so, for this tree we would populate the tables this way:
data:
id | name
----+------------
1 | sql
2 | postgresql
3 | oracle
4 | linux
5 | sco
6 | linux
7 | windows
8 | glibc1
9 | glibc2
structure:
parent_id | child_id | depth
-----------+----------+-------
1 | 1 | 0
2 | 2 | 0
3 | 3 | 0
4 | 4 | 0
5 | 5 | 0
6 | 6 | 0
7 | 7 | 0
8 | 8 | 0
9 | 9 | 0
1 | 2 | 1
1 | 3 | 1
1 | 4 | 2
2 | 4 | 1
1 | 5 | 1
1 | 6 | 1
1 | 7 | 1
3 | 5 | 2
3 | 6 | 2
3 | 7 | 2
1 | 8 | 3
1 | 9 | 3
3 | 8 | 2
3 | 9 | 2
6 | 8 | 1
6 | 9 | 1
(records with depth 0 are technologically not necessary, but they
simplify and speedup some queries).
with this data layout (easily indexable) you can fetch any data with
just one select statement (no recursion needed in any case):
- fetching parent
- fetching childs
- fetching "from id up"
- fetching "from id down"
also when you need to get indirect parents/childs or when you need only
some of the data (from me, up, but not more then to my
grand-grand-grand-father).
i'd like to get some comments on this - how do you see my idea, is it
worth it, do you know any better way to store trees in sql?
best regards
depesz
--
hubert depesz lubaczewski http://www.depesz.pl/
------------------------------------------------------------------------
Mój Boże, spraw abym milczał, dopóki się nie upewnię, że naprawdę mam
coś do powiedzenia. (c) 1998 depesz
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: tree structures in sql - my point of view (with request of comment from joe celko)
@ 2002-09-03 18:17 Josh Berkus <josh@agliodbs.com>
parent: Hubert depesz Lubaczewski <depesz@depesz.pl>
1 sibling, 1 reply; 6+ messages in thread
From: Josh Berkus @ 2002-09-03 18:17 UTC (permalink / raw)
To: depesz@depesz.pl; pgsql-sql
Hubert,
> i recently spent some time on tree-structures in sql.
> i started with simple id/parent_id approach, used by nearly everyone,
> then i stopped at joe celko's nested sets, but i found it not very
> usable.
I'll be posting an article on implementing nested set trees "real soon now".
My experieince:
Adjacency list trees are easier to understand conceptually, there are more
tools on freshmeat.net for them, and they are the most efficient form of tree
for graphical display.
Nested Set trees are hard to wrap your mind around, lack a lot in the way of
code samples on freshmeat, are harder to build GUI tools for, but are much,
much faster for determining branch membership and branch parenthood.
So which model you use depends on what you intend to do with the tree.
--
-Josh Berkus
Aglio Database Solutions
San Francisco
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: tree structures in sql - my point of view (with request
@ 2002-09-03 18:42 Oleg Bartunov <oleg@sai.msu.su>
parent: Hubert depesz Lubaczewski <depesz@depesz.pl>
1 sibling, 1 reply; 6+ messages in thread
From: Oleg Bartunov @ 2002-09-03 18:42 UTC (permalink / raw)
To: Hubert depesz Lubaczewski <depesz@depesz.pl>; +Cc: pgsql-sql
While I don't have a time to comment your message I want to point to
contrib/ltree package which is extremely fast :-)
http://www.sai.msu.su/~megera/postgres/gist/ltree
Oleg
On Tue, 3 Sep 2002, Hubert depesz Lubaczewski wrote:
> hi
> i recently spent some time on tree-structures in sql.
> i started with simple id/parent_id approach, used by nearly everyone,
> then i stopped at joe celko's nested sets, but i found it not very
> usable.
> then i found my own (maybe someone wrote it before, but i haven't read
> it, so idea is mine) way.
> in my way we have two tables:
> create table data (id serial, name text);
> create table structure (parent_id int8, child_id int8, depth int8);
>
> structure table represents all paths in tree.
> for example for this tree:
>
> sql
> / \
> postgresql oracle-----__
> | / | \
> linux sco linux windows
> / \
> glibc1 glibc2
>
> (sorry for used data - it is just template, and personally i don't like
> oracle).
> so, for this tree we would populate the tables this way:
> data:
> id | name
> ----+------------
> 1 | sql
> 2 | postgresql
> 3 | oracle
> 4 | linux
> 5 | sco
> 6 | linux
> 7 | windows
> 8 | glibc1
> 9 | glibc2
>
> structure:
> parent_id | child_id | depth
> -----------+----------+-------
> 1 | 1 | 0
> 2 | 2 | 0
> 3 | 3 | 0
> 4 | 4 | 0
> 5 | 5 | 0
> 6 | 6 | 0
> 7 | 7 | 0
> 8 | 8 | 0
> 9 | 9 | 0
> 1 | 2 | 1
> 1 | 3 | 1
> 1 | 4 | 2
> 2 | 4 | 1
> 1 | 5 | 1
> 1 | 6 | 1
> 1 | 7 | 1
> 3 | 5 | 2
> 3 | 6 | 2
> 3 | 7 | 2
> 1 | 8 | 3
> 1 | 9 | 3
> 3 | 8 | 2
> 3 | 9 | 2
> 6 | 8 | 1
> 6 | 9 | 1
>
> (records with depth 0 are technologically not necessary, but they
> simplify and speedup some queries).
>
> with this data layout (easily indexable) you can fetch any data with
> just one select statement (no recursion needed in any case):
> - fetching parent
> - fetching childs
> - fetching "from id up"
> - fetching "from id down"
> also when you need to get indirect parents/childs or when you need only
> some of the data (from me, up, but not more then to my
> grand-grand-grand-father).
>
> i'd like to get some comments on this - how do you see my idea, is it
> worth it, do you know any better way to store trees in sql?
>
> best regards
>
> depesz
>
>
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] 6+ messages in thread
* Re: tree structures in sql - my point of view (with request
@ 2002-09-03 21:59 mallah@trade-india.com
parent: Oleg Bartunov <oleg@sai.msu.su>
0 siblings, 1 reply; 6+ messages in thread
From: mallah@trade-india.com @ 2002-09-03 21:59 UTC (permalink / raw)
To: oleg@sai.msu.su; +Cc: depesz@depesz.pl; pgsql-sql
Yep! ltree is Faaaast , and i use it at the moment.
But will it work in INGRES,DB2 or ORACLE ?
what if tommorow my boss ask me to use ORACLE?
I have similar issues in using intarray & arrays in PGSQL
though reasons of shifting to others dbs are diminishing
with every major release of PG ;-)
regds
mallah.
> While I don't have a time to comment your message I want to point to contrib/ltree package
> which is extremely fast :-)
>
> http://www.sai.msu.su/~megera/postgres/gist/ltree
>
> Oleg
> On Tue, 3 Sep 2002, Hubert depesz Lubaczewski wrote:
>
>> hi
>> i recently spent some time on tree-structures in sql.
>> i started with simple id/parent_id approach, used by nearly everyone, then i stopped at joe
>> celko's nested sets, but i found it not very usable.
>> then i found my own (maybe someone wrote it before, but i haven't read it, so idea is mine)
>> way.
>> in my way we have two tables:
>> create table data (id serial, name text);
>> create table structure (parent_id int8, child_id int8, depth int8);
>>
>> structure table represents all paths in tree.
>> for example for this tree:
>>
>> sql
>> / \
>> postgresql oracle-----__
>> | / | \
>> linux sco linux windows
>> / \
>> glibc1 glibc2
>>
>> (sorry for used data - it is just template, and personally i don't like oracle).
>> so, for this tree we would populate the tables this way:
>> data:
>> id | name
>> ----+------------
>> 1 | sql
>> 2 | postgresql
>> 3 | oracle
>> 4 | linux
>> 5 | sco
>> 6 | linux
>> 7 | windows
>> 8 | glibc1
>> 9 | glibc2
>>
>> structure:
>> parent_id | child_id | depth
>> -----------+----------+-------
>> 1 | 1 | 0
>> 2 | 2 | 0
>> 3 | 3 | 0
>> 4 | 4 | 0
>> 5 | 5 | 0
>> 6 | 6 | 0
>> 7 | 7 | 0
>> 8 | 8 | 0
>> 9 | 9 | 0
>> 1 | 2 | 1
>> 1 | 3 | 1
>> 1 | 4 | 2
>> 2 | 4 | 1
>> 1 | 5 | 1
>> 1 | 6 | 1
>> 1 | 7 | 1
>> 3 | 5 | 2
>> 3 | 6 | 2
>> 3 | 7 | 2
>> 1 | 8 | 3
>> 1 | 9 | 3
>> 3 | 8 | 2
>> 3 | 9 | 2
>> 6 | 8 | 1
>> 6 | 9 | 1
>>
>> (records with depth 0 are technologically not necessary, but they simplify and speedup some
>> queries).
>>
>> with this data layout (easily indexable) you can fetch any data with just one select statement
>> (no recursion needed in any case):
>> - fetching parent
>> - fetching childs
>> - fetching "from id up"
>> - fetching "from id down"
>> also when you need to get indirect parents/childs or when you need only some of the data (from
>> me, up, but not more then to my
>> grand-grand-grand-father).
>>
>> i'd like to get some comments on this - how do you see my idea, is it worth it, do you know
>> any better way to store trees in sql?
>>
>> best regards
>>
>> depesz
>>
>>
>
> 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
>
>
> ---------------------------(end of broadcast)--------------------------- TIP 2: you can get off
> all lists at once with the unregister command
> (send "unregister YourEmailAddressHere" to majordomo@postgresql.org)
-----------------------------------------
Get your free web based email at trade-india.com.
"India's Leading B2B eMarketplace.!"
http://www.trade-india.com/
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: tree structures in sql - my point of view (with request
@ 2002-09-03 22:07 Bruce Momjian <pgman@candle.pha.pa.us>
parent: mallah@trade-india.com
0 siblings, 0 replies; 6+ messages in thread
From: Bruce Momjian @ 2002-09-03 22:07 UTC (permalink / raw)
To: mallah@trade-india.com; +Cc: oleg@sai.msu.su; depesz@depesz.pl; pgsql-sql
mallah@trade-india.com wrote:
>
> Yep! ltree is Faaaast , and i use it at the moment.
>
> But will it work in INGRES,DB2 or ORACLE ?
> what if tommorow my boss ask me to use ORACLE?
>
> I have similar issues in using intarray & arrays in PGSQL
>
> though reasons of shifting to others dbs are diminishing
> with every major release of PG ;-)
No it will only work on PostgreSQL. If those other apps had loadable
types, you might be able to do it by rewriting the code to match their
API.
--
Bruce Momjian | http://candle.pha.pa.us
pgman@candle.pha.pa.us | (610) 359-1001
+ If your life is a hard drive, | 13 Roberts Road
+ Christ can be your backup. | Newtown Square, Pennsylvania 19073
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: tree structures in sql - my point of view (with request of comment from joe celko)
@ 2002-09-04 17:46 knut.suebert@web.de
parent: Josh Berkus <josh@agliodbs.com>
0 siblings, 0 replies; 6+ messages in thread
From: knut.suebert@web.de @ 2002-09-04 17:46 UTC (permalink / raw)
To: pgsql-sql
Josh Berkus schrieb:
> Adjacency list trees are easier to understand conceptually, there are more
> tools on freshmeat.net for them, and they are the most efficient form of tree
> for graphical display.
Hi,
for graphical display it may be (the application to display could do the
work), but displaying data in tables (or tabulars, if you prefer
LaTeX-Syntax) leeds to recursion, I'd say.
> Nested Set trees are hard to wrap your mind around,
Yes ;-)
> lack a lot in the way of code samples on freshmeat, are harder to
> build GUI tools for, but are much, much faster for determining
> branch membership and branch parenthood.
While wrapping around my mind to understand Nested Sets, I got an idea
to speed up the count of subnodes and leaves (expensive if only "lft"
and "rgt" are used) by adding a third field called "lvl".
See
http://www.net-one.de/~ks/WOoK/postmaster.php
http://www.net-one.de/~ks/WOoK/nset.sql.txt
I wrote something about it here some months ago, got a few PMs with
positive reactions (so I'm writing this) and a correction. Due to time
lack, the 'documents' linked above are still draft, ugly written and
the examples may work or not, sorry.
The idea of "lvl" maybe useless or not? I'm not an expert.
> So which model you use depends on what you intend to do with the tree.
And try to understand Oleg's contrib/ltree. It may be better.
Greetings,
Knut Sübert
^ permalink raw reply [nested|flat] 6+ messages in thread
end of thread, other threads:[~2002-09-04 17:46 UTC | newest]
Thread overview: 6+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2002-09-03 13:22 tree structures in sql - my point of view (with request of comment from joe celko) Hubert depesz Lubaczewski <depesz@depesz.pl>
2002-09-03 18:17 ` Josh Berkus <josh@agliodbs.com>
2002-09-04 17:46 ` knut.suebert@web.de
2002-09-03 18:42 ` Re: tree structures in sql - my point of view (with request Oleg Bartunov <oleg@sai.msu.su>
2002-09-03 21:59 ` Re: tree structures in sql - my point of view (with request mallah@trade-india.com
2002-09-03 22:07 ` Re: tree structures in sql - my point of view (with request Bruce Momjian <pgman@candle.pha.pa.us>
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