Twig Pattern Matching With Positional Predicates In XML Queries

Nowadays, eXtensible Markup Language (XML) has been the factual standard ofdata describing and exchanging. It is widely used in heterogeneous platforms and dataexchange/share for heterogeneous information. For meeting the need of quering andprocessing the XML data, W3C developed XQuery, and released it as a standard que-ry language for XML data. The relationship between XQuery and XML is just as therelationship between SQL and relational database. Combined with the semi-structuredcharacteristic of XML data, XQuery can find all document fragments by XPath ex-pression that satisfy the query or do some scientific calculations according the data.In the processing of XML data, the queries that focus on the branch structure ofXML data are the most basic and common execution unit and one of the most expen-sive operations in XQuery programs. The queries containing ancestor-descendant re-lationship (AD) and parent-child (PC) relationship can be represented as a tree-likequery pattern. How to find the fragments accurately and effectively has been the hotspot in database community.Although holistic twig pattern matching algorithms have been studied inten-sively nowadays, little attention is paid on positional predicates defined on navigationaxis in XPath expressions. Since query results fail to be selected from the holistic pat-tern matching results, those algorithms cannot be used to implement XPath querieswith positional predicates. For implementation of XPath query with the positionalpredicates, in this paper, we extend the traditional twig pattern to a new one calledExTwig to deal with both positional predicates and following-sibling axis. We alsopropose the corresponding holistic twig pattern matching algorithm TwigPos to pro-cess XPath query with label test predicates, positional predicates and follow-ing-sibling axis. Comparison experiments on large benchmarks show that our algo-rithm is efficient and practical.