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 effects. Although studied for over 40 years, DP variants, their complexities, and practical algorithms have been typically explored in isolation. This work presents a unified and generalized framework for DP with several key benefits: (1) It unifies and generalizes all pre- viously known DP variants, effectively subsuming them within a broader class of problems, that includes new, well-motivated vari- ants. (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 regu- larities in the data, i.e. it does not rely on hints about such structural properties as part of the input. (3) It is complete: our framework han- dles 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-specific solutions, sometimes by orders of magnitude. We provide the first experimental results for several problem variants previously studied only in theory.

Based on join work with Neha Makhija from VLDB 2025: https://arxiv.org/pdf/2411.17603

Project page: https://northeastern-datalab.github.io/unified-reverse-data-management/

Earlier slide version: https://gatterbauer.name/download/Gatterbauer-Simons2025-Generalized-Deletion-Propagation.pdf

About the Speaker

Wolfgang Gatterbauer is an associate professor in the Khoury College of Computer Sciences at Northeastern University, based in Boston.

Gatterbauer works on the theory of scalable data management. One of his goals is to extend the capabilities of modern data management systems in generic ways and to allow them to support seemingly difficult novel functionalities. He is a recipient of the NSF Career Award and a co-recipient of the EDBT 2021 Best Paper award; an honorable mention from SIGMOD 2024; “best-of-conference” mentions from PODS 2021, SIGMOD 2017, VLDB 2015, and WALCOM 2017; and two SIGMOD 2021 reproducibility awards.

Prior to joining Northeastern, Gatterbauer was a postdoctoral fellow in the database group at the University of Washington and an assistant professor in the Tepper School of Business at Carnegie Mellon University.

https://gatterbauer.name/