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: h74c3bc40dadfdcca
Venue: VLDB
Year: 2002
Pagerank: 0.0001483008
Overall Rank: 680 | 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
760	Stream Processing of XPath Queries with Predicates	2003	SIGMOD	0.00014154656
1,154	The Lixto Data Extraction Project - Back and Forth between Theory and Practice	2004	PODS	0.0001178814
1,599	Conjunctive Queries over Trees	2004	PODS	0.00010112914
1,978	XPath Satisfiability in the Presence of DTDs	2005	PODS	9.275331e-05
2,179	The Complexity of XPath Query Evaluation	2003	PODS	8.9111534e-05
2,526	Path Queries on Compressed XML	2003	VLDB	8.3393779e-05
2,680	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB	8.1393624e-05
2,817	Secure XML Querying with Security Views	2004	SIGMOD	7.9732421e-05
2,883	On the minimization of XPath queries	2003	VLDB	7.9096688e-05
2,935	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	7.8361406e-05
3,752	Dynamic XML Documents with Distribution and Replication	2003	SIGMOD	7.0485802e-05
3,889	Mixed Mode XML Query Processing	2003	VLDB	6.9415444e-05
4,136	Two-Variable Logic on Data Trees and XML Reasoning	2006	PODS	6.7843007e-05
4,189	Processing Queries on Tree-Structured Data Efficiently	2006	PODS	6.7427859e-05
4,810	On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values	2005	PODS	6.4049669e-05
5,175	Querying in the Age of Graph Databases and Knowledge Graphs	2021	SIGMOD	6.2402956e-05
5,466	Distributed Query Evaluation with Performance Guarantees	2007	SIGMOD	6.1192481e-05
5,494	Lazy Query Evaluation for Active XML	2004	SIGMOD	6.1065309e-05
5,594	Using Partial Evaluation in Distributed Query Evaluation	2006	VLDB	6.0706959e-05
6,269	XML Transformation by Tree-Walking Transducers with Invisible Pebbles	2007	PODS	5.8277954e-05
6,574	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS	5.7430454e-05
7,599	XQuery Optimization	2003	VLDB	5.4854551e-05
8,000	Covering Indexes for XML Queries: Bisimulation - Simulation = Negation	2003	VLDB	5.4086285e-05
8,027	Cost-Sensitive Reordering of Navigational Primitives	2005	SIGMOD	5.4029105e-05
8,189	SXPath - Extending XPath towards Spatial Querying on Web Documents	2011	VLDB	5.379443e-05
8,725	Conditional XPath, the first order complete XPath dialect*	2004	PODS	5.2880532e-05
12,773	XPath Whole Query Optimization	2010	VLDB	4.9769913e-05
12,929	Efficient Algorithms for Evaluating XPath over Streams	2007	SIGMOD	4.9769913e-05
12,930	Querying XML with Update Syntax	2007	SIGMOD	4.9769913e-05
12,985	Locking-Aware Structural Join Operators for XML Query Processing	2006	SIGMOD	4.9769913e-05
13,094	Taming XPath Queries by Minimizing Wildcard Steps	2004	VLDB	4.9769913e-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
179	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00026617591
193	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00025647819
409	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00018859247
1,407	Typechecking for XML Transformers	2000	PODS	0.00010744741
2,226	Monadic Datalog and the Expressive Power of Languages for Web Information Extraction	2002	PODS	8.8050743e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	958	XPath Queries on Streaming Data	2003	SIGMOD
2	5,373	Buffering in Query Evaluation over XML Streams	2005	PODS
3	2,715	A Framework for Using Materialized XPath Views in XML Query Processing	2004	VLDB
4	12,830	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
5	3,747	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS
6	2,883	On the minimization of XPath queries	2003	VLDB
7	12,929	Efficient Algorithms for Evaluating XPath over Streams	2007	SIGMOD
8	14,069	XPath Evaluation in Linear Time	2008	PODS
9	2,179	The Complexity of XPath Query Evaluation	2003	PODS
10	5,505	XPath Evaluation in Linear Time with Polynomial Combined Complexity	2009	PODS