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.2478748e-05
Overall Rank: 4,362 | 69.69%
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,882	High-Performance Complex Event Processing over XML Streams	2012	SIGMOD	5.8523303e-05
6,153	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS	5.1796878e-05
9,104	Decidable XPath Fragments in the Real World	2019	PODS	4.3911866e-05
9,889	The (Almost) Complete Guide to Tree Pattern Containment	2015	PODS	4.2576366e-05
12,177	The Complexity of Text-Preserving XML Transformations	2011	PODS	4.1905499e-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.00021654356
1,662	Conjunctive Queries over Trees	2004	PODS	0.00010966423
1,933	XPath Satisfiability in the Presence of DTDs	2005	PODS	0.00010049404
3,852	The Expressivity of XPath with Transitive Closure*	2006	PODS	6.6993728e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,089	On the minimization of Xpath queries	2003	VLDB	7.5938563e-05
1,662	Conjunctive Queries over Trees	2004	PODS	0.00010966423
6,293	Containment of Nested XML Queries	2004	VLDB	5.1206121e-05
12,348	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB	4.1905499e-05
6,153	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS	5.1796878e-05
3,852	The Expressivity of XPath with Transitive Closure*	2006	PODS	6.6993728e-05
9,104	Decidable XPath Fragments in the Real World	2019	PODS	4.3911866e-05
1,933	XPath Satisfiability in the Presence of DTDs	2005	PODS	0.00010049404
2,250	The Complexity of XPath Query Evaluation	2003	PODS	9.1949563e-05
499	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00021654356