5.1 Introduction

In Chapter 3, we described the semantics of queries in terms of instances of query rules. While the definition is easy to understand and mathematically precise, enumerating instances is not a practical method for computing answers to queries. In this chapter, we present an algorithm that produces the same results but in a more efficient manner.

We begin this chapter with a discussion of evaluation of queries without variables. In Section 5.3, we look at a way of comparing expressions containing variables. In the section after that, we show how to combine that technique with the procedure described here to produce an evaluation procedure for queries with variables. We then discuss the computational complexity of our evaluation algorithm. We close with some techniques for reformulating queries to decrease the cost of query evaluation.

5.2 Evaluating Ground Queries

If a query contains multiple query rules, we check whether the body of each rule is true. If so, we add the head of the rule to the extension of our query. The procedure for determining whether the body is true depends on the type of the body.

1. If the body of a query rule is a single atom, we check whether that atom is contained in our dataset. If so, the body is true.


2. If the body is a negated atom, we check whether the atom is contained in our dataset. If so, the body is false. If the atom is not contained in our dataset, then the body is true.


3. If the body is a conjunction of literals, we first execute this procedure on the first conjunct. If the answer is true, we move on to the next conjunct and so forth until we are done. If the answer to any one of the conjuncts is false, then the value of the body as a whole is false.

Consider the dataset shown below. There are four symbols a, b, c, and d; and there is a single binary predicate p.

Now, imagine that we are asked to evaluate the query shown below. In this case there are three rules. To compute all answers, we execute our procedure on each of these rules.

In the first rule, the body p(a,c) is an atom, so we just check whether or not it is in the dataset. Since it is not there, nothing is contributed to our result.

The body of the second rules is a conjunction p(a,b) & p(b,a), and so we evaluate the conjuncts in order to see whether they are all true. In this case, the first conjunct is true but the second is false, so the conjunction as a whole is false and again nothing is contributed to our result.

The body of the third rule is also a conjunction p(c,d) & ~p(d,c). Again, we check the conjuncts in turn. p(c,d) is true, so we move on to ~p(d,c). p(d,c) is false so the negation is true. Since both conjuncts of the conjunction are true, the conjunction as a whole is true. Consequently, we add the head of our rule goal(c) to our result.

5.3 Matching

Matching is the process of determining whether a pattern (an expression with or without variables) matches an instance (an expression without variables), i.e. whether the two expressions can be made identical by appropriate substitutions for the variables in the pattern.

A substitution is a finite mapping of variables to ground terms. In what follows,, we write substitutions as sets of replacement rules, like the one shown below. In each rule, the variable to which the arrow is pointing is to be replaced by the term from which the arrow is pointing. In this case, X is associated with a and Y is associated with b.

The result of applying a substitution σ to an expression φ is the expression φσ obtained from φ by replacing every occurrence of every variable with a binding in the substitution by the term to which it is bound.

A substitution is a matcher for a pattern and an instance if and only if applying the substitution to the pattern results in the given instance. One good thing about our language is that there is a simple and inexpensive procedure for computing a matcher of a pattern and an expression if it exists.

See below for a version of a matching procedure encoded in Javascript. The procedure assumes a representation of expressions as sequences of subexpressions. 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).

We start the procedure with two expressions (the pattern and the instance) and a substitution (initially empty). We then recursively process the two expressions, comparing the subexpressions at each point. Along the way, we extend the substitution with variable assignments as described below.

1. If the pattern and the instance are the same, then the procedure succeeds, returning the unmodified substitution as result.


2. If the pattern is a variable with a binding, we compare the binding for the variable with the instance. If the pattern is a variable without a binding, we return the composition of the given substitution with a substitution in which the variable is bound to the expression in the given instance.


3. If either the pattern or the instance is a constant, then the procedure fails.


4. If the pattern and the instance have different lengths, we fail.


5. Otherwise, we iterate across the corresponding subexpressions of the pattern and the instance. If we fail to match a sub-pattern and a sub-instance at any point in this process, the procedure as a whole fails. If we finish this recursive comparison of the pattern and the instance, the procedure as a whole succeeds and the accumulated substitution at that point is the resulting matcher.

As an example of this procedure in operation, consider the process of matching the pattern p(X,Y) and the instance p(a,b) with the initial substitution {}. A trace of the execution of the procedure for this case is shown below. We show the beginning of a comparison with a line labelled Compare together with the expressions being compared and the input substitution. We show the result of each comparison with a line labelled Result. The indentation shows the depth of recursion of the procedure.

As another example, consider the process of matching the pattern p(X,X) and the instance p(a,a). A trace is shown below. By the time we compare the last arguments in the two expressions, X is bound to a, so the match succeeds.

As a final example, consider the process of trying to match the pattern p(X,X) and the expression p(a,b). The main interest in this example comes in comparing the last argument in the two expressions, viz. X and b. By the time we reach this point, X is bound to a and the corresponding instance is b. Since the pattern is a symbol and the instance is a different symbol, the match attempt fails.

This matching procedure is quite simple. However, it is worth understanding thoroughly, as it is the basis for more complicated matching procedures defined later.

5.4 Evaluating Queries With Variables

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.

Finally, for a query with more than one rule, we would get the union of the answers to the individual rules.

5.5 Computational Analysis

One nice feature of our query evaluation algorithm is that computational analysis is straightforward. In this section, we assume a standard left-to-right implementation of evaluation with no indexing of datasets and no caching of results once they are computed.

Consider the query shown below.

What is the cost of evaluating this query? In the worst case, there are n² facts in the database, where n is the number of ground terms in our language. So, we need n² steps to evaluate the first conjunct. There are at most n facts that have a as first argument. For each of these, we look at n² possibilities for the second conjunct. Hence, the cost of computing the instance can be expressed as shown below.

Now consider the general version of this query shown below.

What is the cost of computing all answers to this query? In the worst case, there are n² facts in the database, where n is the number of objects in the domain. So, we need n² steps to evaluate the first subgoal. There are at most n² possible values for Y. For each of these, we look at n² possibilities for the second subgoal. The resulting cost is shown below.

Before leaving our analysis of complexity, it is instructive to compare the cost of computing answers using this algorithm with the cost of computing answers in accordance with the semantics described in the preceding chapter, i.e. by enumerating all instances of rules and, for each such instance, checking whether the body of each such instance is true or false.

In the preceding example, the query has just three variables. Consequently, for a domain with n objects, there are n³ instances. To evaluate each of these instances, we must compare each of our two subgoals to every factoid in our dataset, and in the worst case there are n² of these. The overall cost is shown below.

Our algorithm is clearly better in this case, and the relative benefits are greater when we consider sparse datasets, i.e. datasets that do not include all possible factoids. In such cases, the "semantics-based" algorithm must still look at all instances, but our algorithm needs to look at only those instances that are derived form factoids in the dataset.

Note that, in the presence of dataset indexing or caching of results, the details of these analyses are likely to be different, but the style of analysis is the same and the relative merits of the two algorithms are more or less the same.

Exercises

Exercise 5.1: For each of the following patterns and instances, say whether the instance matches the pattern and, if so, give the corresponding matcher.

Exercise 5.2: Suppose that we want to find all goal(X,Y,Z) such that p(X,Y) & q(Y,Z). Select the formula that captures the worst case complexity of our standard evaluation algorithm for this query (assuming no indexing of the dataset). The symbol n here represents the total number of objects in the domain.

Exercise 5.3: For each of the queries shown below, select the expression that captures the worst case complexity of our standard evaluation algorithm without indexing. The symbol n represents the total number of objects in the domain.