Abstract
We present an evaluator for navigational XPath on Xml streams with projection. The idea is to project away those parts of an Xml stream that are irrelevant for evaluating a given XPath query. This task is relevant for processing Xml streams in general since all Xml standard languages are based on XPath. The best existing streaming algorithm for navigational XPath queries runs nested word automata. Therefore, we develop a projection algorithm for nested word automata, for the first time to the best of our knowledge. It turns out that projection can speed up the evaluation of navigational XPath queries on Xml streams by a factor of 4 in average on the usual XPath benchmarks.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Alu, R., Madhusudan, P.: Adding nesting structure to words. J. ACM 56(3), 1–43 (2009)
Debarbieux, D., Gauwin, O., Niehren, J., Sebastian, T., Zergaoui, M.: Early nested word automata for XPath query answering on XML streams. TCS 578, 100–125 (2015)
Debarbieux, D., Sebastian, T., Zergaoui, M., Niehren, J.: Quix-tool suite (2014). https://project.inria.fr/quix-tool-suite/
Franceschet, M.: XPathMark: an XPath benchmark for the XMark generated data. In: Bressan, S., Ceri, S., Hunt, E., Ives, Z.G., Bellahsène, Z., Rys, M., Unland, R. (eds.) XSym 2005. LNCS, vol. 3671, pp. 129–143. Springer, Heidelberg (2005)
Frisch, A.: Regular tree language recognition with static information. In: Levy, J.-J., Mayr, E.W., Mitchell, J.C. (eds.) TCS2004. IFIP, vol. 155, pp. 661–674. Springer, Heidelberg (2004)
Gauwin, O., Niehren, J.: Streamable fragments of forward XPath. In: Bouchou-Markhoff, B., Caron, P., Champarnaud, J.-M., Maurel, D. (eds.) CIAA 2011. LNCS, vol. 6807, pp. 3–15. Springer, Heidelberg (2011)
Kay, M.: The saxon XSLT and XQuery processor. https://www.saxonica.com
Labath, P., Niehren, J.: A uniform programmning language for implementing XML standards. In: Italiano, G.F., Margaria-Steffen, T., Pokorný, J., Quisquater, J.-J., Wattenhofer, R. (eds.) SOFSEM 2015-Testing. LNCS, vol. 8939, pp. 543–554. Springer, Heidelberg (2015)
Madhusudan, P., Viswanathan, M.: Query automata for nested words. In: Královič, R., Niwiński, D. (eds.) MFCS 2009. LNCS, vol. 5734, pp. 561–573. Springer, Heidelberg (2009)
Maneth, S., Nguyen, K.: XPath whole query optimization. VLPB J. 3(1), 882–893 (2010)
Marian, A., Simeon, J.: Projecting XML documents. In: VLDB, pp. 213–224 (2003)
Mozafari, B., Zeng, K., Zaniolo, C.: High-performance complex event processing over XML streams. In: SIGMOD Conference, pp. 253–264. ACM (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sebastian, T., Niehren, J. (2016). Projection for Nested Word Automata Speeds up XPath Evaluation on XML Streams. In: Freivalds, R., Engels, G., Catania, B. (eds) SOFSEM 2016: Theory and Practice of Computer Science. SOFSEM 2016. Lecture Notes in Computer Science(), vol 9587. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-49192-8_49
Download citation
DOI: https://doi.org/10.1007/978-3-662-49192-8_49
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-49191-1
Online ISBN: 978-3-662-49192-8
eBook Packages: Computer ScienceComputer Science (R0)