S3: Evaluation of tree-pattern XML queries supported by structural summaries

XML queries are frequently based on path expressions where their elements are connected to each other in a tree-pattern structure, called query tree pattern (QTP). Therefore, a key operation in XML query processing is finding those elements which match the given QTP. In this paper, we propose a novel method, called S3, which can selectively process the document’s nodes. In S3, unlike all previous methods, path expressions are not directly executed on the XML document, but first they are evaluated against a guidance structure, called QueryGuide. Enriched by information extracted from the QueryGuide, a query execution plan, called SMP, is generated to provide focused pattern matching and avoid document access as far as possible. Moreover, our experimental results confirm that S3 and its optimized version OS3 substantially outperform previous QTP processing methods w.r.t. response time, I/O overhead, and memory consumption – critical parameters in any real multi-user environment.