Download PDFOpen PDF in browserEfficient Provenance-Aware Querying of Graph Databases with DatalogEasyChair Preprint 89789 pages•Date: October 3, 2022AbstractWe 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
|