Complexity of Inconsistency−Tolerant Query Answering in Datalog+/ under Preferred Repairs

Abstract

Inconsistency-tolerant semantics have been proposed to provide meaningful query answers even when knowledge bases are inconsistent. Several of such semantics rely on the notion of a repair, which is a "maximal" consistent subset of the knowledge base's facts, where different maximality criteria might be adopted depending on the application at hand. Previous work in the context of Datalog+/– has considered only the set-inclusion and cardinality criteria. In this paper, we take a step further and study inconsistency-tolerant semantics under other common maximality criteria, namely those based on weights and priority levels. We provide a thorough complexity analysis for a wide range of existential rule languages and for several complexity measures.