More Web Proxy on the site http://driver.im/

research-article

On XPath with transitive axes and data tests

Author:

Diego FigueiraAuthors Info & Claims

PODS '13: Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems

Pages 249 - 260

https://doi.org/10.1145/2463664.2463675

Published: 22 June 2013 Publication History

Abstract

We study the satisfiability problem for XPath with data equality tests. XPath is a node selecting language for XML documents whose satisfiability problem is known to be undecidable, even for very simple fragments. However, we show that the satisfiability for XPath with the rightward, leftward and downward reflexive-transitive axes (namely following-sibling-or-self, preceding-sibling-or-self, descendant-or-self) is decidable. Our algorithm yields a complexity of 3EXPSPACE, and we also identify an expressive-equivalent normal form for the logic for which the satisfiability problem is in 2EXPSPACE. These results are in contrast with the undecidability of the satisfiability problem as soon as we replace the reflexive-transitive axes with just transitive (non-reflexive) ones.

References

[1]

Vince Bárány, Mikołaj Bojańczyk, Diego Figueira, and Paweł Parys. Decidable classes of documents for XPath. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'12), Leibniz International Proceedings in Informatics (LIPIcs), Hyderabad, India, 2012. Leibniz-Zentrum für Informatik.

[2]

Michael Benedikt, Wenfei Fan, and Floris Geerts. XPath satisfiability in the presence of DTDs. Journal of the ACM, 55(2):1--79, 2008.

Digital Library

[3]

Mikołaj Bojańczyk and Sławomir Lasota. An extension of data automata that captures XPath. In Annual IEEE Symposium on Logic in Computer Science (LICS '10), 2010.

Digital Library

[4]

Mikołaj Bojańczyk, Anca Muscholl, Thomas Schwentick, and Luc Segoufin. Two-variable logic on data trees and XML reasoning. Journal of the ACM, 56(3):1--48, 2009.

Digital Library

[5]

James Clark and Steve DeRose. XML path language (XPath). Website, 1999. W3C Recommendation. http://www.w3.org/TR/xpath.

[6]

Claire David, Leonid Libkin, and Tony Tan. Efficient reasoning about data trees via integer linear programming. ACM Transactions on Database Systems, 37(3):19, 2012.

Digital Library

[7]

Wenfei Fan, Chee Yong Chan, and Minos N. Garofalakis. Secure XML querying with security views. In ACM SIGACT-SIGMOD-SIGART International Conference on Management of Data (SIGMOD'04), pages 587--598. ACM Press, 2004.

Digital Library

[8]

Diego Figueira. Satisfiability of downward XPath with data equality tests. In ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS'09), pages 197--206. ACM Press, 2009.

Digital Library

[9]

Diego Figueira. Forward-XPath and extended register automata on data-trees. In International Conference on Database Theory (ICDT'10). ACM Press, 2010.

Digital Library

[10]

Diego Figueira. Reasoning on Words and Trees with Data. Phd thesis, Laboratoire Spécification et Vérification, ENS Cachan, France, December 2010.

[11]

Diego Figueira. A decidable two-way logic on data words. In Annual IEEE Symposium on Logic in Computer Science (LICS'11), pages 365--374, Toronto, Canada, 2011. IEEE Computer Society Press.

Digital Library

[12]

Diego Figueira. Alternating register automata on finite data words and trees. Logical Methods in Computer Science, 8(1), 2012.

[13]

Diego Figueira. Decidability of downward XPath. ACM Trans. Comput. Log., 13(4), 2012.

Digital Library

[14]

Diego Figueira and Luc Segoufin. Future-looking logics on data words and trees. In Int. Symp. on Mathematical Foundations of Comp. Sci. (MFCS'09), volume 5734 of LNCS, pages 331--343. Springer, 2009.

Digital Library

[15]

Diego Figueira and Luc Segoufin. Bottom-up automata on data trees and vertical XPath. In International Symposium on Theoretical Aspects of Computer Science (STACS'11), Leibniz International Proceedings in Informatics (LIPIcs). Leibniz-Zentrum für Informatik, 2011.

[16]

Floris Geerts and Wenfei Fan. Satisfiability of XPath queries with sibling axes. In International Symposium on Database Programming Languages (DBPL'05), volume 3774 of Lecture Notes in Computer Science, pages 122--137. Springer, 2005.

Digital Library

[17]

Georg Gottlob, Christoph Koch, and Reinhard Pichler. Efficient algorithms for processing XPath queries. ACM Transactions on Database Systems, 30(2):444--491, 2005.

Digital Library

[18]

Marcin Jurdziński and Ranko Lazić. Alternating automata on data trees and xpath satisfiability. ACM Trans. Comput. Log., 12(3):19, 2011.

Digital Library

[19]

Michael Kaminski and Nissim Francez. Finite-memory automata. Theoretical Computer Science, 134(2):329--363, 1994.

Digital Library

[20]

Michael Kaminski and Tony Tan. Tree automata over infinite alphabets. In Pillars of Computer Science, volume 4800 of Lecture Notes in Computer Science, pages 386--423. Springer, 2008.

Digital Library

[21]

Wim Martens and Frank Neven. Frontiers of tractability for typechecking simple xml transformations. J. Comput. Syst. Sci., 73(3):362--390, 2007.

Digital Library

[22]

Frank Neven, Thomas Schwentick, and Victor Vianu. Finite state machines for strings over infinite alphabets. ACM Trans. Comput. Log., 5(3):403--435, 2004.

Digital Library

[23]

Tony Tan. An automata model for trees with ordered data values. In Annual IEEE Symposium on Logic in Computer Science (LICS'12), pages 586--595. IEEE Computer Society Press, 2012.

Digital Library

Cited By

Baelde DLick ASchmitz SSuciu DSkritek SKoch C(2019)Decidable XPath Fragments in the Real WorldProceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3294052.3319685(285-302)Online publication date: 25-Jun-2019
https://dl.acm.org/doi/10.1145/3294052.3319685
Figueira D(2018)Satisfiability of Xpath on data treesACM SIGLOG News10.1145/3212019.32120215:2(4-16)Online publication date: 30-Apr-2018
https://dl.acm.org/doi/10.1145/3212019.3212021
Abriola SFigueira DFigueira S(2017)Logics of Repeating Values on Data Trees and Branching Counter SystemsProceedings of the 20th International Conference on Foundations of Software Science and Computation Structures - Volume 1020310.1007/978-3-662-54458-7_12(196-212)Online publication date: 22-Apr-2017
https://dl.acm.org/doi/10.1007/978-3-662-54458-7_12
Show More Cited By

Index Terms

On XPath with transitive axes and data tests
1. Applied computing
  1. Document management and text processing
    1. Document preparation
      1. Markup languages
2. Information systems
  1. Data management systems
    1. Query languages
  2. World Wide Web
    1. Web data description languages
      1. Markup languages

Recommendations

Decidability of Downward XPath

We investigate the satisfiability problem for downward-XPath, the fragment of XPath that includes the child and descendant axes, and tests for (in)equality of attributes’ values. We prove that this problem is decidable, EXPTIME-complete. These bounds ...
Satisfiability of downward XPath with data equality tests
PODS '09: Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

In this work we investigate the satisfiability problem for the logic XPath(↓*, ↓,=), that includes all downward axes as well as equality and inequality tests. We address this problem in the absence of DTDs and the sibling axis. We prove that this ...
XPath, transitive closure logic, and nested tree walking automata
PODS '08: Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

We consider the navigational core of XPath, extended with two operators: the Kleene star for taking the transitive closure of path expressions, and a subtree relativisation operator, allowing one to restrict attention to a specific subtree while ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODS '13: Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems

June 2013

334 pages

ISBN:9781450320665

DOI:10.1145/2463664

General Chair:
Richard Hull
IBM T.J. Watson Research Center, USA
,
Program Chair:
Wenfei Fan
University of Edinburgh, UK

Copyright © 2013 ACM.

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

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMOD/PODS'13

Sponsor:

SIGMOD

SIGMOD/PODS'13: International Conference on Management of Data

June 22 - 27, 2013

New York, New York, USA

Acceptance Rates

PODS '13 Paper Acceptance Rate 24 of 97 submissions, 25%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
130
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)1

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Baelde DLick ASchmitz SSuciu DSkritek SKoch C(2019)Decidable XPath Fragments in the Real WorldProceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3294052.3319685(285-302)Online publication date: 25-Jun-2019
https://dl.acm.org/doi/10.1145/3294052.3319685
Figueira D(2018)Satisfiability of Xpath on data treesACM SIGLOG News10.1145/3212019.32120215:2(4-16)Online publication date: 30-Apr-2018
https://dl.acm.org/doi/10.1145/3212019.3212021
Abriola SFigueira DFigueira S(2017)Logics of Repeating Values on Data Trees and Branching Counter SystemsProceedings of the 20th International Conference on Foundations of Software Science and Computation Structures - Volume 1020310.1007/978-3-662-54458-7_12(196-212)Online publication date: 22-Apr-2017
https://dl.acm.org/doi/10.1007/978-3-662-54458-7_12
Areces CFervari RSeiler N(2017)Tableaux for Hybrid XPath with DataProgress in Artificial Intelligence10.1007/978-3-319-65340-2_50(611-623)Online publication date: 5-Sep-2017
https://dl.acm.org/doi/10.1007/978-3-319-65340-2_50
Bárcenas EBenítez-Guerrero ELavalle J(2016)On Regular Paths with Counting and Data TestsElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2016.11.002328:C(3-16)Online publication date: 8-Dec-2016
https://dl.acm.org/doi/10.1016/j.entcs.2016.11.002
Boiret AHugot VNiehren JTreinen R(2015)Logics for Unordered Trees with Data Constraints on SiblingsLanguage and Automata Theory and Applications10.1007/978-3-319-15579-1_13(175-187)Online publication date: 24-Feb-2015
https://doi.org/10.1007/978-3-319-15579-1_13

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten