Change Propagation Without Joins

Qichen Wang, Xiao Hu, Binyang Dai, Ke Yi

Research output: Contribution to journalConference articlepeer-review


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.

Original languageEnglish
Pages (from-to)1046-1058
Number of pages13
JournalProceedings of the VLDB Endowment
Issue number5
Publication statusPublished - 1 Jan 2023
Event49th International Conference on Very Large Data Bases, VLDB 2023 - Vancouver, Canada
Duration: 28 Aug 20231 Sept 2023

Scopus Subject Areas

  • Computer Science (miscellaneous)
  • Computer Science(all)


Dive into the research topics of 'Change Propagation Without Joins'. Together they form a unique fingerprint.

Cite this