Incremental Query Evaluation in a Ring of Databases

Summary: Introduce a ring-of-databases algebra and polynomial query calculus closed under inverses and deltas, with a polynomial normal form. Show k-th delta of degree-k non-nested polynomial queries depends only on the update, enabling per-aggregate constant-time incremental maintenance and join elimination. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h1af5fb5f221e82ad
Venue: PODS
Year: 2010
Pagerank: 0.00012731074
Overall Rank: 978 | 93.43%
DOI: 10.1145/1807085.1807100

Incoming Non-self Citations Over Time

Authors

1. Christoph Koch (Cornell University)

BibTeX Citation

@inproceedings{koch_pods10,
        address = {New York, NY, USA},
        series = {{PODS} '10},
        title = {{Incremental Query Evaluation in a Ring of Databases}},
        url = {https://dl.acm.org/doi/10.1145/1807085.1807100},
        doi = {10.1145/1807085.1807100},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Koch, Christoph},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 33 of 33 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
357	FAQ: Questions Asked Frequently	2016	PODS	0.00020020639
408	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00018900199
812	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013729015
819	Provenance for Aggregate Queries	2011	PODS	0.00013666629
1,742	How to Architect a Query Compiler	2016	SIGMOD	9.7378418e-05
2,222	Explaining Query Answers with Explanation-Ready Databases	2016	VLDB	8.8109051e-05
2,418	The Semiring Framework for Database Provenance	2017	PODS	8.4928222e-05
3,112	Incremental View Maintenance with Triple Lock Factorization Benefits	2018	SIGMOD	7.6357579e-05
3,128	How to Win a Hot Dog Eating Contest: Distributed Incremental View Maintenance with Batch Updates	2016	SIGMOD	7.6151967e-05
3,187	Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries	2020	PODS	7.5546613e-05
3,673	DBSP: Automatic Incremental View Maintenance for Rich Query Languages	2023	VLDB	7.1092596e-05
4,161	The Relational Data Borg is Learning	2020	VLDB	6.7700593e-05
4,176	Aggregation in Probabilistic Databases via Knowledge Compilation	2012	VLDB	6.7573044e-05
4,321	Generalized Scale Independence Through Incremental Precomputation	2013	SIGMOD	6.6660222e-05
5,145	Conjunctive Queries with Inequalities Under Updates	2018	VLDB	6.2566119e-05
5,457	Code generation for efficient query processing in managed runtimes	2014	VLDB	6.1239347e-05
5,684	iTurboGraph: Scaling and Automating Incremental Graph Analytics	2021	SIGMOD	6.0391416e-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
6,706	Tempura: A General Cost-Based Optimizer Framework for Incremental Data Processing	2021	VLDB	5.7049776e-05
6,876	Insert-Only versus Insert-Delete in Dynamic Query Evaluation	2024	PODS	5.6586279e-05
7,308	Optimization for iterative queries on MapReduce	2014	VLDB	5.5572894e-05
7,703	Interactive Query Explanations Using Fine Grained Provenance	2022	SIGMOD	5.4744994e-05
7,771	DBToaster: Agile Views in a Dynamic Data Management System	2011	CIDR	5.4553987e-05
8,560	Efficient Incrementialization of Correlated Nested Aggregate Queries using Relative Partial Aggregate Indexes (RPAI)	2022	SIGMOD	5.3142933e-05
9,048	Live Programming in the LogicBlox System: A MetaLogiQL Approach	2015	VLDB	5.2308307e-05
9,148	In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework	2024	SIGMOD	5.2189946e-05
9,740	TreeToaster: Towards an IVM-Optimized Compiler	2021	SIGMOD	5.1349531e-05
10,028	Towards Update-Dependent Analysis of Query Maintenance	2025	PODS	5.0925155e-05
10,181	In-Database Data Imputation	2024	SIGMOD	5.0653015e-05
10,544	Approximate Query Processing under Updates	2026	SIGMOD	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
12,128	Programmable View Update Strategies on Relations	2020	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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
39	Efficiently Updating Materialized Views	1986	SIGMOD	0.00046602544
62	Maintaining Views Incrementally	1993	SIGMOD	0.00039045511
213	Eager Aggregation and Lazy Aggregation	1995	VLDB	0.00024759805
246	Deriving Production Rules for Incremental View Maintenance	1991	VLDB	0.00023212582
301	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00021682744
380	Maintenance Of Views	1984	SIGMOD	0.00019511838
388	Incremental Maintenance of Views with Duplicates	1995	SIGMOD	0.00019350381
1,150	Algorithms for Deferred View Maintenance	1996	SIGMOD	0.00011809311
3,873	DBToaster: A SQL Compiler for High-Performance Delta Processing in Main-Memory Databases	2009	VLDB	6.9539394e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,467	Output-sensitive Conjunctive Query Evaluation	2024	PODS
2	8,697	Aggregate Queries on Sparse Databases	2020	PODS
3	1,898	Querying Multiple Features of Groups in Relational Databases	1996	VLDB
4	2,081	Incremental Maintenance for Non-Distributive Aggregate Functions	2002	VLDB
5	10,377	Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations	2026	PODS
6	380	Maintenance Of Views	1984	SIGMOD
7	10,544	Approximate Query Processing under Updates	2026	SIGMOD
8	62	Maintaining Views Incrementally	1993	SIGMOD
9	388	Incremental Maintenance of Views with Duplicates	1995	SIGMOD
10	6,219	Incremental View Maintenance For Collection Programming	2016	PODS