Abstract
This work describes a method for processing XPath on a relational back-end that significantly limits the number of SQL joins required, takes advantage of the strengths of modern SQL query processors, exploits XML schema information and has low implementation complexity. The method is based on the splitting of XPath expressions into Primary Path Fragments (PPFs) and their subsequent combination using an efficient structural join method, and is applicable to all XPath axes. A detailed description of the method is followed by an experimental study that shows our technique yields significant efficiency improvements over other XPath processing techniques and systems.
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
Florescu, D., Kossmann, D.: Storing and Querying XML Data using an RDMBS. Data Engineering Bulletin 22(3) (1999)
Grust, T., Keulen, M.V., Teubner, J.: Accelerating XPath Evaluation in Any RDBMS. ACM Transactions on Database Systems 29(1) (2004)
Yoshikawa, M., Amagasa, T., Shimura, T., Uemura, S.: XRel: A Path-Based Approach to Storage and Retrieval of XML Documents Using Relational Databases. ACM Transactions on Internet Technology 1(1) (2001)
Amer Yahia, S., Du, F., Freire, J.: A Comprehensive Solution to the XML-to-Relational Mapping Problem. In: WIDM 2004, pp. 12–13 (2004)
Shanmugasundaram, J., Tufte, K., et al.: Relational Databases for Querying XML Documents: Limitations and Opportunities. In: Proc. of the 25th VLDB Conf. (1999)
Clark, J., DeRose, S.: XML Path Language (XPath) Version 1.0. W3C Recommendation 16 November (1999), http://www.w3.org/TR/xpath
Boag, S., Chamberlin, D., et al.: Query 1.0: An XML Query Language. W3C Working Draft 04 April (2005), http://www.w3.org/TR/xquery/
DeHaan, D., Toman, D., Consens, M.P., Ozsu, M.T.: A Comprehensive XQuery to SQL Translation using Dynamic Interval Encoding. SIGMOD (2003)
Tatarinov, I., Viglas, S., Beyer, K., Shanmugasundaram, J., Shekita, E., Zhang, C.: Storing and querying ordered XML using a relational database system. In: SIGMOD (2002)
Virmani, A., Agarwal, S., Thathoo, R., Suman, S., Sanyal, S.: A Fast XPATH Evaluation Technique with the Facility of Updates. In: CIKM 2003 ACM (2003)
Krishnamurthy, R., Kaushik, R., Naughton, J.F.: Efficient XML-to-SQL Query Translation: Where to Add the Intelligence? In: Proc. of the 30th VLDB Conf. (2004)
Krishnamurthy, R., Chakaravarthy, V.T., Kaushik, R., Naughton, J.F.: Recursive XML Schemas, Recursive XML Queries, and Relational Storage: XML-to-SQL Query Translation. In: Proc. of the 20th ICDE (2004)
Berglund, A., Boag, S., et al.: XML Path Language (XPath) 2.0. W3C Working Draft (2005), http://www.w3.org/TR/xpath20/
Sur, G.M., Hammer, J., Siméon, J.: UpdateX - An XQuery-Based Language for Processing Updates in XML. PLAN-X 2004. In: Proc., BRICS Notes Series NS-03-4 (2004)
Deschler, K., Rundensteiner, E.: MASS: A Multi-Axis Storage Structure for Large XML Documents. In: CIKM 2003 (2003)
Pal, S., Cseri, I., Seeliger, O., Schaller, G., Giakoumakis, L., Zolotov, V.: Indexing XML Data Stored in a Relational Database. In: Proc. of the 30th VLDB Conference (2004)
IEEE Std 1003.1, Open Group Technical Standard
Boncz, P., Grust, T., Keulen, M., et al.: PathFinder/MonetDB: XQuery-The Relational Way. In: Proc. of the 31st VLDB Conference (2005)
O’Neil, P., O’Neil1, E., Pal, S., Cseri, I., Schalle, G., Westbury, N.: ORDPATHs: Insert-Friendly XML Node Labels. In: SIGMOD (2004)
Schmidt, A., Waas, F., Kersten, M., et al.: XMark: A Benchmark for XML Data Management. In: Proc. of the 28th VLDB Conference (2002)
Franceschet, M.: an XPath benchmark for the XMark generated data. In: XSym 2005, pp. 129–143 (2005)
Florescu, D., et al.: The BEA streaming XQuery processor. VLDB Journal 13(3) (2004)
Papakonstantinou, Y., Vassalos, V.: Architecture and Implementation of an XQuery-based Information Integration Platform. IEEE Data Eng. Bull. 25(1), 18–26 (2002)
Schöning, H., Wäsch, J.: Tamino - an internet database system. In: Zaniolo, C., Grust, T., Scholl, M.H., Lockemann, P.C. (eds.) EDBT 2000. LNCS, vol. 1777, p. 383. Springer, Heidelberg (2000)
Schema, X.M.L.: http://www.w3.org/XML/Schema
Balmin, A., Papakonstantinou, Y.: Storing and querying XML data using denormalized relational databases. Springer, Heidelberg (2004)
Amer-Yahia, S., Kotidis, Y., Srivastava, D.: Teaching Relational Optimizers About XML Processing. In: XSym (2004)
Bruno, N., Koudas, N., Srivastava, D.: Holistic twig joins: optimal XML pattern matching. In: SIGMOD Conference (2002)
Fiebig, T., Helmer, S., et al.: Anatomy of a native XML base management system. VLDB J. 11(4), 292–314 (2002)
Paparizos, S., Al-Khalifa, S., et al.: TIMBER: A Native System for Querying XML. In: SIGMOD Conference (2003)
Abiteboul, S., Cluet, S., Milo, T.: Querying and Updating the File. In: Proc. VLDB Conf. (1993)
Georgiadis, H., Vassalos, V.: Improving the Efficiency of XPath Execution on Relational Systems, Extended version, Available from http://wim.aueb.gr/papers/PPFProcessingfull.pdf
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Georgiadis, H., Vassalos, V. (2006). Improving the Efficiency of XPath Execution on Relational Systems. In: Ioannidis, Y., et al. Advances in Database Technology - EDBT 2006. EDBT 2006. Lecture Notes in Computer Science, vol 3896. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11687238_35
Download citation
DOI: https://doi.org/10.1007/11687238_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32960-2
Online ISBN: 978-3-540-32961-9
eBook Packages: Computer ScienceComputer Science (R0)