Coping with Incomplete Data: Recent Advances
Coping with Incomplete Data: Recent Advances
复制标题
DOI：
10.1145/3375395.3387970
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Marco Console;P. Guagliardo;L. Libkin;Etienne Toussaint
中科院分区：
文献类型：
--
作者：
Marco Console;P. Guagliardo;L. Libkin;Etienne Toussaint
以正确的方式处理不完整的数据是数据库中众所周知的难题。理论上的方法依赖于某些答案的计算困难的概念，而实际的解决方案依赖于基于三值逻辑的特设查询评估技术。我们能否找到一个中间立场，并有效地产生正确的答案？本文综述了近几年来这一问题的研究成果。我们重新审视确定性的概念本身，并表明它比以前认为的要多样化得多。我们确定的情况下，某些答案可以有效地计算，短的，为他们提供确定性和概率近似方案。我们看看在SQL查询评估中使用的三值逻辑的作用，并讨论选择的正确性，以及这种逻辑产生查询答案的必要性。
Handling incomplete data in a correct manner is a notoriously hard problem in databases. Theoretical approaches rely on the computationally hard notion of certain answers, while practical solutions rely on ad hoc query evaluation techniques based on three-valued logic. Can we find a middle ground, and produce correct answers efficiently? The paper surveys results of the last few years motivated by this question. We re-examine the notion of certainty itself, and show that it is much more varied than previously thought. We identify cases when certain answers can be computed efficiently and, short of that, provide deterministic and probabilistic approximation schemes for them. We look at the role of three-valued logic as used in SQL query evaluation, and discuss the correctness of the choice, as well as the necessity of such a logic for producing query answers.