Incremental View Maintenance For Collection Programming

Summary: Cost-model for positive NRC+ on bags; identifies IncNRC+, a large fragment whose deltas beat full re-evaluation, with a semantics-preserving translation from general NRC+ to IncNRC+. Shows incremental maintenance for NRC+ is in NC0 and adapts recursive IVM to IncNRC+ for efficient nested-collection updates. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1680
Venue: PODS
Year: 2016
Pagerank: 5.9471978e-05
Overall Rank: 6,193 | 57.52%
DOI: 10.1145/2902251.2902286

Incoming Non-self Citations Over Time

Authors

1. Christoph Koch (EPFL)
2. Daniel Lupei (EPFL)
3. Val Tannen (University of Pennsylvania)

BibTeX Citation

@inproceedings{koch_pods16,
        address = {New York, NY, USA},
        series = {{PODS} '16},
        title = {{Incremental View Maintenance For Collection Programming}},
        url = {https://dl.acm.org/doi/10.1145/2902251.2902286},
        doi = {10.1145/2902251.2902286},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Koch, Christoph and Lupei, Daniel and Tannen, Val},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,657	Production Machine Learning Pipelines: Empirical Analysis and Optimization Opportunities	2021	SIGMOD	8.2887895e-05
4,865	DBSP: Automatic Incremental View Maintenance for Rich Query Languages	2023	VLDB	6.4731692e-05
6,377	Scalable Querying of Nested Data	2021	VLDB	5.8931544e-05
6,732	Insert-Only versus Insert-Delete in Dynamic Query Evaluation	2024	PODS	5.7885064e-05
9,565	TreeToaster: Towards an IVM-Optimized Compiler	2021	SIGMOD	5.2528121e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
39	Efficiently Updating Materialized Views	1986	SIGMOD	0.00047309646
61	Maintaining Views Incrementally	1993	SIGMOD	0.00039026867
258	Deriving Production Rules for Incremental View Maintenance	1991	VLDB	0.00023131981
292	LINQ: Reconciling Objects, Relations and XML in the .NET Framework	2006	SIGMOD	0.00022259549
375	Incremental Maintenance of Views with Duplicates	1995	SIGMOD	0.00019681204
438	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00018471721
960	Incremental Query Evaluation in a Ring of Databases	2010	PODS	0.00012945163
1,777	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.7849758e-05
3,155	Query Shredding: Efficient Relational Evaluation of Queries over Nested Multisets	2014	SIGMOD	7.695861e-05
3,864	FERRY - Database-Supported Program Execution	2009	SIGMOD	7.0628657e-05
4,702	On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values	2005	PODS	6.5549225e-05
4,847	Avalanche-Safe LINQ Compilation	2010	VLDB	6.4805473e-05
7,086	A Query Language for NC	1994	PODS	5.7073076e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,552	Enabling Incremental Query Re-Optimization	2016	SIGMOD
2	4,865	DBSP: Automatic Incremental View Maintenance for Rich Query Languages	2023	VLDB
3	816	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD
4	1,834	Incremental Maintenance for Materialized Views over Semistructured Data	1998	VLDB
5	7,967	Thrifty Query Execution via Incrementability	2020	SIGMOD
6	10,160	Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations	2026	PODS
7	6,739	Utilizing IDs to Accelerate Incremental View Maintenance	2015	SIGMOD
8	375	Incremental Maintenance of Views with Duplicates	1995	SIGMOD
9	61	Maintaining Views Incrementally	1993	SIGMOD
10	960	Incremental Query Evaluation in a Ring of Databases	2010	PODS