Abstract
We discuss a novel approach for solving reverse data management problems: instead of creating dedicated algorithms for easy (PTIME) and hard cases (NP-complete), we suggest using a unified algorithm that is guaranteed to terminate in PTIME for all easy cases. The algorithm is unified in that it can solve both previously studied restrictions (e.g., self-join-free CQs under set semantics that allow a PTIME solution) and new cases (e.g., all CQs under set or bag semantics). We use (Integer) Linear Programs (ILP/LPs) to encode such unified algorithms and use this approach to: (1) prove dichotomies under bag semantics for the problems of resilience and causal responsibility, (2) discover new tractable cases for the problem of minimal factorization of provenance formulas. We also propose a structural characterization of a unified hardness criterion, which can be used to automatically find hardness proofs for queries whose complexity were previously unknown.
SIGMOD 2024: A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations
https://arxiv.org/pdf/2212.08898
https://northeastern-datalab.github.io/unified-reverse-data-management/