www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/2821

Title: Finite cursor machines in database query processing
Authors: VAN DEN BUSSCHE, Jan
Issue Date: 2004
Publisher: SPRINGER-VERLAG BERLIN
Citation: ABSTRACT STATE MACHINES 2004: ADVANCES IN THEORY AND PRACTICE, PROCEEDINGS. p. 61-61
Series/Report: LECTURE NOTES IN COMPUTER SCIENCE, 3052
Abstract: A database system is often concerned with the processing of lists of tuples in a single scan, using constant amount of memory. In classical relational query processing, many of the relational algebra operators have simple single-scan implementations on sorted lists. In more recent data stream systems, single scan processing is a must. Data warehousing software tools, such as those by Aruna, support database querying using index structures for text searching. To improve our understanding of the possibilities and limitations of single-scan, constant-memory processing on lists of tuples, we define and study the abstract model of finite cursor machines are, of course, instantiations of sequential ASMs. In conjunction with sorting, finite cursor machines can evaluate a wide class of relational algebra expressions; in particular, they can compute all database queries expressible using semijoins, rather than full joins. Challenging problems include delineating the precise computing power of finite cursor machines with sorting, and minimizing the number of sorting operations that are needed. We discuss these problems and present some preliminary results.
Notes: Limburgs Univ Ctr, B-3610 Diepenbeek, Belgium.Van den Bussche, J, Limburgs Univ Ctr, B-3610 Diepenbeek, Belgium.
URI: http://hdl.handle.net/1942/2821
DOI: 10.1007/b98118
ISI #: 000221899300005
ISSN: 0302-9743
Category: A1
Type: Journal Contribution
Validation: ecoom, 2005
Appears in Collections: Research publications

Files in This Item:

There are no files associated with this item.

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