Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/11406
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Robertson, Edward L. | - |
dc.contributor.author | Saxton, Lawrence V. | - |
dc.contributor.author | Van Gucht, Dirk | - |
dc.contributor.author | VANSUMMEREN, Stijn | - |
dc.date.accessioned | 2011-01-03T18:21:02Z | - |
dc.date.available | NO_RESTRICTION | - |
dc.date.available | 2011-01-03T18:21:02Z | - |
dc.date.issued | 2009 | - |
dc.identifier.citation | THEORY OF COMPUTING SYSTEMS, 44 (4). p. 590-619 | - |
dc.identifier.issn | 1432-4350 | - |
dc.identifier.uri | http://hdl.handle.net/1942/11406 | - |
dc.description.abstract | XML query languages need to provide some mechanism to inspect and manipulate nodes at all levels of an input tree. We investigate the expressive power provided in this regard by structural recursion. In particular, we show that the combination of vertical recursion down a tree combined with horizontal recursion across a list of trees gives rise to a robust class of transformations: it captures the class of all primitive recursive queries. Since queries are expected to be computable in at most polynomial time for all practical purposes, we next identify a restriction of structural recursion that captures the polynomial time queries. We also give corresponding results for list-based complex objects. | - |
dc.language.iso | en | - |
dc.publisher | SPRINGER | - |
dc.subject.other | Structural recursion; Primitive recursion; XML; Complex objects; Database | - |
dc.subject.other | Structural recursion; Primitive recursion; XML; Complex objects; Database | - |
dc.title | Structural Recursion as a Query Language on Lists and Ordered Trees | - |
dc.type | Journal Contribution | - |
dc.identifier.epage | 619 | - |
dc.identifier.issue | 4 | - |
dc.identifier.spage | 590 | - |
dc.identifier.volume | 44 | - |
local.format.pages | 30 | - |
local.bibliographicCitation.jcat | A1 | - |
dc.description.notes | [Vansummeren, Stijn] Hasselt Univ, B-3560 Diepenbeek, Belgium. [Vansummeren, Stijn] Translat Univ Limburg, B-3560 Diepenbeek, Belgium. [Saxton, Lawrence V.] Univ Regina, Regina, SK S4S 0A2, Canada. [Robertson, Edward L.; Van Gucht, Dirk] Indiana Univ, Bloomington, IN USA. edrbtsn@cs.indiana.edu; saxton@cs.uregina.ca; vgucht@cs.indiana.edu; stijn.vansummeren@uhasselt.be | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
dc.bibliographicCitation.oldjcat | A1 | - |
dc.identifier.doi | 10.1007/s00224-008-9110-5 | - |
dc.identifier.isi | 000265399700005 | - |
item.fulltext | No Fulltext | - |
item.accessRights | Closed Access | - |
item.validation | ecoom 2010 | - |
item.contributor | Robertson, Edward L. | - |
item.contributor | Saxton, Lawrence V. | - |
item.contributor | Van Gucht, Dirk | - |
item.contributor | VANSUMMEREN, Stijn | - |
item.fullcitation | Robertson, Edward L.; Saxton, Lawrence V.; Van Gucht, Dirk & VANSUMMEREN, Stijn (2009) Structural Recursion as a Query Language on Lists and Ordered Trees. In: THEORY OF COMPUTING SYSTEMS, 44 (4). p. 590-619. | - |
crisitem.journal.issn | 1432-4350 | - |
crisitem.journal.eissn | 1433-0490 | - |
Appears in Collections: | Research publications |
SCOPUSTM
Citations
4
checked on Sep 2, 2020
WEB OF SCIENCETM
Citations
3
checked on Sep 28, 2024
Page view(s)
108
checked on May 30, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.