Database Paper Browser

Back to papers

Containment and Equivalence for an XPath Fragment [Extended Abstract]

Summary: Containment/equivalence for an XPath fragment with branching, label wildcards, and descendant axes: show containment becomes coNP-complete (contrasting prior two-feature tractability). Give an EXPTIME sound-and-complete algorithm, identify parameterized PTIME islands and coNP-hard bounded cases, and propose a fast sound-but-incomplete practical procedure. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1252
Venue
PODS
Year
2002
Pagerank
0.000216753
Overall Rank
499 | 96.54%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 43 of 43 citing papers.

Rank Citing Paper Year Venue Pagerank
713 Efficient Algorithms for Processing XPath Queries 2002 VLDB 0.00017731096
1,929 XPath Satisfiability in the Presence of DTDs 2005 PODS 0.00010058897
2,479 Efficient Query Reformulation in Peer Data Management Systems 2004 SIGMOD 8.6909119e-05
2,704 FleXPath: Flexible Structure and Full-Text Querying for XML 2004 SIGMOD 8.2720556e-05
2,956 Efficient Algorithms for Minimizing Tree Pattern Queries 2002 SIGMOD 7.821865e-05
2,977 A Framework for Using Materialized XPath Views in XML Query Processing 2004 VLDB 7.7876083e-05
3,084 On the minimization of Xpath queries 2003 VLDB 7.6011919e-05
3,610 From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery 2003 VLDB 6.9196208e-05
3,851 The Expressivity of XPath with Transitive Closure* 2006 PODS 6.7057867e-05
4,364 Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents 2006 VLDB 6.2546168e-05
4,366 The Complexity of Query Containment in Expressive Fragments of XPath 2.0 2007 PODS 6.2538592e-05
4,508 iTrails: Pay-as-you-go Information Integration in Dataspaces 2007 VLDB 6.1298098e-05
4,568 Rewriting XPath Queries Using Materialized Views 2005 VLDB 6.0784118e-05
4,625 On Testing Satisfiability of Tree Pattern Queries 2004 VLDB 6.0406081e-05
5,139 Lazy Query Evaluation for Active XML 2004 SIGMOD 5.6686638e-05
5,590 Safe Data Sharing and Data Dissemination on Smart Devices 2005 SIGMOD 5.4215673e-05
5,611 Query Caching and View Selection for XML Databases 2005 VLDB 5.4113701e-05
5,948 Minimization of Tree Pattern Queries with Constraints 2008 SIGMOD 5.2602218e-05
6,294 Containment of Nested XML Queries 2004 VLDB 5.1255418e-05
6,300 Rewriting Nested XML Queries Using Nested Views 2006 SIGMOD 5.1223169e-05
6,681 Query Efficiency in Probabilistic XML Models 2008 SIGMOD 4.9643102e-05
7,298 Structured Materialized Views for XML Queries 2007 VLDB 4.770411e-05
7,783 Maintaining XPath Views in Loosely Coupled Systems 2006 VLDB 4.6521054e-05
8,311 Satisfiability and Relevance for Queries over Active Documents 2009 PODS 4.5435639e-05
8,314 Conditional XPath, the first order complete XPath dialect* 2004 PODS 4.5435639e-05
8,440 Materialized View Selection for XQuery Workloads 2012 SIGMOD 4.5127636e-05
8,771 Client-Based Access Control Management for XML documents 2004 VLDB 4.456315e-05
8,943 Towards Theory for Real-World Data 2022 PODS 4.4258797e-05
9,519 PAXQuery: Parallel Analytical XML Processing 2015 SIGMOD 4.3323764e-05
9,532 Cooperative XPath Caching 2008 SIGMOD 4.3270626e-05
9,534 Answering Tree Pattern Queries Using Views 2006 VLDB 4.3268303e-05
9,676 Schema-Based Query Optimisation for Graph Databases 2025 SIGMOD 4.3047774e-05
9,890 The (Almost) Complete Guide to Tree Pattern Containment 2015 PODS 4.2617199e-05
11,641 Containment of Shape Expression Schemas for RDF 2019 PODS 4.1945683e-05
11,723 Data Citation: Giving Credit Where Credit is Due 2018 SIGMOD 4.1945683e-05
11,827 Minimization of Tree Pattern Queries 2016 PODS 4.1945683e-05
12,129 Answering Queries using Views over Probabilistic XML: Complexity and Tractability 2012 VLDB 4.1945683e-05
12,188 Generating Efficient Execution Plans for Vertically Partitioned XML Databases 2011 VLDB 4.1945683e-05
12,340 Efficient Rewriting of XPath Queries Using Query Set Specifications 2009 VLDB 4.1945683e-05
12,434 Reasoning about XML Update Constraints 2007 PODS 4.1945683e-05
12,491 Structural Characterizations of the Semantics of XPath as Navigation Tool on a Document 2006 PODS 4.1945683e-05
12,604 Answering XPath Queries over Networks by Sending Minimal Views 2004 VLDB 4.1945683e-05
12,606 The NEXT Framework for Logical XQuery Optimization 2004 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,663 Conjunctive Queries over Trees 2004 PODS 0.00010977096
12,296 Satisfiability of Downward XPath with Data Equality Tests 2009 PODS 4.1945683e-05
8,200 On XPath with Transitive Axes and Data Tests 2013 PODS 4.5602267e-05
6,294 Containment of Nested XML Queries 2004 VLDB 5.1255418e-05
1,929 XPath Satisfiability in the Presence of DTDs 2005 PODS 0.00010058897
12,491 Structural Characterizations of the Semantics of XPath as Navigation Tool on a Document 2006 PODS 4.1945683e-05
3,084 On the minimization of Xpath queries 2003 VLDB 7.6011919e-05
12,340 Efficient Rewriting of XPath Queries Using Query Set Specifications 2009 VLDB 4.1945683e-05
9,105 Decidable XPath Fragments in the Real World 2019 PODS 4.3953995e-05
4,366 The Complexity of Query Containment in Expressive Fragments of XPath 2.0 2007 PODS 6.2538592e-05