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 / Calautti, Marco; Libkin, Leonid; Pieris, Andreas. - (2018), pp. 239-251. ((Intervento presentato al convegno PODS 18 tenutosi a Houston, TX nel 10th-15th June 2018.
|Titolo:||An Operational Approach to Consistent Query Answering|
|Autori:||Calautti, Marco; Libkin, Leonid; Pieris, Andreas|
|Titolo del volume contenente il saggio:||PODS 18: Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems|
|Luogo di edizione:||New York City|
|Anno di pubblicazione:||2018|
|Codice identificativo Scopus:||2-s2.0-85047992335|
|Codice identificativo ISI:||WOS:000455483100018|
|Citazione:||An Operational Approach to Consistent Query Answering / Calautti, Marco; Libkin, Leonid; Pieris, Andreas. - (2018), pp. 239-251. ((Intervento presentato al convegno PODS 18 tenutosi a Houston, TX nel 10th-15th June 2018.|
|Appare nelle tipologie:||04.1 Saggio in atti di convegno (Paper in proceedings)|
File in questo prodotto:
|C10.pdf||Versione editoriale (Publisher’s layout)||Tutti i diritti riservati (All rights reserved)||Administrator|