13.3 Datalog: A Relational Rule Language 13.3.1 Semantics of Ground Datalog 13.3.3 Queries with Variables

The third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including full text).

13.3.2 Interpreting Variables

When a variable appears in a clause, the clause is true in an interpretation only if the clause is true for all possible values of that variable.

To formally define semantics of variables, a variable assignment, $\rho$ , is a function from the set of variables into the domain $D$ . Thus, a variable assignment assigns an element of the domain to each variable. Given interpretation $\left<D,\phi,\pi\right>$ and variable assignment $\rho$ , each term denotes an individual in the domain. If the term is a constant, the individual is given by $\phi$ . If the term is a variable, the individual is given by $\rho$ . Given an interpretation and a variable assignment, each atom is either true or false, using the same definition as earlier. Thus, given an interpretation and a variable assignment, each clause is either true or false.

A clause is true in an interpretation if it is true for all variable assignments. The variables are said to be universally quantified in the scope of the clause. Thus, a clause is false in an interpretation means there is a variable assignment under which the clause is false.

Example 13.7.

The clause

part\_of(X,Y)\leftarrow\mbox{}in(X,Y).

is false in the interpretation of Example 13.5, because under the variable assignment with $X$ denoting Kim and $Y$ denoting Room 123, the clause’s body is true and the clause’s head is false.

The clause

in(X,Y)\leftarrow\mbox{}part\_of(Z,Y)\wedge\mbox{}in(X,Z).

is true, because in all variable assignments where the body is true, the head is also true.

Logical consequence is defined in the same way as it was for propositional definite clauses in Section 5.1.2: ground body $g$ is a logical consequence of $K B$ , written $KB\models g$ , if $g$ is true in every model of $K B$ .

Example 13.8.

Suppose the knowledge base $K B$ is

	$\displaystyle{in(kim,r123).}$
	$\displaystyle{part\_of(r123,cs\_building).}$
	$\displaystyle{in(X,Y)\leftarrow\mbox{}}$
	$\displaystyle\ \ \ \ {part\_of(Z,Y)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {in(X,Z).}$

The interpretation defined in Example 13.5 is a model of $K B$ , because each clause is true in that interpretation.

$KB\models in(kim,r123)$ , because this is stated explicitly in the knowledge base. If every clause of $K B$ is true in an interpretation, then $in(kim,r123)$ must be true in that interpretation.

$KB\not\models in(kim,r023)$ . The interpretation defined in Example 13.5 is a model of $K B$ , in which $in(kim,r023)$ is false.

$KB\not\models part\_of(r023,cs\_building)$ . Although $part\_of(r023,cs\_building)$ is true in the interpretation of Example 13.5, there is another model of $K B$ in which $part\_of(r023,cs\_building)$ is false. In particular, the interpretation which is like the interpretation of Example 13.5, but where

\pi(part\_of)(\left<\phi(r023),\phi(cs\_building)\right>)=\mbox{false}

is a model of $K B$ in which $part\_of(r023,cs\_building)$ is false.

$KB\models in(kim,cs\_building)$ . If the clauses in $K B$ are true in interpretation $I$ , it must be the case that $in(kim,cs\_building)$ is true in $I$ , otherwise, there is an instance of the third clause of $K B$ that is false in $I$ – a contradiction to $I$ being a model of $K B$ .

The following example shows how the semantics treats variables appearing in a clause’s body but not in its head.

Example 13.9.

In Example 13.8, the variable $Y$ in the clause defining $i n$ is universally quantified at the level of the clause; thus, the clause is true for all variable assignments. Consider particular values $c_{1}$ for $X$ and $c_{2}$ for $Y$ . The clause

	$\displaystyle{in(c_{1},c_{2})\leftarrow\mbox{}}$
	$\displaystyle\ \ \ \ {part\_of(Z,c_{2})\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {in(c_{1},Z).}$

is true for all variable assignments to $Z$ . If there exists a variable assignment $c_{3}$ for $Z$ such that $part\_of(Z,c_{2})\wedge\mbox{}in(c_{1},Z)$ is true in an interpretation, then $in(c_{1},c_{2})$ must be true in that interpretation. Therefore, you can read the last clause of Example 13.8 as “for all $X$ and for all $Y$ , $in(X,Y)$ is true if there exists a $Z$ such that $part\_of(Z,Y)\wedge\mbox{}in(X,Z)$ is true.”

The definite clause language makes universal quantification implicit. Sometimes it is useful to make quantification explicit. There are two quantifiers that are used in logic:

•

$\forall X~{}p(X)$ , read “for all $X$ , $p(X)$ ” means $p(X)$ is true for every variable assignment for $X$ . $X$ is said to be a universally quantified.
•

$\exists X~{}p(X)$ , read “there exists an $X$ such that $p(X)$ ” means $p(X)$ is true for some variable assignment for $X$ . $X$ is said to be existentially quantified.

The clause $P(X)\leftarrow\mbox{}Q(X,Y)$ means

\forall X~{}\forall Y~{}(P(X)\leftarrow\mbox{}Q(X,Y))

which is equivalent to

\forall X~{}(P(X)\leftarrow\mbox{}\exists Y~{}Q(X,Y)).

Thus, free variables that only appear in the body are existentially quantified in the scope of the body.

It may seem as though there is something peculiar about talking about a clause being true for cases where it does not make sense, as in the following example.

Example 13.10.

Consider the clause

	$\displaystyle{in(cs422,love)\leftarrow\mbox{}}$
	$\displaystyle\ \ \ \ {part\_of(cs422,sky)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {in(sky,love).}$

where $cs422$ denotes a course, $l o v e$ denotes an abstract concept, and $s k y$ denotes the sky. Here, the clause is vacuously true in the intended interpretation according to the truth table for $\leftarrow\mbox{}$ , because the clause’s right-hand side is false in the intended interpretation.

As long as whenever the head is nonsensical, the body is also, the rule can never be used to prove anything nonsensical. When checking for the truth of a clause, you must only be concerned with those cases in which the clause’s body is true. The convention that a clause is true whenever the body is false, even if it strictly does not make sense, makes the semantics simpler and does not cause any problems.

The Human’s View of Semantics

The formal description of semantics does not tell us why semantics is interesting or how it can be used as a basis to build intelligent systems. The methodology for using semantics for propositional logic programs can be extended to Datalog:

Step 1: Select the task domain or world to represent. This could be some aspect of the real world, for example, the structure of courses and students at a university or a laboratory environment at a particular point in time, some imaginary world, such as the world of Alice in Wonderland, or the state of the electrical environment if a switch breaks, or an abstract world, for example, the world of money, numbers and sets. Within this world, let the domain $D$ be the set of all individuals or things that you want to be able to refer to and reason about. Also, select which relations to represent.
Step 2: Associate constants in the language with individuals in the world that you want to name. For each element of $D$ you want to refer to by name, assign a constant in the language. For example, you may select the name “ $k i m$ ” to denote a particular professor, the name “ $cs322$ ” for a particular introductory AI course, the name “ $t w o$ ” for the number that is the successor of the number one, and the name “ $r e d$ ” for the color of stoplights. Each of these names denotes the corresponding individual in the world.
Step 3: For each relation that you may want to represent, associate a predicate symbol in the language. Each $n$ -ary predicate symbol denotes a function from $D^{n}$ into $\{\mbox{true},\mbox{false}\}$ , which specifies the subset of $D^{n}$ for which the relation is true. For example, the predicate symbol “ $t e a c h e s$ ” of two arguments (a teacher and a course) may correspond to the binary relation that is true when the individual denoted by the first argument teaches the course denoted by the second argument. These relations need not be binary. They could have any number of arguments (zero or more). For example, “ $is\_red$ ” may be a predicate that has one argument.

These associations of symbols with their meanings form an intended interpretation.
Step 4: Write clauses that are true in the intended interpretation. This is often called axiomatizing the domain, where the given clauses are the axioms of the domain. If the person who is denoted by the symbol $k i m$ actually teaches the course denoted by the symbol $cs322$ , you can assert the clause $teaches(kim,cs322)$ as being true in the intended interpretation.
Step 5: Ask queries about the intended interpretation. The system gives answers that you can interpret using the meaning assigned to the symbols.

Following this methodology, the knowledge base designer does not actually tell the computer anything until step 4. The first three steps are carried out in the head of the designer. Of course, the designer should document the denotations to make their knowledge base understandable to other people, so that they remember each symbol’s denotation, and so that they can check the truth of the clauses.

The world itself does not prescribe what the individuals are.

Example 13.11.

In one conceptualization of a domain, $p i n k$ may be a predicate symbol of one argument that is true when the individual denoted by that argument is pink. In another conceptualization, $p i n k$ may be an individual that is the color pink, and it may be used as the second argument to a binary predicate $c o l o r$ , which says that the individual denoted by the first argument has the color denoted by the second argument. Alternatively, someone may want to describe the world at a level of detail where various shades of $r e d$ are not distinguished, and so the color $p i n k$ would not be included. Someone else may describe the world in more detail, and decide that $p i n k$ is too general a term, and use the terms $c o r a l$ and $s a l m o n$ .

When the individuals in the domain are real physical things, it is usually difficult to give the denotation without physically pointing at the individual. When the individual is an abstract individual – for example, a university course or the concept of love – it is virtually impossible to write the denotation. However, this does not prevent the system from representing and reasoning about such concepts.

Example 13.12.

Example 5.7 represented the electrical environment of Figure 5.2 using propositions. Using individuals and relations can make the representation more intuitive, because the general knowledge about how switches work can be clearly separated from the knowledge about a specific house.

To represent this domain, the first step is to decide what individuals exist in the domain. In what follows, assume that each switch, each light, and each power outlet is an individual. Each wire between two switches and between a switch and a light is also an individual. Someone may claim that, in fact, there are pairs of wires joined by connectors and that the electricity flow must obey Kirchhoff’s laws. Someone else may decide that even that level of abstraction is inappropriate because we should model the flow of electrons. However, an appropriate level of abstraction is one that is useful for the task at hand. A resident of the house may not know the whereabouts of the connections between the individual strands of wire or even the voltage. Therefore, we assume a flow model of electricity, where power flows from the outside of the house through wires to lights. This model is appropriate for the task of determining whether a light should be lit or not, but it may not be appropriate for other tasks.

Next, give names to each individual to which we want to refer. This is done in Figure 5.2. For example, the individual $w_{0}$ is the wire between light $l_{1}$ and switch $s_{2}$ .

Next, choose which relationships to represent. Assume the following predicates with their associated intended interpretations:

•

$light(L)$ is true if the individual denoted by $L$ is a light.
•

$lit(L)$ is true if the light $L$ is lit and emitting light.
•

$live(W)$ is true if there is power coming into $W$ ; that is, $W$ is live.
•

$up(S)$ is true if switch $S$ is up.
•

$down(S)$ is true if switch $S$ is down.
•

$ok(E)$ is true if $E$ is not faulty; $E$ can be either a circuit breaker or a light.
•

$connected\_to(X,Y)$ is true if component $X$ is connected to $Y$ such that current would flow from $Y$ to $X$ .

At this stage, the computer has not been told anything. It does not know what the predicates are, let alone what they mean. It does not know which individuals exist or their names.

Before anything about the particular house is known, the system can be told general rules such as

\displaystyle{lit(L)\leftarrow\mbox{}light(L)\wedge\mbox{}live(L)\wedge\mbox{}% ok(L).}

Recursive rules let you state what is live from what is connected to what:

	$\displaystyle{live(X)\leftarrow\mbox{}connected\_to(X,Y)\wedge\mbox{}live(Y).}$
	$\displaystyle{live(outside).}$

For the particular house and configuration of components and their connections, the following facts about the world can be told to the computer:

	$\displaystyle{light(l_{1}).}$
	$\displaystyle{light(l_{2}).}$
	$\displaystyle{down(s_{1}).}$
	$\displaystyle{up(s_{2}).}$
	$\displaystyle{ok(cb_{1}).}$
	$\displaystyle{connected\_to(w_{0},w_{1})\leftarrow\mbox{}up(s_{2}).}$
	$\displaystyle{connected\_to(w_{0},w_{2})\leftarrow\mbox{}down(s_{2}).}$
	$\displaystyle{connected\_to(w_{1},w_{3})\leftarrow\mbox{}up(s_{1}).}$
	$\displaystyle{connected\_to(w_{3},outside)\leftarrow\mbox{}ok(cb_{1}).}$

These rules and atomic clauses are all that the computer is told. It does not know the meaning of these symbols. However, it can now answer queries about this particular house.

Artificial Intelligence 2E