Answering Queries with Negation over Existential Rules


  • Stefan Ellmauthaler TU Dresden
  • Markus Krötzsch TU Dresden
  • Stephan Mennicke TU Dresden



Knowledge Representation And Reasoning (KRR)


Ontology-based query answering with existential rules is well understood and implemented for positive queries, in particular conjunctive queries. For queries with negation, however, there is no agreed-upon semantics or standard implementation. This problem is unknown for simpler rule languages, such as Datalog, where it is intuitive and practical to evaluate negative queries over the least model. This fails for existential rules, which instead of a single least model have multiple universal models that may not lead to the same results for negative queries. We therefore propose universal core models as a basis for a meaningful (non-monotonic) semantics for queries with negation. Since cores are hard to compute, we identify syntactic conditions (on rules and queries) under which our core-based semantics can equivalently be obtained for other universal models, such as those produced by practical chase algorithms. Finally, we use our findings to propose a semantics for a broad class of existential rules with negation.




How to Cite

Ellmauthaler, S., Krötzsch, M., & Mennicke, S. (2022). Answering Queries with Negation over Existential Rules. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 5626-5633.



AAAI Technical Track on Knowledge Representation and Reasoning