# Materializing Knowledge Bases via Trigger Graphs

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 69 references that are in the map.
- First posted on arXiv 4 Feb 2021.

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

- [Knowledge Graphs](https://mlsanity.com/paper/2003.02320/) (2020)
- [The Vadalog System: Datalog-based Reasoning for Knowledge Graphs](https://mlsanity.com/paper/1807.08709/) (2018)
- [Column-Oriented Datalog Materialization for Large Knowledge Graphs (Extended Technical Report)](https://mlsanity.com/paper/1511.08915/) (2015)
- [Extracting Novel Facts from Tables for Knowledge Graph Completion (Extended version)](https://mlsanity.com/paper/1907.00083/) (2019)
- [Beyond the Grounding Bottleneck: Datalog Techniques for Inference in Probabilistic Logic Programs (Technical Report)](https://mlsanity.com/paper/1911.07750/) (2019)
- [Query Rewriting and Optimization for Ontological Databases](https://mlsanity.com/paper/1405.2848/) (2014)
- [A Single Approach to Decide Chase Termination on Linear Existential Rules](https://mlsanity.com/paper/1810.02132/) (2018)
- [Modular Materialisation of Datalog Programs](https://mlsanity.com/paper/1811.02304/) (2018)
- [Functional Dependencies Unleashed for Scalable Data Exchange](https://mlsanity.com/paper/1602.00563/) (2016)
- [Datalog Reasoning over Compressed RDF Knowledge Bases](https://mlsanity.com/paper/1908.10177/) (2019)
- [Adaptive Low-level Storage of Very Large Knowledge Graphs](https://mlsanity.com/paper/2001.09078/) (2020)
- [Goal-Driven Query Answering for Existential Rules with Equality](https://mlsanity.com/paper/1711.05227/) (2017)
- [On the k-Boundedness for Existential Rules](https://mlsanity.com/paper/1810.09304/) (2018)

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

- [Knowledge Graphs for the Life Sciences: Recent Developments, Challenges and Opportunities](https://mlsanity.com/paper/2309.17255/) (2023)
- [Epistemic Artificial Intelligence is Essential for Machine Learning Models to Truly 'Know When They Do Not Know'](https://mlsanity.com/paper/2505.04950/) (2025)
- [Chasing Streams with Existential Rules](https://mlsanity.com/paper/2205.02220/) (2022)
- [Normalisations of Existential Rules: Not so Innocuous!](https://mlsanity.com/paper/2206.03124/) (2022)
- [Efficient Temporal Datalog Materialisation for Composite Event Recognition](https://mlsanity.com/paper/2605.02488/) (2026)

## Abstract (arXiv)

The chase is a well-established family of algorithms used to materialize Knowledge Bases (KBs), like Knowledge Graphs (KGs), to tackle important tasks like query answering under dependencies or data cleaning. A general problem of chase algorithms is that they might perform redundant computations. To counter this problem, we introduce the notion of Trigger Graphs (TGs), which guide the execution of the rules avoiding redundant computations. We present the results of an extensive theoretical and empirical study that seeks to answer when and how TGs can be computed and what are the benefits of TGs when applied over real-world KBs. Our results include introducing algorithms that compute (minimal) TGs. We implemented our approach in a new engine, and our experiments show that it can be significantly more efficient than the chase enabling us to materialize KBs with 17B facts in less than 40 min on commodity machines.