KR2024Proceedings of the 21st International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning

Hanoi, Vietnam. November 2-8, 2024.

Edited by

ISSN: 2334-1033
ISBN: 978-1-956792-05-8

Sponsored by
Published by

Copyright © 2024 International Joint Conferences on Artificial Intelligence Organization

Ontology-Based Query Answering over Datalog-Expressible Rule Sets is Undecidable

  1. David Carral(LIRMM, Inria, University of Montpellier, CNRS, Montpellier, France)
  2. Lucas Larroque(Inria, DI ENS, ENS, CNRS, PSL University, Paris, France)
  3. Michaël Thomazo(Inria, DI ENS, ENS, CNRS, PSL University, Paris, France)

Keywords

  1. Computational aspects of knowledge representation-General
  2. Ontologies and knowledge-enriched data management-General

Abstract

Ontology-based query answering is a problem that takes as input a set of facts F, an ontology R (typically expressed by existential rules), a Boolean query q , and asks whether R and F entails q. This problem is undecidable in general, and a widely investigated approach to tackle it is called query rewriting: from (R,q) (a ``rule query'') is computed q_R such that for any set of facts F, it holds that R and F entail q iff F entails q_R. The literature mostly focused on q_R expressed as a union of conjunctive queries (UCQs), and an algorithm that such a q_R whenever it exists has been proposed in the literature.

However, UCQ-rewritability is applicable only in restricted settings. This raises the question whether such a generic algorithm can be designed for a more expressive language, such as datalog. We solve this question by the negative, by studying the difference between datalog-expressibility and datalog-rewritability. In particular, we show that query answering under datalog-expressible rule queries is undecidable.