A Unified Approach for Reverse Data Management Problems

Explore a groundbreaking unified approach to solving reverse data management problems in this 28-minute lecture by Neha Makhija from Northeastern University. Delve into a novel algorithm that guarantees PTIME termination for all easy cases, eliminating the need for separate algorithms for PTIME and NP-complete scenarios. Discover how this unified method utilizes (Integer) Linear Programs to tackle both previously studied restrictions and new cases across set and bag semantics. Learn about the application of this approach in proving dichotomies for resilience and causal responsibility under bag semantics, and uncovering new tractable cases for minimal factorization of provenance formulas. Examine the proposed structural characterization of a unified hardness criterion and its potential for automating hardness proofs for queries with previously unknown complexity.