Please use this identifier to cite or link to this item:
|Title:||Finite cursor machines in database query processing||Authors:||VAN DEN BUSSCHE, Jan||Issue Date:||2004||Publisher:||SPRINGER-VERLAG BERLIN||Source:||ABSTRACT STATE MACHINES 2004: ADVANCES IN THEORY AND PRACTICE, PROCEEDINGS. p. 61-61||Series/Report:||LECTURE NOTES IN COMPUTER SCIENCE||Series/Report no.:||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.||Document URI:||http://hdl.handle.net/1942/2821||ISSN:||0302-9743||DOI:||10.1007/b98118||ISI #:||000221899300005||Category:||A1||Type:||Journal Contribution||Validations:||ecoom 2005|
|Appears in Collections:||Research publications|
Show full item record
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.