Database Query Processing Using Finite Cursor Machines
- Martin Grohe ,
- Yuri Gurevich ,
- Dirk Leinders ,
- Nicole Schweikardt ,
- Jerzy Tyszkiewicz ,
- Jan Van den Bussche
Theory of Computing Systems |
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.
An earlier version appeared in: ICDT 2007, International Conference on Database Theory, Springer Lecture Notes in Computer Science 4353 (2007), 284-298.