From Consistent Query Answering to Query Rewriting: A Detour around Answer Set Programs

by Leopoldo Bertossi

Consistent query answering (CQA) is the problem of specifying and computing consistent answers to queries from an inconsistent database, i.e. that fails to satisfy a given set of integrity constraints. In this presentation we revisit the notion of CQA and the methodology based on first-order (FO) query rewriting. We also survey some computational complexity results for CQA.

Given the limitations of CQA in terms of complexity and FO rewritability, we briefly review the application of Answer Set Programs (ASPs) to CQA, and also to virtual data integration and peer data exchange in the presence of inconsistencies.

Finally, we show how to apply some recent results about the specification of stable models using second-order classical logic to shed some light back on the logic of CQA and query rewriting for CQA. For this purpose, quantifier elimination techniques are utilized.