Abstract
XML data usually consists of tree-structured hierarchical data, which affects the storing and searching mechanisms for XML. When storing XML data into databases the hierarchical relationships among XML nodes need to be considered. User’s search queries that specify hierarchical relationships among the nodes also require appropriate processing mechanisms. Structural join operations provide a solution to this problem by efficiently computing hierarchical relationships in XML databases based on the node numbering storage scheme. However, in order to process a branch query containing several hierarchical relationships on XML data, many structural joins need to be sequentially carried out and result in a high query execution cost. This paper proposes mechanisms to reduce the cost of processing branch pattern XML queries requiring multiple structural joins. We discuss two approaches for rewriting a query composed of a single branch, and then apply these approaches to general branch queries. The first approach uses the concept of equivalence class relationships among regular path expression queries. The second approach uses a bottom-up approach to reduce the overhead identified in the first scheme. Experimental results show that the proposed schemes can reduce the query execution cost by up to an order of magnitude of the original execution cost.
This work was supported by the faculty research fund of Konkuk University in 2005.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Chien, S.-Y., Vagena, Z., Zhang, D., Tsotras, V.J., Zaniolo, C.: Efficient structural joins on indexed XML documents. In: Proc. of the 28th VLDB conference, Hong Kong, China, August 2002, pp. 263–274 (2002)
Christophides, V., Cluet, S., Moerkotte, G.: Evaluating queries with generalized path expressions. In: Proc. of the 1996 ACM-SIGMOD conference, Montreal, Canada, June 1996, pp. 413–422 (1996)
Cooper, B., Sample, N., Franklin, M.J., Hjaltason, G.R., Shadmon, M.: A fast index for semistructured data. In: Proc. of the 27th VLDB conference, Rome, Italy, September 2001, pp. 341–350 (2001)
Goldman, R., Widom, J.: Dataguides: Enabling query formulation and optimization in semistructured databases. In: Proc. of the 23rd VLDB conference, Athens, Greece, August 1997, pp. 436–445 (1997)
Li, Q., Moon, B.: Indexing and querying XML data for regular path expressions. In: Proc. of the 27th VLDB conference, Rome, Italy (September 2001)
Schmidt, A., Waas, F., Kersten, M.L., Carey, M.J., Manolescu, I., Busse, R.: XMark: A Benchmark for XML Data Management. In: Proc. of the 28th VLDB conference, Hong Kong, China, August 2002, pp. 974–985 (2002)
Srivastava, D., Al-Khalifa, S., Jagadish, H.V., Koudas, N., Patel, J.M., Wu, Y.: Structural joins: A primitive for efficient XML query pattern matching. In: Proc. of the 2002 IEEE conference on Data Engineering (February 2002)
Zhang, C., Naughton, J.F., Luo, Q., DeWitt, D.J., Lohman, G.M.: On supporting containment queries in relational database management systems. In: Proc. of the 2001 ACM-SIGMOD conference (May 2001)
Fernandez, M., Suciu, D.: Optimizing regular path expressions using graph schemas. In: Proc. of the 1998 IEEE Conference on Data Engineering, Orlando, Florida, February 1998, pp. 4–13 (1998)
Sleepycat Software Inc., http://www.sleepycat.com
Jiang, H., Lu, H., Wang, W., Ooi, B.C.: XR-Tree: Indexing XML Data for Efficient Structural Joins. In: Proc. of the 2003 IEEE conference on Data Engineering, Bangalore, India, March 2003, pp. 253–263 (2003)
Li, H., Lee, M., Hsu, W., Chen, C.: An Evaluation of XML Indexes for Structural Join. SIGMOD Record 33(3), 28–33 (2004)
Wu, Y., Patel, J.M., Jagadish, H.V.: Structural Join Order Selection for XML Query Optimization. In: Proc. of the 2003 IEEE conference on Data Engineering, Bangalore, India, March 2003, pp. 443–454 (2003)
Chung, C.-W., Min, J.-K., Shim, K.: APEX: an adaptive path index for XML data. In: Proc. of the 2002 ACM-SIGMOD conference, Madison, Wisconsin, USA, June 2002, pp. 121–132 (2002)
Tatarinov, I., Viglas, S.D., Beyer, K., Shanmugasundaram, J., Shekita, E., Zhang, C.: Storing and querying ordered XML using a relational database system. In: Proc. of the 2002 ACM-SIGMOD conference (June 2002)
Bruno, N., Koudas, N., Srivastava, D.: Holistic twig joins: optimal XML pattern matching. In: Proc. of the 2002 ACM-SIGMOD conference, Madison, Wisconsin, USA, June 2002, pp. 311–321 (2002)
Jiang, H., Wang, W., Lu, H., Yu, J.X.: Holistic Twig Joins on Indexed XML Documents. In: Proc. of the 29th VLDB conference, Berlin, Germany, September 2003, pp. 273–284 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Shin, H., Lee, M. (2005). An Efficient Branch Query Rewriting Algorithm for XML Query Optimization. In: Meersman, R., Tari, Z. (eds) On the Move to Meaningful Internet Systems 2005: CoopIS, DOA, and ODBASE. OTM 2005. Lecture Notes in Computer Science, vol 3761. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11575801_45
Download citation
DOI: https://doi.org/10.1007/11575801_45
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29738-3
Online ISBN: 978-3-540-32120-0
eBook Packages: Computer ScienceComputer Science (R0)