An instance of a clause is obtained by uniformly substituting terms for variables in the clause. All occurrences of a particular variable are replaced by the same term.

The specification of which value is assigned to each variable is called a substitution. A substitution is a set of the form $\{V_1/t_1,\mathrm{\dots },V_n/t_n\}$, where each $V_i$ is a distinct variable and each $t_i$ is a term. The element $V_i/t_i$ is a binding for variable $V_i$. A substitution is in normal form if no $V_i$ appears in any $t_j$.

The application of a substitution $\sigma =\{V_1/t_1,\mathrm{\dots },V_n/t_n\}$ to expression $e$, written $e\sigma$, is an expression that is the same as the original expression $e$ except that each occurrence of $V_i$ in $e$ is replaced by the corresponding $t_i$. The expression $e\sigma$ is called an instance of $e$. If $e\sigma$ does not contain any variables, it is called a ground instance of $e$.

A substitution $\sigma$ is a unifier of expressions $e_1$ and $e_2$ if $e_1\sigma$ is identical to $e_2\sigma$; expressions $e_1$ and $e_2$ are said to unify. That is, a unifier of two expressions is a substitution that when applied to each expression results in the same expression.

Expressions can have many unifiers.

Substitution $\sigma$ is a most general unifier (MGU) of expressions $e_1$ and $e_2$ if

• •

  $\sigma$ is a unifier of the two expressions, and

• •

  if substitution ${\sigma }^{\prime }$ is also a unifier of $e_1$ and $e_2$, then $e{\sigma }^{\prime }$ must be an instance of $e\sigma$ for all expressions $e$.

Expression $e_1$ is a renaming of $e_2$ if they differ only in the names of variables. In this case, they are both instances of each other.

If two expressions have a unifier, they have at least one MGU. The expressions resulting from applying the MGUs to the expressions are all renamings of each other. That is, if $\sigma$ and ${\sigma }^{\prime }$ are both MGUs of expressions $e_1$ and $e_2$, then $e_1\sigma$ is a renaming of $e_1{\sigma }^{\prime }$.

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.

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, 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 $\varphi$ 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\vDash g$ for ground atom $g$, then $g$ is true in the minimal model and, thus, is eventually derived.

A computer does not need to reason at the propositional level by grounding. Instead, it can reason in terms of variables instead of multiple ground instances. Sometimes, it needs to replace variables by other variables or by constants.

The problem of unification is the following: given two atoms or terms, determine whether they unify, and, if they do, return a unifier of them. The unification algorithm finds a most general unifier (MGU) of two atoms or returns $\perp$ if they do not unify.

The unification algorithm is given in Figure 15.4. $E$ is a set of equality statements implying and implied by the unification of $t_1$ and $t_2$. $S$ is a substitution in normal form; if $\alpha /\beta$ is in the substitution $S$, then, by construction, $\alpha$ is a variable that does not appear elsewhere in $S$ or in $E$. In line 20, $\alpha$ and $\beta$ must have the same predicate and the same number of arguments; otherwise the unification fails.

The top-down proof procedure for propositional definite clauses can be extended to handle variables by allowing instances of rules to be used in the derivation.

A generalized answer clause is of the form

where $t_1,\mathrm{\dots },t_k$ are terms and $a_1,\mathrm{\dots },a_m$ are atoms. The use of $yes$ enables answer extraction: determining which instances of the query variables are a logical consequence of the knowledge base.

Initially, the generalized answer clause for query $q$ is

where $V_1,\mathrm{\dots },V_k$ are the variables that appear in the query $q$. Intuitively this means that an instance of $yes(V_1,\mathrm{\dots },V_k)$ is true if the corresponding instance of the query is true.

The proof procedure maintains a current generalized answer clause.

At each stage, the algorithm selects an atom in the body of the generalized answer clause. It then chooses a clause in the knowledge base whose head unifies with the atom.

The SLD resolution where SLD stands for selection linear definite, of the generalized answer clause

on $a_1$ with the chosen clause

where $a_1$ and $a$ have most general unifier $\sigma$, is the answer clause

where the body of the chosen clause has replaced $a_1$ in the answer clause, and the MGU $\sigma$ is applied to the whole answer clause.

An SLD derivation is a sequence of generalized answer clauses ${\gamma }_0$, ${\gamma }_1$, $\mathrm{\dots }$, ${\gamma }_n$ such that

• •

  ${\gamma }_0$ is the answer clause corresponding to the original query. If the query is $q$, with free variables $V_1,\mathrm{\dots },V_k$, the initial generalized answer clause ${\gamma }_0$ is

  $yes(V_1,\mathrm{\dots },V_k)\leftarrow q.$

• •

  ${\gamma }_i$ is obtained by selecting an atom $a_1$ in the body of ${\gamma }_{i-1}$; choosing a copy of a clause $a\leftarrow b_1\wedge \mathrm{\dots }\wedge b_p$ in the knowledge base whose head, $a$, unifies with $a_i$; replacing $a_1$ with the body, $b_1\wedge \mathrm{\dots }\wedge b_p$; and applying the unifier to the whole resulting answer clause.

  The main difference between this and the propositional top-down proof procedure is that, for clauses with variables, the proof procedure must take copies of clauses from the knowledge base. The copying renames the variables in the clause with new names. This is both to remove name clashes between variables and because a single proof may use different instances of a clause.

• •

  ${\gamma }_n$ is an answer. That is, it is of the form

  $yes(t_1,\mathrm{\dots },t_k)\leftarrow .$

  When this occurs, the algorithm returns the answer

  $$V_1=t_1,\mathrm{\dots },V_k=t_k.$$

Notice how the answer is extracted; the arguments to $yes$ keep track of the instances of the variables in the initial query that lead to a successful proof.

Figure 15.5 gives a non-deterministic algorithm that answers queries by searching for SLD derivations. This is non-deterministic in the sense that all derivations can be found by making appropriate choices that do not fail. If all choices fail, the algorithm fails, and there are no derivations. The “choose” on line 13 is implemented using search, as in Example 5.12. Recall that $Unify(a_i,a)$ returns an MGU of $a_i$ and $a$, if there is one, and $\perp$ if they do not unify. The algorithm for $Unify$ is given in Figure 15.4.