Indexing Schemes for Efficient Aggregate Computation over Structural Joins Priya Mandawat and Vassilis J. Tsotras   View Paper (PDF)   Return to Paper Session 3: XML Abstract With the increasing popularity of XML as a standard for data representation and exchange, efficient XML query processing has become a necessity. One popular approach encodes the hierarchical structure of XML data through a node numbering scheme, thus reducing typical queries to special forms (structural, path, twig) of containment joins. In this paper we consider how using an index can facilitate the computation of (exact) aggregates over structural joins. Consider for example, counting how many times item nodes appear under store nodes in a chain-store database. One straightforward solution would be to actually compute the result of the structural join (store//item) and count all such occurrences. However, this requires time proportional to the join computation (which with appropriate buffering is O(n) where n is the total number of store and item elements in the database). Instead, we propose the Aggregation B-tree (aB-tree), a balanced index specifically designed for computing aggregate queries such as count, sum, min, max, average. The efficiency of this structure arises from the manner in which it maintains pre-computed partially aggregated results. The overall aggregate is then computed following specific paths of the tree and accumulating partial values, resulting in an overall O(log n) time complexity. Since the aB-tree is an index built on the sorted element lists, it can also be used to perform efficient structural joins by skipping elements that do not participate in the join. ©2006 Association for Computing Machinery