Why is it Hard to Obtain a Dichotomy for Consistent Query Answering?
Why is it Hard to Obtain a Dichotomy for Consistent Query Answering?
复制标题
为什么很难获得一致的查询应答的二分法？
DOI：
10.1109/lics.2013.62
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
G. Fontaine
中科院分区：
文献类型：
--
作者：
G. Fontaine
由于各种原因，数据库可能与给定的一组完整性约束不一致。为了克服这个问题，已经提出了一种查询这种不一致数据库的形式化方法，并且从那时起，已经花费了大量的努力来分类在各种约束类型下一致查询回答的复杂性。众所周知，对于最常见的约束和查询，问题是在CONP中，并且可能是CONP困难的，但是已经确定了几个相关的可处理类。此外，出现的结果表明，给定一组键约束和一个连接查询，一致查询应答的问题要么是PTIME的，要么是CONP-complete的。然而，尽管做了所有的工作，直到今天，这种二分法仍然是一种猜想。本文的主要贡献是解释为什么在一致查询回答的设置中很难获得二分结果。也就是说，我们证明了约束和查询的公共类的二分法比约束满足问题的二分法更难实现，约束满足问题是自20世纪90年代以来的一个著名的开放问题。
A database may for various reasons become inconsistent with respect to a given set of integrity constraints. To overcome the problem, a formal approach to querying such inconsistent databases has been proposed and since then, a lot of efforts have been spent to classify the complexity of consistent query answering under various classes of constraints. It is known that for the most common constraints and queries, the problem is in CONP and might be CONP-hard, yet several relevant tractable classes have been identified. Additionally, the results that emerged suggested that given a set of key constraints and a conjunctive query, the problem of consistent query answering is either in PTIME or is CONP-complete. However, despite all the work, as of today this dichotomy remains a conjecture. The main contribution of this paper is to explain why it appears so difficult to obtain a dichotomy result in the setting of consistent query answering. Namely, we prove that such a dichotomy w.r.t. common classes of constraints and queries, is harder to achieve than a dichotomy for the constraint satisfaction problem, which is a famous open problem since the 1990s.
关系和 XML 数据交换
DOI：
10.2200/s00297ed1v01y201008dtm008
发表时间：
2010
期刊：
Synthesis Lectures on Data Management
影响因子：
--
作者：
Arenas M
通讯作者：
Arenas M