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: 1289
Venue: PODS
Year: 2003
Pagerank: 9.119436e-05
Overall Rank: 2,132 | 85.38%
DOI: 10.1145/773153.773171

Incoming Non-self Citations Over Time

Authors

1. Georg Gottlob (Vienna University of Technology)
2. Christoph Koch (University of Edinburgh)
3. Reinhard Pichler (Vienna University of Technology)

BibTeX Citation

@inproceedings{gottlob_pods03,
        address = {New York, NY, USA},
        series = {{PODS} '03},
        title = {{The Complexity of XPath Query Evaluation}},
        url = {https://dl.acm.org/doi/10.1145/773153.773171},
        doi = {10.1145/773153.773171},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Gottlob, Georg and Koch, Christoph and Pichler, Reinhard},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,864	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	8.0195639e-05
3,659	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS	7.2176232e-05
3,711	The Expressivity of XPath with Transitive Closure*	2006	PODS	7.1778094e-05
3,976	Rewriting XPath Queries Using Materialized Views	2005	VLDB	6.9785468e-05
4,537	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.6417534e-05
4,702	On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values	2005	PODS	6.5549225e-05
5,247	Buffering in Query Evaluation over XML Streams	2005	PODS	6.3009176e-05
5,936	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	6.0353909e-05
7,267	Structured Materialized Views for XML Queries	2007	VLDB	5.6597556e-05
7,460	XQuery Optimization	2003	VLDB	5.6119031e-05
7,664	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB	5.5720259e-05
8,488	Machine Models and Lower Bounds for Query Processing	2007	PODS	5.4153038e-05
8,550	Conditional XPath, the first order complete XPath dialect*	2004	PODS	5.4119882e-05
12,633	Efficient Algorithms for Evaluating XPath over Streams	2007	SIGMOD	5.093636e-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
666	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00015166582
2,864	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	8.0195639e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,336	Distributed Query Evaluation with Performance Guarantees	2007	SIGMOD
2	13,753	XPath Evaluation in Linear Time	2008	PODS
3	5,247	Buffering in Query Evaluation over XML Streams	2005	PODS
4	12,534	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
5	3,659	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS
6	12,633	Efficient Algorithms for Evaluating XPath over Streams	2007	SIGMOD
7	2,817	On the minimization of XPath queries	2003	VLDB
8	4,504	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS
9	666	Efficient Algorithms for Processing XPath Queries	2002	VLDB
10	5,371	XPath Evaluation in Linear Time with Polynomial Combined Complexity	2009	PODS