Forum OpenACS Q&A: Interesting article on hierarchical queries

If you're into such things, a very geeky treatment of tree queries on DBAZine.
Posted by Don Baccus on
We use adjacency lists in both Oracle and PG where we need to test against all ancestors of an object but don't care about preserving the hierarchical structure in our resultset.

An example is the table that maps objects to their context parents.  We only need to see if a given permission exists for at least one context parent, so we join children and parents using the map using "exists".  This is extremely fast and we don't care that the query doesn't return any information about the hierarchy itself.

To model trees in PostgreSQL, which has no hierarchical query support, we use materialized paths and numerated siblings.  We also use the recursive trick for recovering ancestors mentioned in the article.

Our first implementation used varchars and the concatenate operator much as their example does. But most operations are not indexable using varchar as the data type which olds the hierarchical key.

Therefore I rewrote our implementation using PG's "bit varying" type.  All operations are now fully indexed.

Likewise OF used Oracle's RAW type in the forums package to implement hierarchical keys.  To be honest I'm not sure this is better than CONNECT BY, though CONNECT BY has its issues, to be sure.  It would be interesting to compare the two approaches empirically.  I know that insertion of rows using  hierarchical keys represented as materialized paths is more expensive than just inserting data with no hierarchical key (because you may have to recalculate keys for much of the tree when you insert a row in the middle of it).  On the other hand you can find all the ancestors without touching the database, which isn't true of the CONNECT BY approach, and unlike CONNECT BY you can freely join against thet tree and maintain sort order.

Posted by Andrew Piskorski on
Btw, the OpenACS tree query discussions starting Oct. 11, Oct. 20, and Nov. 8 2000 seem to cover a lot of ground similar to the dbazine article.