Repository files navigation

DDlog is a programming language forincremental computation. It is well suited forwriting programs that continuously 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 onFrank McSherry'sexcellentdifferential dataflow library.

DDlog has the following key properties:

1. Relational: A DDlog program transforms a set of input relations (or tables) into a set of output relations.It is thus well suited for applications that operate on relational data, ranging from real-time analytics tocloud management systems and static program analysis tools.

2. Dataflow-oriented: At runtime, a DDlog program accepts astream of updates to input relations.Each update inserts, deletes, or modifies a subset of input records. DDlog responds to an input updateby outputting an update to its output relations.

3. Incremental: DDlog processes input updates by performing the minimum amount of worknecessary to compute changes to output relations. This has significant performance benefits for many queries.

4. Bottom-up: DDlog starts from a set of input facts andcomputesall possible derived facts by following user-defined rules, in a bottom-up fashion. Incontrast, top-down engines are optimized to answer individual user queries without computing allpossible facts ahead of time. For example, given a Datalog program that computes pairs of connectedvertices in a graph, a bottom-up engine maintains the set of all such pairs. A top-down engine, onthe other hand, is triggered by a user query to determine whether a pair of vertices is connectedand handles the query by searching for a derivation chain back to ground facts. The bottom-upapproach is preferable in applications where all derived facts must be computed ahead of time and inapplications where the cost of initial computation is amortized across a large number of queries.

5. In-memory: DDlog stores and processes data in memory. In a typical use case, a DDlog programis used in conjunction with a persistent database, with database records being fed to DDlog asground 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 singlemachine. We are working on a distributed version of DDlog that will be able topartition its state and computation across multiple machines.

6. Typed: In its classical textbook form Datalog is more of a mathematical formalism than apractical tool for programmers. In particular, pure Datalog does not have concepts like types,arithmetics, strings or functions. To facilitate writing of safe, clear, and concise code, DDlogextends pure Datalog with:

   1. A powerful type system, including Booleans, unlimited precision integers, bitvectors, floating point numbers, strings,tuples, tagged unions, vectors, sets, and maps. All of these types can bestored in DDlog relations and manipulated by DDlog rules. Thus, with DDlogone can perform relational operations, such as joins, directly over structured data,without having to flatten it first (as is often done in SQL databases).

   2. Standard integer, bitvector, and floating point 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.

7. Integrated: while DDlog programs can be run interactively via a command line interface, itsprimary use case is to integrate with other applications that require deductive databasefunctionality. A DDlog program is compiled into a Rust library that can be linked against a Rust,C/C++, Java, or Go 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.

• Follow thetutorial for a step-by-step introduction to DDlog.
• DDloglanguage reference.
• DDlogcommand reference for writing and testing your own Datalog programs.
• How to use DDlog from Java.
• How to use DDlog from C.
• How to use DDlog from Go andGo API documentation.
• How to use DDlog from Rust (by example)
• Tutorial on profiling DDlog programs
• DDlog overview paper, Datalog 2.0 workshop, 2019.

To install a precompiled version of DDlog, download thelatest binary release, extract it from archive, addddlog/bin to your$PATH, and set$DDLOG_HOME to point to theddlog directory. You will also need to install the Rust toolchain (see instructions below).

If you're using OS X, you will need to override the binary's security settings throughthese instructions. Else, when first running the DDlog compiler (through callingddlog), you will get the following warning dialog:

"ddlog" cannot be opened because the developer cannot be verified.macOS cannot verify that this app is free from malware.

You are now ready tostart coding in DDlog.

• Haskellstack:

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

• Rust toolchain v1.52.1 or later:

  curl https://sh.rustup.rs -sSf | sh. $HOME/.cargo/envrustup component add rustfmtrustup component add clippy

  Note: Therustup 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 currentshell runsource $HOME/.cargo/env.
• JDK, e.g.:

  apt install default-jdk

• Google FlatBuffers library. Download and build FlatBuffers release 1.11.0 fromgithub. Make surethat theflatc tool is in your$PATH. Additionally, make sure that FlatBuffersJava classes are in your$CLASSPATH:

  ./tools/install-flatbuf.shcd flatbuffersexport CLASSPATH=`pwd`"/java":$CLASSPATHexport PATH=`pwd`:$PATHcd ..

• Static versions of the following libraries:libpthread.a,libc.a,libm.a,librt.a,libutil.a,libdl.a,libgmp.a, andlibstdc++.a can be installed from distro-specific packages. On Ubuntu:

  apt install libc6-dev libgmp-dev

  On Fedora:

  dnf install glibc-static gmp-static libstdc++-static

To build the software once you've installed the dependencies using one of theabove methods, clone this repository and set$DDLOG_HOME variable to pointto the root of the repository. Run

stack build

anywhere inside the repository to build the DDlog compiler.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 test basic DDlog functionality:

stack test --ta '-p path'

Note: this takes a few minutes

You are now ready tostart coding in DDlog.

The easiest way to enable differential datalog syntax highlighting for.dl files in Vim is bycreating a symlink from<ddlog-folder>/tools/vim/syntax/dl.vim into~/.vim/syntax/.

If you are using a plugin manager you may be able to directly consume the file from the upstreamrepository as well. In the case ofVundle, for example,configuration could look as follows:

callvundle#begin('~/.config/nvim/bundle')...Plugin'vmware/differential-datalog', {'rtp':'tools/vim'} <---- relevantline...callvundle#end()

To run the test suite with the GHCi debugger:

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

and typedo main in the command prompt.

stack clean

followed by

stack build --profile

or

stack test --profile