# DBSP: Automatic Incremental View Maintenance for Rich Query Languages

arXiv: https://arxiv.org/abs/2203.16684 · HTML: https://mlsanity.com/paper/2203.16684/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Mar 2022.

## Built on by (most cited first, 3 of 3)

- [Activity Frames: Deterministic Screen-Activity Compilation for Agent Memory and Replay](https://mlsanity.com/paper/2608.05784/) (2026)
- [Parsing the Stream: A Live Trace Model for Long-Horizon Agents and Their Observers](https://mlsanity.com/paper/2609.01466/) (2026)
- [ArrivalBench: Agent-Generated Data Pipelines Are Correct Once and Wrong Under Time](https://mlsanity.com/paper/2610.02363/) (2026)

## Abstract (arXiv)

Incremental view maintenance has been for a long time a central problem in database theory. Many solutions have been proposed for restricted classes of database languages, such as the relational algebra, or Datalog. These techniques do not naturally generalize to richer languages. In this paper we give a general solution to this problem in 3 steps: (1) we describe a simple but expressive language called DBSP for describing computations over data streams; (2) we give a general algorithm for solving the incremental view maintenance problem for arbitrary DBSP programs, and (3) we show how to model many rich database query languages (including the full relational queries, grouping and aggregation, monotonic and non-monotonic recursion, and streaming aggregation) using DBSP. As a consequence, we obtain efficient incremental view maintenance techniques for all these rich languages.