The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries
The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries
复制标题
DOI：
10.14778/2850583.2850592
复制
发表时间：
2015-11
期刊：
影响因子：
--
通讯作者：
C. Freire;Wolfgang Gatterbauer;N. Immerman;A. Meliou
中科院分区：
文献类型：
--
作者：
C. Freire;Wolfgang Gatterbauer;N. Immerman;A. Meliou
数据管理领域的一些研究重点集中在理解数据的变化如何影响视图或常设查询的输出。示例应用程序包括解释查询结果、通过视图传播更新以及匿名化数据集。这种分析的一个重要方面是从输入表中删除最小数量的元组以使给定的布尔查询为假的问题，我们称之为“查询的弹性”。在本文中，我们研究了具有任意函数依赖的自连接自由合取查询的弹性的复杂性。我们工作的基石是新概念的三元组，一个简单的结构属性的查询，导致我们在本文中显示的几个二分法的结果。三合会和弹性的概念之间的连接桥梁的删除传播和因果责任的问题，并允许我们大大推进这些主题中已知的复杂性结果。具体来说，我们显示了一个二分法的弹性，识别以前未知的听话的家庭删除传播源的副作用的复杂性，我们扩展了这一结果，占功能依赖。此外，我们确定了一个错误，在以前的二分法的因果责任，并提供了一个修订后的表征纯粹基于查询的结构形式（存在或不存在的三合会）。最后，我们以两种方式扩展了因果责任的二分法：（a）我们考虑了输入表中的函数依赖关系，（B）我们计算了通过通配符指定的元组集的责任。
Several research thrusts in the area of data management have focused on understanding how changes in the data affect the output of a view or standing query. Example applications are explaining query results, propagating updates through views, and anonymizing datasets. An important aspect of this analysis is the problem of deleting a minimum number of tuples from the input tables to make a given Boolean query false, which we refer to as "the resilience of a query." In this paper, we study the complexity of resilience for self-join-free conjunctive queries with arbitrary functional dependencies. The cornerstone of our work is the novel concept of triads, a simple structural property of a query that leads to the several dichotomy results we show in this paper. The concepts of triads and resilience bridge the connections between the problems of deletion propagation and causal responsibility, and allow us to substantially advance the known complexity results in these topics. Specifically, we show a dichotomy for the complexity of resilience, which identifies previously unknown tractable families for deletion propagation with source side-effects, and we extend this result to account for functional dependencies. Further, we identify a mistake in a previous dichotomy for causal responsibility, and offer a revised characterization based purely on the structural form of the query (presence or absence of triads). Finally, we extend the dichotomy for causal responsibility in two ways: (a) we account for functional dependencies in the input tables, and (b) we compute responsibility for sets of tuples specified via wildcards.