# Stratified Negation in RDF Rules: A Correct Approach (Extended Version)

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 26 references that are in the map.
- First posted on arXiv 30 Jul 2026.

## Builds on (most cited first, 6 of 6)

- [The Vadalog System: Datalog-based Reasoning for Knowledge Graphs](https://mlsanity.com/paper/1807.08709/) (2018)
- [Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies](https://mlsanity.com/paper/1406.4110/) (2014)
- [Column-Oriented Datalog Materialization for Large Knowledge Graphs (Extended Technical Report)](https://mlsanity.com/paper/1511.08915/) (2015)
- [Answering Queries with Negation over Existential Rules](https://mlsanity.com/paper/2112.07376/) (2021)
- [Efficient Dependency Analysis for Rule-Based Ontologies](https://mlsanity.com/paper/2207.09669/) (2022)
- [Existential Notation3 Logic](https://mlsanity.com/paper/2308.07332/) (2023)

## Abstract (arXiv)

Combining RDF rule languages, such as N3 or SHACL Rules, with default negation is challenging. Existing methods to stratify negation often fail for RDF rules, since individual triples do not carry enough information to meaningfully restrict potential dependencies. Blank nodes in rule heads further complicate the matter, since the order of rule applications may determine whether new values are created, which in turn can change the applicability of rules with negation. To solve these open problems, we propose chain stratification as a robust new condition that guarantees a well-behaved semantics for RDF rules with negation, and existential rules in general. Our condition combines an elaborate analysis of potential multistep derivations with a mechanism for using integrity constraints to discard impossible cases. Applying rules in any order that respects chain stratification is guaranteed to derive an RDF graph that is unique, lean, and justified under the usual negation-as-failure semantics. To show the practicality, we also provide a prototype implementation.