An Operational Approach to Consistent Query Answering

Marco Calautti, Leonid Libkin, Andreas Pieris

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Consistent query answering (CQA) aims to find meaningful answers to queries when databases are inconsistent, i.e., do not conform to their specifications. Such answers must be certainly true in all repairs, which are consistent databases whose difference from the inconsistent one is minimal, according to some measure. This task is often computationally intractable, and much of CQA research concentrated on finding islands of tractability; but still for many relevant queries no solutions exist, which is reflected by the limited practical applicability of the CQA approach. To remedy this, one needs to devise a new CQA framework that provides explicit guarantees on the quality of query answers. However, the standard notions of repair and certain answers are too coarse to permit more elaborate schemes of query answering. Our goal is to provide a new framework for CQA based on revised definitions of repairs and query answering that opens up the possibility of efficient approximate query answering with explicit guarantees. The key idea is to replace the current declarative definition of a repair with an operational one, which explains how a repair is constructed, and how likely it is that a consistent instance is a repair. This lets us define how certain we are that a tuple should
be in the answer. Using this approach, we study the complexity of both exact and approximate CQA. Even though some of the problems remain hard, for many common classes of constraints we can provide meaningful answers in reasonable time, for queries going far beyond the standard CQA approach.
Original languageEnglish
Title of host publicationProceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2018
PublisherACM
Pages239-251
Number of pages13
ISBN (Electronic)978-1-4503-4706-8
DOIs
Publication statusPublished - 27 May 2018
EventACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2018 - Texas, Houston, United States
Duration: 10 Jun 201815 Jun 2018
https://sigmod2018.org/

Conference

ConferenceACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2018
CountryUnited States
CityHouston
Period10/06/1815/06/18
Internet address

Fingerprint Dive into the research topics of 'An Operational Approach to Consistent Query Answering'. Together they form a unique fingerprint.

Cite this