Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation

Summary: A unified ILP framework subsumes known and new deletion-propagation variants, including self-joins, unions, and bag semantics. Its coarse-grained instance-optimal solver automatically exploits data structure, achieves PTIME on tractable cases, and often outperforms specialized methods. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hf0edbe5c0259d0eb
Venue: VLDB
Year: 2025
Pagerank: 5.283642e-05
Overall Rank: 8,761 | 41.10%
DOI: 10.14778/3742728.3742756

Incoming Non-self Citations Over Time

Authors

1. Neha Makhija (Northeastern University)
2. Wolfgang Gatterbauer (Northeastern University)

BibTeX Citation

@article{makhija_vldb25,
        title = {{Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation}},
        author = {Makhija, Neha and Gatterbauer, Wolfgang},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {8},
        pages = {2667--2680},
        doi = {10.14778/3742728.3742756},
        url = {https://doi.org/10.14778/3742728.3742756},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,688	Stress-Testing Causal Claims via Cardinality Repairs	2026	SIGMOD	4.9793485e-05
10,987	GDPView: An Interactive Interface that Unifies Variants of Deletion Propagation (DP)	2026	VLDB	4.9793485e-05
11,095	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 25 of 25 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010679641
189	Scorpion: Explaining Away Outliers in Aggregate Queries	2013	VLDB	0.00025840026
578	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB	0.00016096504
590	On Propagation of Deletions and Annotations Through Views	2002	PODS	0.00015890019
670	A Formal Approach to Finding Explanations for Database Queries	2014	SIGMOD	0.00014954494
803	Interventional Fairness : Causal Database Repair for Algorithmic Fairness	2019	SIGMOD	0.00013836858
1,051	Tiresias: The Database Oracle for How-To Queries	2012	SIGMOD	0.00012279821
1,725	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	9.7902443e-05
1,812	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.5803973e-05
1,814	ProvSQL: Provenance and Probability Management in PostgreSQL	2018	VLDB	9.5800565e-05
2,360	Artemis: A System for Analyzing Missing Answers	2009	VLDB	8.5770202e-05
2,949	Reverse Data Management	2011	VLDB	7.821181e-05
3,139	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD	7.6046928e-05
4,062	The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries	2016	VLDB	6.8247395e-05
4,323	Multi-Tuple Deletion Propagation: Approximations and Complexity	2013	VLDB	6.6658586e-05
4,437	Maximizing Conjunctive Views in Deletion Propagation	2011	PODS	6.6001218e-05
4,566	HYPER: Hypothetical Reasoning With What-If and How-To Queries Using a Probabilistic Causal Approach	2022	SIGMOD	6.5310568e-05
4,747	New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins	2020	PODS	6.4374568e-05
4,827	QFix: Diagnosing Errors through Query Histories	2017	SIGMOD	6.3917868e-05
4,847	Explaining Wrong Queries Using Small Examples	2019	SIGMOD	6.3823876e-05
5,994	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	5.922611e-05
7,383	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB	5.5387855e-05
7,419	A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations	2023	SIGMOD	5.5326094e-05
7,773	The Perm Provenance Management System in Action	2009	SIGMOD	5.455099e-05
8,128	Scaling Package Queries to a Billion Tuples via Hierarchical Partitioning and Customized Optimization	2024	VLDB	5.3939686e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,508	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
2	2,595	Efficient Querying of Inconsistent Databases with Binary Integer Programming	2013	VLDB
3	3,139	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD
4	8,651	Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation	2026	VLDB
5	4,437	Maximizing Conjunctive Views in Deletion Propagation	2011	PODS
6	4,323	Multi-Tuple Deletion Propagation: Approximations and Complexity	2013	VLDB
7	5,994	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS
8	590	On Propagation of Deletions and Annotations Through Views	2002	PODS
9	7,383	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB
10	7,419	A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations	2023	SIGMOD