An Operational Approach to Consistent Query Answering

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.