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 provenance for a specific class of semirings. Theoretical and practical optimizations lead to an efficient implementation using \textsc{Souffl\'e}, a state-of-the-art Datalog interpreter. Experimental results on real-world data suggest this approach to be efficient in practical contexts, even competing with our previous dedicated solutions for computing provenance in annotated graph databases. The cost overhead compared to plain Datalog evaluation is fairly moderate in many cases of interest.
翻译:我们建立了一种翻译机制,用于对高光谱进行动态编程和计算基于半环的数据程序源代码。这种翻译的好处是,为特定类别的半环程序计算出源代码的新方法。理论和实践优化导致使用最新数据解析器\ textsc{Soffl\'e}(最新数据解析器)的高效实施。现实世界数据的实验结果表明,这种方法在实际中是有效的,甚至与我们先前在附加注释的图表数据库中计算源代码的专门解决方案相竞争。在很多感兴趣的情况下,与普通数据评估相比,成本管理相对比较是相当温和的。