DBSP: Automatic Incremental View Maintenance for Rich Query Languages

Summary: DBSP recasts IVM as stream differentiation over commutative groups, avoiding query-specific partial derivatives. Its four-operator, Lean-verified calculus heuristically incrementalizes rich programs spanning SQL, nested relations, aggregation, flatmap, recursion, and windows. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h72445947edb456d3
Venue: VLDB
Year: 2023
Pagerank: 7.1092596e-05
Overall Rank: 3,673 | 75.31%
DOI: 10.14778/3587136.3587137

Incoming Non-self Citations Over Time

Authors

1. Mihai Budiu (VMware)
2. Tej Chajed (VMware)
3. Frank McSherry (Materialize)
4. Leonid Ryzhyk (VMware)
5. Val Tannen (University of Pennsylvania)

BibTeX Citation

@article{budiu_vldb23,
        title = {{DBSP: Automatic Incremental View Maintenance for Rich Query Languages}},
        author = {Budiu, Mihai and Chajed, Tej and McSherry, Frank and Ryzhyk, Leonid and Tannen, Val},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {7},
        pages = {1601--1614},
        doi = {10.14778/3587136.3587137},
        url = {https://doi.org/10.14778/3587136.3587137},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,636	Physical Visualization Design: Decoupling Interface and System Design	2025	SIGMOD	5.7262507e-05
6,876	Insert-Only versus Insert-Delete in Dynamic Query Evaluation	2024	PODS	5.6586279e-05
9,180	Twisted Twin: A Collaborative and Competitive Memory Management Approach in HTAP Systems	2025	VLDB	5.2120789e-05
9,226	Streaming Democratized: Ease Across the Latency Spectrum with Delayed View Semantics and Snowflake Dynamic Tables	2025	SIGMOD	5.2056825e-05
9,648	Disaggregated State Management in Apache Flink 2.0	2025	VLDB	5.1453267e-05
9,995	Enzyme Demo: Incremental View Maintenance for Data Engineering	2026	VLDB	5.0979044e-05
10,149	Datalog with First-Class Facts	2025	VLDB	5.0715586e-05
10,377	Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations	2026	PODS	4.9793485e-05
10,544	Approximate Query Processing under Updates	2026	SIGMOD	4.9793485e-05
10,925	The Live Database: Firestore’s Scalable and Consistent Realtime Queries	2026	VLDB	4.9793485e-05
11,036	The Dataflow Model Revisited Or: That Feeling When You Realize Every Problem You've Been Solving Is a Database Problem	2026	VLDB	4.9793485e-05
11,382	Streaming View: An Efficient Data Processing Engine for Modern Real-time Data Warehouse of Alibaba Cloud	2025	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 21 of 21 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
17	Provenance Semirings	2007	PODS	0.00059752575
62	Maintaining Views Incrementally	1993	SIGMOD	0.00039045511
246	Deriving Production Rules for Incremental View Maintenance	1991	VLDB	0.00023212582
379	Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources	2018	SIGMOD	0.00019514689
388	Incremental Maintenance of Views with Duplicates	1995	SIGMOD	0.00019350381
442	Differential dataflow	2013	CIDR	0.00018210463
812	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013729015
978	Incremental Query Evaluation in a Ring of Databases	2010	PODS	0.00012731074
1,089	Incremental Maintenance of Externally Materialized Views	1996	VLDB	0.00012088658
2,523	Incremental Evaluation of Rules and its Relationship to Parallelism	1991	SIGMOD	8.3464708e-05
2,739	General Incremental Sliding-Window Aggregation	2015	VLDB	8.0721161e-05
3,112	Incremental View Maintenance with Triple Lock Factorization Benefits	2018	SIGMOD	7.6357579e-05
3,631	Efficient Maintenance of Materialized Mediated Views (Extended Abstract)	1995	SIGMOD	7.1495656e-05
3,873	DBToaster: A SQL Compiler for High-Performance Delta Processing in Main-Memory Databases	2009	VLDB	6.9539394e-05
4,400	Shared Arrangements: practical inter-query sharing for streaming dataflows	2020	VLDB	6.6151947e-05
4,940	Explaining Outputs in Modern Data Analytics	2016	VLDB	6.345789e-05
5,145	Conjunctive Queries with Inequalities Under Updates	2018	VLDB	6.2566119e-05
5,784	Maintenance of Stratified Databases Viewed as a Belief Revision System	1987	PODS	5.9961885e-05
6,219	Incremental View Maintenance For Collection Programming	2016	PODS	5.8471493e-05
6,386	Maintaining Acyclic Foreign-Key Joins under Updates	2020	SIGMOD	5.8040725e-05
8,560	Efficient Incrementialization of Correlated Nested Aggregate Queries using Relative Partial Aggregate Indexes (RPAI)	2022	SIGMOD	5.3142933e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,128	Programmable View Update Strategies on Relations	2020	VLDB
2	7,462	Update-Pattern-Aware Modeling and Processing of Continuous Queries	2005	SIGMOD
3	5,667	Enabling Incremental Query Re-Optimization	2016	SIGMOD
4	246	Deriving Production Rules for Incremental View Maintenance	1991	VLDB
5	62	Maintaining Views Incrementally	1993	SIGMOD
6	6,219	Incremental View Maintenance For Collection Programming	2016	PODS
7	388	Incremental Maintenance of Views with Duplicates	1995	SIGMOD
8	13,330	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB
9	978	Incremental Query Evaluation in a Ring of Databases	2010	PODS
10	5,038	Query Languages and Data Models for Database Sequences and Data Streams	2004	VLDB