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)
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,699 | Stress-Testing Causal Claims via Cardinality Repairs | 2026 | SIGMOD | 4.9769913e-05 |
| 10,996 | GDPView: An Interactive Interface that Unifies Variants of Deletion Propagation (DP) | 2026 | VLDB | 4.9769913e-05 |
| 11,104 | Smallest Synthetic Witnesses for Conjunctive Queries | 2025 | PODS | 4.9769913e-05 |
Previous
Page 1 / 1
Next
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.
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 10,519 | Succinct Structure Representations for Efficient Query Optimization | 2026 | SIGMOD |
| 2 | 2,597 | Efficient Querying of Inconsistent Databases with Binary Integer Programming | 2013 | VLDB |
| 3 | 3,140 | Solving the Join Ordering Problem via Mixed Integer Linear Programming | 2017 | SIGMOD |
| 4 | 8,659 | Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation | 2026 | VLDB |
| 5 | 4,439 | 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 | 591 | On Propagation of Deletions and Annotations Through Views | 2002 | PODS |
| 9 | 7,385 | Aggregated Deletion Propagation for Counting Conjunctive Query Answers | 2021 | VLDB |
| 10 | 7,422 | A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations | 2023 | SIGMOD |