Zodd

A small embeddable Datalog engine in Zig

---

You can try Zodd in your web browser here.

You can download and use the latest pre-built Docker image for the web version of Zodd from the GHCR and run it with the following command:

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

Then open http://localhost:8085 in your browser.

What is Datalog?

Datalog is a declarative logic programming language for deductive databases. In contrast to SQL, which needs explicit joins and subqueries, Datalog lets you express recursive relationships naturally. Instead of defining a schema and queries in a relational database, you define a set of facts (base data) and rules (logical implications), and a Datalog engine automatically computes all derivable conclusions iteratively.

Below is a Datalog program that defines a directed graph and computes its transitive closure. The Simple Example section shows how to implement this using Zodd in Zig.

% 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

Datalog is used in many application domains, especially when recursive querying over structured data is needed. For example:

• Security and access control
  • Role-based authorization with hierarchical permission inheritance and explicit denials
  • Network reachability analysis through routing policies and firewall rules
  • Taint analysis to trace untrusted data through program flows and detect vulnerabilities
• Data governance and compliance
  • Data lineage tracking through ETL pipelines for GDPR and CCPA compliance
  • PII propagation analysis with anonymization checkpoints
• Healthcare and life sciences
  • Medical ontology reasoning with type hierarchies and property inheritance
  • Drug-disease relationship inference and side effect prediction
• Software engineering
  • Dependency resolution with transitive closure and cycle detection
  • Points-to analysis and other static analyses over program representations

Why Zodd?

• Written in pure Zig with a simple API
• Implements semi-naive evaluation for efficient recursive query processing
• Uses immutable, sorted, and deduplicated relations as core data structures
• Provides primitives for multi-way joins, anti-joins, secondary indexes, and aggregation
• Includes a Datalog frontend with a parser, a builder API, stratified negation, aggregates, and comparison operators

See ROADMAP.md for the list of implemented and planned 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

You can add Zodd to your project and start using it by following the steps below.

Installation

Run the following command in the root directory of your project to download Zodd:

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

Replace <branch_or_tag> with the desired branch or release tag, like main (for the developmental version) or v0.1.0. This command will download Zodd and add it to Zig's global cache and update your project's build.zig.zon file.

Note

Zodd is developed and tested with Zig version 0.16.0.

Adding to Build Script

Next, modify your build.zig file to make Zodd available to your build target as a module.

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

Finally, you can @import("zodd") and start using it in your Zig project.

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

You can find the API documentation for the latest release of Zodd here.

Examples

Check out the examples directory for example usages of Zodd.

---

Contributing

See CONTRIBUTING.md for details on how to make a contribution.

License

Zodd is licensed under the MIT License (see LICENSE).

Acknowledgements

• The logo shows a directed graph that edges form a Z, with a dashed arc for the derived fact path(a, d).
• This project uses the Minish for property-based testing and the Ordered for B-tree indices.
• Zodd is inspired and modeled after the Datafrog Datalog engine for Rust.