A Unified Approach for Reverse Data Management Problems
summary
Proposes a concrete encoding of reverse data management problems as an ILP encoding whose LP relaxation matches the ILP on all known PTIME cases so solvers often finish in polynomial time by solving the LP first; extends from set to bag semantics and handles self-join-free queries and many self-join cases. Uses this to prove dichotomies for resilience and causal responsibility, finds new tractable minimal‑factorization cases, and automates hardness via independent joint path gadgets and a disjunctive logic program search that resolves five of seven prior open cases.
AI-written summary · about
chapters (8)
- 0:00Introduction to reverse data
- 4:06The resilience problem
- 7:29Unified algorithmic approach
- 9:04LP and ILP equivalence
- 13:20Hardness proofs and gadgets
- 17:05Automating hardness proofs
- 21:01Conjectures and conclusions
- 24:01Q&A session
related talks
18mMaximum Consensus Floating Point Solutions for Infeasible Low-Dimensional Linear(…)
28mA Dichotomy Structure Theorem for the Resilience Problem
38mThe Intensional-Extensional Problem in Probabilistic Databases
43mA Dichotomy for Queries with Negation in Probabilistic Databases
41mOptimizing Relational Programs I
24mWhen Less Is More: Consequence-Finding in a Weak Theory of Arithmetic
36mOptimizing Relational Programs II
01h 24mIntroduction to Constraint Logic Programming