All-Instances Oblivious Chase Termination is Undecidable for Single-Head Binary TGDs
All-Instances Oblivious Chase Termination is Undecidable for Single-Head Binary TGDs
Bartosz Bednarczyk, Robert Ferens, Piotr Ostropolski-Nalewaja
Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 1719-1725.
https://doi.org/10.24963/ijcai.2020/238
The chase is a famous algorithmic procedure in database
theory with numerous applications in ontology-mediated query answering.
We consider static analysis of the chase termination
problem, which asks, given set of TGDs, whether the chase
terminates on all input databases. The problem was recently
shown to be undecidable by Gogacz et al. for
sets of rules containing only ternary predicates.
In this work, we show that undecidability occurs already
for sets of single-head TGD over binary vocabularies.
This question is relevant since many real-world ontologies, e.g.,
those from the Horn fragment of the popular OWL, are of this shape.
Keywords:
Knowledge Representation and Reasoning: Logics for Knowledge Representation
Multidisciplinary Topics and Applications: Databases