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.
2020, Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Pages 33-47
Coping with Incomplete Data: Recent Advances (04b Atto di convegno in volume)
Console M., Guagliardo P., Libkin L., Toussaint E.
Gruppo di ricerca: Artificial Intelligence and Knowledge Representation