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

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

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

Vortrag von David Carral
Ontology-based query answering takes as input an ontology R (typically given by existential rules), a set F of facts, and a Boolean conjunctive query q, and asks whether R, F ⊨ q. This problem is undecidable in general, and a widely studied way of dealing with it in specific cases is query rewriting: given a rule query (R, q), we compute a Boolean query qR such that, for every fact set F, we have that (R, F) ⊨ q if and only if F ⊨ qR.


Previous work has mostly focused on rewritings expressed as unions of conjunctive queries (UCQs), and an algorithm exists that computes such a rewriting whenever one exists. However, UCQ-rewritability is quite restrictive, and many interesting real-world rule queries admit no UCQ-rewriting. This raises the question of whether a similarly generic algorithm can be designed for a more expressive target language, such as datalog. We answer this question negatively: by studying the difference between datalog-expressibility and datalog-rewritability, we show that query answering is undecidable even for datalog-expressible rule queries.