The paper Towards Elastic Incrementalization for Datalog has been published in PPDP 2021: 23rd International Symposium on Principles and Practice of Declarative Programming. A recorded talk is available here.

The paper describes a framework for elastic incremental Datalog evaluation, allowing for the result of a Datalog program to be updated given changes to the input. Note that this work is not yet available in the main branch of Soufflé, but can be found in this branch.

Abstract

Various incremental evaluation strategies for Datalog have been developed that reuse computations for small input changes. These methods assume that incrementalization is always a better strategy than recomputation. However, in real-world applications such as static program analysis, recomputation can be cheaper than incrementalization for large updates. This work introduces an elastic incremental approach with two strategies that can be selected based on the impact of the input change. The first strategy is a Bootstrap strategy that recomputes the entire result for high-impact changes. The second is an Update strategy that performs an incremental update for low-impact changes. Our approach allows for a lightweight Bootstrap strategy suitable for high-impact changes, with the trade-off that Update may require more work for small changes. We demonstrate our approach using real-world applications and compare our elastic incremental approach to existing methods.