We've also been talking to the RHDB team about CONNECT BY (we're encouraging them to implement something like DB2's recursive queries, but the end result is that we're hoping that by 7.3 PG will have a solution for tree queries)
The tree sortkey approach we've taken is a lot more flexible than Oracle's CONNECT BY and appears to be roughly comparable in performance. There is a cost in storage, but our BIT VARYING implementation is quite economical.
In fact Open Force likes this approach so much that they've begun using it rather than CONNECT BY in Oracle, using the RAW datatype to hold the hierarchical keys.
While I don't forsee us abandoning CONNECT BY queries in the near future due to the large number of queries involved and the tediousness of generating upgrade scripts, if we were to do so we could get rid of parent ids altogether and just use the tree sortkeys to generate parents (one nice thing is that you can generate the full set of parent keys rather than just the immediate parent without selecting against any db table).
If I were designing from scratch, I'm about 90% convinced that I'd use the tree sortkey approach in both PG and Oracle.
PG 7.3 will be in beta in five days so I doubt CONNECT BY will be implemented. There is a contrib extension that implements tree operators which was developed after we did our tree sortkey implementation, but frankly I don't see that it gives us anything that we don't already have in our implementation using the standard PG BIT VARYING type.
