gem-hunter

A small embeddable Datalog engine in Zig

docker run -d -p 8085:80 --rm ghcr.io/cogitatortech/zodd-web:latest

What is Datalog?

% Facts: a graph (with four nodes and three edges)
edge(1, 2).
edge(2, 3).
edge(3, 4).

% Rule: transitive closure of the graph
% The transitive closure is the set of all node pairs (X, Y) where node Y is
% reachable from node X through one or more directed edges.
reachable(X, Y) :- edge(X, Y).
reachable(X, Z) :- reachable(X, Y), edge(Y, Z).

% Query: find all pairs of nodes that are reachable from each other
?- reachable(X, Y).

%% Output:
% X = 1, Y = 2
% X = 1, Y = 3
% X = 1, Y = 4
% X = 2, Y = 3
% X = 2, Y = 4
% X = 3, Y = 4

Features

Important

Zodd is in early development, so bugs and breaking changes are expected. Please use the issues page to report bugs or request features.

Getting Started

Installation

zig fetch --save=zodd "https://github.com/CogitatorTech/zodd/archive/<branch_or_tag>.tar.gz"

Note

Zodd is developed and tested with Zig version 0.17.0.

Build Configuration

pub fn build(b: *std.Build) void {
    // ... The existing setup ...

    const zodd_dep = b.dependency("zodd", .{});
    const zodd_module = zodd_dep.module("zodd");
    exe.root_module.addImport("zodd", zodd_module);
}

Simple Example

const std = @import("std");
const zodd = @import("zodd");

pub fn main() !void {
    var gpa = std.heap.DebugAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    const Edge = struct { u32, u32 };

    // Base relation: edges in a graph
    var edges = try zodd.Relation(Edge).fromSlice(allocator, &[_]Edge{
        .{ 1, 2 },
        .{ 2, 3 },
        .{ 3, 4 },
    });
    defer edges.deinit();

    // Variable holding the reachability closure
    var reachable = zodd.Variable(Edge).init(allocator);
    defer reachable.deinit();
    try reachable.insertSlice(edges.elements);

    // Fixed-point iteration: reachable(X, Z) :- reachable(X, Y), edge(Y, Z)
    while (try reachable.changed()) {
        var batch: std.ArrayList(Edge) = .empty;
        defer batch.deinit(allocator);

        for (reachable.recent.elements) |r| {
            for (edges.elements) |e| {
                if (e[0] == r[1]) try batch.append(allocator, .{ r[0], e[1] });
            }
        }

        if (batch.items.len > 0) {
            const rel = try zodd.Relation(Edge).fromSlice(allocator, batch.items);
            try reachable.insert(rel);
        }
    }

    var result = try reachable.complete();
    defer result.deinit();

    std.debug.print("Reachable pairs: {d}\n", .{result.len()});
}

Documentation

Examples

Contributing

License

Acknowledgements