Women in Technology

Hear us Roar



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.