Efficient Provenance-Aware Querying of Graph Databases with Datalog

EasyChair Preprint 8978

Abstract

We establish a translation between a formalism for dynamic programming over hypergraphs and the computation of semiring-based provenance for Datalog programs. The benefit of this translation is a new method for computing the provenance of Datalog programs for specific classes of semirings, which we apply to provenance-aware querying of graph databases. Theoretical results and practical optimizations lead to an efficient implementation using \textsc{Soufflé}, a state-of-the-art Datalog interpreter. Experimental results on real-world data suggest this approach to be efficient in practical contexts, competing with dedicated solutions for graphs.

Keyphrases: Datalog, Graph Databases, Provenance, dynamic programming, semirings, transportation networks

@booklet{EasyChair:8978,
  author    = {Yann Ramusat and Silviu Maniu and Pierre Senellart},
  title     = {Efficient Provenance-Aware Querying of Graph Databases with Datalog},
  howpublished = {EasyChair Preprint 8978},
  year      = {EasyChair, 2022}}