See below for a top-down view evaluation procedure encoded in Javascript. The procedure takes as arguments an answer pattern, a query expression, a dataset (a list of factoids), and a ruleset ( a list of rules). It calls a subroutine queryall 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.

As with simple query evaluation, the queryall procedure does all of the hard work in evaluating view queries. It takes as arguments a list of subgoals, a substitution (initially empty), a dataset, and a ruleset. It returns a list of all variable substitutions that make all of the given subgoals true on the basis of the given dataset and ruleset.

The procedure assumes that the subgoals in the query, the factoids in the dataset, and the rules in the ruleset 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. If the predicate in the goal is a base relation, we iterate through our dataset comparing the goal to each factoid in turn. If there is an extension of the given substitution that unifies the goal and the factoid, we add that extended substitution to our list of answers. Once we have finished examining all relevant factoids, we return the list of substitutions we have accumulated along the way. (If we do not find any factoids that unify with the goal, we return an empty list.)


4. If our goal is an atom and the predicate is a view relation, we iterate through the rules in our program. We first copy each rule, replacing the variables by new variables (to avoid possible conflicts with variables in our goal). We then try to find a most general unifier for the given goal and the head of the rule starting with the given substitution. If we succeed, we call the procedure recursively on the body of the rule (together with the remaining subgoals) and the resulting unifier. We add all substitutions returned from this recursive call to our output list. When we have finished examining all of the rules, we return the substitutions we have collected along the way.

Once again, consider the dataset we saw earlier (repeated on the left below), and consider a version of the logic program with some of the object constants replaced by variables (shown on the right below).

To see our procedure in action, let's start with a simple case. Imagine that we want to find all objects that appear in both the p relation and the q relation. We call our procedure with p(X) & q(X) as goal and the empty substitution {} as initial substitution. Since our goal is a conjunction, we first call the procedure recursively on p(X) and {}. Our goal p(X) with initial substitution {} unifies all three of the p factoids in our dataset, and so the result of the recursive call is a list of the resulting substitutions, i.e. {X←a} and {X←b} and {X←c}. For each of these substitutions, we then call the procedure recursively on the second conjunct q(X). There is no factoid that unifies with q(X) given the {X←a} substitution, so in this case we return the empty list. In the second case, we are luckier. q(X) and q(b) do unify given the substitution {X←b}, so we return a list containing that substitution. The third case is similar to the first in that there is no unifiable factoid, so again we get an empty list. Having checked the second conjunct for each of the answers to the first conjunct, we return the list of substitutions we have accumulated along the way, in this case the list consisting of the single substitution {X←b}.

The procedure just described computes all answers to a given query. If we want just a few answers, we can use a "pipelined" version of the algorithm that returns one answer at a time. When processing a rule, rather than computing all answers to a subgoal before proceeding, once we have a single answer we check whether that solution leads to an answer to the remaining subgoals. If it does, we return that answer. If not, we generate another answer to our subgoal and try again.