From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery Zhimin Chen, H. V. Jagadish, Laks V. S. Lakshmanan, and Stelios Paparizos   View Paper (PDF)   Return to XML Query Processing II (Session A6) Abstract XQuery is the de facto standard XML query lan- guage, and it is important to have efficient query evaluation techniques available for it. A core op- eration in the evaluation of XQuery is the finding of matches for specified tree patterns, and there has been much work towards algorithms for find- ing such matches efficiently. Multiple XPath ex- pressions can be evaluated by computing one or more tree pattern matches. However, relatively little has been done on effi- cient evaluation of XQuery queries as a whole. In this paper, we argue that there is much more to XQuery evaluation than a tree pattern match. We propose a structure called generalized tree pat- tern (GTP) for concise representation of a whole XQuery expression. Evaluating the query reduces to finding matches for its GTP. Using this idea we develop efficient evaluation plans for XQuery expressions, possibly involving join, quantifiers, grouping, aggregation, and nesting. XML data often conforms to a schema. We show that using relevant constraints from the schema, one can optimize queries significantly, and give algorithms for automatically inferring GTP sim- plifications given a schema. Finally, we show, through a detailed set of experiments using the TIMBER XML database system, that plans via GTPs (with or without schema knowledge) sig- nificantly outperform plans based on navigation and straightforward plans obtained directly from the query. ©2004 Association for Computing Machinery