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/dataset: 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

Google ScholarTM

Check

Altmetric


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