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: 14098
Venue: VLDB
Year: 2025
Pagerank: 5.4049137e-05
Overall Rank: 8,598 | 41.02%
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 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,502	Stress-Testing Causal Claims via Cardinality Repairs	2026	SIGMOD	5.093636e-05
10,652	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	5.093636e-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.0010828372
191	Scorpion: Explaining Away Outliers in Aggregate Queries	2013	VLDB	0.00026096009
605	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB	0.00015839628
620	On Propagation of Deletions and Annotations Through Views	2002	PODS	0.00015703409
663	A Formal Approach to Finding Explanations for Database Queries	2014	SIGMOD	0.00015174751
863	Interventional Fairness : Causal Database Repair for Algorithmic Fairness	2019	SIGMOD	0.00013531835
1,096	Tiresias: The Database Oracle for How-To Queries	2012	SIGMOD	0.00012189583
1,699	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	9.975915e-05
1,857	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.6047945e-05
1,965	ProvSQL: Provenance and Probability Management in PostgreSQL	2018	VLDB	9.3852716e-05
2,358	Artemis: A System for Analyzing Missing Answers	2009	VLDB	8.6996414e-05
2,914	Reverse Data Management	2011	VLDB	7.9667467e-05
3,158	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD	7.6888079e-05
3,991	The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries	2016	VLDB	6.9695922e-05
4,248	Multi-Tuple Deletion Propagation: Approximations and Complexity	2013	VLDB	6.8052749e-05
4,670	New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins	2020	PODS	6.5734205e-05
4,759	Explaining Wrong Queries Using Small Examples	2019	SIGMOD	6.5207388e-05
4,901	Maximizing Conjunctive Views in Deletion Propagation	2011	PODS	6.4528526e-05
4,959	QFix: Diagnosing Errors through Query Histories	2017	SIGMOD	6.4283324e-05
5,025	HYPER: Hypothetical Reasoning With What-If and How-To Queries Using a Probabilistic Causal Approach	2022	SIGMOD	6.3974766e-05
5,905	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	6.0461963e-05
7,269	A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations	2023	SIGMOD	5.6595955e-05
7,625	The Perm Provenance Management System in Action	2009	SIGMOD	5.5803061e-05
7,964	Scaling Package Queries to a Billion Tuples via Hierarchical Partitioning and Customized Optimization	2024	VLDB	5.5177726e-05
8,700	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB	5.3829336e-05

Semantically Similar Papers

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