The means of combination used in the query language may at first seem
identical to the operations `and`, `or`, and `not` of
mathematical logic, and the application of query-language rules is in
fact accomplished through a legitimate method of
inference.[1] This identification of the query language with mathematical
logic is not really valid, though, because the query language provides
a
*control structure* that interprets the logical statements
procedurally. We can often take advantage of this control structure.
For example, to find all of the supervisors of programmers we could
formulate a query in either of two logically equivalent forms:

and(job(x, list("computer", "programmer")), supervisor(x, y));

and(supervisor(x, y), job(x, list("computer", "programmer")));

If a company has many more supervisors than programmers (the usual
case), it is better to use the first form rather than the second
because the data base must be scanned for each intermediate result
(frame) produced by the first clause of the `and`.

The aim of logic programming is to provide the programmer with
techniques for decomposing a computational problem into two separate
problems: what

is to be computed, and how

this should be
computed. This is accomplished by selecting a subset of the
statements of mathematical logic that is powerful enough to be able to
describe anything one might want to compute, yet weak enough to have a
controllable procedural interpretation. The intention here is that,
on the one hand, a program specified in a logic programming language
should be an effective program that can be carried out by a computer.
Control (how

to compute) is effected by using the order of
evaluation of the language. We should be able to arrange the order of
clauses and the order of subgoals within each clause so that the
computation is done in an order deemed to be effective and efficient.
At the same time, we should be able to view the result of the
computation (what

to compute) as a simple consequence of the laws
of logic.

Our query language can be regarded as just such a procedurally
interpretable subset of mathematical logic. An assertion represents a
simple fact (an atomic proposition). A rule represents the
implication that the rule conclusion holds for those cases where the
rule body holds. A rule has a natural procedural interpretation: To
establish the conclusion of the rule, establish the body of the rule.
Rules, therefore, specify computations. However, because rules can
also be regarded as statements of mathematical logic, we can justify any inference

accomplished by a logic program by asserting that
the same result could be obtained by working entirely within
mathematical logic.[2]

A consequence of the procedural interpretation of logic programs is that it is possible to construct hopelessly inefficient programs for solving certain problems. An extreme case of inefficiency occurs when the system falls into infinite loops in making deductions. As a simple example, suppose we are setting up a data base of famous marriages, including

assert(married("Minnie", "Mickey"));

If we now ask

married("Mickey", who);

assert(rule(married(x, y), married(y, x)));

married("Mickey", who);

Unfortunately, this will drive the system into an infinite loop, as follows:

- The system finds that the
`married`rule is applicable; that is, the rule conclusion`married(x, y)`successfully unifies with the query pattern`married("Mickey", who)`to produce a frame in which`x`is bound to`"Mickey"`and`y`is bound to`who`. So the interpreter proceeds to evaluate the rule body`married(x, y)`in this frame—in effect, to process the query`married(who, "Mickey")`. - One answer appears directly as an assertion in the data
base:
`married("Minnie", "Mickey")`. - The
`married`rule is also applicable, so the interpreter again evaluates the rule body, which this time is equivalent to`married("Mickey", who)`.

The system is now in an infinite loop. Indeed, whether the system
will find the simple answer `married("Minnie", "Mickey")` before it
goes into the loop depends on implementation details concerning the
order in which the system checks the items in the data base. This is
a very simple example of the kinds of loops that can occur.
Collections of interrelated rules can lead to loops that are much
harder to anticipate, and the appearance of a loop can depend on the order
of clauses in an `and` (see exercise 4.55)
or on low-level details concerning the order in which the system
processes queries.[3]

Another quirk in the query system concerns `not`. Given the data
base of section 4.4.1, consider the
following two queries:

and(supervisor(x, y), not(job(x, list("computer", "programmer")))); and(not(job(x, list("computer", "programmer"))), supervisor(x, y));

These two queries do not produce the same result. The first query
begins by finding all entries in the data base that match `supervisor(x, y)`, and then filters the resulting frames by removing
the ones in which the value of
`x`
satisfies `job(x, list("computer", "programmer"))`. The second query begins by filtering the
incoming frames to remove those that can satisfy `job(x, list("computer", "programmer"))`. Since the only incoming frame is empty, it
checks the data base to see if there are any patterns that satisfy
`job(x, list("computer", "programmer"))`. Since there generally are
entries of this form, the `not` clause filters out the empty frame
and returns an empty stream of frames. Consequently, the entire
compound query returns an empty stream.

The trouble is that our implementation of `not` really is meant to
serve as a filter on values for the variables. If a `not` clause
is processed with a frame in which some of the variables remain
unbound (as does
`x`
in the example above), the system will
produce unexpected results. Similar problems occur with the use of
`javascript_value`—the JavaScript predicate can't work if some of its
arguments are unbound. See exercise 4.68.

There is also a much more serious way in which the `not` of the
query language differs from the `not` of mathematical logic. In
logic, we interpret the statement not $P$

to mean that $P$ is not
true. In the query system, however, not $P$

means that $P$ is not
deducible from the knowledge in the data base. For example, given the
personnel data base of section 4.4.1, the
system would happily deduce all sorts of `not` statements, such as
that Ben Bitdiddle is not a baseball fan, that it is not raining
outside, and that $2 + 2$ is not 4.[4] In other words, the `not`
of logic programming languages reflects the so-called
*closed
world assumption* that all relevant information has been included in
the data base.[5]

rule(outranked_by(staff_person, boss), or(supervisor(staff_person, boss), and(outranked_by(middle_manager, boss), supervisor(staff_person, middle_manager))));

outanked_by(list("Bitdiddle", "Ben"), who);

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

wheel(who);

// Query results: wheel(list("Warbucks", "Oliver")) wheel(list("Bitdiddle", "Ben")) wheel(list("Warbucks", "Oliver")) wheel(list("Warbucks", "Oliver")) wheel(list("Warbucks", "Oliver"))

sum(amount, and(job(x, list("computer", "programmer")), salary(x, amount)));

Oh, no, my simple accumulation scheme won't work!What has Ben just realized? Outline a method he can use to salvage the situation.

greatsto a grandson relationship. This should enable the system to deduce that Irad is the great-grandson of Adam, or that Jabal and Jubal are the great-great-great-great-great-grandsons of Adam. (Hint: Represent the fact about Irad, for example, as

[1]
That a particular method of inference is
legitimate is not a trivial assertion. One must prove that if one
starts with true premises, only true conclusions can be derived. The
method of inference represented by rule applications is
*modus
ponens*, the familiar method of inference that says that if *A* is
true and *A implies B* is true, then we may conclude that *B*
is true.

[2]
We must qualify this statement by
agreeing that, in speaking of the `not` and
`javascript_value`.
As we will describe below,
the `not` implemented in the query language is not always
consistent with the `not` of mathematical logic, and
`javascript_value`
introduces additional complications. We could implement a
language consistent with mathematical logic by simply removing `not` and
`javascript_value`
from the language and agreeing to write
programs using only simple queries, `and`, and `or`. However,
this would greatly restrict the expressive power of the language. One
of the major concerns of research in logic programming is to find ways
to achieve more consistency with mathematical logic without unduly
sacrificing expressive power.

inferenceaccomplished by a logic program, we assume that the computation terminates. Unfortunately, even this qualified statement is false for our implementation of the query language (and also false for programs in Prolog and most other current logic programming languages) because of our use of

[3]
This is not a problem of the logic but one of the
procedural interpretation of the logic provided by our interpreter.
We could write an interpreter that would not fall into a loop here.
For example, we could enumerate all the proofs derivable from our
assertions and our rules in a breadth-first rather than a depth-first
order. However, such a system makes it more difficult to take
advantage of the order of deductions in our programs. One attempt to
build sophisticated control into such a program is described in
deKleer et al. 1977 .
Another technique, which does not lead to such
serious control problems, is to put in special knowledge, such as
detectors for particular kinds of loops
(exercise 4.58). However, there can be no
general scheme for reliably preventing a system from going down
infinite paths in performing deductions. Imagine a diabolical rule of
the form

To show $P(x)$ is true, show that $P(f(x))$ is true,for some suitably chosen function $f$.

[4]
Consider the query `not(baseball_fan(list("Bitdiddle", "Ben")))`. The system finds that `baseball_fan(list("Bitdiddle", "Ben"))` is not in the data base, so the empty
frame does not satisfy the pattern and is not filtered out of the
initial stream of frames. The result of the query is thus the empty
frame, which is used to instantiate the input query to produce
`not(baseball_fan(list("Bitdiddle", "Ben")))`.

[5]
A discussion and justification of this
treatment of `not` can be found in the article by Clark (1978).

4.4.3 Is Logic Programming Mathematical Logic?