First-order under-approximations of consistent query answers
Faculty of Sciences. Mathematics and Computer Science
Engineering sciences. Technology
Lecture notes in computer science
, p. 354-367
University of Antwerp
Consistent Query Answering (CQA) has by now been widely adopted as a principled approach for answering queries on inconsistent databases. The consistent answer to a query q on an inconsistent database db is the intersection of the answers to q on all repairs, where a repair is any consistent database that is maximally close to db. Unfortunately, computing consistent answers under primary key constraints has already exponential data complexity for very simple conjunctive queries, which is completely impracticable. In this paper, we propose a new framework for divulging an inconsistent database to end users, which adopts two postulates. The first postulate complies with CQA and states that inconsistencies should never be divulged to end users. Therefore, end users should only get consistent query answers. The second postulate states that the data complexity of user queries must remain tractable (i.e., in P or even in FO). User queries with exponential data complexity will be rejected. We investigate which consistent query answers can still be obtained under such access postulates.