An Operational Approach to Consistent Query Answering
An Operational Approach to Consistent Query Answering
复制标题
一致查询应答的操作方法
DOI：
10.1145/3196959.3196966
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Calautti M
中科院分区：
文献类型：
--
作者：
Calautti M
一致性查询应答(Consistent Query Answing，CQA)的目的是在数据库不一致，即不符合其规范的情况下，为查询找到有意义的答案。这样的答案在所有修复中肯定都是正确的，根据某种衡量标准，这些修复是一致的数据库，与不一致的数据库的差异很小。这项任务通常很难计算，而且许多CQA研究都集中在寻找易处理的孤岛上。然而，有许多相关的问题没有有效的解决方案，CQA方法的实际适用性有限就反映了这一点。要纠正这一点，需要设计一个新的CQA框架，对查询答案的质量提供明确的保证。然而，修复和某些答案的标准概念太粗糙了，不能允许更详细的查询回答方案。我们的目标是为CQA提供一个新的框架，该框架基于修改后的修复和查询回答的定义，从而打开了具有显式保证的高效近似查询回答的可能性。关键思想是用可操作的定义替换当前的声明性修复定义，该定义解释了修复是如何构造的，以及一致的实例是修复的可能性有多大。这允许我们定义我们在多大程度上确定元组应该在答案中。利用这种方法，我们研究了精确和近似CQA的复杂性。尽管有些问题仍然很困难，但对于许多常见的约束类别，我们可以在合理的时间内为远远超出标准CQA方法的查询提供有意义的答案。
Consistent query answering (CQA) aims to find meaningful answers to queries when databases are inconsistent, i.e., do not conform to their specifications. Such answers must be certainly true in all repairs, which are consistent databases whose difference from the inconsistent one is minimal, according to some measure. This task is often computationally intractable, and much of CQA research concentrated on finding islands of tractability. Nevertheless, there are many relevant queries for which no efficient solutions exist, which is reflected by the limited practical applicability of the CQA approach. To remedy this, one needs to devise a new CQA framework that provides explicit guarantees on the quality of query answers. However, the standard notions of repair and certain answers are too coarse to permit more elaborate schemes of query answering. Our goal is to provide a new framework for CQA based on revised definitions of repairs and query answering that opens up the possibility of efficient approximate query answering with explicit guarantees. The key idea is to replace the current declarative definition of a repair with an operational one, which explains how a repair is constructed, and how likely it is that a consistent instance is a repair. This allows us to define how certain we are that a tuple should be in the answer. Using this approach, we study the complexity of both exact and approximate CQA. Even though some of the problems remain hard, for many common classes of constraints we can provide meaningful answers in reasonable time, for queries going far beyond the standard CQA approach.
登录
查看更多内容
为什么很难获得一致的查询应答的二分法？
DOI：
10.1109/lics.2013.62
发表时间：
2013
期刊：
2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
G. Fontaine
通讯作者：
G. Fontaine
DOI：
10.1007/978-0-387-30162-4_28
发表时间：
2021-08
期刊：
Proceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN'97)
影响因子：
--
作者：
通讯作者：
--
简单键原子一致查询应答复杂性的二分法
DOI：
--
发表时间：
2012
期刊：
International Conference on Database Theory
影响因子：
--
作者：
Paraschos Koutris;Dan Suciu
通讯作者：
Dan Suciu
通过源首选项解决数据集成中的不一致问题
DOI：
--
发表时间：
2004
期刊：
Information Quality in Information Systems
影响因子：
--
作者：
Giuseppe De Giacomo;D. Lembo;M. Lenzerini;R. Rosati
通讯作者：
R. Rosati
通过保密视图和基于空的虚拟更新实现数据隐私
影响因子：
8.9
作者：
L. Bertossi;Lechen Li
通讯作者：
Lechen Li