Consistent query answering (CQA) aims to find meaningful answersto queries when databases are inconsistent, i.e., do not conformto their specifications. Such answers must be certainly true in allrepairs, which are consistent databases whose difference from theinconsistent one is minimal, according to some measure. This taskis often computationally intractable, and much of CQA researchconcentrated on finding islands of tractability. Nevertheless, thereare many relevant queries for which no efficient solutions exist,which is reflected by the limited practical applicability of the CQAapproach. To remedy this, one needs to devise a new CQA framework that provides explicit guarantees on the quality of queryanswers. However, the standard notions of repair and certain answers are too coarse to permit more elaborate schemes of queryanswering. Our goal is to provide a new framework for CQA basedon revised definitions of repairs and query answering that opensup the possibility of efficient approximate query answering withexplicit guarantees. The key idea is to replace the current declarative definition of a repair with anoperationalone, which explainshowa repair is constructed, and how likely it is that a consistentinstance is a repair. This allows us to define how certain we arethat a tuple should be in the answer. Using this approach, we studythe complexity of both exact and approximate CQA. Even thoughsome of the problems remain hard, for many common classes ofconstraints we can provide meaningful answers in reasonable time,for queries going far beyond the standard CQA approach.

An Operational Approach to Consistent Query Answering / M. Calautti, L. Libkin, A. Pieris - In: PODS '18: Proceedings / [a cura di] M. Arenas, M. Ugarte, J. Van den Bussche. - New York City : ACM, 2018. - ISBN 978-1-4503-4706-8. - pp. 239-251 (( Intervento presentato al 37. convegno Symposium on Principles of Database Systems tenutosi a Houston nel 2018 [10.1145/3196959.3196966].

An Operational Approach to Consistent Query Answering

M. Calautti;
2018

Abstract

Consistent query answering (CQA) aims to find meaningful answersto queries when databases are inconsistent, i.e., do not conformto their specifications. Such answers must be certainly true in allrepairs, which are consistent databases whose difference from theinconsistent one is minimal, according to some measure. This taskis often computationally intractable, and much of CQA researchconcentrated on finding islands of tractability. Nevertheless, thereare many relevant queries for which no efficient solutions exist,which is reflected by the limited practical applicability of the CQAapproach. To remedy this, one needs to devise a new CQA framework that provides explicit guarantees on the quality of queryanswers. However, the standard notions of repair and certain answers are too coarse to permit more elaborate schemes of queryanswering. Our goal is to provide a new framework for CQA basedon revised definitions of repairs and query answering that opensup the possibility of efficient approximate query answering withexplicit guarantees. The key idea is to replace the current declarative definition of a repair with anoperationalone, which explainshowa repair is constructed, and how likely it is that a consistentinstance is a repair. This allows us to define how certain we arethat a tuple should be in the answer. Using this approach, we studythe complexity of both exact and approximate CQA. Even thoughsome of the problems remain hard, for many common classes ofconstraints we can provide meaningful answers in reasonable time,for queries going far beyond the standard CQA approach.
Settore INF/01 - Informatica
2018
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
3196959.3196966.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 1.36 MB
Formato Adobe PDF
1.36 MB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

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/2434/953306
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 24
  • ???jsp.display-item.citation.isi??? 14
social impact