Search

With the widespread use of Web technologies and the growing number of applications adopting XML as the standard language for representing and exchanging structured data and documents on the Internet, XML query processing becomes important as well as XML data management. In this paper, we propose a new novel XML path query evaluating approach, called Automata Match (AM). In our AM algorithm, all XML path expression queries are first converted into query automata as finite state automata. If the path schema of path instances in the XML data tree is accepted by the query automata, the corresponding path instances will be included in the result set. Our AM algorithm supports all basic operators used in regular path expressions (RPE) such as "*", "+", "?" and "$|$". In addition, we also support both predicate filtering and "//" (for containment joins). It is worth noting that "//" is not an operator in regular path expressions. In order to support "//", schema automata are proposed in this paper with two optimization strategies. We describe the implementation details of our approach, and conducted extensive performance studies using XML benchmarks. The AM approach outperforms existing approaches even for containment joins. We will report our findings in this paper. [ABSTRACT FROM AUTHOR]