Chapter 12: Datalog & Logic Programming

                Learning Objectives:

                Learn Datalog, a declarative logic programming language. Write clean logical rules for knowledge representation, perform queries, and understand how Datalog differs from imperative programming.

What is Datalog?

Datalog is a declarative logic programming language. Instead of writing step-by-step instructions (imperative), you declare facts and rules about relationships, then ask questions. The system figures out how to find answers.

Key Difference:
Imperative (Python): "Do this, then do that, then check this condition"
Declarative (Datalog): "Facts are X. Rules are Y. Question: what is Z?"

Datalog Basics: Facts and Rules

Simple Family Example

Facts (ground facts):

% Parent relationships (facts)
parent(john, mary).
parent(john, bob).
parent(mary, alice).
parent(bob, charlie).

% Male/Female (facts)
male(john).
male(bob).
male(charlie).
female(mary).
female(alice).

Rules (inferred relationships):

% Rule: X is a grandparent of Z if X is parent of Y and Y is parent of Z
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

% Rule: X is a child of Y if Y is parent of X
child(X, Y) :- parent(Y, X).

% Rule: X and Y are siblings if they share a parent
sibling(X, Y) :- parent(Z, X), parent(Z, Y), X \= Y.

Queries (asking questions):

% Query 1: Who is the grandparent of alice?
?- grandparent(X, alice).
Answer: X = john

% Query 2: Who are all of john's children?
?- child(X, john).
Answer: X = mary; X = bob

% Query 3: Who are the siblings of alice?
?- sibling(alice, X).
Answer: X = (no one, alice has no siblings)

Medical Knowledge in Datalog

Disease Diagnosis Rules

% Facts: Patient symptoms
symptom(patient1, fever).
symptom(patient1, cough).
symptom(patient1, sore_throat).

% Facts: Disease-symptom mappings
disease_symptom(cold, fever).
disease_symptom(cold, cough).
disease_symptom(cold, sore_throat).

disease_symptom(flu, fever).
disease_symptom(flu, cough).
disease_symptom(flu, fatigue).

% Rule: Patient X has disease D if:
% - X has all symptoms required for disease D
% - No conflicting symptoms present
possible_disease(Patient, Disease) :-
    disease_symptom(Disease, Symptom1),
    disease_symptom(Disease, Symptom2),
    disease_symptom(Disease, Symptom3),
    symptom(Patient, Symptom1),
    symptom(Patient, Symptom2),
    symptom(Patient, Symptom3).

% Queries
?- possible_disease(patient1, X).
Answer: X = cold

Key Datalog Concepts

Concept	Example
Fact - Ground truth	parent(john, mary).
Rule - Inference	grandparent(X,Z) :- parent(X,Y), parent(Y,Z).
Query - Question	?- grandparent(john, X).
Variable - Placeholder	X, Y, Z (uppercase)
Predicate - Relationship	parent(X, Y)
Unification - Pattern matching	Finding X such that parent(X, mary) is true

Advantages of Datalog

Why Use Datalog?

Declarative: Specify WHAT, not HOW. System figures out the steps.
Logical: Rules follow formal logic. Provably correct.
Composable: Rules build on each other. Easy to understand relationships.
Auditable: Every answer traces back to specific facts and rules.
Scalable: Efficient query engines can optimize large datasets.

Datalog vs Other Languages

Same Problem: Find All Grandparents

Imperative Python:

# How to do it (step-by-step)
grandparents = []
for parent_id, child_id in parents_list:
    for parent_id2, child_id2 in parents_list:
        if child_id == parent_id2:
            grandparents.append((parent_id, child_id2))
return grandparents

Datalog (Logic):

% What we want (declarative)
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
?- grandparent(X, Z).

SQL:

-- SQL is also declarative, but for relational data
SELECT p1.parent_id, p2.child_id
FROM parents p1
JOIN parents p2 ON p1.child_id = p2.parent_id;

Running Datalog: Practical Tools

Datalog isn't built into Python, but several libraries implement it:

# Python-Datalog: Pure Python implementation
from pyDatalog import pyDatalog

pyDatalog.clear()
# Declare predicates
pyDatalog.create_terms('parent, X, Y, Z, grandparent, child')

# Facts
parent('john', 'mary') <= True
parent('john', 'bob') <= True
parent('mary', 'alice') <= True

# Rules
(grandparent(X, Z) <= (parent(X, Y) & parent(Y, Z)))

# Query
print(grandparent(X, 'alice'))
# Output: ((john,),)

When to Use Datalog

Datalog is especially useful for:

Knowledge representation: Facts and rules about domain
Graph traversal: Multi-hop relationships, reachability
Logical inference: Deriving new facts from old ones
Constraint checking: Ensuring data satisfies logical rules
Neuro-symbolic systems: Symbolic reasoning layer in hybrid AI

Key Takeaways

Datalog is a declarative logic language: state facts and rules, ask questions
Rules use pattern matching and unification to infer new facts
Every answer is traceable back to specific facts and rules (auditable)
Scales well for knowledge graphs and multi-hop reasoning
Perfect for the symbolic reasoning component of neuro-symbolic AI

🔤 Datalog & Logic Programming