Evaluating queries with variables is complicated by the fact that there can be multiple variable bindings that make the query true; and, consequently, there can be multiple possible answers. In some cases, we want just a single answer; in some cases, we want several answers; and, in other cases, we want all answers. In what follows, we talk about a procedure for generating all answers. The procedures for the other cases are analogous.

See below for a top-down query evaluation procedure encoded in Javascript. The procedure takes as arguments an answer pattern, a query expression, and a dataset (a list of factoids). It calls a subroutine compall to produce a list of substitutions that make the query true, substitutes the variable bindings into the answer pattern, and returns a list of the resulting instances.

The compall procedure does all of the hard work in evaluating queries. It takes as arguments a list of subgoals, a substitution (initially empty), and a dataset. It returns a list of all variable substitutions that make all of the given subgoals true on the basis of the given dataset.

The procedure assumes that the subgoals in the query and the factoids in the dataset are all represented as sequences of expressions. For example, the expression p(X,f(b)) can be thought of as a sequence with three elements, viz. the predicate p, the variable X, and the expression f(b).

The procedure processes the subgoals in order. If at any point there are no subgoals, then the procedure returns a list of the given substitution as answer. Otherwise, it processes the first subgoal to get a list of answers that make it true and then executes the procedure recursively on the remaining subgoals, once for each answer to the first subgoal.

1. If the first subgoal is a negation, the procedure calls itself on the argument of the negation and the given substitution. If the result is a non-empty set (i.e. there are any substitutions that work), then the negation is false and the procedure returns false as answer. If the result of the recursive execution is the empty set (i.e. there are no substitutions that work), then the negation as a whole is true and the procedure calls itself recursively with the remaining subgoals and the corresponding substitution and returns the result.


2. If the query is a conjunction, the procedure adds the conjuncts to the subgoal list and calls itself recursively.


3. Otherwise, the subgoal must be an atom. In this case, the procedure tries matching the atom to the factoids in the given dataset. For each factoid that matches the atom, the procedure calls itself recursively with the remaining subgoals and the corresponding substitution and returns the answers obtained from these recursive calls.

To illustrate the overall procedure, consider the dataset shown below.

Now, consider the answer pattern goal(Y) and the query p(a,Y). The subgoal p(a,Y) matches two factoids in our dataset, and so there are two workable substitutions, leading to two overall results.

Suppose instead we had the query p(a,Y) & p(Y,d). Once again, the subgoal p(a,Y) matches just two factoids in our dataset. Given {Y←b}, the subgoal p(Y,d) does not match any factoids; given {Y←c}, the pattern p(Y,d) matches just p(c,d). Thus, there is just one answer in this case.

Given the conjunctive query p(a,Y) & ~p(Y,d), we would again find two answers to the first conjunct, viz. {Y←b} and {Y←c}. Given the first of these, the negation ~p(Y,d)is satisfied, and so the conjunction is true. Given the second answer to the first conjunct, the negation fails and so there is no answer in this case. As with the last query, there is just one answer.