Skip to main content

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

Thomas Lukasiewicz‚ Enrico Malizia and Cristian Molinaro


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.

Book Title
Proceedings of 20th International Conference on Principles of Knowledge Representation and Reasoning‚ KR 2023‚ Rhodes‚ Greece‚ September 2−8‚ 2023
Pierre Marquis and Tran Cao Son
AAAI Press