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 | Size | Format | |
---|---|---|---|---|
23 walkingpods.pdf | 285.57 kB | Adobe PDF | View/Open |
Page view(s)
64
checked on Oct 30, 2023
Download(s)
284
checked on Oct 30, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.