Efficient Algorithms for Processing XPath Queries

Summary: Empirical analysis: popular XPath processors exhibit exponential worst-case query time. Introduces main-memory algorithms with polynomial-time combined evaluation and two XPath fragments enabling linear-time query processing. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9027
Venue: VLDB
Year: 2002
Pagerank: 0.00015166582
Overall Rank: 666 | 95.44%
DOI: 10.1016/B978-155860869-6/50017-2

Incoming Non-self Citations Over Time

Authors

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

BibTeX Citation

@article{gottlob_vldb02,
        title = {{Efficient Algorithms for Processing XPath Queries}},
        author = {Gottlob, Georg and Koch, Christoph and Pichler, Reinhard},
        journal = {PVLDB},
        series = {{VLDB} '02},
        doi = {10.1016/B978-155860869-6/50017-2},
        url = {https://doi.org/10.1016/B978-155860869-6/50017-2},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 31 of 31 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
738	Stream Processing of XPath Queries with Predicates	2003	SIGMOD	0.00014484337
1,131	The Lixto Data Extraction Project - Back and Forth between Theory and Practice	2004	PODS	0.00012044716
1,564	Conjunctive Queries over Trees	2004	PODS	0.00010349456
1,916	XPath Satisfiability in the Presence of DTDs	2005	PODS	9.4878711e-05
2,132	The Complexity of XPath Query Evaluation	2003	PODS	9.119436e-05
2,472	Path Queries on Compressed XML	2003	VLDB	8.5327655e-05
2,625	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB	8.3300135e-05
2,757	Secure XML Querying with Security Views	2004	SIGMOD	8.1601016e-05
2,817	On the minimization of XPath queries	2003	VLDB	8.0945626e-05
2,864	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	8.0195639e-05
3,667	Dynamic XML Documents with Distribution and Replication	2003	SIGMOD	7.2133927e-05
3,814	Mixed Mode XML Query Processing	2003	VLDB	7.1026815e-05
4,071	Two-Variable Logic on Data Trees and XML Reasoning	2006	PODS	6.927159e-05
4,107	Processing Queries on Tree-Structured Data Efficiently	2006	PODS	6.8973582e-05
4,702	On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values	2005	PODS	6.5549225e-05
5,336	Distributed Query Evaluation with Performance Guarantees	2007	SIGMOD	6.2612462e-05
5,360	Lazy Query Evaluation for Active XML	2004	SIGMOD	6.2487273e-05
5,453	Querying in the Age of Graph Databases and Knowledge Graphs	2021	SIGMOD	6.2137771e-05
5,458	Using Partial Evaluation in Distributed Query Evaluation	2006	VLDB	6.2115011e-05
6,137	XML Transformation by Tree-Walking Transducers with Invisible Pebbles	2007	PODS	5.9643797e-05
6,442	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS	5.8776391e-05
7,460	XQuery Optimization	2003	VLDB	5.6119031e-05
7,836	Covering Indexes for XML Queries: Bisimulation - Simulation = Negation	2003	VLDB	5.5353696e-05
7,864	Cost-Sensitive Reordering of Navigational Primitives	2005	SIGMOD	5.5294867e-05
8,022	SXPath - Extending XPath towards Spatial Querying on Web Documents	2011	VLDB	5.5055198e-05
8,550	Conditional XPath, the first order complete XPath dialect*	2004	PODS	5.4119882e-05
12,476	XPath Whole Query Optimization	2010	VLDB	5.093636e-05
12,633	Efficient Algorithms for Evaluating XPath over Streams	2007	SIGMOD	5.093636e-05
12,634	Querying XML with Update Syntax	2007	SIGMOD	5.093636e-05
12,689	Locking-Aware Structural Join Operators for XML Query Processing	2006	SIGMOD	5.093636e-05
12,798	Taming XPath Queries by Minimizing Wildcard Steps	2004	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
175	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00027226333
187	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00026138589
395	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00019298983
1,372	Typechecking for XML Transformers	2000	PODS	0.00010994864
2,180	Monadic Datalog and the Expressive Power of Languages for Web Information Extraction	2002	PODS	9.0110009e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	928	XPath Queries on Streaming Data	2003	SIGMOD
2	5,247	Buffering in Query Evaluation over XML Streams	2005	PODS
3	2,658	A Framework for Using Materialized XPath Views in XML Query Processing	2004	VLDB
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	2,817	On the minimization of XPath queries	2003	VLDB
7	12,633	Efficient Algorithms for Evaluating XPath over Streams	2007	SIGMOD
8	13,753	XPath Evaluation in Linear Time	2008	PODS
9	2,132	The Complexity of XPath Query Evaluation	2003	PODS
10	5,371	XPath Evaluation in Linear Time with Polynomial Combined Complexity	2009	PODS