Order-Aware Twigs: Adding Order Semantics to Twigs

Abstract

Although  many algorithms have been proposed for evaluating   XPath queries containing child and descendantaxes and predicates XPATH (/,//,[ ]) against XML data,  there are very few efforts towards eveloping algorithms for processing path expressions with other axes namely, following, preceding, following-sibling and preceding-sibling. In this paper, we demonstrate that the conventional twig-structure, which is used to represent  expressions in the subset XPATH (/,//,[ ]) has no order information built into it and hence fails to model XPath expressions with ordered axes. This motivates   us to introduce a new type of twig-structure, which we call Order-aware Twig, to effectively represent XPath expressions with ordered axes.