Syntax and semantics of logic programming

Logic programming is a programming paradigm that includes languages based on formal logic, including Datalog and Prolog. This article describes the syntax and semantics of the purely declarative subset of these languages that consist entirely of Horn clauses. Programs in the languages considered in this article consist entirely of rules of the form

h(x1, ..., xn) :- b1(y1, ..., ym), ..., bk(z1, ..., zm).

which can be read as implications

$b_{1}(y_{1},\ldots ,y_{m}),\ldots ,b_{k}(z_{1},\ldots ,z_{m})\rightarrow h(x_{1},\ldots ,x_{n})$

Concrete syntax

Datalog

A logic program consists of a list of rules (Horn clauses). 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 grammar expresses the structure of a logic 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>
<constant-list> ::= <constant> | <constant> "," <constant-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.

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

r(x) :- .

Facts are sometimes written without the :-, like so:

r(x).

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

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

References

Sources

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