Database Query Processing Using Finite Cursor Machines

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

Title:	Database Query Processing Using Finite Cursor Machines
Authors:	Grohe, Martin Gurevich, Yuri LEINDERS, Dirk Schweikardt, Nicole Tyszkiewicz, Jerzy VAN DEN BUSSCHE, Jan
Issue Date:	2009
Publisher:	Springer New York
Source:	THEORY OF COMPUTING SYSTEMS, 44(4). p. 533-560
Abstract:	We introduce a new abstract model of database query processing, finite cursor machines, that incorporates certain data streaming aspects. The model describes quite faithfully what happens in so-called “one-pass” and “two-pass query processing”. Technically, the model is described in the framework of abstract state machines. Our main results are upper and lower bounds for processing relational algebra queries in this model, specifically, queries of the semijoin fragment of the relational algebra.
Notes:	(1) Humboldt-University Berlin, Berlin, Germany (2) Microsoft Research, Redmond, WA, USA (3) Hasselt University and Transnational University of Limburg, Diepenbeek, Belgium (4) University of Warsaw, Warsaw, Poland
Keywords:	Database, Relational algebra, Semijoin, Query processing
Document URI:	http://hdl.handle.net/1942/10659
Link to publication/dataset:	http://hdl.handle.net/1942/7847
ISSN:	1432-4350
e-ISSN:	1433-0490
DOI:	10.1007/s00224-008-9137-7
ISI #:	000265399700003
Category:	A1
Type:	Journal Contribution
Validations:	ecoom 2010
Appears in Collections:	Research publications

Check