# Efficient Dependency Analysis for Rule-Based Ontologies

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 27 references that are in the map.
- First posted on arXiv 20 Jul 2022.

## 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)
- [Anatomy of the chase](https://mlsanity.com/paper/1303.6682/) (2013)
- [Answering Queries with Negation over Existential Rules](https://mlsanity.com/paper/2112.07376/) (2021)
- [Capturing Homomorphism-Closed Decidable Queries with Existential Rules](https://mlsanity.com/paper/2107.07811/) (2021)

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

- [Stratified Negation in RDF Rules: A Correct Approach (Extended Version)](https://mlsanity.com/paper/2607.28778/) (2026)
- [Recovering Explanations from Transformed Rule-Based Ontologies](https://mlsanity.com/paper/2608.06399/) (2026)

## Abstract (arXiv)

Several types of dependencies have been proposed for the static analysis of existential rule ontologies, promising insights about computational properties and possible practical uses of a given set of rules, e.g., in ontology-based query answering. Unfortunately, these dependencies are rarely implemented, so their potential is hardly realised in practice. We focus on two kinds of rule dependencies -- positive reliances and restraints -- and design and implement optimised algorithms for their efficient computation. Experiments on real-world ontologies of up to more than 100,000 rules show the scalability of our approach, which lets us realise several previously proposed applications as practical case studies. In particular, we can analyse to what extent rule-based bottom-up approaches of reasoning can be guaranteed to yield redundancy-free "lean" knowledge graphs (so-called cores) on practical ontologies.