Debugging Large-Scale Datalog: A Scalable Provenance Evaluation Strategy
summary
A bottom-up evaluation augments Soufflé relations with proof annotations (rule id + minimal proof-tree height) so the engine computes and updates heights during semi-naïve fixpoint evaluation. An interactive provenance generator uses those annotations to build minimal-height proof trees on demand. Implementation handles DOOP/DaCapo and other benchmarks, produces annotations for tens of millions of tuples, adds specialized parallel data structures, and shows a measured runtime overhead of about 1.31× on average.
AI-written summary · about
chapters (19)
- 0:00A Brief History of Datalog
- 1:30Modern Datalog for Static Analysis
- 2:54Datalog Example
- 4:10Real World Datalog Program Analysis
- 4:39Datalog Debugging Challenge
- 6:06Debugging with Provenance
- 6:59Provenance for Datalog
- 8:08Constructing a Proof Tree
- 11:12Novel Provenance Evaluation Strategy for Debugging
- 13:23Computing Proof Annotations
- 18:04Complexity of Height Updates
- 19:36Augmented Datalog Evaluation in Summary
- 20:00Proof Tree Construction
- 20:17Constructing Proof Trees
- 22:08Soufflé
- 22:42Implementation of Provenance
- 23:53Performance Evaluation
- 24:51Provenance System
- 25:24Conclusion
related talks
30mAchieving Understandability and Privacy With Provenance-Based Explanations
17mInteractive Debugging of Datalog Programs
24mA Counterexample-Guided Debugger for Non-Recursive Datalog
17mBring Your Own Data Structures to Datalog
01h 06mAlgebraic Structures in Logic and Query Evaluation 1
13mAccelerating Program Analyses in Datalog by Merging Library Facts
34mProvenance for Reproducible Data Science
33mTowards Interpretable Data Science