A General Framework for Inconsistency−Tolerant Query Answering in Datalog+⁄−

Abstract

Inconsistency management in knowledge bases is an important problem that has been studied for a long time. During the recent years, additional interest in this topic has been sparked with the advent of the Semantic Web. In this paper, we study different semantics for query answering in inconsistent Datalog+⁄− ontologies. Datalog+⁄− is a family of ontology languages that is in particular useful for representing and reasoning over lightweight ontologies in the Semantic Web. We develop a general framework for inconsistency management in Datalog+⁄− ontologies based on incision functions from belief revision, in which we can characterize several query answering semantics as special cases: (i) consistent answers, originally developed for relational databases and recently adopted for some classes of description logics (DLs); (ii) intersection semantics, a sound approximation of consistent answers; and (iii) lazy answers, a novel semantics proposed as an alternative to approximations to consistent answers that, taking the union of lazy answers, can be used to obtain a good compromise between quality of answers and computation time for some fragments of Datalog+⁄−. We also provide complexity results for query answering under the different semantics, including data tractability results and first-order rewritability for query answering under the intersection semantics for linear Datalog+⁄−.