What is Datalog?

Datalog is a declarative logic programming language descended from Prolog, designed for querying and reasoning over relational data. It is the database-focused cousin of Prolog — stripped of Prolog's arbitrary side effects and uncontrolled recursion, and fortified with guarantees that make it suitable for production systems.

This guide covers what Datalog is, where it came from, how it differs from Prolog, how it is used in industry, and how you can use it — including as a knowledge storage and reasoning layer for large language models.

A Brief History

The Logic Programming Lineage

The story begins in 1972 with Prolog (Programmation en Logique), created by Alain Colmerauer and Philippe Roussel at the University of Aix-Marseille. Prolog brought a radical idea: instead of writing how to compute an answer, you write what is true, and the engine figures out the rest.

Prolog's foundation is Horn clauses — a restricted form of first-order logic where each clause has at most one positive literal:

mortal(X) :- human(X).
human(socrates).

Read: "X is mortal if X is human. Socrates is human." From these two statements, Prolog derives mortal(socrates).

Prolog spread through AI research, expert systems, and computational linguistics through the 1980s. Japan's Fifth Generation Computer Systems project (1982–1992) chose Prolog as its primary language, bringing significant attention and funding.

But Prolog had problems that made it unsuitable as a general-purpose database query language:

1. The negation problem. Prolog's negation-as-failure (\+) depends on clause ordering. Reorder your clauses and you get different answers.
2. Termination. Left-recursive rules like path(X,Z) :- path(X,Y), edge(Y,Z) cause infinite loops unless carefully ordered.
3. Side effects. Prolog's cut (!) and assert/retract make programs unpredictable and non-declarative.
4. Direction dependence. Prolog rules can be run "backwards" — given mortal(X), you can ask "who is mortal?" or "is Socrates mortal?" — but this bidirectionality creates subtle bugs and complicates optimization.

Datalog Emerges

Datalog was defined in the mid-1980s by researchers working at the intersection of logic programming and database theory, most prominently Serge Abiteboul, Richard Hull, and Victor Vianu. Their work appears in Foundations of Databases (1995), but the language crystallized earlier through papers by Ullman, Maier, and others at Stanford and Bell Labs.

The key insight: if you take Prolog and enforce three constraints, you get something that is guaranteed to terminate, has predictable negation, and is amenable to database-style optimization:

These constraints are not limitations — they are design choices that trade expressiveness for guarantees. A Datalog program will always terminate. A Datalog program will always give the same answer regardless of rule ordering. A Datalog program's negation is well-founded.

The Fixpoint Connection

Datalog's semantics are rooted in fixed-point theory. Given a set of rules and facts, the "meaning" of a Datalog program is the least fixpoint — the smallest set of facts that makes all rules true simultaneously.

This is computed bottom-up: start with the given facts, apply rules to derive new facts, repeat until no new facts are produced. This bottom-up approach is the opposite of Prolog's top-down resolution (where you start from a query and work backwards to facts), and it is what makes Datalog terminable by construction.

The semi-naive evaluation algorithm (Bancilhon & Ramakrishnan, 1986) is the standard optimization: instead of re-evaluating all rules against all facts on each iteration, only consider facts that are new since the last iteration. This turns naive O(n²) evaluation into efficient delta-based computation.

Datalog vs. Prolog

The comparison is worth making in detail because it clarifies Datalog's design goals:

The key philosophical difference: Prolog is a programming language where you express algorithms in logic. Datalog is a query language where you express what you want to know, and the engine decides how to compute it.

Core Concepts

Facts

Facts are ground tuples — unconditional truths about the world:

parent(alice, bob).
parent(bob, carol).
parent(carol, dave).

In ExDatalog:

program
|> Program.add_relation("parent", [:atom, :atom])
|> Program.add_fact("parent", [:alice, :bob])
|> Program.add_fact("parent", [:bob, :carol])
|> Program.add_fact("parent", [:carol, :dave])

Rules

Rules are conditional truths — if the body is true, the head must be true:

ancestor(X, Y) :- parent(X, Y).
ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z).

In ExDatalog:

|> Program.add_rule(
     Rule.new(
       Atom.new("ancestor", [Term.var("X"), Term.var("Y")]),
       [{:positive, Atom.new("parent", [Term.var("X"), Term.var("Y")])}]
     )
   )
|> Program.add_rule(
     Rule.new(
       Atom.new("ancestor", [Term.var("X"), Term.var("Z")]),
       [
         {:positive, Atom.new("parent", [Term.var("X"), Term.var("Y")])},
         {:positive, Atom.new("ancestor", [Term.var("Y"), Term.var("Z")])}
       ]
     )
   )

The first rule says "X is an ancestor of Y if X is a parent of Y." The second says "X is an ancestor of Z if X is a parent of Y and Y is an ancestor of Z." This is recursion — a rule references its own head relation.

Negation

Datalog supports negation through stratified negation — you can write rules that say "X is true if Y is not true", as long as there is no circular dependency through negation:

bachelor(X) :- male(X), not married(X, _).

In ExDatalog:

|> Program.add_rule(
     Rule.new(
       Atom.new("bachelor", [Term.var("X")]),
       [
         {:positive, Atom.new("male", [Term.var("X")])},
         {:negative, Atom.new("married", [Term.var("X"), Term.wildcard()])}
       ]
     )
   )

The engine evaluates strata in order: first derive all positive facts in stratum 0, then use those results when evaluating negated literals in stratum 1. This guarantees that not married(X, _) is evaluated against a complete set of married couples — not a partial set.

Constraints (Built-in Predicates)

Rules can include comparison and arithmetic constraints:

high_earner(X) :- income(X, S), S > 100000.
tax(X, T) := income(X, A), rate(R), T = A * R.

In ExDatalog:

|> Program.add_rule(
     Rule.new(
       Atom.new("high_earner", [Term.var("X")]),
       [{:positive, Atom.new("income", [Term.var("X"), Term.var("S")])}],
       [Constraint.gt(Term.var("S"), Term.const(100_000))]
     )
   )

How Datalog Is Used in Industry

1. Static Analysis and Program Verification

Datalog's most successful industrial application is static analysis. The idea: encode a program's structure (calls, data flow, types) as facts, write rules that detect bugs, and let the engine compute all violations.

Soufflé (https://souffle-lang.github.io/) is a Datalog engine developed at Oracle Labs specifically for static analysis. It is used in production at Oracle, Facebook (now Meta), and several other companies to analyze Java, C++, and Go codebases with millions of lines of code.

Real-world examples:

• Doop (Bravenboer & Smaragdakis, 2009) uses Datalog to implement points-to analysis for Java — determining every object a reference variable can point to. A single Doop analysis can process hundreds of thousands of methods and produce millions of derived facts.
• CodeQL (GitHub) uses a Datalog-derived language for semantic code analysis. Security researchers write queries like "find SQL injection vulnerabilities" and the engine finds all matches across a repository.
• Facebook Infer uses a Datalog-based abstract interpretation to detect memory bugs in C++, Objective-C, and Java code before it ships.

2. Networking and Access Control

Datalog's recursive Rule evaluation makes it ideal for computing reachability in graphs — which is exactly what network access control requires.

CISCO's network verification tools use Datalog to check whether access control policies are correct and consistent. A single rule can express transitively reachable hosts:

reachable(X, Y) :- link(X, Y).
reachable(X, Z) :- link(X, Y), reachable(Y, Z).

Google's Zanzibar paper (2019) describes a system that evaluates authorization decisions using a relation-based model that is essentially Datalog. Google Drive, YouTube, and Cloud use it for the "anyone with the link can view" permission model.

Open Policy Agent (OPA) uses a Datalog-like language (Rego) for policy decisions across cloud-native infrastructure. Rego is not pure Datalog — it has some extensions — but its evaluation model is fixpoint- based.

3. Data Integration and ETL

Datalog excels at integration because rules can express both schema mapping and data cleaning logic in a single declarative specification:

customer_email(X, E) :- account(X, E, _).
customer_email(X, E) :- legacy_contact(X, E, _, _).

This says: "a customer's email is either from the account system or the legacy system." The engine computes all matches.

LogicBlox (later Reltio) built a commercial platform on Datalog that handled data integration, business rules, and analytics for enterprise customers in healthcare, retail, and finance.

4. Knowledge Graphs and Semantic Web

The RDF (Resource Description Framework) and OWL (Web Ontology Language) standards underpinning the Semantic Web are closely related to Datalog. RDF triples (subject, predicate, object) map directly to Datalog facts, and OWL inference rules (subclass, subproperty, transitivity) map to Datalog rules.

subClass(X, Z) :- subClass(X, Y), subClass(Y, Z).

This single rule computes transitive subclass closure — find every class that an entity belongs to, including through inheritance chains.

5. Security and Compliance

Auth0 (now Okta) published work on using Datalog for access control policy evaluation. Aserto builds authorization engines on Datalog-like evaluation. The pattern: encode your organization's policies as facts and rules, then query "can this user access this resource?" and get every reason why or why not.

Domain-Specific Use Case Examples

Use Case 1: Social Network — Friend-of-Friend Recommendations

# Declare relations
relation "friend", [:atom, :atom]
relation "suggested", [:atom, :atom]
relation "blocked", [:atom, :atom]

# Facts
fact "friend", [:alice, :bob]
fact "friend", [:bob, :carol]
fact "friend", [:bob, :dave]
fact "blocked", [:alice, :dave]

# Rules: suggest friends that are 2 hops away but not already friends
rule "suggested(X, Z) <- friend(X, Y), friend(Y, Z), not friend(X, Z), not blocked(X, Z)"

This computes every friend-of-friend recommendation, excludes current friends, and respects block lists. The transitive closure happens automatically through fixpoint evaluation.

Use Case 2: Supply Chain — Bill of Materials Explosion

# Direct subcomponents
relation "contains", [:atom, :atom]        # product, subcomponent
relation "lead_time", [:atom, :integer]    # part, days to procure
relation "critical", [:atom, :atom]         # part, risk_category

# Derived: transitive bill of materials
rule "bom_contains(X, Z) <- contains(X, Y), contains(Y, Z)"
rule "bom_contains(X, Z) <- contains(X, Z)"

# Derived: longest lead time in a product's BOM
rule "max_lead(P, D) <- bom_contains(P, C), lead_time(C, D), D > 14"

The bom_contains rule computes the full transitive closure of subcomponents. If a car contains an engine, and the engine contains a bolt, then the car contains the bolt — derived automatically, no recursive SQL needed.

Use Case 3: Fraud Detection — Circular Money Flows

relation "transfer", [:atom, :atom, :integer]  # from, to, amount
relation "cycle", [:atom, :atom]

# A transfer cycle exists when money flows from A back to A
rule "cycle(X, Z) <- transfer(X, Y, A), transfer(Y, Z, A), transfer(Z, X, _)"
rule "cycle(X, Z) <- transfer(X, Y, _), cycle(Y, Z)"

# Flag suspicious: large cycles where money returns to origin
rule "suspicious(X) <- cycle(X, X), transfer(_, X, A), A > 10000"

Datalog's transitive closure makes cycle detection natural — in SQL, this requires recursive CTEs that most developers find unintuitive.

Use Case 4: Bioinformatics — Protein Interaction Networks

relation "interacts", [:atom, :atom]
relation "in_pathway", [:atom, :atom]   # protein, pathway
relation "drug_target", [:atom, :atom]   # drug, protein

# Proteins in the same pathway interact
rule "pathway_interaction(P1, P2) <- in_pathway(P1, W), in_pathway(P2, W), interacts(P1, P2)"

# Drugs that target proteins interacting with a disease pathway
rule "repurpose_candidate(D, W) <- drug_target(D, P), pathway_interaction(P, Q), in_pathway(Q, W)"

Drug repurposing is a natural fit for Datalog: encode known interactions, let transitive rules discover chains, and query for candidates.

Use Case 5: Infrastructure — Network Reachability

relation "link", [:atom, :atom]
relation "firewall", [:atom, :atom]       # allows traffic from A to B
relation "reachable", [:atom, :atom]

# Direct reachability through links
rule "reachable(X, Y) <- link(X, Y)"

# Transitive reachability
rule "reachable(X, Z) <- link(X, Y), reachable(Y, Z)"

# Reachability through firewalls
rule "allowed(X, Y) <- reachable(X, Y), firewall(X, Y)"

# Find policy violations: reachable but not allowed
rule "violation(X, Y) <- reachable(X, Y), not allowed(X, Y)"

This is essentially what Cisco's formal verification tools and cloud security groups compute. One fixpoint evaluation replaces pages of imperative graph traversal code.

Datalog and LLMs: Knowledge Storage and Reasoning

The Problem

Large language models (LLMs) are powerful pattern matchers with significant limitations as knowledge stores:

Architecture: Datalog as a Knowledge Layer for LLMs

┌──────────────────────────────────────────────┐
│                  LLM Agent                    │
│  (natural language understanding/generation)│
└──────────────┬────────────────┬───────────────┘
               │                │
        "Tell me about X"   "What follows from Y?"
               │                │
               ▼                ▼
┌──────────────────────────────────────────────┐
│             ExDatalog Engine                  │
│  (declarative rules, fixpoint evaluation,      │
│   stratified negation, provenance)            │
└──────────────┬────────────────┬───────────────┘
               │                │
     Facts derived          Facts asserted
     from text extraction    from structured sources
               │                │
               ▼                ▼
┌──────────────────────────────────────────────┐
│           Knowledge Base (facts)              │
│  parent(alice, bob).  employee(alice, eng).    │
│  manages(alice, carol). ...                   │
└──────────────────────────────────────────────┘

Pattern 1: LLM as Fact Extractor, Datalog as Reasoner

The LLM reads unstructured text and extracts relational facts. Datalog rules then derive new knowledge that the LLM could not produce reliably:

# LLM extracts from a document:
fact "works_for", [:alice, :acme]
fact "works_for", [:bob, :acme]
fact "manages", [:carol, :alice]
fact "manages", [:carol, :bob]

# Datalog rules derive organizational hierarchy:
rule "reports_to(X, Y) <- manages(Y, X)"
rule "colleague(X, Y) <- works_for(X, C), works_for(Y, C), not X = Y"
rule "skip_level(X, Z) <- manages(Y, X), manages(Z, Y)"

The LLM can answer "Who are Alice's colleagues?" by querying the Datalog engine — the answer is derived, not hallucinated.

Pattern 2: Datalog as Consistency Checker

LLMs generating structured data often produce contradictions. Datalog rules can detect them:

# The LLM asserts two contradictory facts:
fact "alive", [:socrates]
fact "deceased", [:socrates]

# Datalog rule flags contradiction:
rule "contradiction(X) <- alive(X), deceased(X)"

A Datalog engine returns contradiction(socrates) — the LLM's output failed a consistency check.

Pattern 3: Datalog as Agent Memory

An autonomous LLM agent accumulates facts during a session. Datalog rules maintain derived beliefs:

# Agent observes:
fact "in_room", [:agent, :kitchen]
fact "in_room", [:cup, :kitchen]
fact "reachable", [:agent, :cup]    # I can reach the cup

# Rules derive affordances:
rule "can_use(X, Y) <- in_room(X, L), in_room(Y, L), reachable(X, Y)"
rule "in_room(X, L) <- in_room(X, L)"  # stability: things stay where they are

# After observation: "I moved to the living room"
fact "in_room", [:agent, :living_room]   # update

# Derived fact remains: can_use(agent, cup) if the cup is still reachable
# Datalog's fixpoint recomputes only what changed

Pattern 4: Multi-Agent Knowledge Sharing

Multiple LLM agents can share a Datalog knowledge base:

# Agent A contributes:
fact "observes", [:agent_a, :smoke, :kitchen]

# Agent B contributes:
fact "observes", [:agent_b, :fire_alarm, :hallway]

# Shared rules derive collective knowledge:
rule "fire_detected(L) <- observes(_, :smoke, L)"
rule "building_emergency <- fire_detected(_), observes(_, :fire_alarm, _)"

# Any agent can query: "Is there a building emergency?"
# The answer is derived from both agents' observations.

Why Not Just Use an LLM?

An LLM can answer "Is Alice an ancestor of Dave?" by pattern-matching on its training data. But:

1. Precision: The LLM might say "probably" or "I think so." Datalog says ancestor(alice, dave) is true or false — no hedging.
2. Completeness: Ask the LLM "list all ancestors of Dave" and it might miss some. Datalog's fixpoint semantics guarantee: if it can be derived, it will be.
3. Size: The LLM's context window holds maybe 100K tokens. A Datalog engine holds millions of facts in storage and evaluates in milliseconds.
4. Update: Tell the LLM "actually, Bob is not Carol's parent" and it might not correctly retract all consequences. In Datalog, you retract parent(bob, carol) and re-evaluate — ancestor(bob, carol), ancestor(alice, carol), and all transitive consequences update correctly.

Limitations and When Not to Use Datalog with LLMs

Datalog is not a replacement for vector databases or embedding search:

The sweet spot: use Datalog for structured, rule-based reasoning where correctness matters, and use the LLM for natural language understanding, extraction, and generation.

ExDatalog's Place in the Ecosystem

ExDatalog is a pure-Elixir implementation of a bottom-up, semi-naive Datalog engine with:

• Stratified negation — not works correctly, with the guarantee that negated literals are evaluated against the complete lower stratum.
• Provenance tracking — explain: true tells you which rule derived each fact.
• Telemetry — :telemetry events for query start, stop, and exception.
• Pluggable storage — swap the Storage.Map backend for ETS, Postgres, or any key-value store.
• No function symbols — pure Datalog semantics, guaranteed termination.

It is designed to be embedded in Elixir applications that need declarative reasoning: authorization engines, configuration validation, data pipelines, and yes — knowledge layers for AI agents.

Further Reading

• Abiteboul, Hull, Vianu. Foundations of Databases. 1995. The formal reference for Datalog semantics.
• Ceri, Gottlob, Tanca. What You Always Wanted to Know About Datalog (And Never Dared to Ask). IEEE TKDE 1989. Classic survey.
• Green, Kass, Bravenboer, Smaragdakis. Datalog as a Static Analysis Tool. 2010. The Doop approach.
• Soufflé: https://souffle-lang.github.io/ — Production Datalog engine for static analysis.
• Ngo, Reinecke, Faber, Batory. Datalog for the Web. 2018. Web-scale reasoning.
• Zanzibar: https://research.google/pubs/pub48190/ — Google's authorization system, Datalog-inspired.