This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(March 2023) (Learn how and when to remove this message)

Logic programming is aprogramming paradigm that includes languages based on formal logic, includingDatalog andProlog. This article describes the syntax and semantics of the purelydeclarative subset of these languages. Confusingly, the name "logic programming" also refers to aspecific programming language that roughly corresponds to the declarative subset of Prolog. Unfortunately, the term must be used in both senses in this article.

Declarative logic programs consist entirely ofrules of the form

H:-B1,...,BN.

Each such rule can be read as animplication:

${\displaystyle B_1\wedge \dots \wedge B_n\to H}$

meaning "If each${\displaystyle B_i}$ is true, then${\displaystyle H}$ is true". Logic programs compute the set of facts that are implied by their rules.

Many implementations of Datalog, Prolog, and related languages add procedural features such as Prolog'scut operator or extra-logical features such as aforeign function interface. The formal semantics of such extensions are beyond the scope of this article.

Datalog is the simplest widely-studied logic programming language. There are three major definitions of the semantics of Datalog, and they are all equivalent. The syntax and semantics of other logic programming languages are extensions and generalizations of those of Datalog.

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]

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

r(x):-.

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

r(x).

Many 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.

The following program computes the relationpath, which is thetransitive closure of the relationedge.

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 to be equivalent.^[3]

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 ground 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. Aninterpretation (also known as adatabase instance) is a subset of the Herbrand base. A ground atom is true in an interpretationI if it is an element ofI. A rule istrue in an interpretationI if for each ground instance of that rule, if all the clauses in the body are true inI, then the head of the rule is also true inI.

AHerbrand model of a Datalog programP is an interpretationI ofP which contains all the ground facts ofP, and makes all of the rules ofP true inI.Model-theoretic semantics state that the meaning of a Datalog program is its minimal Herbrand model (equivalently, the intersection of all its Herbrand models).^[4]

For example, this program:

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

has this Herbrand universe:x,y,z

and this Herbrand base:edge(x, x),edge(x, y), ...,edge(z, z),path(x, x), ...,path(z, z)

and this minimal Herbrand model:edge(x, y),edge(y, z),path(x, y),path(y, z),path(x, z)

LetI be the set of interpretations of a Datalog programP, that is,I =P(H), whereH is the Herbrand base ofP andP is thepowerset operator. Theimmediate consequence operator forP is the following mapT fromI toI: For each ground instance of each rule inP, if every clause in the body is in the input interpretation, then add the head of the ground instance to the output interpretation. This mapT ismonotonic with respect to thepartial order given by subset inclusion onT. By theKnaster–Tarski theorem, this map has a least fixed point; by theKleene fixed-point theorem the fixed point is thesupremum of the chain${\displaystyle T(\mathrm{\varnothing }),T(T(\mathrm{\varnothing })),\dots ,T^n(\mathrm{\varnothing }),\dots }$. The least fixed point ofM coincides with the minimal Herbrand model of the program.^[5]

Thefixpoint semantics suggest an algorithm for computing the minimal Herbrand 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.

Given a programP, aproof tree of a ground atomA is atree with a root labeled byA, leaves labeled by ground atoms from the heads of facts inP, and branches with children${\displaystyle A_1,\dots ,A_n}$ labeled by ground atomsG such that there exists a ground instance

G :- A1, ..., An.

of a rule inP. The proof-theoretic semantics defines the meaning of a Datalog program to be the set of ground atoms that can be derived from such trees. This set coincides with the minimal Herbrand model.^[6]

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, such a reading informs theSLD resolution algorithm, which forms the basis for the evaluation ofProlog.

The semantics of Datalog have also been studied in the context of fixpoints over more generalsemirings.^[7]

While the name "logic programming" is used to refer to the entire paradigm of programming languages including Datalog and Prolog, when discussing formal semantics, it generally refers to an extension of Datalog withfunction symbols. Logic programs are also calledHorn clause programs. Logic programming as discussed in this article is closely related to the "pure" ordeclarative subset ofProlog.

The syntax of logic programming extends the syntax of Datalog with function symbols. Logic programming drops the range restriction, allowing variables to appear in the heads of rules that do not appear in their bodies.^[8]

Due to the presence of function symbols, the Herbrand models of logic programs can be infinite. However, the semantics of a logic program is still defined to be its minimal Herbrand model. Relatedly, the fixpoint of the immediate consequence operator may not converge in a finite number of steps (or to a finite set). However, any ground atom in the minimal Herbrand model will have a finite proof tree. This is why Prolog is evaluated top-down.^[8] Just as in Datalog, the three semantics can be proven equivalent.

Logic programming has the desirable property that all three major definitions of the semantics of logic programs agree. In contrast, there are many conflicting proposals for the semantics of logic programs with negation. The source of the disagreement is that logic programs have a unique minimal Herbrand model, but in general, logic programming (or even Datalog) programs with negation do not.

Negation is writtennot, and can appear in front of any atom in the body of a rule.

<atom-list>::=<atom> | "not"<atom> |<atom> ","<atom-list> | ""

This sectionneeds expansion with: a formal definition of stratification. You can help byadding to it.(March 2023)

A logic program with negation isstratified when it is possible to assign each relation to somestratum, such that if a relationR appears negated in the body of a relationS, thenR is in a lower stratum thanS.^[9] The model-theoretic and fixed-point semantics of Datalog can be extended to handle stratified negation, and such extensions can be proved equivalent.

Many implementations of Datalog use a bottom-up evaluation model inspired by the fixed point semantics. Since this semantics can handle stratified negation, several implementations of Datalog implement stratified negation.

While stratified negation is a common extension to Datalog, there are reasonable programs that cannot be stratified. The following program describes a two-player game where a player wins if their opponent has no moves:^[10]

move(a,b).win(X):-move(X,Y),notwin(Y).

This program is not stratified, but it seems reasonable to think thata should win the game.

This section is empty. You can help byadding to it.(March 2023)

This section is empty. You can help byadding to it.(March 2023)

The stable model semantics define a condition for calling certain Herbrand models of a programstable. Intuitively, stable models are the "possible sets of beliefs that a rational agent might hold, given [the program]" as premises.^[11]

A program with negation may have many stable models or no stable models. For instance, the program

p:-notq.q:-notp.

has two stable models${\displaystyle \{p\}}$,${\displaystyle \{q\}}$. The one-rule program

p:-notp.

has no stable models.

Every stable model is a minimal Herbrand model. A Datalog program without negation has a single stable model, which is exactly its minimal Herbrand model. The stable model semantics defines the meaning of a logic program with negation to be its stable model, if there is exactly one. However, it can be useful to investigateall (or at least, several) of the stable models of a program; this is the goal ofanswer set programming.

This section is empty. You can help byadding to it.(March 2023)

Several other extensions of Datalog have been proposed and studied, including variants with support forinteger constants and functions (includingDatalogZ),^[12][13]inequality constraints in the bodies of rules, andaggregate functions.

Constraint logic programming allows for constraints over domains such as thereals orintegers to appear in the bodies of rules.

• Herbrand structure
• Logic programming
• Negation as failure
• Prolog syntax and semantics

• 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.

• Programming language syntax
• Logic programming

• Articles lacking in-text citations from March 2023
• All articles lacking in-text citations
• Articles with short description
• Short description matches Wikidata
• Articles to be expanded from March 2023
• All articles to be expanded
• Articles with empty sections from March 2023
• All articles with empty sections