Datalog is adeclarativelogic programming language. While it is syntactically a subset ofProlog, Datalog generally uses a bottom-up rather than top-down evaluation model. This difference yields significantly different behavior and properties fromProlog. It is often used as aquery language fordeductive databases. Datalog has been applied to problems indata integration,networking,program analysis, and more.

A Datalog program consists offacts, which are statements that are held to be true, andrules, which say how to deduce new facts from known facts. For example, here are two facts that meanxerces is a parent of brooke andbrooke 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 answerqueries:

?-ancestor(xerces,X).

This query asks:Who are all the X that xerces is an ancestor of? For this example, it would returnbrooke anddamocles.

The non-recursive subset of Datalog is closely related to query languages forrelational databases, such asSQL. The following table maps between Datalog,relational algebra, andSQL concepts:

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

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

CREATETABLEs(z0TEXTNONNULL,z1TEXTNONNULL,PRIMARYKEY(z0,z1));CREATETABLEt(z0TEXTNONNULLPRIMARYKEY);INSERTINTOsVALUES('x','y');INSERTINTOtVALUES('y');CREATEVIEWrASSELECTs.z0,s.z1FROMs,tWHEREs.z1=t.z0;

A Datalog program consists of a list ofrules (Horn clauses).^[1] Ifconstant andvariable are twocountable sets of constants and variables respectively andrelation is a countable set ofpredicate symbols, then the followingBNF 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 asliterals. The atom to the left of the:- symbol is called thehead of the rule; the atoms to the right are thebody. 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 therange 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 doesnot include negation nor aggregates; see§ Extensions for more information about those constructs.

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

r(x):-.

The set of facts is called theextensional database orEDB of the Datalog program. The set of tuples computed by evaluating the Datalog program is called theintensional database orIDB.

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

r(x).

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

p:-q.

These are merely abbreviations (syntactic sugar); they have no impact on the semantics of the program.

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, andproof-theoretic. These three approaches can be proven equivalent.^[4]

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

A rule is called ground if all of its atoms (head and body) are ground. A ruleR₂ is aground instance of another ruleR₁ ifR₂ is the result of asubstitution of constants for all the variables inR₁. TheHerbrand base of a Datalog program is the set of all ground atoms that can be made with the constants appearing in the program. TheHerbrand model 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.^[5] The model-theoretic semantics define the minimal Herbrand model to be the meaning of the program.

LetI be thepower set of the Herbrand base of a programP. Theimmediate consequence operator forP is a mapT fromI toI 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 ofT to be the meaning of the program; this coincides with the minimal Herbrand model.^[6]

Thefixpoint 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 callednaïve evaluation.

The proof-theoretic semantics defines the meaning of a Datalog program to be the set of facts with correspondingproof 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 suchqueries. This reading informs theSLD resolution algorithm, which forms the basis for the evaluation ofProlog.

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

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 mirrors thefixpoint 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.^[7]

This sectionneeds expansion. You can help byadding missing information.(February 2023)

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

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 mentionedabove, each non-recursive Datalog rule corresponds precisely to aconjunctive query. Therefore, many of the techniques fromdatabase theory used to speed up conjunctive queries are applicable to bottom-up evaluation of Datalog, such as

• Index selection^[10]
• Query optimization, especially join order^[11][12]
• Join algorithms
• Selection ofdata structures used to store relations; common choices includehash tables andB-trees, other possibilities includedisjoint set data structures (for storingequivalence relations),^[13] bries (a variant oftries),^[14]binary decision diagrams,^[15] and evenSMT formulas^[16]

Many such techniques are implemented in modern bottom-up Datalog engines such asSoufflé. Some Datalog engines integrate SQL databases directly.^[17]

Bottom-up evaluation of Datalog is also amenable toparallelization. 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 usinglocking orlock-free data structures. The shared-memory setting may be further divided intosingle instruction, multiple data andmultiple instruction, multiple data paradigms:
  • Datalog engines that execute ongraphics processing units fall into the SIMD paradigm.^[18]
  • Datalog engines usingOpenMP^[19] are instances of the MIMD paradigm.
• In theshared-nothing setting, Datalog engines execute on acluster of nodes. Such engines generally operate by splitting relations into disjoint subsets based on ahash function, performing computations (joins) on each node, and then exchanging newly-generated tuples over the network.^[20] Examples include Datalog engines based onMPI,^[9]Hadoop,^[21] andSpark.^[22]

This sectionneeds expansion. You can help byadding missing information.(March 2023)

SLD resolution is sound and complete for Datalog programs.

Top-down evaluation strategies begin with aquery orgoal. Bottom-up evaluation strategies can answer queries by computing the entire minimal model and matching the query against it, but this can be inefficient if the answer only depends on a small subset of the entire model. Themagic sets algorithm takes a Datalog program and a query, and produces a more efficient program that computes the same answer to the query while still using bottom-up evaluation.^[23] A variant of the magic sets algorithm has been shown to produce programs that, when evaluated usingsemi-naïve evaluation, are as efficient as top-down evaluation.^[24]

Thedecision problem formulation of Datalog evaluation is as follows: "Given a Datalog programP split into a set of facts (EDB)E and a set of rulesR, and a ground atomA. IsA in the minimal model ofP?" In this formulation, there are three variations of thecomputational complexity of evaluating Datalog programs:^[25]

• Thedata complexity is the complexity of the decision problem whenA andE are inputs andR is fixed.
• Theprogram complexity is the complexity of the decision problem whenA andR are inputs andE is fixed.
• Thecombined complexity is the complexity of the decision problem whenA,E, andR are inputs.

With respect to data complexity, the decision problem for Datalog isP-complete (See Theorem 4.4 in^[25]). P-completeness for data complexity means that there exists a fixed Datalog query for which evaluation is P-complete. The proof is based onDatalog metainterpreter for propositional logic programs.

With respect to program complexity, the decision problem isEXPTIME-complete. In particular, evaluating Datalog programs always terminates; Datalog is notTuring-complete.

Some extensions to Datalog do not preserve these complexity bounds. Extensions implemented in someDatalog 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 allowobject-oriented programming, or to allowdisjunctions as heads ofclauses. These extensions have significant impacts on the language's semantics and on the implementation of a corresponding interpreter.

Datalog is a syntactic subset ofProlog,disjunctive Datalog,answer set programming,DatalogZ, andconstraint logic programming. When evaluated as an answer set program, a Datalog program yields a single answer set, which is exactly its minimal model.^[26]

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

This sectionneeds expansion. You can help byadding missing information.(February 2023)

Datalog can be extended to supportaggregate functions.^[27]

Notable Datalog engines that implement aggregation include:

• LogicBlox^[28]
• Soufflé

Adding negation to Datalog complicates its semantics, leading to whole new languages and strategies for evaluation. For example, the language that results from adding negation with thestable model semantics is exactlyanswer set programming.

Stratified negation can be added to Datalog while retaining its model-theoretic and fixed-point semantics. Notable Datalog engines that implement stratified negation include:

• LogicBlox^[29]
• Soufflé

Unlike inProlog, statements of a Datalog program can be stated in any order. Datalog does not have Prolog'scut operator. This makes Datalog a fullydeclarative language.

In contrast to Prolog, Datalog

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

This article deals primarily with Datalog without negation (see alsoSyntax and semantics of logic programming § Negation). However, stratified negation is a common addition to Datalog; the following list contrastsProlog with Datalog with stratified negation. Datalog with stratified negation

• also disallows complex terms as arguments ofpredicates,
• requires that every variable that appears in the head of aclause 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.^{[30][unreliable source?]}

Datalog generalizes many other query languages. For instance,conjunctive queries andunion of conjunctive queries can be expressed in Datalog. Datalog can also expressregular path queries.

When we considerordered databases, i.e., databases with anorder relation on theiractive domain, then theImmerman–Vardi theorem implies that the expressive power of Datalog is precisely that of the classPTIME: a property can be expressed in Datalog if and only if it is computable in polynomial time.^[31]

Theboundedness problem for Datalog asks, given a Datalog program, whether it isbounded, 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, or, equivalently, as aunion of conjunctive queries. Solving the boundedness problem on arbitrary Datalog programs isundecidable,^[32] but it can be made decidable by restricting to some fragments of Datalog.

Systems that implement languages inspired by Datalog, whethercompilers,interpreters,libraries, orembedded DSLs, are referred to asDatalog engines. Datalog engines often implement extensions of Datalog, extending it with additionaldata types,foreign function interfaces, or support for user-definedlattices. Such extensions may allow for writingnon-terminating or otherwise ill-defined programs.^{[citation needed]}

Here is a short list of systems that are either based on Datalog or provide a Datalog interpreter:

• FoundationDB provides a free-of-charge database binding for pyDatalog, with a tutorial on its use.^[37]
• Leapsight Semantic Dataspace (LSD) is a distributed deductive database that offers high availability, fault tolerance, operational simplicity, and scalability. LSD uses Leaplog (a Datalog implementation) for querying and reasoning and was created by Leapsight.^[38]
• LogicBlox, a commercial implementation of Datalog used for web-based retail planning and insurance applications.
• Profium Sense is a native RDF compliantgraph database written in Java. It provides Datalog evaluation support of user defined rules.
• .QL, a commercial object-oriented variant of Datalog created by Semmle for analyzing source code to detect security vulnerabilities.^[39]
• SecPAL a security policy language developed byMicrosoft Research.^[40]
• Stardog is agraph database, implemented inJava. It provides support forRDF and allOWL 2 profiles providing extensive reasoning capabilities, including datalog evaluation.
• StrixDB: a commercial RDF graph store,SPARQL compliant withLua API and Datalog inference capabilities. Could be used as httpd (Apache HTTP Server) module or standalone (although beta versions are under the Perl Artistic License 2.0).

Datalog is quite limited in its expressivity. It is notTuring-complete, and doesn't include basic data types such asintegers orstrings. This parsimony is appealing from a theoretical standpoint, but it means Datalogper se is rarely used as a programming language orknowledge representation language.^[41] MostDatalog 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 indata integration,information extraction,networking,security,cloud computing andmachine learning.^[42][43]Google has developed an extension to Datalog forbig data processing.^[44]

Datalog has seen application instatic program analysis.^[45] TheSoufflé dialect has been used to writepointer analyses forJava and acontrol-flow analysis forScheme.^[46][47] Datalog has been integrated withSMT solvers to make it easier to write certain static analyses.^[48] TheFlix dialect is also suited to writing static program analyses.^[49]

Some widely used database systems include ideas and algorithms developed for Datalog. For example, theSQL:1999 standard includesrecursive queries, and the Magic Sets algorithm (initially developed for the faster evaluation of Datalog queries) is implemented in IBM'sDB2.^[50]

The origins of Datalog date back to the beginning oflogic programming, but it became prominent as a separate area around 1977 when Hervé Gallaire andJack Minker organized a workshop onlogic anddatabases.^[51]David Maier is credited with coining the term Datalog.^[52]

• Answer set programming
• Conjunctive query
• DatalogZ
• Disjunctive Datalog
• Flix
• SWRL
• Tuple-generating dependency (TGD), a language forintegrity constraints onrelational 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.Bibcode:1989ITKDE...1..146C.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.

• Query languages
• Logic programming languages
• Declarative programming languages

• CS1 maint: work parameter with ISBN
• CS1 errors: periodical ignored
• CS1 maint: multiple names: authors list
• Articles with short description
• Short description matches Wikidata
• Articles to be expanded from February 2023
• All articles to be expanded
• Articles to be expanded from March 2023
• All articles lacking reliable references
• Articles lacking reliable references from March 2023
• All articles with unsourced statements
• Articles with unsourced statements from October 2023