## 12.3 Datalog: A Relational Rule Language

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 ("*_*"):

- A logical
**variable**is a word starting with an upper-case letter or the underscore.For example

*X*,*Room*,*B4*,*Raths*, and*The_big_guy*are all variables.Logical variables are not the same as algebraic variables or random 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. - We expand the definition of
**atomic symbol**, or simply an**atom**, to be of the form*p*or*p(t*, where_{1},...,t_{n})*p*is a predicate symbol and each*t*is a term. Each_{i}*t*is called an_{i}**argument**to the predicate.For example,

*teaches(sue,cs422)*,*in(kim,r123)*,*sunny*,*father(bill,Y)*,*happy(C)*, and*outgrabe(mome,Raths)*can all be atoms. From context in the atom*outgrabe(mome,Raths)*, we know that*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
**body**is an atom or a conjunction of atoms. - A
**definite clause**is either an atom, called a**atomic clause**, or of the form*a←b*, called a**rule**, where*a*, the**head**, is an atom and*b*is a body. We will end clauses with a period. - A
**knowledge base**is a set of definite clauses. - A
**query**is of the form, where**ask**b*b*is a body. - 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.

**Example 12.2:**The following is a knowledge base:

*in(kim,R) ←teaches(kim,cs422) ∧in(cs422,R).*

*grandfather(sam,X)←father(sam,Y)∧parent(Y,X).*

*slithy(toves)←mimsy ∧borogroves∧outgrabe(mome,Raths).*

From context, *kim*, *cs422*,
*sam*, *toves*, and *mome* are constants;
*in*, *teaches*, *grandfather*, *father*, *parent*, *slithy*, *mimsy*, *borogroves*, and
*outgrabe* are predicate symbols; and *X*, *Y*, and *Raths* are
variables.

The first two clauses about Kim and Sam may make some intuitive sense, even though we have not explicitly provided any formal specification for the meaning of sentences of the definite clause language. However, regardless of the mnemonic names' suggestiveness, as far as the computer is concerned, the first two clauses have no more meaning than the third. Meaning is provided only by virtue of a semantics.

An expression
is **ground** if it does not contain any
variables. For example, *teaches(fred,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.