Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/614
Title: On the power of walking for querying tree-structured data
Authors: NEVEN, Frank 
Issue Date: 2002
Publisher: ACM Press
Source: Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems.
Abstract: XSLT is the prime example of an XML query language based on tree-walking. Indeed, stripped down, XSLT is just a tree-walking tree-transducer equipped with registers and look-ahead. Motivated by this connection, we want to pinpoint the computational power of devices based on tree-walking. We show that in the absence of unique identifiers even very powerful extensions of the tree-walking paradigm are not relationally complete. That is, these extensions do not capture all of first-order logic. In contrast, when unique identifiers are available, we show that various restrictions allow to capture LOGSPACE, PTIME, PSPACE, and EXPTIME. These complexity classes are defined w.r.t. a Turing machine model working directly on (attributed) trees. When no attributes are present, relational storage does not add power; whether look-ahead adds power is related to the open question whether tree-walking captures the regular tree languages.
Document URI: http://hdl.handle.net/1942/614
Link to publication: http://doi.acm.org/10.1145/543613.543624
ISBN: 1-58113-507-6
Category: C1
Type: Proceedings Paper
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
23 walkingpods.pdf285.57 kBAdobe PDFView/Open
Show full item record

Page view(s)

44
checked on May 25, 2022

Download(s)

210
checked on May 25, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.