pg.ddx.io pgsql-sql@postgresql.org mailing list archive
help / color / mirror / Atom feedModeling trees with Nested Sets and Nested Intervals
2+ messages / 2 participants
[nested] [flat]
* Modeling trees with Nested Sets and Nested Intervals
@ 2006-04-07 07:28 Daniel Browning <db@kavod.com>
2006-04-10 01:14 ` Re: Modeling trees with Nested Sets and Nested Intervals Michael Glaesemann <grzm@myrealbox.com>
0 siblings, 1 reply; 2+ messages in thread
From: Daniel Browning @ 2006-04-07 07:28 UTC (permalink / raw)
To: pgsql-sql
I would like to model some hierarchical (tree) data in PostgreSQL. Where can
I find high quality Nested Set (or Nested Interval) source code and
documentation?
I know this question gets asked a lot. To illustrate the point, here is just
one thread from each of the last five years:
http://archives.postgresql.org/pgsql-sql/2001-08/msg00242.php
http://archives.postgresql.org/pgsql-sql/2002-05/msg00270.php
http://archives.postgresql.org/pgsql-general/2003-12/msg00247.php
http://archives.postgresql.org/pgsql-general/2004-03/msg00804.php
http://archives.postgresql.org/pgsql-sql/2005-04/msg00231.php
Luckily, no one has asked this question yet in 2006. :-)
I've been scouring the Net for a while now, but I hope there are more
resources out there that I haven't stumbled onto yet. Here's what I've found
so far:
* Static Hierarchies and Binary Fractions in PostgreSQL, by Michael Glaesemann
http://www.grzm.com/fornow/archives/2004/07/10/static_hierarchies
This is the most complete out-of-the-box solution I've found. It uses binary
fractions and nested intervals (well, Manfred Koizar says its more of a
Materialized Path model). Lots of handholding, documentation, and functions
for everything you would want to do to a tree. Limited to 61 nodes in the
first branch, plus other limitations.
* Modified "m-vgID method", by OpenACS
http://cvs.openacs.org/cvs/openacs-4/packages/acs-kernel/sql/postgresql/
Reported to support 2^31 nodes per level, uses bitstring encoding.
* m-vgID method, by Miguel Sofer
http://www.utdt.edu/~mig/sql-trees/
Uses base 159 encoding (all latin1 chars).
* Joe Celko's SQL for Smarties: Advanced SQL Programming, 2nd Edition
Highly recommended book. Joe also has a few articles and mailing list posts
floating around the web:
http://www.dbmsmag.com/9603d06.html
http://archives.postgresql.org/pgsql-sql/2001-11/msg00004.php
http://archives.postgresql.org/pgsql-sql/2003-01/msg00459.php
To be clear, I'm not looking for an adjacency model, materialized path model,
contrib/ltree, or connect by. Other resources that have been helpful:
http://troels.arvin.dk/db/rdbms/links/#hierarchical
http://groups.google.com/group/comp.databases.theory/msg/7b772060322df739
Maybe all this would make a good project on pgfoundry.
--
Daniel Browning - Kavod Technologies. Random Fortune:
To Perl, or not to Perl, that is the kvetching.
-- Larry Wall in <199801200310.TAA11670@wall.org>
^ permalink raw reply [nested|flat] 2+ messages in thread
* Re: Modeling trees with Nested Sets and Nested Intervals
2006-04-07 07:28 Modeling trees with Nested Sets and Nested Intervals Daniel Browning <db@kavod.com>
@ 2006-04-10 01:14 ` Michael Glaesemann <grzm@myrealbox.com>
0 siblings, 0 replies; 2+ messages in thread
From: Michael Glaesemann @ 2006-04-10 01:14 UTC (permalink / raw)
To: Daniel Browning <db@kavod.com>; +Cc: pgsql-sql
On Apr 7, 2006, at 16:28 , Daniel Browning wrote:
> * Static Hierarchies and Binary Fractions in PostgreSQL, by Michael
> Glaesemann
> http://www.grzm.com/fornow/archives/2004/07/10/static_hierarchies
>
> This is the most complete out-of-the-box solution I've found.
I wrote up Tropashko's method because I had found enough material on
the nested set method on the web to apply it to PostgreSQL (which
works quite well once you get it set up) and was interested in seeing
what else was out there. Though, as you note, there's no ready-to-go
nested set solution specifically for PostgreSQL. You may also want to
take a look at contib/ltree in the PostgreSQL sources for handling
hierarchical data. I haven't used it myself, but many others smarter
than me have reported satisfaction with it.
If you start implementing the nested set method and have some
questions, feel free to post them here. I'm sure someone will be able
to answer them.
Good luck!
Michael Glaesemann
grzm myrealbox com
^ permalink raw reply [nested|flat] 2+ messages in thread
end of thread, other threads:[~2006-04-10 01:14 UTC | newest]
Thread overview: 2+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2006-04-07 07:28 Modeling trees with Nested Sets and Nested Intervals Daniel Browning <db@kavod.com>
2006-04-10 01:14 ` Michael Glaesemann <grzm@myrealbox.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