论文标题
通过整数线性编程（ILP）和LP放松的统一弹性和因果责任的方法
A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations
论文作者
论文摘要
弹性是各种形式的反向数据管理（例如视图维护，删除繁殖和公平性的各种干预措施）的关键算法问题之一：从数据库中删除的单元数量最少，以便从查询中删除所有答案？一个漫长的问题是确定可以在保证的ptime中解决此问题的结合查询（CQ）。我们通过提出统一的整数线性编程（ILP）配方，对此进行了新的启示以及因果责任的相关问题。它的统一是因为它可以解决先前的研究限制（例如，允许PimeTime解决方案的设置语义的无自结合的CQ）和新案例（例如，所有的CQ或BAG语义的所有CQ均已统一，因为所有查询都可以用相同的方法来处理所有查询，并且所有的案例都可以自行处理，并且可以轻松地终止了Pimirite of Pimirite pimile，因此，我们可以在Pimirite中均可用来。 CQS，我们的编码的线性编程（LP）放松与ILP解决方案相同，因此，确保标准的ILP求解器可以在PTIME中返回解决方案。 2）我们对因果责任的复杂性进行更细粒度的分析。 3）我们恢复了一般硬性查询的简便实例，例如具有读取源的实例和由于数据中的功能依赖性而变得容易的实例。 4）我们解决了PODS 2020的开放猜想。5）实验证实，我们的结果确实可以预测渐近运行时间，并且我们的通用ILP编码有时甚至比以前提出的专用流量算法更快地解决了PTIME情况。
Resilience is one of the key algorithmic problems underlying various forms of reverse data management (such as view maintenance, deletion propagation, and various interventions for fairness): What is the minimal number of tuples to delete from a database in order to remove all answers from a query? A long-open question is determining those conjunctive queries (CQs) for which this problem can be solved in guaranteed PTIME. We shed new light on this and the related problem of causal responsibility by proposing a unified Integer Linear Programming (ILP) formulation. It is unified in that it can solve both prior 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 It is also unified in that all queries and all instances are treated with the same approach, and the algorithm is guaranteed to terminate in PTIME for the easy cases. We prove that, for all easy self-join-free CQs, the Linear Programming (LP) relaxation of our encoding is identical to the ILP solution and thus standard ILP solvers are guaranteed to return the solution in PTIME. Our approach opens up the door to new variants and new fine-grained analysis: 1) It also works under bag semantics and we give the first dichotomy result for bags semantics in the problem space. 2) We give a more fine-grained analysis of the complexity of causal responsibility. 3) We recover easy instances for generally hard queries, such as instances with read-once provenance and instances that become easy because of Functional Dependencies in the data. 4) We solve an open conjecture from PODS 2020. 5) Experiments confirm that our results indeed predict the asymptotic running times, and that our universal ILP encoding is at times even faster to solve for the PTIME cases than a prior proposed dedicated flow algorithm.
