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

Download PDF

Abstract

Deletion Propagation (DP) refers to a family of database problems rooted in the classical view-update problem: how to propagate intended deletions in a view (query output) back to the source database while satisfying constraints and minimizing side e!ects. Although studied for over 40 years, DP variants, their complexities, and practical algorithms have been typically explored in isolation. This work presents a uni"ed and generalized framework for DP with several key bene"ts: (1) It uni!es and generalizes all previously known DP variants, e!ectively subsuming them within a broader class of problems, including new, well-motivated variants. (2) It comes with a practical and general-purpose algorithm that is “ coarse-grained instance-optimal ”: it runs in PTIME for all known PTIME cases and can automatically exploit structural regularities in the data, i.e. it does not rely on hints about such regularities as part of the input. (3) It is complete : our framework handles all known DP variants in all settings (including those involving self-joins, unions, and bag semantics), and allows us to provide new complexity results. (4) It is easy to implement and, in many cases, outperforms prior variant-speci"c solutions, sometimes by orders of magnitude. We provide the "rst experimental results for several DP variants previously studied only in theory.