Example queries and data for dynamic Datalog computation

This repository maintains a list of dynamic Datalog engines, those that update query outputs in response to changes in the input fact sets.

The repository also maintains several paired Datalog queries and input data, meant to exercise dynamic Datalog execution engines in non-trivial ways. These can be found in the ./problems/ subdirectory. These problems may also be independently interesting for evaluating non-dynamic Datalog engines.

• Differential Dataflow - A Rust framework for incremental data-parallel computation.
• Declarative Dataflow - An interpreted layer on top of Differential Dataflow.
• Differential Datalog - A compiler targeting Differential Dataflow.
• IncA - A framework for incremental program analysis with a Datalog-like language.

We also use the excellent Souffle as a non-dynamic baseline.

• crdt - A CRDT implementation of a shared text editor, from Martin Kleppmann.
• doop - A fragment of the Doop program analysis tool, from Yannis Smaragdakis.
• galen - An inference task in the GALEN medical ontology, from John Liagouris

For each problem we record reported times for various systems in various configurations, both to perform any query-specific compilation and then execution. These measurements are meant to be representative rather than definitive. All of the systems support multiple worker threads, and could be run in a variety of configurations on a variety of hardware platforms.

Unlike other measurements, the Differential Dataflow measurements are for hand-written code in a larger language, and can reflect implementation and optimizations not easily available within Datalog.

Souffle can often benefit from join planning help; without this help it can take orders of magnitude longer than it could. Such help is currently only provided for the Doop benchmark, and measurements for other queries could improve in the future.

The CRDT benchmark contains stratified negation, as well as several "maximization" idioms represented in Datalog using a quadratic number of facts, which can be more efficiently implemented as data-parallel reduce operations.

The DOOP benchmark is just really quite large.

The GALEN bencmark contains joins on highly skewed keys, for which correct or adaptive join orders are important.