Re: contrib/tree

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