• Ontology-Based Query Answering...

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

Title:
Ontology-Based Query Answering over Datalog-Expressible Rule Sets is Undecidable
Authors:
Carral, David, Larroque, Lucas, Thomazo, Michaël
Contributors:
Représentation de Connaissances et Langages à Base de Règles pour Raisonner sur les Données (BOREAL), Centre Inria d'Université Côte d'Azur, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Perpignan Via Domitia (UPVD)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Université de Montpellier Paul-Valéry (UMPV)-Université de Perpignan Via Domitia (UPVD)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Université de Montpellier Paul-Valéry (UMPV), Value from Data (VALDA), Département d'informatique - ENS-PSL (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris Sciences et Lettres (PSL)-Université Paris Sciences et Lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris Sciences et Lettres (PSL)-Université Paris Sciences et Lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)
Publisher Information:
CCSD, 2024.
Publication Year:
2024
Collection:
collection:ENS-PARIS
collection:CNRS
collection:INRIA
collection:UNIV-MONTP3
collection:UNIV-PERP
collection:INRIA-SOPHIA
collection:INRIA-ROCQ
collection:INRIASO
collection:INRIA_TEST
collection:INRIA34
collection:TESTALAIN1
collection:LIRMM
collection:INRIA2
collection:PSL
collection:INRIA-PSL
collection:UNIV-MONTPELLIER
collection:UNIV-COTEDAZUR
collection:ENS-PSL
collection:UPVM-TI
collection:UM-2015-2021
collection:UM-EPE
collection:BOREAL
collection:DIENS
Subject Terms:
Existential rules, Datalog, Undecidability, [INFO.INFO-LO]Computer Science [cs], Logic in Computer Science [cs.LO]
Subject Geographic:
Hanoi, Vietnam
Original Identifier:
HAL: hal-04710719
Document Type:
Konferenz conferenceObject<br />Conference papers
Language:
English
Access URL:
https://hal.science/hal-04710719
https://hal.science/hal-04710719v1/document
https://hal.science/hal-04710719v1/file/2024-kr-obqa-datalog-expressible-undecidable.pdf
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.hal.04710719v1
Database:
HAL

Weitere Informationen

Ontology-based query answering is a problem that takes as input an ontology R (in our context, a set of existential rules), a set F of facts, and a Boolean conjunctive query (CQ) q, and asks whether q follows from (R, F) under standard first-order semantics. This problem is undecidable in general, and a widely investigated approach to tackle it in some cases is query rewriting: given a "rule query" (R, q), we compute a Boolean query q' such that, for any fact set F, it holds that q follows from (R, F) if and only if q' follows from F. Insofar, previous work has mostly focused on output queries q' expressed as union of Boolean conjunctive queries (UCQs), and an effective algorithm that computes such a query q' whenever it exists has been proposed in the literature. However, UCQ-rewritability is not a very general notion and many real-world interesting rule queries do no admit UCQ-rewritings. This raises the question whether such a generic algorithm can be designed for a more expressive target language, such as datalog. We solve this question by the negative, by studying the difference between datalog-expressibility and datalog-rewritability. More precisely, we show that query answering under datalog-expressible rule queries is undecidable.