Counting Database Repairs under Primary Keys Revisited
Counting Database Repairs under Primary Keys Revisited
复制标题
重新审视主键下的数据库修复计数
DOI：
10.1145/3294052.3319703
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Calautti M
中科院分区：
文献类型：
--
作者：
Calautti M
一致性查询回答（CQA）旨在在不一致的数据库上评估查询时提供有意义的答案。这样的答案在所有的修复中肯定是正确的，这些修复是一致的数据库，其与不一致的数据库的差异在某种程度上是最小的。在此上下文中，一个有趣的任务是计算需要查询的修复次数。这个问题已经在合取查询和主键中研究过了;我们知道在多项式时间图灵约简下，它在数据复杂度上是#P-完全的（也称为#P-完全）。库克减少）。然而，正如在计数复杂性的文献中已经观察到的那样，存在“难以计数-易于决定”的问题，在较弱的约简下，特别是在标准的多-一对数空间约简下，对于#P，这些问题是不完整的（在合理的假设下）。简约缩减）。对于这样的“难以计数但容易决定”的问题，一个关键的问题是我们是否可以通过寻找它们所属的#P的子类来确定它们的精确复杂度。理想情况下，我们希望证明这样的问题对于#P的子类在多-一对数空间约简下是完全的。这项工作的主要目标是执行这样一个精细的分析的问题，计算修复的主键下，需要查询的数量。
Consistent query answering (CQA) aims to deliver meaningful answers when queries are evaluated over inconsistent databases. Such answers must be certainly true in all repairs, which are consistent databases whose difference from the inconsistent one is somehow minimal. An interesting task in this context is to count the number of repairs that entail the query. This problem has been already studied for conjunctive queries and primary keys; we know that it is #P-complete in data complexity under polynomial-time Turing reductions (a.k.a. Cook reductions). However, as it has been already observed in the literature of counting complexity, there are problems that are ''hard-to-count-easy-to-decide'', which cannot be complete (under reasonable assumptions) for #P under weaker reductions, and, in particular, under standard many-one logspace reductions (a.k.a. parsimonious reductions). For such ''hard-to-count-easy-to-decide'' problems, a crucial question is whether we can determine their exact complexity by looking for subclasses of #P to which they belong. Ideally, we would like to show that such a problem is complete for a subclass of #P under many-one logspace reductions. The main goal of this work is to perform such a refined analysis for the problem of counting the number of repairs under primary keys that entail the query.
登录
查看更多内容
“计数满足自连接联合查询的数据库修复”的勘误表
DOI：
--
发表时间：
2019
期刊：
arXiv.org
影响因子：
--
作者：
Jef Wijsen
通讯作者：
Jef Wijsen
PP 与多项式时间层次结构一样困难
DOI：
--
发表时间：
1991
期刊：
SIAM journal on computing (Print)
影响因子：
--
作者：
Seinosuke Toda
通讯作者：
Seinosuke Toda
DOI：
10.1145/3196959.3196966
发表时间：
2018
期刊：
--
影响因子：
--
作者：
Calautti M
通讯作者：
Calautti M
使用 Easy Decision 版本计算函数的复杂性
影响因子：
2
作者：
Aris Pagourtzis;S. Zachos
通讯作者：
S. Zachos
一个非常难的日志空间计数类
DOI：
10.1109/sct.1990.113964
发表时间：
1990
期刊：
Proceedings Fifth Annual Structure in Complexity Theory Conference
影响因子：
--
作者：
Carme Àlvarez;Birgit Jenner
通讯作者：
Birgit Jenner