On the Power of Walking for Querying Tree-Structured Data
Summary: Analyzes computational power of tree-walking devices (XSLT-like); shows that without unique node IDs even very powerful extensions are not relationally complete (do not capture FO). With unique IDs, natural restrictions characterize LOGSPACE, PTIME, PSPACE and EXPTIME over attributed trees; without attributes relational storage adds no power and the impact of lookâahead is tied to the open question whether tree-walking captures the regular tree languages. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Frank Neven
Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 12,169 | The Complexity of Text-Preserving XML Transformations | 2011 | PODS | 4.1945683e-05 |
| 12,430 | Expressiveness and Complexity of XML Publishing Transducers | 2007 | PODS | 4.1945683e-05 |
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 | Pagerank |
|---|---|---|---|---|
| 3,086 | Tree Logical Classes for Efficient Evaluation of XQuery | 2004 | SIGMOD | 7.596041e-05 |
| 1,848 | Typing and Querying XML Documents: Some Complexity Bounds | 2003 | PODS | 0.00010330772 |
| 2,855 | Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach | 2003 | VLDB | 8.0059865e-05 |
| 12,215 | Certain Answers for XML Queries | 2010 | PODS | 4.1945683e-05 |
| 3,610 | From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery | 2003 | VLDB | 6.9196208e-05 |
| 9,178 | Tree-Pattern Queries on a Lightweight XML Processor | 2005 | VLDB | 4.3828426e-05 |
| 3,117 | Processing Queries on Tree-Structured Data Efficiently | 2006 | PODS | 7.5407318e-05 |
| 12,430 | Expressiveness and Complexity of XML Publishing Transducers | 2007 | PODS | 4.1945683e-05 |
| 6,150 | XPath, Transitive Closure Logic, and Nested Tree Walking Automata | 2008 | PODS | 5.1846373e-05 |
| 1,663 | Conjunctive Queries over Trees | 2004 | PODS | 0.00010977096 |