On the complexity of XPath containment in the presence of disjunction, DTDs, and variables

Frank Neven; Thomas Schwentick

doi:10.2168/LMCS-2(3:1)2006

Frank Neven ; Thomas Schwentick - On the complexity of XPath containment in the presence of disjunction, DTDs, and variables

lmcs:2243 - Logical Methods in Computer Science, July 26, 2006, Volume 2, Issue 3 - https://doi.org/10.2168/LMCS-2(3:1)2006

On the complexity of XPath containment in the presence of disjunction, DTDs, and variablesArticle

Authors: Frank Neven ; Thomas Schwentick

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. We restrict attention to the most common XPath expressions which navigate along the child and/or descendant axis. In addition to basic expressions using only node tests and simple predicates, we also consider disjunction and variables (ranging over nodes). Further, we investigate the containment problem relative to a given DTD. With respect to variables we study two semantics, (1) the original semantics of XPath, where the values of variables are given by an outer context, and (2) an existential semantics introduced by Deutsch and Tannen, in which the values of variables are existentially quantified. In this framework, we establish an exact classification of the complexity of the containment problem for many XPath fragments.

https://doi.org/10.2168/LMCS-2(3:1)2006

Source: arXiv.org:cs/0606065

Volume: Volume 2, Issue 3

Published on: July 26, 2006

Submitted on: August 18, 2005

Keywords: Computer Science - Databases,Computer Science - Logic in Computer Science,H.2,I.7.2,F.4

Licence: arXiv.org - Assumed non-exclusive license to distribute

Bibliographic References

49 Documents citing this article

Yeting Li;Haiming Chen;Zixuan Chen, 2022, Learning Disjunctive Multiplicity Expressions and Disjunctive Generalize Multiplicity Expressions From Both Positive and Negative Examples, The Computer Journal, 66, 7, pp. 1733-1748, 10.1093/comjnl/bxac037.

David Baelde;Anthony Lick;Sylvain Schmitz, Decidable XPath Fragments in the Real World, 2019, Amsterdam Netherlands, 10.1145/3294052.3319685, https://hal.inria.fr/hal-01852475.

Matthew Hague;Anthony W. Lin;Chih-Duo Hong, 2019, CSS Minification via Constraint Solving, ACM Transactions on Programming Languages and Systems, 41, 2, pp. 1-76, 10.1145/3310337.

Diego Figueira, 2018, Satisfiability of Xpath on data trees, SIGLOG news, 5, 2, pp. 4-16, 10.1145/3212019.3212021, https://doi.org/10.1145/3212019.3212021.

Wojciech Czerwi Nacute;ski;Wim Martens;Matthias Niewerth;Paweł Parys, 2018, Minimization of Tree Patterns, Journal of the ACM, 65, 4, pp. 1-46, 10.1145/3180281.

Wojciech Czerwinski;Wim Martens;Matthias Niewerth;Pawel Parys, 2017, Optimizing Tree Patterns for Querying Graph- and Tree-Structured Data, Sigmod Record, 46, 1, pp. 15-22, 10.1145/3093754.3093759.

Wojciech Czerwiński;Claire David;Filip Murlak;Paweł Parys, 2017, Reasoning about integrity constraints for tree-structured data, 62, 4, pp. 941-976, 10.1007/s00224-017-9771-z, https://hal-upec-upem.archives-ouvertes.fr/hal-01799446.

Wojciech Czerwiński;Claire David;Katja Losemann;Wim Martens, 2017, Deciding definability by deterministic regular expressions, Journal of Computer and System Sciences, 10.1016/j.jcss.2017.03.011.

Filip Mazowiecki;Filip Murlak;Adam Witkowski, 2016, Monadic Datalog and Regular Tree Pattern Queries, CiteSeer X (The Pennsylvania State University), 41, 3, pp. 1-43, 10.1145/2925986, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.587.2068.

Henrik Björklund;Wim Martens;Thomas Schwentick, 2016, Conjunctive query containment over trees using schema information, Acta informatica, 55, 1, pp. 17-56, 10.1007/s00236-016-0282-1.

Maarten Marx;Evgeny Sherkhonov, 2016, Containment for queries over trees with attribute value comparisons, Wiardi Beckman Foundation (Wiardi Beckman Foundation), 58, pp. 1-13, 10.1016/j.is.2015.11.003, https://pure.uva.nl/ws/files/17065520/Containment_for_queries_over_trees_with_attribute_value_comparisons.pdf.

Paweł Parys, 2016, Weak containment for partial words is coNP-complete, Information Processing Letters, 116, 2, pp. 125-127, 10.1016/j.ipl.2015.09.012.

Wojciech Czerwinski;Wim Martens;Matthias Niewerth;Pawel Parys, Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Minimization of Tree Pattern Queries, 2016, San Francisco California USA, 10.1145/2902251.2902295.

Houari Mahfoud;Abdessamad Imine, Lecture Notes in Computer Science, Efficient Querying of XML Data Through Arbitrary Security Views, pp. 75-114, 2015, 10.1007/978-3-662-48567-5_3.

Mikołaj Bojańczyk;Filip Murlak;Adam Witkowski, CiteSeer X (The Pennsylvania State University), Containment of Monadic Datalog Programs via Bounded Clique-Width, pp. 427-439, 2015, 10.1007/978-3-662-47666-6_34, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.697.1152.

Timos Antonopoulos;Dag Hovland;Wim Martens;Frank Neven, 2015, Deciding Twig-definability of Node Selecting Tree Automata, Duo Research Archive (University of Oslo), 57, 4, pp. 967-1007, 10.1007/s00224-015-9623-7, http://hdl.handle.net/10852/9113.

Wojciech Czerwiński;Wim Martens;Pawel Parys;Marcin Przybylko, The (Almost) Complete Guide to Tree Pattern Containment, 2015, Melbourne Victoria Australia, 10.1145/2745754.2745766.

Evgeny Sherkhonov, Proceedings of the 2014 SIGMOD PhD symposium, Data exchange for document-centric XML, 2014, Snowbird Utah USA, 10.1145/2602622.2602628.

Filip Mazowiecki;Filip Murlak;Adam Witkowski, CiteSeer X (The Pennsylvania State University), Monadic Datalog and Regular Tree Pattern Queries, pp. 426-437, 2014, 10.1007/978-3-662-44522-8_36, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.587.2068.

Iovka Boneva;Radu Ciucanu;Sławek Staworko, 2014, Schemas for Unordered XML on a DIME, arXiv (Cornell University), 57, 2, pp. 337-376, 10.1007/s00224-014-9593-1, https://arxiv.org/abs/1311.7307.

Laks V. Lakshmanan;Alex Thomo, Lecture notes in computer science, View-Based Tree-Language Rewritings for XML, pp. 270-289, 2014, 10.1007/978-3-319-04939-7_13.

Amélie Gheerbrant;Leonid Libkin;Cristina Sirangelo, Reasoning About Pattern-Based XML Queries, pp. 4-18, 2013, 10.1007/978-3-642-39666-3_2, https://hal.inria.fr/hal-00908414.

Henrik Björklund;Wim Martens;Thomas Schwentick, Lecture notes in computer science, Validity of Tree Pattern Queries with Respect to Schema Information, pp. 171-182, 2013, 10.1007/978-3-642-40313-2_17.

Wojciech Czerwiński;Claire David;Katja Losemann;Wim Martens, Lecture Notes in Computer Science, Deciding Definability by Deterministic Regular Expressions, pp. 289-304, 2013, 10.1007/978-3-642-37075-5_19, https://doi.org/10.1007/978-3-642-37075-5_19.

Thomas Schwentick, Lecture notes in computer science, Foundations of XML Based on Logic and Automata: A Snapshot, pp. 23-33, 2012, 10.1007/978-3-642-28472-4_2.

Foto N. Afrati;Sara Cohen;Gabriel Kuper, 2011, On the complexity of tree pattern containment with arithmetic comparisons, Information Processing Letters, 111, 15, pp. 754-760, 10.1016/j.ipl.2011.04.014.

Pantelis Aravogliadis;Vasilis Vassalos, Lecture notes in computer science, On Equivalence and Rewriting of XPath Queries Using Views under DTD Constraints, pp. 1-16, 2011, 10.1007/978-3-642-23091-2_1.

Sara Cohen;Yaacov Y. Weiss, 2011, Bag equivalence of tree patterns, ACM transactions on database systems, 36, 4, pp. 1-35, 10.1145/2043652.2043657.

Geert Jan Bex;Frank Neven;Thomas Schwentick;Stijn Vansummeren, 2010, Inference of concise regular expressions and DTDs, ACM Transactions on Database Systems, 35, 2, pp. 1-47, 10.1145/1735886.1735890.

Geert Jan Bex;Wouter Gelade;Frank Neven;Stijn Vansummeren, 2010, Learning Deterministic Regular Expressions for the Inference of Schemas from XML Data, arXiv (Cornell University), 4, 4, pp. 1-32, 10.1145/1841909.1841911, https://arxiv.org/abs/1004.2372.

Henrik Björklund;Wouter Gelade;Wim Martens, 2010, Incremental XPath evaluation, Document Server@UHasselt (UHasselt), 35, 4, pp. 1-43, 10.1145/1862919.1862926, http://hdl.handle.net/1942/9914.

Jun Liu;Mark Roantree;Zohra Bellahsene, Lecture notes in computer science, A SchemaGuide for Accelerating the View Adaptation Process, pp. 160-173, 2010, 10.1007/978-3-642-16373-9_12.

Junhu Wang;Jeffrey Xu Yu, Lecture notes in computer science, Chasing Tree Patterns under Recursive DTDs, pp. 250-261, 2010, 10.1007/978-3-642-12026-8_20.

Ki-Hoon Lee;Kyu-Young Whang;Wook-Shin Han, 2010, XMin: Minimizing Tree Pattern Queries with Minimality Guarantee, World Wide Web, 13, 3, pp. 343-371, 10.1007/s11280-010-0089-x.

Pablo Barceló;Leonid Libkin;Antonella Poggi;Cristina Sirangelo, 2010, XML with incomplete information, CiteSeer X (The Pennsylvania State University), 58, 1, pp. 1-62, 10.1145/1870103.1870107, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.306.6772.

Balder ten Cate;Carsten Lutz, 2009, The complexity of query containment in expressive fragments of XPath 2.0, Journal of the Association for Computing Machinery, 56, 6, pp. 1-48, 10.1145/1568318.1568321.

Bernd Amann, Springer eBooks, XSL/XSLT, pp. 3676-3681, 2009, 10.1007/978-0-387-39940-9_773.

Bogdan Cautis;Serge Abiteboul;Tova Milo, 2009, Reasoning about XML update constraints, CiteSeer X (The Pennsylvania State University), 75, 6, pp. 336-358, 10.1016/j.jcss.2009.02.001, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.160.2682.

Sara Cohen;Tali Brodianskiy, 2009, Correcting queries for XML, Information Systems, 34, 8, pp. 690-710, 10.1016/j.is.2009.05.001.

Sven Hartmann;Sebastian Link, 2009, Efficient reasoning about a robust XML key fragment, ACM Transactions on Database Systems, 34, 2, pp. 1-33, 10.1145/1538909.1538912.

Henrik Björklund;Wim Martens;Thomas Schwentick, CiteSeer X (The Pennsylvania State University), Optimizing Conjunctive Queries over Trees Using Schema Information, pp. 132-143, 2008, 10.1007/978-3-540-85238-4_10, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.182.2832.

Leonid Libkin;Cristina Sirangelo, Edinburgh Research Explorer (University of Edinburgh), Reasoning about XML with Temporal Logics and Automata, pp. 97-112, 2008, 10.1007/978-3-540-89439-1_7, https://www.pure.ed.ac.uk/ws/files/17831759/Libkin_Sirangelo_2010_Reasoning_about_XML_with_Temporal_Logics_and_Automata.pdf.

Michael Benedikt;Wenfei Fan;Floris Geerts, 2008, XPath satisfiability in the presence of DTDs, Document Server@UHasselt (UHasselt), 55, 2, pp. 1-79, 10.1145/1346330.1346333, http://hdl.handle.net/1942/956.

Sven Hartmann;Henning Köhler;Sebastian Link;Thu Trinh;Jing Wang, Lecture Notes in Computer Science, On the Notion of an XML Key, pp. 103-112, 2008, 10.1007/978-3-540-88594-8_5.

Balder ten Cate;Carsten Lutz, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, The complexity of query containment in expressive fragments of XPath 2.0, 2007, Beijing China, 10.1145/1265530.1265541.

Bogdan Cautis;Serge Abiteboul;Tova Milo, Reasoning about XML update constraints, 2007, Beijing China, 10.1145/1265530.1265558, https://hal.inria.fr/inria-00137171.

Henrik Björklund;Wim Martens;Thomas Schwentick, Springer eBooks, Conjunctive Query Containment over Trees, pp. 66-80, 2007, 10.1007/978-3-540-75987-4_5.

Manizheh Montazerian;Peter T. Wood;Seyed R. Mousavi, Lecture Notes in Computer Science, XPath Query Satisfiability is in PTIME for Real-World DTDs, pp. 17-30, 2007, 10.1007/978-3-540-75288-2_3.

Wouter Gelade;Wim Martens;Frank Neven, Document Server@UHasselt (UHasselt), Optimizing Schema Languages for XML: Numerical Constraints and Interleaving, pp. 269-283, 2006, 10.1007/11965893_19, http://hdl.handle.net/1942/9220.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 1014 times.

This article's PDF has been downloaded 456 times.