13.4.2 Bottom-up Procedure with Variables

The propositional bottom-up proof procedure can be extended to Datalog by using ground instances of the clauses. A ground instance of a clause is obtained by uniformly substituting constants for the variables in the clause. The constants required are those appearing in the knowledge base or in the query. If there are no constants in the knowledge base or the query, one must be invented.

Example 13.19.

Suppose the knowledge base is

	$\displaystyle{q(a).}$
	$\displaystyle{q(b).}$
	$\displaystyle{r(a).}$
	$\displaystyle{s(W)\leftarrow\mbox{}r(W).}$
	$\displaystyle{p(X,Y)\leftarrow\mbox{}q(X)\wedge\mbox{}s(Y).}$

The set of all ground instances is

	$\displaystyle{q(a).}$
	$\displaystyle{q(b).}$
	$\displaystyle{r(a).}$
	$\displaystyle{s(a)\leftarrow\mbox{}r(a).}$
	$\displaystyle{s(b)\leftarrow\mbox{}r(b).}$
	$\displaystyle{p(a,a)\leftarrow\mbox{}q(a)\wedge\mbox{}s(a).}$
	$\displaystyle{p(a,b)\leftarrow\mbox{}q(a)\wedge\mbox{}s(b).}$
	$\displaystyle{p(b,a)\leftarrow\mbox{}q(b)\wedge\mbox{}s(a).}$
	$\displaystyle{p(b,b)\leftarrow\mbox{}q(b)\wedge\mbox{}s(b).}$

The propositional bottom-up proof procedure of Section 5.3.2 can be applied to the grounding to derive $q(a)$ , $q(b)$ , $r(a)$ , $s(a)$ , $p(a,a)$ , and $p(b,a)$ as the ground instances that are logical consequences.

Example 13.20.

Suppose the knowledge base is

	$\displaystyle{p(X,Y).}$
	$\displaystyle{g\leftarrow\mbox{}p(W,W).}$

The bottom-up proof procedure for query “ $\mbox{{ask}~{}}~{}g$ ” must invent a new constant symbol, say $c$ . The set of all ground instances is then

	$\displaystyle{p(c,c).}$
	$\displaystyle{g\leftarrow\mbox{}p(c,c).}$

The propositional bottom-up proof procedure will derive $p(c,c)$ and $g$ .

If the query were “ $\mbox{{ask}~{}}~{}p(b,d)$ ” the set of ground instances would change to reflect the constants $b$ and $d$ .

The bottom-up proof procedure applied to the grounding of the knowledge base is sound, because each instance of each rule is true in every model. This procedure is essentially the same as the variable-free case, but it uses the set of ground instances of the clauses, all of which are true because the variables in a clause are universally quantified.

This bottom-up procedure will eventually halt for Datalog because there are only finitely many grounded atoms, and one ground atom is added to the consequence set each time through the loop.

This procedure is also complete for ground atoms. That is, if a ground atom is a consequence of the knowledge base, it will be derived. To prove this, as in the propositional case, we construct a particular generic model. Recall that a model specifies the domain, what the constants denote, and what is true. A Herbrand interpretation is an interpretation where the domain is symbolic and consists of all constants of the language. A constant is invented if there are no constants in the knowledge base or the query. In a Herbrand interpretation, each constant denotes itself. Thus, in the definition of an interpretation, $D$ and $\phi$ are fixed for a given program, and all that needs to be specified is $\pi$ , which defines the predicate symbols.

Consider the Herbrand interpretation where the true atoms are the ground instances of the relations that are eventually derived by the bottom-up procedure. It is easy to see that this Herbrand interpretation is a model of the rules given. As in the variable-free case, it is a minimal model in that it has the fewest true atoms of any model. If $KB\models g$ for ground atom $g$ , then $g$ is true in the minimal model and, thus, is eventually derived.

Example 13.21.

Consider the clauses of Figure 13.2. The bottom-up proof procedure can immediately derive each instance of $imm\_west$ given as a fact. The algorithm can then add the $imm\_east$ atoms to the consequence set:

	$\displaystyle{imm\_east(r103,r101)}$
	$\displaystyle{imm\_east(r105,r103)}$
	$\displaystyle{imm\_east(r107,r105)}$
	$\displaystyle{imm\_east(r109,r107)}$
	$\displaystyle{imm\_east(r111,r109)}$
	$\displaystyle{imm\_east(r129,r131)}$
	$\displaystyle{imm\_east(r127,r129)}$
	$\displaystyle{imm\_east(r125,r127)}$

Next, the $next\_door$ relations that follow can be added to the set of consequences, including

	$\displaystyle{next\_door(r101,r103)}$
	$\displaystyle{next\_door(r103,r101)}$

The $two\_door\_east$ relations can be added to the set of consequences, including

	$\displaystyle{two\_door\_east(r105,r101)}$
	$\displaystyle{two\_door\_east(r107,r103)}$

Finally, the $w e s t$ relations that follow can be added to the set of consequences.

Artificial Intelligence 2E

13.4.2 Bottom-up Procedure with Variables

Example 13.19.

Example 13.20.

Example 13.21.

Artificial
Intelligence 2E