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.

Coping with Incomplete Data: Recent Advances / Console, M.; Guagliardo, P.; Libkin, L.; Toussaint, E.. - (2020), pp. 33-47. (Intervento presentato al convegno ACM SIGMOD-SIGACT-SIGART Conference on Principles of Database Systems tenutosi a usa) [10.1145/3375395.3387970].

Coping with Incomplete Data: Recent Advances

Console M.
;
Libkin L.
;
2020

Abstract

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
ACM SIGMOD-SIGACT-SIGART Conference on Principles of Database Systems
approximate query answering; certain answers; incomplete information; many-valued logics; naive evaluation; relational databases
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Coping with Incomplete Data: Recent Advances / Console, M.; Guagliardo, P.; Libkin, L.; Toussaint, E.. - (2020), pp. 33-47. (Intervento presentato al convegno ACM SIGMOD-SIGACT-SIGART Conference on Principles of Database Systems tenutosi a usa) [10.1145/3375395.3387970].
File allegati a questo prodotto
File Dimensione Formato  
Console_Coping_2020.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.51 MB
Formato Adobe PDF
1.51 MB Adobe PDF   Contatta l'autore
Console_preprint_Coping_2020.pdf

accesso aperto

Note: DOI: 10.1145/3375395.3387970
Tipologia: Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.12 MB
Formato Adobe PDF
1.12 MB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1501965
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 7
social impact