# Change Propagation Without Joins

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jan 2023.

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

- [Selective Use of Yannakakis' Algorithm to Improve Query Performance: Machine Learning to the Rescue](https://mlsanity.com/paper/2502.20233/) (2025)

## Abstract (arXiv)

We revisit the classical change propagation framework for query evaluation under updates. The standard framework takes a query plan and materializes the intermediate views, which incurs high polynomial costs in both space and time, with the join operator being the culprit. In this paper, we propose a new change propagation framework without joins, thus naturally avoiding this polynomial blowup. Meanwhile, we show that the new framework still supports constant-delay enumeration of both the deltas and the full query results, the same as in the standard framework. Furthermore, we provide a quantitative analysis of its update cost, which not only recovers many recent theoretical results on the problem, but also yields an effective approach to optimizing the query plan. The new framework is also easy to be integrated into an existing streaming database system. Experimental results show that our system prototype, implemented using Flink DataStream API, significantly outperforms other systems in terms of space, time, and latency.