Towards Elastic Incrementalization for Datalog
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.