  Incremental processing is widely-adopted in many applications, ranging from
incremental view maintenance, stream computing, to recently emerging
progressive data warehouse and intermittent query processing. Despite many
algorithms developed on this topic, none of them can produce an incremental
plan that always achieves the best performance, since the optimal plan is data
dependent. In this paper, we develop a novel cost-based optimizer framework,
called Tempura, for optimizing incremental data processing. We propose an
incremental query planning model called TIP based on the concept of
time-varying relations, which can formally model incremental processing in its
most general form. We give a full specification of Tempura, which can not only
unify various existing techniques to generate an optimal incremental plan, but
also allow the developer to add their rewrite rules. We study how to explore
the plan space and search for an optimal incremental plan. We conduct a
thorough experimental evaluation of Tempura in various incremental processing
scenarios to show its effectiveness and efficiency.
