An inconsistent database is a database that violates one or more integrity constraints, such as key constraints and denial constraints. The semantics of a database query posed on an inconsistent database is formalized using the notion of consistent answers, which is the intersection of the answers to the query posed on all repairs of the given inconsistent database. This is a principled approach to the semantics of queries on inconsistent databases, but it comes at a price: even for fixed conjunctive queries and fixed key constraints, computing the consistent answers can be a coNP-complete problem. The aim of this talk is to first survey the complexity of consistent query answering and then present an overview of CAvSAT, which is the first SAT-based system for consistent query answering. CAvSAT can handle the consistent answers of unions of conjunctive queries under denial constraints, as well as the range consistent answers of aggregation queries with the COUNT and SUM operators.

This is joint work with Akhil Dixit at Google.