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: hdb709dbf1df11efb
Venue: PODS
Year: 2002
Pagerank: 0.00018797031
Overall Rank: 409 | 97.27%
DOI: 10.1145/543613.543623

Incoming Non-self Citations Over Time

Authors

1. Gerome Miklau (University of Washington)
2. Dan Suciu (University of Washington)

BibTeX Citation

@inproceedings{miklau_pods02,
        address = {New York, NY, USA},
        series = {{PODS} '02},
        title = {{Containment and Equivalence for an XPath Fragment [Extended Abstract]}},
        url = {https://dl.acm.org/doi/10.1145/543613.543623},
        doi = {10.1145/543613.543623},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Miklau, Gerome and Suciu, Dan},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 43 of 43 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
683	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00014781223
1,983	XPath Satisfiability in the Presence of DTDs	2005	PODS	9.2451473e-05
2,333	Efficient Query Reformulation in Peer Data Management Systems	2004	SIGMOD	8.6088875e-05
2,677	FleXPath: Flexible Structure and Full-Text Querying for XML	2004	SIGMOD	8.1266688e-05
2,726	A Framework for Using Materialized XPath Views in XML Query Processing	2004	VLDB	8.0711806e-05
2,743	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD	8.0513978e-05
2,897	On the minimization of XPath queries	2003	VLDB	7.8835751e-05
3,252	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB	7.475123e-05
3,806	The Expressivity of XPath with Transitive Closure*	2006	PODS	6.9902521e-05
4,090	Rewriting XPath Queries Using Materialized Views	2005	VLDB	6.7964465e-05
4,176	Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents	2006	VLDB	6.7488554e-05
4,616	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS	6.4852899e-05
4,659	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.4686105e-05
5,152	iTrails: Pay-as-you-go Information Integration in Dataspaces	2007	VLDB	6.2375943e-05
5,378	Query Caching and View Selection for XML Databases	2005	VLDB	6.1392368e-05
5,513	Lazy Query Evaluation for Active XML	2004	SIGMOD	6.0866688e-05
6,074	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	5.877868e-05
6,150	Minimization of Tree Pattern Queries with Constraints	2008	SIGMOD	5.8555004e-05
6,333	Containment of Nested XML Queries	2004	VLDB	5.7933985e-05
6,627	Safe Data Sharing and Data Dissemination on Smart Devices	2005	SIGMOD	5.7127887e-05
7,080	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	5.5901209e-05
7,441	Structured Materialized Views for XML Queries	2007	VLDB	5.5118606e-05
8,325	Maintaining XPath Views in Loosely Coupled Systems	2006	VLDB	5.3387063e-05
8,586	Materialized View Selection for XQuery Workloads	2012	SIGMOD	5.2939333e-05
8,742	Satisfiability and Relevance for Queries over Active Documents	2009	PODS	5.2705676e-05
8,745	Conditional XPath, the first order complete XPath dialect*	2004	PODS	5.2705676e-05
9,133	Client-Based Access Control Management for XML documents	2004	VLDB	5.208561e-05
9,210	Towards Theory for Real-World Data	2022	PODS	5.1930561e-05
9,877	PAXQuery: Parallel Analytical XML Processing	2015	SIGMOD	5.1046184e-05
9,897	Cooperative XPath Caching	2008	SIGMOD	5.0998483e-05
9,904	Answering Tree Pattern Queries Using Views	2006	VLDB	5.0983308e-05
10,024	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	5.082116e-05
10,275	The (Almost) Complete Guide to Tree Pattern Containment	2015	PODS	5.0352713e-05
12,186	Containment of Shape Expression Schemas for RDF	2019	PODS	4.9605343e-05
12,276	Data Citation: Giving Credit Where Credit is Due	2018	SIGMOD	4.9605343e-05
12,374	Minimization of Tree Pattern Queries	2016	PODS	4.9605343e-05
12,665	Answering Queries using Views over Probabilistic XML: Complexity and Tractability	2012	VLDB	4.9605343e-05
12,723	Generating Efficient Execution Plans for Vertically Partitioned XML Databases	2011	VLDB	4.9605343e-05
12,873	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB	4.9605343e-05
12,966	Reasoning about XML Update Constraints	2007	PODS	4.9605343e-05
13,022	Structural Characterizations of the Semantics of XPath as Navigation Tool on a Document	2006	PODS	4.9605343e-05
13,134	Answering XPath Queries over Networks by Sending Minimal Views	2004	VLDB	4.9605343e-05
13,136	The NEXT Framework for Logical XQuery Optimization	2004	VLDB	4.9605343e-05

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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,830	Satisfiability of Downward XPath with Data Equality Tests	2009	PODS
2	1,606	Conjunctive Queries over Trees	2004	PODS
3	8,636	On XPath with Transitive Axes and Data Tests	2013	PODS
4	6,333	Containment of Nested XML Queries	2004	VLDB
5	1,983	XPath Satisfiability in the Presence of DTDs	2005	PODS
6	13,022	Structural Characterizations of the Semantics of XPath as Navigation Tool on a Document	2006	PODS
7	2,897	On the minimization of XPath queries	2003	VLDB
8	12,873	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
9	9,458	Decidable XPath Fragments in the Real World	2019	PODS
10	4,616	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS