Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20]

@

Journal of Information Science and Engineering, Vol. 23 No. 5, pp. 1523-1540 (September 2007)

A Path-based Approach for Efficient Evaluation of Twig Queries over XML Data*

Ya-Hui Chang, Cheng-Ta Lee and Wang-Chien Lee+
Department of Computer Science
National Taiwan Ocean University
Keelung, 202 Taiwan
E-mail: yahui@ntou.edu.tw
+Department of Computer Science and Engineering
Penn State University
University Park, PA 16802, U.S.A.
E-mail: wlee@cse.psu.edu

Efficient XML query processing has been a critical issue for these days. In this paper, a path-based approach is proposed to process XML queries which can be represented as a query tree with twig patterns. We summarize and encode all the possible paths in the XML data in advance, so that we could efficiently determine where the physical paths, which satisfy the constraint of individual path expressions in the input query, need to be glued to form the final correct match. We have conducted a series of experiments to evaluate the performance of the proposed system. The results show that our approach has a great advantage over the state-of-the-art element-based or hybrid approach.

Keywords: XML, query processing, twig query, encoding, indexing method

Full Text () Retrieve PDF document (200709_14.pdf)

Received July 11, 2005; revised November 15, 2005 & February 10, 2006; accepted March 20, 2006.
Communicated by Suh-Yin Lee.
*This work was partially supported by the National Science Council of Taiwan, R.O.C., under contract No. NSC 92-2213-E-019-010-