KR2023Proceedings of the 20th International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning

Rhodes, Greece. September 2-8, 2023.

Edited by
  1. Pierre Marquis,
  2. Tran Cao Son
  3. Gabriele Kern-Isberner

ISSN: 2334-1033
ISBN: 978-1-956792-02-7

Sponsored by
Published by

Copyright © 2023 International Joint Conferences on Artificial Intelligence Organization

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

  1. Thomas Lukasiewicz(Vienna University of Technology, University of Oxford)
  2. Enrico Malizia(University of Bologna)
  3. Cristian Molinaro(University of Calabria)
PDF
BibTeX
https://doi.org/10.24963/kr.2023/46

Keywords

  1. Inconsistency- and exception tolerant reasoning, paraconsistent logics
  2. Computational aspects of knowledge representation
  3. Ontology-based data access, integration, and exchange

Abstract

Inconsistency-tolerant semantics have been proposed to provide meaningful ontological query answers even in the presence of inconsistencies. Several such semantics rely on the notion of a repair, which is a "maximal" consistent subset of the database, where different maximality criteria might be adopted depending on the application at hand. Previous work in the context of Datalog+/- has considered only the subset and cardinality maximality criteria.

We take here a step further and study inconsistency-tolerant semantics under maximality criteria 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.