On the role of composition in XQuery Christoph Koch   View Paper (PDF)   Return to Paper Session 3: XML Abstract Nonrecursive XQuery is known to be hard for nondeterministic exponential time. Thus it is commonly believed that any algorithm for evaluating XQuery has to require exponential amounts of working memory and doubly exponential time in the worst case. In this paper we present a property - the lack of a certain form of composition - that virtually all real-world XQueries have and that allows for query evaluation in singly exponential time and polynomial space. Still, we are able to show for an important special case - our nonrecursive XQuery fragment restricted to atomic value equality - that the composition-free language is just as expressive as the language with composition. Thus, under widely-held complexity-theoretic assumptions, the composition-free language is an exponentially less succinct version of the language with composition. ©2006 Association for Computing Machinery