Skip to content
An in-memory incremental Datalog engine based on Differential Dataflow
Haskell Rust Java Python C Yacc Other
Branch: master
Clone or download
Latest commit a3e8f6a Sep 20, 2019
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.travis Unified Travis scripts with installation script Aug 23, 2019
adapters/ovsdb Haskell warnings Aug 19, 2019
app Haskell warnings Aug 19, 2019
doc Java API documentation Sep 18, 2019
java XTest.java: typos Sep 21, 2019
lib Fix implementation of `Debug` for container types Aug 21, 2019
rust/template clippy: Fix occurrences of type_complexity lint Sep 18, 2019
src/Language/DifferentialDatalog Bump version to 0.9.0 Sep 18, 2019
test Integrate api & server_api tests with newly added unit testing feature Sep 19, 2019
tools Support relation names with dots; fixes #332 Sep 13, 2019
.gitignore Script to install dependencies (except Java) Aug 23, 2019
.travis.yml Fix cargo vendor usage to work with workspaces Sep 19, 2019
ChangeLog.md stack-based project (#2) Apr 3, 2018
LICENSE Update LICENSE Mar 20, 2018
Makefile Type cast implementation May 31, 2019
README.md Upgrade rustc dependency to 1.37.0 Sep 18, 2019
Setup.hs stack-based project (#2) Apr 3, 2018
install-dependencies.sh Do not install in HOME Aug 23, 2019
package.yaml
stack.yaml Consume githash in version 0.1.3.3 Sep 16, 2019

README.md

Build Status rustc

Differential Datalog (DDlog)

DDlog is a bottom-up, incremental, in-memory, typed Datalog engine. It is well suited for writing programs that incrementally update their output in response to input changes. With DDlog, the programmer does not need to worry about writing incremental algorithms. Instead they specify the desired input-output mapping in a declarative manner, using a dialect of Datalog. The DDlog compiler then synthesizes an efficient incremental implementation. DDlog is based on Frank McSherry's excellent differential dataflow library.

  1. Bottom-up: DDlog starts from a set of ground facts (i.e., facts provided by the user) and computes all possible derived facts by following Datalog rules, in a bottom-up fashion. In contrast, top-down engines are optimized to answer individual user queries without computing all possible facts ahead of time. For example, given a Datalog program that computes pairs of connected vertices in a graph, a bottom-up engine maintains the set of all such pairs. A top-down engine, on the other hand, is triggered by a user query to determine whether a pair of vertices is connected and handles the query by searching for a derivation chain back to ground facts. The bottom-up approach is preferable in applications where all derived facts must be computed ahead of time and in applications where the cost of initial computation is amortized across a large number of queries.

  2. Incremental: whenever the set of ground facts changes, DDlog only performs the minimum computation necessary to compute all changes in the derived facts. This has significant performance benefits for many queries.

  3. In-memory: DDlog stores and processes data in memory. In a typical use case, a DDlog program is used in conjunction with a persistent database, with database records being fed to DDlog as ground facts and the derived facts computed by DDlog being written back to the database.

    At the moment, DDlog can only operate on databases that completely fit the memory of a single machine. (This may change in the future, as DDlog builds on the differential dataflow library that supports distributed computation over partitioned data).

  4. Typed: Although Datalog is a programming language, in its classical textbook form it is more of a mathematical formalism than a practical tool for programmers. In particular, pure Datalog does not have concepts like data types, arithmetics, strings or functions. To facilitate writing of safe, clear, and concise code, DDlog extends pure Datalog with:

    1. A powerful type system, including Booleans, unlimited precision integers, bitvectors, strings, tuples, tagged unions, vectors, sets, and maps.

    2. Standard integer and bitvector arithmetic.

    3. A simple procedural language that allows expressing many computations natively in DDlog without resorting to external functions.

    4. String operations, including string concatenation and interpolation.

    5. Syntactic sugar for writing imperative-style code using for/let/assignments.

  5. Integrated: while DDlog programs can be run interactively via a command line interface, its primary use case is to integrate with other applications that require deductive database functionality. A DDlog program is compiled into a Rust library that can be linked against a Rust, C/C++ or Java program (bindings for other languages can be easily added). This enables good performance, but somewhat limits the flexibility, as changes to the relational schema or rules require re-compilation.

Documentation

Differential Datalog, Leonid Ryzhyk and Mihai Budiu Datalog 2.0, Philadelphia, PA, June 4-5, 2019.

Installation

From sources

To install the required dependencies for buidling DDlog run . ./install-dependencies.sh (If you want to use other versions of the Rust or Haskell tools you can manually install the required dependencies, as described below.)

Prerequisites

This section describes the manual installation of dependencies. We have tested our software on Ubuntu Linux and MacOS.

The compilers are written in Haskell. One needs the Glasgow Haskell Compiler. The Haskell compiler is managed by the stack tool. DDlog requires stack version 1.9.3 or later. To download stack (if you don't already have it) use:

wget -qO- https://get.haskellstack.org/ | sh

You will also need to install the Rust toolchain v1.37 or later:

curl https://sh.rustup.rs -sSf | sh

Note: The rustup script adds path to Rust toolchain binaries (typically, $HOME/.cargo/bin) to ~/.profile, so that it becomes effective at the next login attempt. To configure your current shell run source $HOME/.cargo/env.

If you intend to run the test suite or want to generate Java bindings, you will also need a Java installation containing javac.

Finally, you will need static versions of the following libraries: libpthread.a, libc.a, libm.a, librt.a, libutil.a, libdl.a, libgmp.a, which can be installed from distro-specific packages.

If you plan to use DDlog Java bindings, you will additionally need the Google FlatBuffers library. Download and build FlatBuffers release 1.11.0 from github. Make sure that the flatc tool is in your $PATH. Additionally, make sure that FlatBuffers Java classes are in your $CLASSPATH.

Building

To build the software:

git clone https://github.com/ryzhyk/differential-datalog.git
cd differential-datalog
stack build

To install DDlog binaries in Haskell stack's default binary directory:

stack install

To install to a different location:

stack install --local-bin-path <custom_path>

To run the tests execute (Note: this takes a while (~30 minutes on my system) and requires ~20GB of disk space):

stack test

Binary

To install a precompiled version of DDlog, download the latest binary release, extract it from archive and add ddlog/bin to your $PATH. You will also need to install the Rust toolchain (see instructions above)

vim syntax highlighting

Create a symlink to tools/dl.vim from the ~/.vim/syntax/ directory to enable differential datalog syntax highlighting in .dl files.

Debugging with GHCi

To run the test suite with the GHCi debugger:

stack ghci --ghci-options -isrc --ghci-options -itest differential-datalog:differential-datalog-test

and type do main in the command prompt.

Building with profiling info enabled

stack clean

followed by

stack build --profile

or

stack test --profile
You can’t perform that action at this time.