# Answering Queries with Negation over Existential Rules

arXiv: https://arxiv.org/abs/2112.07376 · HTML: https://mlsanity.com/paper/2112.07376/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Dec 2021.

## Built on by (most cited first, 4 of 4)

- [Efficient Dependency Analysis for Rule-Based Ontologies](https://mlsanity.com/paper/2207.09669/) (2022)
- [Existential Notation3 Logic](https://mlsanity.com/paper/2308.07332/) (2023)
- [SHACL Validation in the Presence of Ontologies: Semantics and Rewriting Techniques](https://mlsanity.com/paper/2507.12286/) (2025)
- [Stratified Negation in RDF Rules: A Correct Approach (Extended Version)](https://mlsanity.com/paper/2607.28778/) (2026)

## Abstract (arXiv)

Ontology-based query answering with existential rules is well understood and implemented for positive queries, in particular conjunctive queries. The situation changes drastically for queries with negation, where there is no agreed-upon semantics or standard implementation. Stratification, as used for Datalog, is not enough for existential rules, since the latter still admit multiple universal models that can differ on 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 descriptions of queries that can equivalently be answered over other types of models. This leads to fragments of queries with negation that can safely be evaluated by current chase implementations. We establish new techniques to estimate how the core model differs from other universal models, and we incorporate our findings into a new reasoning approach for existential rules with negation.