skip to main content
10.1145/1055558.1055562acmconferencesArticle/Chapter ViewAbstractPublication PagespodsConference Proceedingsconference-collections
Article

Conditional XPath, the first order complete XPath dialect

Published: 14 June 2004 Publication History

Abstract

XPath is the W3C -- standard node addressing language for XML documents. XPath is still under development and its technical aspects are intensively studied. What is missing at present is a clear characterization of the expressive power of XPath, be it either semantical or with reference to some well established existing (logical) formalism. Core XPath (the logical core of XPath 1.0 defined by Gottlob et al.) cannot express queries with conditional paths as exemplified by "do a child step, while test is true at the resulting node." In a first-order complete extension of Core XPath, such queries are expressible, We add conditional axis relations to Core XPath and show that the resulting language, called conditional XPath, is equally expressive as first-order logic when interpreted on ordered trees. Both the result, the extended XPath language, and the proof are closely related to temporal logic. Specifically, while Core XPath may be viewed as a simple temporal logic, conditional XPath extends this with (counterparts of) the since and until operators.

References

[1]
M. Benedikt, W. Fan, and G. Kuper. Structural properties of XPath fragments. In Proc. ICDT'03, 2003.
[2]
P. Blackburn and W. Meyer-Viol. Linguistics, logic, and finite trees. Logic J. of the IGPL, 2:3--29, 1994.
[3]
A. Chandra and P. Merlin. Optimal implementation of conjunctive queries in relational databases. In Proceedings of 9th ACM Symposium on Theory of Computing, pages 77--90, 1977.
[4]
M. Frick and M. Grohe. The complexity of first-order and monadic second-order logic revisited. In Proc. LICS'02, pages 215--224, 2002.
[5]
D. M. Gabbay, I. Hodkinson, and M. Reynolds. Temporal Logic. Oxford Science Publications, 1994. Volume 1: Mathematical Foundations and Computational Aspects.
[6]
D. M. Gabbay, A. Pnueli, S. Shelah, and J. Stavi. On the temporal analysis of fairness. In Proc. 7th ACM Symposium on Principles of Programming Languages, pages 163--173, 1980.
[7]
G. Gottlob, C. Koch, and R. Pichler. Efficient algorithms for processing XPath queries. In Proc. VLDB'02, 2002.
[8]
G. Gottlob, C. Koch, and R. Pichler. The complexity of XPath query evaluation. In Proc. PODS 2003, pages 179--190, 2003.
[9]
G. Gottlob and C. Koch. Monadic queries over tree-structured data. In Proc. LICS'02, 2002.
[10]
N. Immerman. Upper and lower bounds for first order expressibility. J. Comput. Syst. Sci., 25:76--98, 1982.
[11]
N. Immerman and D. Kozen. Definability with bounded number of bound variables. In Proc. LICS, pages 236--244, Washington, 1987. Computer Society Press.
[12]
J.A.W. Kamp. Tense Logic and the Theory of Linear Order. PhD thesis, U. of California, LA, 1968.
[13]
C. Koch. Efficient processing of expressive node-selecting queries on XML data in secondary storage: A tree automata-based approach. In VLDB 2003, pages 249--260, 2003.
[14]
M. Kracht. Inessential features. In Christian Retore, editor, Logical Aspects of Computational Linguistics, number 1328 in LNAI, pages 43--62. Springer, 1997.
[15]
M. Marx. XPath with conditional axis relations. In Proc. EDBT'04, pages 477--494. 2004.
[16]
F. Neven and T. Schwentick. Expressive and Efficient Pattern Languages for Tree-Structured Data. In Proc. PODS'02, pages 145--156. 2000.
[17]
G. Miklau and D. Suciu. Containment and equivalence for an XPath fragment. In Proc. PODS'02, pages 65--76, 2002.
[18]
A. Palm. Transforming tree constraints into formal grammars. PhD thesis, Universität Passau, 1997.
[19]
A. Rabinovich. Expressive power of temporal logics. In CONCUR 2002, Proceedings, volume 2421 of LNAI, pages 57--75, 2002.
[20]
J. Rogers. A descriptive approach to language theoretic complexity. CSLI Press, 1998.
[21]
B-H. Schlingloff. Expressive completeness of temporal logic of trees. Journal of Applied Non -- Classical Logics, 2(2):157--180, 1992.
[22]
A. Tarski and S. Givant. A Formalization of Set Theory without Variables, volume 41. AMS Colloquium publications, Providence, Rhode Island, 1987.
[23]
W. Thomas. Ehrenfeucht Games, the Composition Method, and the Monadic Theory of Ordinal Words. In Structures in Logic and Computer Science, A Selection of Essays in Honor of Andrzej Ehrenfeucht. Pages 118--143,Springer, 1997.
[24]
M. Vardi. On the complexity of bounded--variable queries. In Proceedings PODS-95, pages 266--276, 1995.
[25]
W3C. XML path language (XPath): Version 1.0. http://www.w3.org/TR/xpath.html.
[26]
W3C. XML path language (XPath): Version 2.0. http://www.w3.org/TR/xpath20/.
[27]
W3C. XML schema part 1: Structures. http://www.w3.org/TR/xmlschema-1.
[28]
W3C. Xquery 1.0: A query language for XML. http://www.w3.org/TR//xquery/.
[29]
W3C. XSL transformations language (XSLT): Version 2.0. http://www.w3.org/TR/xslt20/.
[30]
P. Wadler. Two semantics for XPath. Technical report. Bell Labs, 2000.

Cited By

View all
  • (2019)Semantic Query Language for Temporal Genealogical TreesProceedings of 6th International Conference in Software Engineering for Defence Applications10.1007/978-3-030-14687-0_9(94-109)Online publication date: 19-Mar-2019
  • (2016)Limiting Until in Ordered Tree Query LanguagesACM Transactions on Computational Logic10.1145/285610417:2(1-34)Online publication date: 17-Mar-2016
  • (2014)Equipping IDEs with XML-Path Reasoning CapabilitiesACM Transactions on Internet Technology10.1145/260257313:4(1-20)Online publication date: 1-Jul-2014
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODS '04: Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
June 2004
350 pages
ISBN:158113858X
DOI:10.1145/1055558
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2004

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

SIGMOD/PODS04

Acceptance Rates

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 30 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2019)Semantic Query Language for Temporal Genealogical TreesProceedings of 6th International Conference in Software Engineering for Defence Applications10.1007/978-3-030-14687-0_9(94-109)Online publication date: 19-Mar-2019
  • (2016)Limiting Until in Ordered Tree Query LanguagesACM Transactions on Computational Logic10.1145/285610417:2(1-34)Online publication date: 17-Mar-2016
  • (2014)Equipping IDEs with XML-Path Reasoning CapabilitiesACM Transactions on Internet Technology10.1145/260257313:4(1-20)Online publication date: 1-Jul-2014
  • (2012)Reasoning and Ontologies in Data ExtractionReasoning Web. Semantic Technologies for Advanced Query Answering10.1007/978-3-642-33158-9_5(184-210)Online publication date: 2012
  • (2009)Four lessons in versatility or how query languages adapt to the webSemantic techniques for the web10.5555/1809268.1809270(50-160)Online publication date: 1-Jan-2009
  • (2009)How big must complete XML query languages be?Proceedings of the 12th International Conference on Database Theory10.1145/1514894.1514917(183-200)Online publication date: 23-Mar-2009
  • (2009)XPath leashedACM Computing Surveys10.1145/1456650.145665341:1(1-54)Online publication date: 15-Jan-2009
  • (2009)Four Lessons in Versatility or How Query Languages Adapt to the WebSemantic Techniques for the Web10.1007/978-3-642-04581-3_2(50-160)Online publication date: 2009
  • (2008)On the expressibility of functions in XQuery fragmentsInformation Systems10.1016/j.is.2008.01.00333:4-5(435-455)Online publication date: 1-Jun-2008
  • (2007)Efficient and expressive tree filtersProceedings of the 27th international conference on Foundations of software technology and theoretical computer science10.5555/1781794.1781834(461-472)Online publication date: 12-Dec-2007
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media