Datalog

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(xerces, brooke).
parent(brooke, damocles).

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

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

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(xerces, brooke).
parent(brooke, damocles).
ancestor(xerces, brooke).
ancestor(brooke, damocles).
ancestor(xerces, damocles).

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

?- ancestor(xerces, X).

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

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:

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

s(x, y).
t(y).
r(A, B) :- s(A, B), t(B).

CREATE TABLE s (
  z0 TEXT NONNULL,
  z1 TEXT NONNULL,
  PRIMARY KEY (z0, z1)
);
CREATE TABLE t (
  z0 TEXT NONNULL PRIMARY KEY
);
INSERT INTO s VALUES ('x', 'y');
INSERT INTO t VALUES ('y');
CREATE VIEW r AS
SELECT s.z0, s.z1
FROM s, t
WHERE s.z1 = t.z0;

A Datalog program consists of a list of rules (Horn clauses).[1] 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:

<program> ::= <rule> <program> | ""
<rule> ::= <atom> ":-" <atom-list> "."
<atom> ::= <relation> "(" <term-list> ")"
<atom-list> ::= <atom> | <atom> "," <atom-list> | ""
<term> ::= <constant> | <variable>
<term-list> ::= <term> | <term> "," <term-list> | ""

Atoms are also referred to as literals. The atom to the left of the :- symbol is called the head of the rule; the atoms to the right are the body. Every Datalog program must satisfy the condition that every variable that appears in the head of a rule also appears in the body (this condition is sometimes called the range restriction).[1][2]

There are two common conventions for variable names: capitalizing variables, or prefixing them with a question mark ?.[3]

Note that under this definition, Datalog does not include negation nor aggregates; see § Extensions for more information about those constructs.

Rules with empty bodies are called facts. For example, the following rule is a fact:

r(x) :- .

The set of facts is called the extensional database or EDB of the Datalog program. The set of tuples computed by evaluating the Datalog program is called the intensional database or IDB.

r(x).

p :- q.

edge(x, y).
edge(y, z).
path(A, B) :- 
  edge(A, B).
path(A, C) :- 
  path(A, B), 
  edge(B, C).

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.[4]

An atom is called ground 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.

Proof-theoretic

Proof tree showing the derivation of the ground atom path(x, z) from the program

edge(x, y).
edge(y, z).
path(A, B) :- 
  edge(A, B).
path(A, C) :- 
  path(A, B), 
  edge(B, C).

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.

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

Performance considerations

A parallel Datalog engine was evaluated on the Theta supercomputer at Argonne National Laboratory.[9]

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

• Index selection and data structures (hash table, B-tree, etc.)[10]
• Query optimization, especially join order[11][12]
• Join algorithms

Many such techniques are implemented in modern bottom-up Datalog engines such as Soufflé. Some Datalog engines integrate SQL databases directly.[13]

Bottom-up evaluation of Datalog is also amenable to parallelization. Parallel Datalog engines are generally divided into two paradigms:

• In the shared-memory, multi-core setting, Datalog engines execute on a single node. Coordination between threads may be achieved using locking or lock-free data structures. Examples include Datalog engines using OpenMP.[14]

• In the shared-nothing setting, Datalog engines execute on a cluster of nodes. Such engines generally operate by splitting relations into disjoint subsets based on a hash function, performing computations (joins) on each node, and then exchanging newly-generated tuples over the network.[15] Examples include Datalog engines based on MPI,[16] Hadoop,[17] and Spark.[18]

The decision problem formulation of Datalog evaluation is as follows: Given a Datalog program P split into a set of facts (EDB) E and a set of rules R, and a ground atom A, is A in the minimal model of P? In this formulation, there are three variations of the computational complexity of evaluating Datalog programs:[21]

• The data complexity is the complexity of the decision problem when A and E are inputs and R is fixed.
• The program complexity is the complexity of the decision problem when A and R are inputs and E is fixed.
• The combined complexity is the complexity of the decision problem when A, E, and R are inputs.

With respect to data complexity, the decision problem for Datalog is P-complete. With respect to program complexity, the decision problem is EXPTIME-complete. In particular, evaluating Datalog programs always terminates; Datalog is not Turing-complete.

Some extensions to Datalog do not preserve these complexity bounds. Extensions implemented in some Datalog engines, such as algebraic data types, can even make the resulting language Turing-complete.

Several extensions have been made to Datalog, e.g., to support negation, aggregate functions, inequalities, to allow object-oriented programming, or to allow disjunctions as heads of clauses. These extensions have significant impacts on the language's semantics and on the implementation of a corresponding interpreter.

Datalog is a syntactic subset of Prolog, disjunctive Datalog, answer set programming, DatalogZ, and constraint logic programming. When evaluated as an answer set program, a Datalog program yields a single answer set, which is exactly its minimal model.[22]

Many implementations of Datalog extend Datalog with additional features; see § Datalog engines for more information.

Unlike in Prolog, statements of a Datalog program can be stated in any order. Datalog does not have Prolog's cut operator. This makes Datalog a fully declarative language.

In contrast to Prolog, Datalog

• disallows complex terms as arguments of predicates, e.g., p(x, y) is admissible but not p(f(x), y),
• disallows negation,
• requires that every variable that appears in the head of a clause also appear in a literal in the body of the clause.

This article deals primarily with Datalog without negation (see also Syntax and semantics of logic programming § Extending Datalog with negation). However, stratified negation is a common addition to Datalog; the following list contrasts Prolog with Datalog with stratified negation. Datalog with stratified negation

• also disallows complex terms as arguments of predicates,
• requires that every variable that appears in the head of a clause also appear in a positive (i.e., not negated) atom in the body of the clause,
• requires that every variable appearing in a negative literal in the body of a clause also appear in some positive literal in the body of the clause.[26]

The boundedness problem for Datalog asks, given a Datalog program, whether it is bounded, i.e., the maximal recursion depth reached when evaluating the program on an input database can be bounded by some constant. In other words, this question asks whether the Datalog program could be rewritten as a nonrecursive Datalog program. Solving the boundedness problem on arbitrary Datalog programs is undecidable,[27] but it can be made decidable by restricting to some fragments of Datalog.

Systems that implement languages inspired by Datalog, whether compilers, interpreters, libraries, or embedded DSLs, are referred to as Datalog engines. Datalog engines often implement extensions of Datalog, extending it with additional data types, foreign function interfaces, or support for user-defined lattices. Such extensions may allow for writing non-terminating or otherwise ill-defined programs.

Datalog is quite limited in its expressivity. It is not Turing-complete, and doesn't include basic data types such as integers or strings. This parsimony is appealing from a theoretical standpoint, but it means Datalog per se is rarely used as a programming language or knowledge representation language.[28] Most Datalog engines implement substantial extensions of Datalog. However, Datalog has a strong influence on such implementations, and many authors don't bother to distinguish them from Datalog as presented in this article. Accordingly, the applications discussed in this section include applications of realistic implementations of Datalog-based languages.

Datalog has been applied to problems in data integration, information extraction, networking, security, cloud computing and machine learning.[29][30] Google has developed an extension to Datalog for big data processing.[31]

Datalog has seen application in static program analysis.[32] The Soufflé dialect has been used to write pointer analyses for Java and a control-flow analysis for Scheme.[33][34] Datalog has been integrated with SMT solvers to make it easier to write certain static analyses.[35] The Flix dialect is also suited to writing static program analyses.[36]

Some widely used database systems include ideas and algorithms developed for Datalog. For example, the SQL:1999 standard includes recursive queries, and the Magic Sets algorithm (initially developed for the faster evaluation of Datalog queries) is implemented in IBM's DB2.[37]

The origins of Datalog date back to the beginning of logic programming, but it became prominent as a separate area around 1977 when Hervé Gallaire and Jack Minker organized a workshop on logic and databases.[38] David Maier is credited with coining the term Datalog.[39]

• Answer set programming
• Conjunctive query
• DatalogZ
• Disjunctive Datalog
• Flix
• SWRL
• Tuple-generating dependency (TGD), a language for integrity constraints on relational databases with a similar syntax to Datalog

• Ceri, S.; Gottlob, G.; Tanca, L. (March 1989). "What you always wanted to know about Datalog (and never dared to ask)" (PDF). IEEE Transactions on Knowledge and Data Engineering. 1 (1): 146–166. CiteSeerX 10.1.1.210.1118. doi:10.1109/69.43410. ISSN 1041-4347.
• Abiteboul, S. (1995). Foundations of databases. Richard Hull, Victor Vianu. Reading, Mass.: Addison-Wesley. ISBN 0-201-53771-0. OCLC 30546436.