Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).
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(t1,...,tn), where p is a
predicate symbol and each ti is a term. Each ti is called an
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 ask b, where 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.
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.
