The Space Complexity of Processing XML Twig Queries Over Indexed Documents

Current twig join algorithms incur high memory costs on queries that involve child-axis nodes. This paper provides an analytical explanation for this phenomenon. In a first large-scale study of the space complexity of evaluating XPath queries over indexed XML documents the authors show the space to depend on three factors: whether the query is a path or a tree; the types of axes occurring in the query and their occurrence pattern; and the mode of query evaluation filtering, full-fledged, or "Pattern Matching". The lower bounds imply that evaluation of a large class of queries that have child-axis nodes indeed requires large space.