论文标题
用于计数连接查询答案的汇总删除传播
Aggregated Deletion Propagation for Counting Conjunctive Query Answers
论文作者
论文摘要
我们研究了最小化源副作用的计算复杂性，以便从连接查询的输出中删除给定数量的元素。这是研究良好的{\ em删除传播}问题的变体，其差异是我们有兴趣删除输入元素的最小子集以删除给定数量的输出元素}，而删除繁殖集中在删除特定的输出元组上。我们将其称为{\ em汇总的删除传播}问题。我们完全表征了此问题的多个时间可溶性，用于任意无自结合的任意结合查询。这包括一个多时间算法来决定可溶性，以及NP-HARD实例的确切结构表征。我们还为此问题提供了一种实用算法（NP-HARD实例的启发式），并评估其在真实和合成数据集上的实验性能。
We investigate the computational complexity of minimizing the source side-effect in order to remove a given number of tuples from the output of a conjunctive query. This is a variant of the well-studied {\em deletion propagation} problem, the difference being that we are interested in removing the smallest subset of input tuples to remove a given number of output tuples} while deletion propagation focuses on removing a specific output tuple. We call this the {\em Aggregated Deletion Propagation} problem. We completely characterize the poly-time solvability of this problem for arbitrary conjunctive queries without self-joins. This includes a poly-time algorithm to decide solvability, as well as an exact structural characterization of NP-hard instances. We also provide a practical algorithm for this problem (a heuristic for NP-hard instances) and evaluate its experimental performance on real and synthetic datasets.
