Datalog


Datalog is a declarative logic programming language. While it is syntactically a subset of Prolog, Datalog generally uses a bottom-up rather than top-down evaluation model. This difference yields significantly different behavior and properties from Prolog. It is often used as a query language for deductive databases. Datalog has been applied to problems in data integration, networking, program analysis, and more.

Example

A Datalog program consists of facts, which are statements that are held to be true, and rules, which say how to deduce new facts from known facts. For example, here are two facts that mean xerces is a parent of brooke and brooke is a parent of damocles:

parent.
parent.

The names are written in lowercase because strings beginning with an uppercase letter stand for variables. Here are two rules:

ancestor :- parent.
ancestor :- parent, ancestor.

The :- symbol is read as "if", and the comma is read "and", so these rules mean:
  • X is an ancestor of Y if X is a parent of Y.
  • X is an ancestor of Y if X is a parent of some Z, and Z is an ancestor of Y.
The meaning of a program is defined to be the set of all of the facts that can be deduced using the initial facts and the rules. This program's meaning is given by the following facts:

parent.
parent.
ancestor.
ancestor.
ancestor.

Some Datalog implementations don't deduce all possible facts, but instead answer queries:

?- ancestor.

This query asks: Who are all the X that xerces is an ancestor of? For this example, it would return brooke and damocles.

Comparison to relational databases

The non-recursive subset of Datalog is closely related to query languages for relational databases, such as SQL. The following table maps between Datalog, relational algebra, and SQL concepts:
DatalogRelational algebraSQL
RelationRelationTable
FactTupleRow
RuleMaterialized view
QuerySelectQuery

More formally, non-recursive Datalog corresponds precisely to unions of conjunctive queries, or equivalently, negation-free relational algebra.

s.
t.
r :- s, t.


CREATE TABLE s ;
CREATE TABLE t ;
INSERT INTO s VALUES ;
INSERT INTO t VALUES ;
CREATE VIEW r AS
SELECT s.z0, s.z1
FROM s, t
WHERE s.z1 = t.z0;

Syntax

A Datalog program consists of a list of rules. If constant and variable are two countable sets of constants and variables respectively and relation is a countable set of predicate symbols, then the following BNF grammar expresses the structure of a Datalog program:

::= | ""
::= ":-" "."
::= ""
::= | "," | ""
::= |
::= | "," | ""

Atoms are also referred to as. The atom to the left of the :- symbol is called the of the rule; the atoms to the right are the. Every Datalog program must satisfy the condition that every variable that appears in the head of a rule also appears in the body.
There are two common conventions for variable names: capitalizing variables, or prefixing them with a question mark ?.
Note that under this definition, Datalog does include negation nor aggregates; see for more information about those constructs.
Rules with empty bodies are called. For example, the following rule is a fact:

r :-.

The set of facts is called the or of the Datalog program. The set of tuples computed by evaluating the Datalog program is called the or.

Syntactic sugar

Many implementations of logic programming extend the [|above] grammar to allow writing facts without the :-, like so:

r.

Some also allow writing 0-ary relations without parentheses, like so:

p :- q.

These are merely abbreviations ; they have no impact on the semantics of the program.

Semantics

Program
edge.
edge.
path :-
edge.
path :-
path,
edge.
Herbrand universex, y, z
Herbrand baseedge, edge,..., edge, path,..., path
Herbrand modeledge, edge, path, path, path

There are three widely-used approaches to the semantics of Datalog programs: model-theoretic, fixed-point, and proof-theoretic. These three approaches can be proven equivalent.
An atom is called if none of its subterms are variables. Intuitively, each of the semantics define the meaning of a program to be the set of all ground atoms that can be deduced from the rules of the program, starting from the facts.

Model theoretic

A rule is called ground if all of its atoms are ground. A rule R2 is a ground instance of another rule R1 if R2 is the result of a substitution of constants for all the variables in R1. The Herbrand base of a Datalog program is the set of all ground atoms that can be made with the constants appearing in the program. The of a Datalog program is the smallest subset of the Herbrand base such that, for each ground instance of each rule in the program, if the atoms in the body of the rule are in the set, then so is the head. The model-theoretic semantics define the minimal Herbrand model to be the meaning of the program.

Fixed-point

Let be the power set of the Herbrand base of a program P. The immediate consequence operator for P is a map from to that adds all of the new ground atoms that can be derived from the rules of the program in a single step. The least-fixed-point semantics define the least fixed point of to be the meaning of the program; this coincides with the minimal Herbrand model.
The [|fixpoint semantics] suggest an algorithm for computing the minimal model: Start with the set of ground facts in the program, then repeatedly add consequences of the rules until a fixpoint is reached. This algorithm is called [|naïve evaluation].

Proof-theoretic

The proof-theoretic semantics defines the meaning of a Datalog program to be the set of facts with corresponding proof trees. Intuitively, a proof tree shows how to derive a fact from the facts and rules of a program.
One might be interested in knowing whether or not a particular ground atom appears in the minimal Herbrand model of a Datalog program, perhaps without caring much about the rest of the model. A top-down reading of the proof trees described above suggests an algorithm for computing the results of such queries. This reading informs the SLD resolution algorithm, which forms the basis for the evaluation of Prolog.

Evaluation

There are many different ways to evaluate a Datalog program, with different performance characteristics.

Bottom-up evaluation strategies

Bottom-up evaluation strategies start with the facts in the program and repeatedly apply the rules until either some goal or query is established, or until the complete minimal model of the program is produced.

Naïve evaluation

Naïve evaluation mirrors the fixpoint semantics for Datalog programs. Naïve evaluation uses a set of "known facts", which is initialized to the facts in the program. It proceeds by repeatedly enumerating all ground instances of each rule in the program. If each atom in the body of the ground instance is in the set of known facts, then the head atom is added to the set of known facts. This process is repeated until a fixed point is reached, and no more facts may be deduced. Naïve evaluation produces the entire minimal model of the program.

Semi-naïve evaluation

Semi-naïve evaluation is a bottom-up evaluation strategy that can be asymptotically faster than naïve evaluation.

Performance considerations

Naïve and semi-naïve evaluation both evaluate recursive Datalog rules by repeatedly applying them to a set of known facts until a fixed point is reached. In each iteration, rules are only run for "one step", i.e., non-recursively. As mentioned above, each non-recursive Datalog rule corresponds precisely to a conjunctive query. Therefore, many of the techniques from database theory used to speed up conjunctive queries are applicable to bottom-up evaluation of Datalog, such as
Many such techniques are implemented in modern bottom-up Datalog engines such as Soufflé. Some Datalog engines integrate SQL databases directly.
Bottom-up evaluation of Datalog is also amenable to parallelization. Parallel Datalog engines are generally divided into two paradigms: