ONJava.com -- The Independent Source for Enterprise Java
oreilly.comSafari Books Online.Conferences.

advertisement

AddThis Social Bookmark Button
Article:
  Hierarchical SQL
Subject:   tangentially related....
Date:   2004-08-09 04:09:42
From:   bazzargh
I came across an interesting paper the other day describing indexing techniques to accelerate XPaths on relational DBs...


http://www.inf.uni-konstanz.de/~grust/files/xpath-accel.pdf


...they assign a 2d coordinate to a node from its order in a depth-first traversal of the tree (the node count on the way in, and the node count on the way out). In these coordinates, the usual XPath partition of the tree into preceding, following, ancestor, descendant axes becomes the 4 quadrants around a node on the graph. This is obviously ideal for db's with spatial indexes.


In their usage, there were no updates (the obvious problem with this algorithm) so its not a panacea for update, aggregation performance. I guess that's true for all tree structures on RDBMS, you have to choose the one that suits your usage scenarios. A nice idea nonetheless.