Dartfrog

---

Datafrog with a few more warts

What Is It?

This header-only library is a port and expansion of the Datafrog crate to C++

• #include <dartfrog.hpp> - Datafrog-equivalent APIs
• #include <datalog.hpp> - A Datalog inspired, compile-time DSL

Building

cmake -G "Unix Makefiles" -B bin
cmake --build bin
ctest --test-dir bin

Syntax Examples

Dartfrog

Transitive Closure

#include <dartfrog.hpp>

auto [iter1, edge] = Iteration{}.variable<std::pair<int, int>>();
auto [iter, path] = std::move(iter1).variable<std::pair<int, int>>();

edge->insert(Relation<std::pair<int, int>>::from_vec({{1, 2}, {2, 3}}));

while (iter.changed()) {
    path->from_join(*edge, *edge, *path,
                    [](int x, int z, int _) { return std::pair{x, z}; });
}

auto result = std::move(*path).complete();

Dartfrog DSL

Transitive Closure

#include <datalog.hpp>


auto x = Var<0>();
auto y = Var<1>();
auto z = Var<2>();

Datalog dl;
Predicate<int, 2> Edge(dl), Path(dl);

std::vector<std::array<int, 2>> edges = {{1, 2}, {2, 3}};
Edge.insert(rel<int>(edges));

dl.add_rule(Path(x, y) <= Edge(x, y));
dl.add_rule(Path(x, z) <= Path(x, y), Edge(y, z));
dl.solve();

auto result = Path.extract();

Translating Datalog into Dartfrog DSL

Let's translate the datalog rule head(VAR1, VAR2) :- foo(VAR1), bar(VAR2).

First you must instantiate a Datalog query object. This will act as the executable program we'll add rules to. For example:

#include <datalog.hpp>

Datalog dl;

You'll also need to declare variables, which can be done with the DL_VARS() macro:

DL_VARS(VAR1, VAR2);

which is syntactic sugar for the equivalent:

Var<0> VAR1;
Var<1> VAR2;

Note an important difference between variables in Dartfrog and standard Datalog. Datalog variables are placeholder names unified during computation and isolated to each rule. Each Dartfrog variable is a named wrapper over a column index. Each Dartfrog variable projects the indexed columns from the body atoms into the result tuple. Dartfrog variables are lexically scoped, meaning you can enclose rules in a block scope { ... } with a new DL_VARS() to rename or reset indices for individual rules.

For now we'll declare our predicates by specifying their data type and arity.

Predicate<int, 2> head(dl); /* head/2 */
Predicate<int, 1> foo(dl);  /* foo/1  */
Predicate<int, 1> bar(dl);  /* bar/1  */

Next we can write our rule using our predicates and our variables

RULE(dl, head(VAR1, VAR2) <= foo(VAR1), bar(VAR2));

And now we can solve this to fixpoint:

dl.solve();

But we haven't inserted any facts, so this won't do anything yet. In datalog we might write facts like this

FOO(1).
FOO(2).

BAR(1).
BAR(2).

In Dartfrog we assert a list of facts for each predicate instead:

foo.insert(rel({{1}, {2}}));
bar.insert(rel({{1}, {2}}));

Now after we run dl.solve() we can look at the head predicate to see the cross-product in the IDB:

auto results = head.extract();
ASSERT_EQ(results, {{1, 1}, {1, 2}, {2, 1}, {2, 2}});

If our rule was an equi-join instead like head(VAR1, VAR2, VAR3) :- foo(VAR1, VAR2), bar(VAR2, VAR3)., dartfrog would join across the shared VAR2 in both atoms. make_reindexed can be used to tell the engine to automatically build secondary indices to perform these kinds of equijoins faster in exchange for more memory.

Negation is handled by applying the ! operator on the relevant atom.

RULE(dl, head(VAR1, VAR2) <= foo(VAR1), !bar(VAR2));

You can use filter expressions as well:

RULE(dl, head(VAR1, VAR2) <=
                foo(VAR1),
                bar(VAR2),
                where<VAR2>([](int var2) {
                    return var2 > 1;
                }))

and one aggregate per rule:

RULE(dl, head(VAR1, VAR2) <=
                foo(VAR1),
                bar(VAR2),
                where<VAR2>([](int var2) {
                    return var2 > 1;
                }),
                group_by<VAR1>([](std::span<const int> values) {
                    return std::accumulate(values.begin(), values.end(), 0);
                }))