2021/08/25 by Xiaowen Hu, Joshua Karp, Hu, Xiaowen +9
Computer Science · #FOS: Computer and information sciences #Programming Languages (cs.PL) #Software Engineering Research #Software System Performance and Reliability #Software Testing and Debugging Techniques
paper · pdf · doi:10.48550/arxiv.2108.11212
openalex publication_date 2021/08/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Datalog has become a popular implementation language for solving large-scale, real-world problems, including bug finders, network analysis tools, and disassemblers. These applications express complex behaviour with hundreds of relations and rules that often require a non-deterministic choice for tuples in relations to express worklist algorithms. This work is an experience report that describes the implementation of a choice construct in the Datalog engine Souffle. With the choice construct, we can express worklist algorithms such as spanning trees in a few lines of code. We highlight the differences between rule-based choice as described in prior work, and relation-based choice introduced by this work. We show that a choice construct enables certain worklist algorithms to be computed up to 10kx faster than having no choice construct.