4 papers
Tight Lower Bounds for Query Processing on Streaming and External Memory Data
Martin Grohe, Christoph Koch, Nicole Schweikardt
We study a clean machine model for external memory and stream processing. We show that the number of scans of the external data induces a strict hierarchy (as long as work space is…
Schema-based Scheduling of Event Processors and Buffer Minimization for Queries on Structured Data Streams
Christoph Koch, Stefanie Scherzinger, Nicole Schweikardt +1
We introduce an extension of the XQuery language, FluX, that supports event-based query processing and the conscious handling of main memory buffers. Purely event-based queries of…
An Ehrenfeucht-Fraisse Game Approach to Collapse Results in Database Theory
Nicole Schweikardt
We present a new Ehrenfeucht-Fraisse game approach to collapse results in database theory and we show that, in principle, this approach suffices to prove every natural generic coll…
Arithmetic, First-Order Logic, and Counting Quantifiers
Nicole Schweikardt
This paper gives a thorough overview of what is known about first-order logic with counting quantifiers and with arithmetic predicates. As a main theorem we show that Presburger ar…