Skip to Main content Skip to Navigation
Journal articles

Materializing Knowledge Bases via Trigger Graphs

Efthymia Tsamoura 1 David Carral 2 Enrico Malizia 3 Jacopo Urbani 4
2 GRAPHIK - Graphs for Inferences on Knowledge
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : The chase is a well-established family of algorithms used to materialize Knowledge Bases (KBs) for 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, called GLog, and our experiments show that it can be significantly more efficient than the chase enabling us to materialize Knowledge Graphs with 17B facts in less than 40 min using a single machine with commodity hardware.
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03344217
Contributor : David Carral Connect in order to contact the contributor
Submitted on : Tuesday, September 14, 2021 - 5:18:51 PM
Last modification on : Monday, October 11, 2021 - 1:24:06 PM

File

trigger-graphs-tr.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Efthymia Tsamoura, David Carral, Enrico Malizia, Jacopo Urbani. Materializing Knowledge Bases via Trigger Graphs. Proceedings of the VLDB Endowment (PVLDB), VLDB Endowment, 2021, 14 (6), pp.943-956. ⟨10.14778/3447689.3447699⟩. ⟨lirmm-03344217⟩

Share

Metrics

Record views

81

Files downloads

120