This section expands the syntax for the propositional definite clause language. The syntax is based on normal mathematical notation for predicate symbols but follows Prolog’s convention for variables.

The syntax of Datalog is given by the following, where a word is a sequence of letters, digits, or an underscore (“$\mathrm{\_}$”):

• •

  A logical variable is a word starting with an upper-case letter or with “_”. For example $X$, $Room$, $B4$, $Raths$, and $The\mathrm{\_}big\mathrm{\_}guy$ are all variables.

• •

  A constant is a word that starts with a lower-case letter, or is a number constant or a string.

• •

  A predicate symbol is a word that starts with a lower-case letter. Constants and predicate symbols are distinguishable by their context in a knowledge base.

  For example, $kim$, $r123$, $f$, $grandfather$, and $borogroves$ can be constants or predicate symbols, depending on the context; $725$ is a constant.

• •

  A term is either a variable or a constant.

  For example $X$, $kim$, $cs422$, $mome$, or $Raths$ can be terms.

• •

  An atomic symbol, or simply an atom, is of the form $p$ or $p(t_1,\mathrm{\dots },t_n)$, where $p$ is a predicate symbol and each $t_i$ is a term. Each $t_i$ is called an argument to the predicate.

  For example, $teaches(sue,cs422)$, $in(kim,r123)$, $father(bill,Y)$, $happy(C)$, $outgrabe(mome,Raths)$, and $sunny$ can all be atoms. From context in the atom $outgrabe(mome,Raths)$, the symbol $outgrabe$ is a predicate symbol and $mome$ is a constant.

The notions of definite clause, rule, query, and knowledge base are the same as for propositional definite clauses but with the expanded definition of atom. The definitions are repeated here.

• •

  A definite clause is of the form

  $$h\leftarrow a_1\wedge \mathrm{\dots }\wedge a_m.$$

  where $h$ is an atom, the head of the clause, and each $a_i$ is an atom. It can be read “$h$ if $a_1$ and …and $a_m$”.

  If $m>0$, the clause is called a rule. $a_1\wedge \mathrm{\dots }\wedge a_m$ is the body of the clause.

  If $m=0$ the arrow can be omitted and the clause is called atomic clause or fact. An atomic clause has an empty body.

• •

  A knowledge base is a set of definite clauses.

• •

  A query is of the form

  $$\text{𝖺𝗌𝗄}{a}_1\wedge \mathrm{\dots }\wedge a_m.$$

• •

  An expression is either a term, an atom, a definite clause, or a query.

In our examples, we will follow the Prolog convention that comments, which are ignored by the system, extend from a “%” to the end of the line.

An expression is ground if it does not contain any variables. For example, $teaches(chris,cs322)$ is ground, but $teaches(Prof,Course)$ is not ground.

The next section defines the semantics. We first consider ground expressions and then extend the semantics to include variables.