Deletion Propagation for Multiple Key Preserving Conjunctive Queries: Approximations and Complexity
Deletion Propagation for Multiple Key Preserving Conjunctive Queries: Approximations and Complexity
复制标题
DOI：
10.1109/icde.2019.00052
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Zhipeng Cai;Dongjing Miao;Yingshu Li
中科院分区：
文献类型：
--
作者：
Zhipeng Cai;Dongjing Miao;Yingshu Li
本文从最小化视图副作用的角度研究删除传播问题。它是数据溯源和质量管理的一个基本问题，可能是分析视图传播和修复数据的关键步骤。所研究的问题是标准删除传播问题的一个变体，给定一个源数据库\(D\)、一组保持键的合取查询\(Q\)以及由\(Q\)中的查询得到的视图集合\(V\)，我们试图从\(D\)中确定一个元组集合\(T\)，其删除可以阻止视图\(\Delta V\)中给定删除集合中的所有元组，同时保留任何其他结果。对于只有单个查询的情况，这个问题的复杂性已经得到了充分研究。针对不同的设置，已经得出了二分法，甚至三分法。然而，对于更现实的多个查询的情况，没有给出相关结果。我们研究了优化视图副作用的复杂性和近似情况，即找到\(T\)以在删除\(\Delta V\)的所有元组后最小化对\(V\)的额外损害。我们关注保持键的合取查询类，对于单个查询的情况它是二分的。令人惊讶的是，我们发现除了单个查询的情况，就视图副作用而言，即使对于一组非平凡的无投影合取查询，这个问题在任何常数范围内都是难以近似的。所提出的算法表明，它可以在一个取决于\(V\)和\(\Delta V\)的元组数的界限内进行近似。我们确定了一类多项式可处理的输入，并提供了一个动态规划算法来解决这个问题。除了数据溯源，对这个问题的研究还可以为数据修复中的计算问题提供重要基础。此外，我们介绍了这个问题的一些相关应用，特别是对于基于查询反馈的数据清理。
This paper studies the deletion propagation problem in terms of minimizing view side-effect. It is a problem funda-mental to data lineage and quality management which could be a key step in analyzing view propagation and repairing data. The investigated problem is a variant of the standard deletion propagation problem, where given a source database D, a set of key preserving conjunctive queries Q, and the set of views V obtained by the queries in Q, we try to identify a set T of tuples from D whose elimination prevents all the tuples in a given set of deletions on views △V while preserving any other results. The complexity of this problem has been well studied for the case with only a single query. Dichotomies, even trichotomies, for different settings are developed. However, no results on multiple queries are given which is a more realistic case. We study the complexity and approximations of optimizing the side-effect on the views, i.e., find T to minimize the additional damage on V after removing all the tuples of △V. We focus on the class of key-preserving conjunctive queries which is a dichotomy for the single query case. It is surprising to find that except the single query case, this problem is NP-hard to approximate within any constant even for a non-trivial set of multiple project-free conjunctive queries in terms of view side-effect. The proposed algorithm shows that it can be approximated within a bound depending on the number of tuples of both V and △V. We identify a class of polynomial tractable inputs, and provide a dynamic programming algorithm to solve the problem. Besides data lineage, study on this problem could also provide important foundations for the computational issues in data repairing. Furthermore, we introduce some related applications of this problem, especially for query feedback based data cleaning.