Tractable approaches to consistent query answering in ontology-based-data access
In this talk, we address the problem of consistent query answering in ontology-based data access (OBDA). A robust system for ontology-based data access should provide meaningful answers to queries even when the data conflicts with the ontology. This can be accomplished by adopting an inconsistency-tolerant semantics, with the consistent query answering (CQA) semantics being the most prominent example. Unfortunately, query answering under the CQA semantics has been shown to be computationally intractable, even when extremely simple ontology languages are considered. First, we present and compare the CQA semantics and other inconsistency-tolerant semantics that have been proposed to overcome the above computational problem. Then, we propose two new families of inconsistency-tolerant semantics which approximate the CQA semantics from above and from below and converge to it in the limit. We study the data complexity of conjunctive query answering under these new semantics, and show a general tractability result for all known first-order rewritable ontology languages. We also analyze the combined complexity of query answering for ontology languages of the DL-Lite family. This is joint work with Meghyn Bienvenu (CNRS & Université Paris-Sud).