Thread: 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.TAA11670@wall.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