Closed-World Semantics for Conjunctive Queries with Negation over ELH-bottom Ontologies

Closed-World Semantics for Conjunctive Queries with Negation over ELH-bottom Ontologies

Stefan Borgwardt, Walter Forkel

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Best Sister Conferences. Pages 6131-6135. https://doi.org/10.24963/ijcai.2019/849

Ontology-mediated query answering is a popular paradigm for enriching answers to user queries with background knowledge.  For querying the absence of information, however, there exist only few ontology-based approaches.  Moreover, these proposals conflate the closed-domain and closed-world assumption, and therefore are not suited to deal with the anonymous objects that are common in ontological reasoning. We propose a new closed-world semantics for answering conjunctive queries with negation over ontologies formulated in the description logic ELH-bottom, based on the minimal canonical model.  We propose a rewriting strategy for dealing with negated query atoms, which shows that query answering is possible in polynomial time in data complexity.
Keywords:
Knowledge Representation and Reasoning: Description Logics and Ontologies
Knowledge Representation and Reasoning: Computational Complexity of Reasoning
Knowledge Representation and Reasoning: Logics for Knowledge Representation
Knowledge Representation and Reasoning: Knowledge Representation Languages