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.00021654356
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
712 Efficient Algorithms for Processing XPath Queries 2002 VLDB 0.00017714027
1,933 XPath Satisfiability in the Presence of DTDs 2005 PODS 0.00010049404
2,480 Efficient Query Reformulation in Peer Data Management Systems 2004 SIGMOD 8.682497e-05
2,707 FleXPath: Flexible Structure and Full-Text Querying for XML 2004 SIGMOD 8.265158e-05
2,957 Efficient Algorithms for Minimizing Tree Pattern Queries 2002 SIGMOD 7.8143379e-05
2,980 A Framework for Using Materialized XPath Views in XML Query Processing 2004 VLDB 7.7800968e-05
3,089 On the minimization of Xpath queries 2003 VLDB 7.5938563e-05
3,613 From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery 2003 VLDB 6.9139845e-05
3,852 The Expressivity of XPath with Transitive Closure* 2006 PODS 6.6993728e-05
4,360 Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents 2006 VLDB 6.2486086e-05
4,362 The Complexity of Query Containment in Expressive Fragments of XPath 2.0 2007 PODS 6.2478748e-05
4,510 iTrails: Pay-as-you-go Information Integration in Dataspaces 2007 VLDB 6.1239848e-05
4,568 Rewriting XPath Queries Using Materialized Views 2005 VLDB 6.0725918e-05
4,624 On Testing Satisfiability of Tree Pattern Queries 2004 VLDB 6.034764e-05
5,140 Lazy Query Evaluation for Active XML 2004 SIGMOD 5.6632963e-05
5,595 Safe Data Sharing and Data Dissemination on Smart Devices 2005 SIGMOD 5.4167719e-05
5,621 Query Caching and View Selection for XML Databases 2005 VLDB 5.4061733e-05
5,950 Minimization of Tree Pattern Queries with Constraints 2008 SIGMOD 5.2551296e-05
6,293 Containment of Nested XML Queries 2004 VLDB 5.1206121e-05
6,300 Rewriting Nested XML Queries Using Nested Views 2006 SIGMOD 5.1174095e-05
6,682 Query Efficiency in Probabilistic XML Models 2008 SIGMOD 4.9596732e-05
7,295 Structured Materialized Views for XML Queries 2007 VLDB 4.7658356e-05
7,783 Maintaining XPath Views in Loosely Coupled Systems 2006 VLDB 4.6476417e-05
8,305 Satisfiability and Relevance for Queries over Active Documents 2009 PODS 4.5392079e-05
8,308 Conditional XPath, the first order complete XPath dialect* 2004 PODS 4.5392079e-05
8,431 Materialized View Selection for XQuery Workloads 2012 SIGMOD 4.5084372e-05
8,768 Client-Based Access Control Management for XML documents 2004 VLDB 4.4520434e-05
8,947 Towards Theory for Real-World Data 2022 PODS 4.4216375e-05
9,520 PAXQuery: Parallel Analytical XML Processing 2015 SIGMOD 4.3282242e-05
9,533 Cooperative XPath Caching 2008 SIGMOD 4.3229158e-05
9,535 Answering Tree Pattern Queries Using Views 2006 VLDB 4.3226836e-05
9,676 Schema-Based Query Optimisation for Graph Databases 2025 SIGMOD 4.3006524e-05
9,889 The (Almost) Complete Guide to Tree Pattern Containment 2015 PODS 4.2576366e-05
11,645 Containment of Shape Expression Schemas for RDF 2019 PODS 4.1905499e-05
11,729 Data Citation: Giving Credit Where Credit is Due 2018 SIGMOD 4.1905499e-05
11,835 Minimization of Tree Pattern Queries 2016 PODS 4.1905499e-05
12,137 Answering Queries using Views over Probabilistic XML: Complexity and Tractability 2012 VLDB 4.1905499e-05
12,196 Generating Efficient Execution Plans for Vertically Partitioned XML Databases 2011 VLDB 4.1905499e-05
12,348 Efficient Rewriting of XPath Queries Using Query Set Specifications 2009 VLDB 4.1905499e-05
12,443 Reasoning about XML Update Constraints 2007 PODS 4.1905499e-05
12,500 Structural Characterizations of the Semantics of XPath as Navigation Tool on a Document 2006 PODS 4.1905499e-05
12,613 Answering XPath Queries over Networks by Sending Minimal Views 2004 VLDB 4.1905499e-05
12,615 The NEXT Framework for Logical XQuery Optimization 2004 VLDB 4.1905499e-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,662 Conjunctive Queries over Trees 2004 PODS 0.00010966423
12,304 Satisfiability of Downward XPath with Data Equality Tests 2009 PODS 4.1905499e-05
8,199 On XPath with Transitive Axes and Data Tests 2013 PODS 4.5558541e-05
6,293 Containment of Nested XML Queries 2004 VLDB 5.1206121e-05
1,933 XPath Satisfiability in the Presence of DTDs 2005 PODS 0.00010049404
12,500 Structural Characterizations of the Semantics of XPath as Navigation Tool on a Document 2006 PODS 4.1905499e-05
3,089 On the minimization of Xpath queries 2003 VLDB 7.5938563e-05
12,348 Efficient Rewriting of XPath Queries Using Query Set Specifications 2009 VLDB 4.1905499e-05
9,104 Decidable XPath Fragments in the Real World 2019 PODS 4.3911866e-05
4,362 The Complexity of Query Containment in Expressive Fragments of XPath 2.0 2007 PODS 6.2478748e-05