Abstract
XPath is a simple language for navigating an XML tree and returning a set of answer nodes. The focus in this paper is on the complexity of the containment problem for various fragments of XPath. In addition to the basic operations (child, descendant, filter, and wildcard), we consider disjunction, DTDs and variables. W.r.t. variables we study two semantics: (1) the value of variables is given by an outer context; (2) the value of variables is defined existentially.We establish an almost complete classification of the complexity of the containment problem w.r.t. these fragments.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Benedikt, W. Fan, and G. M. Kuper. Structural properties of XPath fragments. ICDT 2003, this volume.
G. J. Bex, S. Maneth, and F. Neven. A formal model for an expressive fragment of XSLT. Information Systems, 27(1):21–39, 2002.
D. Chamberlin, J. Clark, D. Florescu, J. Robie, J. Simeon, and M. Stefanascu. XQuery 1.0: An XML query language. http://www.w3.org/TR/xquery/, 2002.
B. S. Chlebus. Domino-tiling games. Journal of Computer and System Sciences, 32(3):374–392, 1986.
J. Clark. XML Path Language (XPath). http://www.w3.org/TR/xpath.
James Clark. XSL transformations version 1.0. http://www.w3.org/TR/WD-xslt, August 1999.
S. DeRose, E. Maler, and R. Daniel. XML pointer language (XPointer) version 1.0. http://www.w3.org/TR/xptr/, 2001.
S. DeRose, E. Maler, and D. Orchard. XML linking language (XLink) version 1.0. http://www.w3.org/TR/xlink/, 2001.
A. Deutsch and V. Tannen. Containment and integrity constraints for xpath. In Maurizio Lenzerini, Daniele Nardi, Werner Nutt, and Dan Suciu, editors, Proceedings of the 8th International Workshop on Knowledge Representation meets Databases (KRDB 2001), number 45 in CEUR Workshop Proceedings, 2001.
G. Gottlob and C. Koch. Monadic queries over tree-structured data. In Proc. 17th IEEE Symposium on Logic in Computer Science (LICS 2002), 2002.
G. Gottlob, C. Koch, and R. Pichler. Efficient algorithms for processing XPath queries. In Proc. of 28th Conf. on VLDB, 2002.
J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
G. Miklau and D. Suciu. Containment and equivalence for an XPath fragment. In Proc. 21th Symposium on Principles of Database Systems (PODS 2002), pages 65–76, 2002.
G. Moerkotte. Incorporating XSL processing into database engines. In Proc. of 28th Conf. on VLDB, 2002.
F. Neven. Automata, logic, and XML. In J. C. Bradfield, editor, CSL, volume 2471 of Lecture Notes in Computer Science, pages 2–26. Springer, 2002.
F. Neven. Automata theory for XML researchers. SIGMOD Record, 31(3), 2002.
F. Neven and T. Schwentick. Automata-and logic-based pattern languages for tree-structured data. Unpublished, 2001.
F. Neven and T. Schwentick. Query automata on finite trees. Theoretical Computer Science, 275:633–674, 2002.
G. Slutzki. Alternating tree automata. Theoretical Computer Science, 41(2-3):305–318, 1985.
P. T. Wood. Containment for XPath fragments under DTD constraints. ICDT 2003, this volume.
P. T. Wood. Minimising simple XPath expressions. WebDB informal proceedings, 2001.
P. T. Wood. On the equivalence of XML patterns. In Lloyd et al., editor, Computational Logic — CL 2000, volume 1861 of Lecture Notes in Artificial Intelligence, pages 1152–1166. Springer, 2000.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Neven, F., Schwentick, T. (2003). XPath Containment in the Presence of Disjunction, DTDs, and Variables. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds) Database Theory — ICDT 2003. ICDT 2003. Lecture Notes in Computer Science, vol 2572. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36285-1_21
Download citation
DOI: https://doi.org/10.1007/3-540-36285-1_21
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00323-6
Online ISBN: 978-3-540-36285-2
eBook Packages: Springer Book Archive