  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.
