Efficient XPath Evaluation Using a Structural Summary Index
Xiaojie Yuan, Xin Wang, Chenying Wang · 2008
XPath has been widely used as a query language for selecting nodes from XML documents. Efficient XPath evaluation is thus a core building block in XML query processors. In the paper, we first introduce a compact structural summary index for XML data and then propose an efficient XPath evaluation algorithm based on this index. Our algorithm takes full advantage of the structural summary to prune a large unnecessary search space. By combining consecutive parent-child steps into a single path fragment, we show how the number of required index lookups and join operations can be significantly reduced. More importantly, our algorithm can process a large class of twig patterns consisting of both parent-child and ancestor-descendant relationships. Finally, we report experimental results on a range of data and queries.