XPath Evaluation in Linear Time

Summary: Studying an XPath fragment restricted to attribute-equality tests, the paper shows that for any fixed unary query the set of answer nodes can be computed in time linear in the document size. Establishes optimal data-complexity (linear-time) evaluation and clarifies the tractability boundary for XPath with attribute equalities. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1463
Venue: PODS
Year: 2008
Pagerank: -
Overall Rank: 13,753 | 5.65%
DOI: 10.1145/1376916.1376951

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Mikołaj Bojańczyk (University of Warsaw)
2. Paweł Parys (University of Warsaw)

BibTeX Citation

@inproceedings{bojanczyk_pods08,
        address = {New York, NY, USA},
        series = {{PODS} '08},
        title = {{XPath Evaluation in Linear Time}},
        url = {https://dl.acm.org/doi/10.1145/1376916.1376951},
        doi = {10.1145/1376916.1376951},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Bojańczyk, Mikołaj and Parys, Paweł},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,371	XPath Evaluation in Linear Time with Polynomial Combined Complexity	2009	PODS	6.2427638e-05
13,683	Efficient Evaluation for a Temporal Logic on Changing XML Documents	2011	PODS	-

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,534	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
2	2,817	On the minimization of XPath queries	2003	VLDB
3	3,659	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS
4	5,247	Buffering in Query Evaluation over XML Streams	2005	PODS
5	4,537	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB
6	13,786	Polynomial Time Fragments of XPath with Variables	2007	PODS
7	2,132	The Complexity of XPath Query Evaluation	2003	PODS
8	12,633	Efficient Algorithms for Evaluating XPath over Streams	2007	SIGMOD
9	666	Efficient Algorithms for Processing XPath Queries	2002	VLDB
10	5,371	XPath Evaluation in Linear Time with Polynomial Combined Complexity	2009	PODS