Abstract
We study structural properties of each of the main sublanguages of XPath [8] commonly used in practice. First, we characterize the expressive power of these language fragments in terms of both logics and tree patterns. Second, we investigate closure properties, focusing on the ability to perform basic Boolean operations while remaining within the fragment. We give a complete picture of the closure properties of these fragments, treating XPath expressions both as functions of arbitrary nodes in a document tree, and as functions that are applied only at the root of the tree. Finally, we provide sound and complete axiom systems and normal forms for several of these fragments. These results are useful for simplification of XPath expressions and optimization of XML queries.
Supported in part by NSF Career Award IIS-0093168; on leave from Temple Univ.
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, V. Lakshmaman, and D. Srivistava. Minimization of tree pattern queries. In SIGMOD, 2001.
A. Berglund et al. XML Path Language (XPath) 2.0. W3C Working Draft, Dec. 2001. http://www.w3.org/TR/xpath20.
G. Bex, S. Maneth, and F. Neven. A formal model for an expressive fragment of XSLT. Information Systems, 27(1):21–39, 2002.
D. Calvanese, G. De Giacomo, M. Lenzerini, and D. Nardi. Reasoning in expressive description logics. In Handbook of Automated Reasoning, pages 1581–1634. Elsevier, 2001.
D. Chamberlin et al. XQuery 1.0: An XML query language. W3C Working Draft, June 2001. http://www.w3.org/TR/xquery.
C. Chan, P. Felber, M. Garofalakis, and R. Rastogu. Efficient filtering of XML documents with XPath expressions. In ICDE, 2002.
J. Clark. XSL Transformations (XSLT). W3C Recommendation, Nov. 1999. http://www.w3.org/TR/xslt.
J. Clark and S. DeRose. XML Path Language (XPath). W3C Recommendation, Nov. 1999. http://www.w3.org/TR/xpath.
A. Deutsch and V. Tannen. Containment for classes of XPath expressions under integrity constraints. In KRDB, 2001.
G. Gottlob, C. Koch, and R. Pichler. Efficient algorithms for processing XPath queries. In VLDB, 2002.
D. Harel, D. Kozen, and J. Tiuryn. Dynamic Logic. The MIT Press, 2000.
C. Hoffmann and M. O’Donnell. Pattern matching in trees. JACM, 29(1):68–95, 1982.
P. Kilpelainen and H. Manilla. Ordered and unordered tree inclusion. SIAM J. Comput., 24(2):340–356, 1995.
G. Miklau and D. Suciu. Containment and equivalence of XPath expressions. In PODS, 2002.
T. Milo, D. Suciu, and V. Vianu. Typechecking for XML transformers. In PODS, 2001.
M. Murata. Extended path expressions for XML. In PODS, 2001.
F. Neven and T. Schwentick. Expressive and efficient languages for tree-structured data. In PODS, 2000.
D. Olteanu, H. Meuss, T. Furche, and F. Bry. XPath: Looking forward. In Workshop on XML-Based Data Management (XMLDM), 2002.
P. Ramanan. Efficient algorithms for minimizing tree pattern queries. In SIGMOD, 2002.
V. Redko. On defining relations for the algebra of regular events. Ukrainskii Matematicheskii Zhurnal, 16:120–126, 1964. (Russian).
J. Robie, J. Lapp, and D. Schach. XML Query Language (XQL). Workshop on XML Query Languages, Dec. 1998.
H. Thompson et al. XML Schema. W3C Working Draft, May 2001. http://www.w3.org/XML/Schema.
P. Wadler. Two semantics for XPath. Technical report, Bell Labs, 2000.
P. Wood. On the equivalence of XML patterns. In Computational Logic, 2000.
P. Wood. Minimising simple XPath expressions. In WebDB, 2001.
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
Benedikt, M., Fan, W., Kuper, G.M. (2003). Structural Properties of XPath Fragments. 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_6
Download citation
DOI: https://doi.org/10.1007/3-540-36285-1_6
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