The Complexity of XPath Query Evaluation

Summary: Precisely characterizes XPath 1.0 complexity: data and query complexity lie in low, highly parallelizable classes, but combined complexity is PTIME-hard. Identifies a large practical fragment that is LOGCFL-complete (hence in NC2), isolating sources of hardness and enabling parallel evaluation for common patterns. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1290
Venue: PODS
Year: 2003
Pagerank: 9.2038466e-05
Overall Rank: 2,248 | 84.37%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,848	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	0.00010330772
3,695	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS	6.8345021e-05
3,851	The Expressivity of XPath with Transitive Closure*	2006	PODS	6.7057867e-05
4,568	Rewriting XPath Queries Using Materialized Views	2005	VLDB	6.0784118e-05
4,611	On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values	2005	PODS	6.0488752e-05
4,625	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.0406081e-05
5,248	Buffering in Query Evaluation over XML Streams	2005	PODS	5.6056584e-05
6,300	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	5.1223169e-05
6,872	XQuery Optimization	2003	VLDB	4.8991822e-05
7,298	Structured Materialized Views for XML Queries	2007	VLDB	4.770411e-05
7,762	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB	4.6583829e-05
8,241	Machine Models and Lower Bounds for Query Processing	2007	PODS	4.5519176e-05
8,314	Conditional XPath, the first order complete XPath dialect*	2004	PODS	4.5435639e-05
12,439	Efficient Algorithms for Evaluating XPath over Streams	2007	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
713	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00017731096
1,848	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	0.00010330772

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,317	Distributed Query Evaluation with Performance Guarantees	2007	SIGMOD	5.5719038e-05
13,553	XPath Evaluation in Linear Time	2008	PODS	-
5,248	Buffering in Query Evaluation over XML Streams	2005	PODS	5.6056584e-05
12,340	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB	4.1945683e-05
3,695	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS	6.8345021e-05
12,439	Efficient Algorithms for Evaluating XPath over Streams	2007	SIGMOD	4.1945683e-05
3,084	On the minimization of Xpath queries	2003	VLDB	7.6011919e-05
4,366	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS	6.2538592e-05
713	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00017731096
4,663	XPath Evaluation in Linear Time with Polynomial Combined Complexity	2009	PODS	6.0128493e-05