The Complexity of Query Containment in Expressive Fragments of XPath 2.0

Summary: Complexity map for CoreXPath+{intersection,equality,complementation,for‑loops,TC}: cases range EXPTIME, 2‑EXPTIME, to non‑elementary. Intersection typically adds one exponential; equality/TC usually inert (TC makes downward+intersection EXPSPACE→2‑EXPTIME); complementation/for‑loops cause non‑elementary; results extend to DTDs and satisfiability. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1417
Venue: PODS
Year: 2007
Pagerank: 6.2538592e-05
Overall Rank: 4,366 | 69.63%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Balder ten Cate
2. Carsten Lutz

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,880	High-Performance Complex Event Processing over XML Streams	2012	SIGMOD	5.8573822e-05
6,150	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS	5.1846373e-05
9,105	Decidable XPath Fragments in the Real World	2019	PODS	4.3953995e-05
9,890	The (Almost) Complete Guide to Tree Pattern Containment	2015	PODS	4.2617199e-05
12,169	The Complexity of Text-Preserving XML Transformations	2011	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
499	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.000216753
1,663	Conjunctive Queries over Trees	2004	PODS	0.00010977096
1,929	XPath Satisfiability in the Presence of DTDs	2005	PODS	0.00010058897
3,851	The Expressivity of XPath with Transitive Closure*	2006	PODS	6.7057867e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,084	On the minimization of Xpath queries	2003	VLDB	7.6011919e-05
1,663	Conjunctive Queries over Trees	2004	PODS	0.00010977096
6,294	Containment of Nested XML Queries	2004	VLDB	5.1255418e-05
12,340	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB	4.1945683e-05
6,150	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS	5.1846373e-05
3,851	The Expressivity of XPath with Transitive Closure*	2006	PODS	6.7057867e-05
9,105	Decidable XPath Fragments in the Real World	2019	PODS	4.3953995e-05
1,929	XPath Satisfiability in the Presence of DTDs	2005	PODS	0.00010058897
2,248	The Complexity of XPath Query Evaluation	2003	PODS	9.2038466e-05
499	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.000216753