Efficiently processing XML path queries using automata

In XML query processing, path expressions applied in most XML query languages have a powerful ability in locating and querying XML data as well as structural relationships. Due to the semi-structured feature of XML data, the query processing techniques of XML path expression query has new characteristics and challenges compared to traditional database query processing techniques. So far, some techniques have been proposed for processing path queries. However, when they are applied to large scale of XML documents and complicated path expressions, their performance degrade dramatically. This paper proposes a high efficient XML path expression query processing method-SAM based on the automata technique. Its basic idea is transforming a path expression query to an equivalent automata and matching the automata with the schema paths abstracting from the XML document. This paper also presents an approach to computing the '//' operation based on the SAM method. The experimental results show that SAM is an efficient and practical method for computing complicated path expression queries on large scale XML documents.