pg.ddx.io  pgsql-sql@postgresql.org mailing list archive  

help / color / mirror / Atom feed
From: Daniel Browning <db@kavod.com>
To: pgsql-sql@postgresql.org
Subject: Modeling trees with Nested Sets and Nested Intervals
Date: Fri, 7 Apr 2006 00:28:15 -0700
Message-ID: <200604070028.15476.db@kavod.com> (raw)

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>



view thread (2+ messages)  latest in thread

Message-ID: <200604070028.15476.db@kavod.com>
Permalink:  ../200604070028.15476.db@kavod.com/
Also on:    postgresql.org/message-id/200604070028.15476.db@kavod.com

 · 

reply
Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: pgsql-sql@postgresql.org
  Cc: db@kavod.com
  Subject: Re: Modeling trees with Nested Sets and Nested Intervals
  In-Reply-To: <200604070028.15476.db@kavod.com>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

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