Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/7740
Title: Structural Recursion on Ordered Trees and List-Based Complex Objects
Authors: ROBERTSON, Edward L.
LAWRENCE, Saxton V.
VAN GUCHT, Dirk
VANSUMMEREN, Stijn 
Issue Date: 2007
Publisher: Springer
Source: Database Theory - ICDT 2007. p. 344-358
Series/Report: Lecture Notes in Computer Science
Series/Report no.: 4353
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.
Keywords: Computer science, structural recursion, nested relational calculus, XQuery, intrinsic computational complexity, polynomial time
Document URI: http://hdl.handle.net/1942/7740
ISBN: 3-540-69269-X
DOI: 10.1007/11965893_24
ISI #: 000244800500024
Category: C1
Type: Proceedings Paper
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
barcelona.pdfPreprint232.55 kBAdobe PDFView/Open
Show full item record

SCOPUSTM   
Citations

1
checked on Sep 2, 2020

Page view(s)

62
checked on May 18, 2022

Download(s)

186
checked on May 18, 2022

Google ScholarTM

Check

Altmetric


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