Re: contrib/tree - Mailing list pgsql-hackers

Peter Eisentraut wrote:

> Oleg Bartunov writes:
> 
> 
>>does your approach handle directed graphs ( DAG ) ?
>>Actually our module is just a result of our research for new
>>data type which could handle DAGs ( yahoo, dmoz -like hierarchies)
>>effectively in PostgreSQL.
>>While we didn't find a solution we decided to release this module
>>because 64 children would quite ok for many people.
>>Of course, 128 would be better :-)
>>
> 
> I was under the impression that the typical way to handle tree structures
> in relational databases was with recursive unions.  It's probably
> infinitely slower than stuffing everything into one datum, but it gets you
> all the flexibility that the DBMS has to offer.


As I explained to Oleg privately (I think it was privately, at least) a 
key-based approach doesn't work well for DAGs because in essence you 
need a set of keys, one for each path that can reach the node.  One of 
my websites tracks bird sightings for people in the Pacific NW and our 
geographical database is a DAG, not a tree (we have wildlife refuges 
that overlap states, counties etc).   In that system I use a 
parent-child table to track the relationships.

My impression is that there's no single "best way" to handle trees or 
graphs in an RDBMS that doesn't provide internal support (such as Oracle 
with its "CONNECT BY" extension).

The method we use in OpenACS works very well for us.  Insertion and 
selection are fast, and these are the common operations in *our* 
environment.  YMMV, of course.  Key-based approaches are fairly well 
known, at least none of us claim to have invented anything here.  The 
only novelty, if you will, is our taking advantage of the fact that PG's 
implementation of BIT VARYING just happens to work really well as a 
datatype for storing keys.  Full indexing support, substring, position, 
etc ... very slick.

Someone asked about using an integer array to store the hierarchical 
information.  I looked at that a few months back but it would require 
providing custom operators, so rejected it in favor of the approach 
we're now using.  It is important to us that users be able to fire up 
OpenACS 4 on a vanilla PG, such as the one installed by their Linux or 
BSD distribution.  That rules out special operators that require contrib 
code or the like.

We do use Oleg's full-text search stuff, but searching's optional and 
can be added in after the user's more comfortable with our toolkit, 
PostgreSQL, etc.  A lot of our users are new to Postgres, or at least 
have a lot more Oracle experience than PG experience.

But the integer array approach might well work for folks who don't mind 
the need to build in special operators.


-- 
Don Baccus
Portland, OR
http://donb.photo.net, http://birdnotes.net, http://openacs.org