Re: contrib/tree - Mailing list pgsql-hackers

dhogaza@pacifier.com (Don Baccus) writes:
> Peter Eisentraut wrote:
> > 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.

... Where parent/child has the unfortunate demerit that walking the
tree requires (more-or-less; it could get _marginally_ hidden in a
stored procedure) a DB query for each node that gets explored.

> 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.

Have you a URL for this?  (A link to a relevant source code file would
be acceptable...)

> 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.

Are you referring to the "nested tree" model (particularly promoted by
Joe Celko; I don't know of a seminal source behind him)?  It
unfortunately doesn't work with graphs...
-- 
(concatenate 'string "cbbrowne" "@ntlug.org")
http://www3.sympatico.ca/cbbrowne/nonrdbms.html
"Did you  ever walk in a  room and forget  why you walked in?  I think
that's how dogs spend their lives." -- Sue Murphy