Abstract
The containment and equivalence problems for various fragments of XPath have been studied by a number of authors. For some fragments, deciding containment (and even minimisation) has been shown to be in PTIME, while for minor extensions containment has been shown to be CONP-complete. When containment is with respect to trees satisfying a set of constraints (such as a schema or DTD), the problem seems to be more difficult. For example, containment under DTDs is CONP-complete for an XPath fragment denoted XP for which containment is in PTIME. It is also undecidable for a larger class of XPath queries when the constraints are so-called simple XPath integrity constraints (SXICs). In this paper, we show that containment is decidable for an important fragment of XPath, denoted XP{[ ],*,//}, when the constraints are DTDs. We also identify XPath fragments for which containment under DTDs can be decided in PTIME.
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
S. Amer-Yahia, S. Cho, L. V. S. Lakshmanan, and D. Srivastava. Minimization of tree pattern queries. In Proc. ACM SIGMOD Conf., pages 497–508, 2001.
J. Bailey, A. Poulovassilis, and P. T. Wood. An event-condition-action language for XML. In Proc. 11th Int. Conf. on the World Wide Web, pages 486–495, 2002.
K. Böhm, K. Aberer, M. T. Özsu, and K. Gayer. Query optimization for structured documents based on knowledge of the document type definition. In Proc. IEEE Advances in Digital Libraries, pages 196–205, 1998.
A. Bruggemann-Klein, M. Murata, and D. Wood. Regular tree languages over non-ranked alphabets. Available at ftp://ftp11.informatik.tu-muenchen.de/pub/misc/caterpillars/, 1998.
D. Calvanese, G. de Giacomo, and M. Lenzerini. On the decidability of query containment under constraints. In Proc. 17th ACM Symp. on Principles of Databases Systems, pages 149–158, 1998.
B. Chidlovskii. Using regular tree automata as XML schemas. In Proc. IEEE Advances in Digital Libraries, pages 89–104, 2000.
A. Deutsch and V. Tannen. Containment and integrity constraints for XPath fragments. In Proc. 8th Int. Workshop on Knowledge Representation Meets Databases, 2001.
D. Maier, A. O. Mendelzon, and Y. Sagiv. Testing implications of data dependencies. ACM Trans. on Database Syst., 4(4):455–469, 1979.
G. Miklau and D. Suciu. Containment and equivalence for an XPath fragment. In Proc. 21st ACM Symp. on Principles of Databases Systems, 2002.
F. Neven and T. Schwentick. XPath containment in the presence of disjunction, DTDs, and variables. In Proc. 9th Int. Conf. on Database Theory, 2003.
Y. Papakonstantinou and V. Vassalos. Query rewriting for semistructured data. In Proc. ACM SIGMOD Conf., pages 455–466, 1999.
Y. Papakonstantinou and V. Vianu. DTD inference for views of XML data. In Proc. 19th ACM Symp. on Principles of Databases Systems, pages 35–46, 2000.
H. Seidl. Deciding equivalence of finite tree automata. SIAM J. Computing, 19(3):424–437, June 1990.
P. Wadler. A formal semantics of patterns in XSLT. In Markup Technologies, pages 183–202, 1999.
P. T. Wood. On the equivalence of XML patterns. In Proc. 1st Int. Conf. on Computational Logic, LNAI 1861, pages 1152–1166, 2000. Springer-Verlag.
P. T. Wood. Minimising simple XPath expressions. In Proc. WebDB 2001: Fourth Int. Workshop on the Web and Databases, pages 13–18, 2001. nr17._World Wide Web Consortium. XML Path Language (XPath), Version 1.0. See http://www.w3.org/TR/xpath, November 1999. W3C Recommendation.
M. Yannakakis. Algorithms for acyclic database schemes. In Proc. 7th Int. Conf. on Very Large Data Bases, pages 82–94, 1981.
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
Wood, P.T. (2003). Containment for XPath Fragments under DTD Constraints. 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_20
Download citation
DOI: https://doi.org/10.1007/3-540-36285-1_20
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