Skip to content
Book Open access

The Backbone of Consistent Query Answering

Nov 2026 · Proceedings of the 35th ACM International Conference on Information and Knowledge Management · 0 citations · 40 references

Abstract

The existence of inconsistencies in databases has motivated the study of Consistent Query Answering (CQA) since the 1990s. Recent work proposed the use of Maximum Satisfiability (MaxSAT) for solving CQA for concrete types of inconsistencies. This paper shows that, for the types of inconsistencies solved with MaxSAT, it is the case that CQA corresponds to finding the backbone of a propositional formula. This observation not only yields a novel characterization in terms of the computational complexity of the problem, but it also enables significantly more efficient practical solutions. The experiments confirm that significant performance improvements can be obtained by computing the backbone instead of solving MaxSAT.

Read PDF

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.