Consistent query answering (CQA) is about formally characterizing and computing semantically correct answers to queries posed to a database that may fail to satisfy certain integrity constraints. In this paper, we revisit the decidability status of consistent query answering by considering different parameters of the problem as input to the decision problem. More specifically, we obtain some new results about the undecidability and combined complexity of CQA.

4th Alberto Mendelzon International Workshop on Foundations of Data Management, AMW 2010
School of Computer Science

Arenas, M. (Marcelo), & Bertossi, L. (2010). On the decidability of consistent query answering. Presented at the 4th Alberto Mendelzon International Workshop on Foundations of Data Management, AMW 2010.