QuickXScan: Efficient Streaming XPath Evaluation.
Guogen Zhang, Qinghua Zou · 2006
Abstract- Many XML applications over the Internet favor high-performance single-pass streaming XPath evaluation. Finite automata-based algorithms suffer from potentially combinatorial explosion of dynamic states for matching descendant axes. We present QuickXScan for streaming evaluation of XPath queries containing child and descendant axes with complex predicates. Using a tree representation for an XPath query, it employs a matching grid, a compact tree of interrelated stacks as in the holistic twig join algorithms, to represent the matches and their relationships. QuickXScan fully utilizes transitivity for matching, thus reduces the number of active states to the query size in the worst case. It also evaluates expressions incrementally using propagation and iterative rules, and produces result sequences without the need for duplicate removal. QuickXScan is practical and highly efficient.