Modeling trees with Nested Sets and Nested Intervals

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(dot)TAA11670(at)wall(dot)org>

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