Fast Provenance in a Bottom-Up Evaluation

David Zhao, Bernhard Scholz, Paul Subotic
University of Sydney

Logic programming languages including Datalog-like languages, have seen a rise in popularity in recent years, now being widely used to answer questions about real world systems including program analysis, security analysis, declarative networking, cloud computing and business processes. Logic programing provides rapid-prototyping capabilities for applications, however, debugging of logic programming is still tedious and time consuming.  The concept of “provenance” has been introduced as a way of explaining the output of a Datalog programs.

In this talk, we present a new method that computes “proof trees” as form of “provenance”. We present a novel approach to lazily generate proof trees in a space- and time-efficient manner for a bottom-up Datalog evaluation strategy. We show that our approach scales better than existing methods, and can be applied to large-scale industrial real-world problems.  We demonstrate a prototype implementation of this method in Souffle, and show that it has superior performance compared to existing state of the art provenance systems.