Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/7740
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | ROBERTSON, Edward L. | - |
dc.contributor.author | LAWRENCE, Saxton V. | - |
dc.contributor.author | VAN GUCHT, Dirk | - |
dc.contributor.author | VANSUMMEREN, Stijn | - |
dc.date.accessioned | 2008-01-04T07:59:53Z | - |
dc.date.available | 2008-01-04T07:59:53Z | - |
dc.date.issued | 2007 | - |
dc.identifier.citation | Database Theory - ICDT 2007. p. 344-358 | - |
dc.identifier.isbn | 3-540-69269-X | - |
dc.identifier.issn | 1611-3349 | - |
dc.identifier.uri | http://hdl.handle.net/1942/7740 | - |
dc.description.abstract | XML query languages need to provide some mechanism to inspect and manipulate nodes at all levels of an input tree. In this paper we investigate the expressive power provided in this regard by structural recursion. 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. Although this restriction is semantical in nature, and therefore undecidable, we provide an effective syntax. We also give corresponding results for list-based complex objects. | - |
dc.language.iso | en | - |
dc.publisher | Springer | - |
dc.relation.ispartofseries | Lecture Notes in Computer Science | - |
dc.subject.other | Computer science, structural recursion, nested relational calculus, XQuery, intrinsic computational complexity, polynomial time | - |
dc.title | Structural Recursion on Ordered Trees and List-Based Complex Objects | - |
dc.type | Proceedings Paper | - |
local.bibliographicCitation.authors | Schwentick, Thomas | - |
local.bibliographicCitation.authors | Suciu, Dan | - |
local.bibliographicCitation.conferencedate | 2007 | - |
local.bibliographicCitation.conferencename | International Conference on Database Theory | - |
dc.bibliographicCitation.conferencenr | 11 | - |
local.bibliographicCitation.conferenceplace | Barcelona, SPAIN, JAN 10-12, 2007 | - |
dc.identifier.epage | 358 | - |
dc.identifier.spage | 344 | - |
local.bibliographicCitation.jcat | C1 | - |
local.type.refereed | Refereed | - |
local.type.specified | Proceedings Paper | - |
local.relation.ispartofseriesnr | 4353 | - |
dc.bibliographicCitation.oldjcat | C1 | - |
dc.identifier.doi | 10.1007/11965893_24 | - |
dc.identifier.isi | 000244800500024 | - |
local.bibliographicCitation.btitle | Database Theory - ICDT 2007 | - |
item.accessRights | Open Access | - |
item.fulltext | With Fulltext | - |
item.fullcitation | ROBERTSON, Edward L.; LAWRENCE, Saxton V.; VAN GUCHT, Dirk & VANSUMMEREN, Stijn (2007) Structural Recursion on Ordered Trees and List-Based Complex Objects. In: Database Theory - ICDT 2007. p. 344-358. | - |
item.contributor | ROBERTSON, Edward L. | - |
item.contributor | LAWRENCE, Saxton V. | - |
item.contributor | VAN GUCHT, Dirk | - |
item.contributor | VANSUMMEREN, Stijn | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
barcelona.pdf | Non Peer-reviewed author version | 232.55 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
1
checked on Sep 2, 2020
Page view(s)
68
checked on Sep 7, 2022
Download(s)
204
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.