Logic programming excels in providing interfaces to
data bases for
information retrieval. The query language we shall implement in this
chapter is designed to be used in this way.
In order to illustrate what the query system does, we will show how it
can be used to manage the data base of personnel records for
Gargle, a thriving high-technology company in the
Boston area. The language provides pattern-directed access to
personnel information and can also take advantage of general rules in
order to make logical deductions.
A sample data base
The personnel data base for Gargle
contains
assertions about company personnel. Here is the
information about Ben Bitdiddle, the resident computer wizard:
Another option for syntactically representing facts in the data base
would have been to use simply lists, also for the top level
predicates, as in the original book. We did not resist the
temptation to syntactically introduce predicate symbols,
for the following reasons:
In JavaScript, facts in a datalog data base look much more natural
when rendered as p(x, y) rather
than as list("p", x, y).
The analogy between logic programming and functional programming
comes out much clearer; the predicate is in familiar position
and the reader is reminded of function declarations when reading:
append_to_form(list("a", "b"), y, list("a", "b", "c", "d")) rather than
list("append_to_form", list("a", "b"), y, list("a", "b", "c", "d")).
The most decisive argument is that in this treatment, function
symbols (as in the predicate calculus) come for free: We can write
predicates such as plus without
any additional effort in the interpreter:
rule(plus($x, 0, $x) and
rule(plus($x, s($y), s($z)), plus($x, $y, $z)).
Original
JavaScript
Each assertion is a list (in this case a triple) whose elements can
themselves be lists.
Assertions look just like function applications in JavaScript, but
they actually represent information in the data base. The first
symbols—here address,
job and
salary—describe the
kind of information contained in the respective assertion, and
the arguments are lists or primitive values such as strings
and numbers. The first symbols do not need to be declared, as do constants
or variables in JavaScript; their scope is global.
We shy away from calling these symbols
predicate symbols instead of
kind of information
because the term
predicate is already used, also in this section,
for JavaScript expressions and functions that return boolean values.
As resident wizard, Ben is in charge of the company's computer
division, and he supervises two programmers and one technician. Here
is the information about them:
The data base also contains assertions about which kinds of jobs can
be done by people holding other kinds of jobs. For instance, a
computer wizard can do the jobs of both a computer programmer and a
computer technician:
The query language allows users to retrieve information from the data
base by posing queries in response to the system's prompt.
For example, to find all computer programmers one can say
The input query specifies that we are looking for entries in the data
base that match a certain
pattern.
Original
JavaScript
In this example, the pattern
specifies entries consisting of three items, of which the first is the
literal symbol job, the second can be
anything, and the third is the literal list
(computer programmer).
The anything that can be the second item in the matching
list is specified by a
pattern variable,
?x.
The general form of a pattern variable is a symbol, taken to be the name
of the variable, preceded by a question mark. We will see below why it
is useful to specify names for pattern variables rather than just putting
?
into patterns to represent anything.
In this example, the pattern
specifies job as the kind of information
that we are looking for. The first item can be
anything, and the second is the literal list
list("computer", "programmer").
The anything that can be the first item in the matching
assertion is specified by a
pattern variable,
$x. As pattern variables, we use
JavaScript names that start with a dollar sign.
We will see below why
it is useful to specify names for pattern variables rather than just
putting a single symbol such as $
into patterns to represent anything.
The system responds to a simple query by showing all entries in the data
base that match the specified pattern.
A pattern can have more than one variable. For example, the query
Original
JavaScript
(address ?x ?y)
address($x, $y)
will list all the employees' addresses.
A pattern can have no variables, in which case the query simply
determines whether that pattern is an entry in the data base. If so,
there will be one match; if not, there will be no matches.
The same pattern variable can appear more than once in a query,
specifying that the same anything must appear in each
position. This is why variables have names. For example,
Original
JavaScript
(supervisor ?x ?x)
supervisor($x, $x)
finds all people who supervise themselves (though there are no
such assertions in our sample data base).
The query
Original
JavaScript
(job ?x (computer ?type))
job($x, list("computer", $type))
matches all job entries whose
third
second
item is a two-element list whose
first item is
computer:
"computer":
This same pattern does not match
(job (Reasoner Louis) (computer programmer trainee))
because the third item in the entry is a list of three elements, and
the pattern's third item specifies that there should be two
elements. If we wanted to change the pattern so that the third item
could be any
list beginning with
computer,
we could
specify[1]
This same pattern does not match
job(list("Reasoner", "Louis"),
list("computer", "programmer", "trainee"))
because the second item in the assertion is a list of three
elements, and the pattern's second item specifies that there
should be two elements. If we wanted to change the pattern so that the
second item could be any
list beginning with
"computer",
we could
specify
There is no need for dotted-tail notation in the
JavaScript edition: We simply use
pair instead of
list where needed.
Original
JavaScript
(job ?x (computer . ?type))
job($x, pair("computer", $type))
For example,
Original
JavaScript
(computer . ?type)
pair("computer", $type)
matches the data
Original
JavaScript
(computer programmer trainee)
list("computer", "programmer", "trainee")
with
?type$type
as
the list (programmer trainee).list("programmer", "trainee").
It also matches the data
Original
JavaScript
(computer programmer)
list("computer", "programmer")
with
?type$type
as
the list (programmer),list("programmer"),
and matches the data
Original
JavaScript
(computer)
list("computer")
with
?type$type
as the empty
list ().list, null.
We can describe the query language's processing of simple queries as
follows:
The system finds all assignments to variables in the query
pattern that
satisfy the pattern—that is, all sets
of values for the variables such that if the pattern variables are
instantiated with (replaced by) the values, the result is
in the data base.
The system responds to the query by listing all instantiations of the
query pattern with the variable assignments that satisfy it.
Note that if the pattern has no variables, the query reduces to a
determination of whether that pattern is in the data base. If so, the
empty assignment, which assigns no values to variables, satisfies that
pattern for that data base.
Exercise 4.65
Give simple queries that retrieve the following information from the
data base:
all people supervised by Ben Bitdiddle;
the names and jobs of all people in the accounting division;
the names and addresses of all people who live
in Slumerville.
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.
Compound queries
Simple queries form the primitive operations of the query language.
In order to form compound operations, the query language provides
means of combination. One thing that makes the query language a logic
programming language is that the means of combination mirror the means
of combination used in forming logical expressions:
and, or, and
not.
(Here and, or,
and not are not the Lisp primitives, but
rather operations built into the query language.)
We can use
and as follows to find the addresses
of all the computer programmers:
In general,
(and $\langle \textit{query}_{1}\rangle$ $\langle \textit{query}_{2} \rangle$ $\ldots$ $\langle \textit{query}_{n} \rangle$)
is
satisfied by all sets of values for the pattern variables that
simultaneously satisfy
$\langle\textit{query}_{1}\rangle\ldots \langle\textit{query}_{n}\rangle$.
In general,
and($query$$_{1}$, $query$$_{2}$, $\ldots$, $query$$_{n})$
is
satisfied by all sets of values for the pattern variables that
simultaneously satisfy
$query$$_{1}, \ldots,$ $query$$_{n}$.
As for simple queries, the system processes a compound query by
finding all assignments to the pattern variables that satisfy the
query, then displaying instantiations of the query with those values.
Another means of constructing compound queries is through
or. For example,
In general,
(or $\langle \textit{query}_{1}\rangle$ $\langle \textit{query}_{2}\rangle$ $\ldots$ $\langle \textit{query}_{n}\rangle$)
is satisfied by all sets of values for the pattern variables that
satisfy at least one of
$\langle \textit{query}_{1}\rangle \ldots \langle \textit{query}_{n}\rangle$.
In general,
or($query$$_{1}$, $query$$_{2}$, $\ldots$, $query$$_{n}$)
is satisfied by all sets of values for the pattern variables that
satisfy at least one of
$query$$_{1} \ldots$ $query$$_{n}$.
Compound queries can also be formed with
not.
For example,
finds all people supervised by Ben Bitdiddle who are not computer
programmers. In general,
Original
JavaScript
(not $\langle \textit{query}_{1}\rangle$)
not($query$$_{1}$)
is satisfied by all assignments to the pattern variables that do not
satisfy
$\langle \textit{query}_{1} \rangle$$query$$_{1}$.[2]
Original
JavaScript
The final combining form is called
lisp-value. When
lisp-value is the first element of a
pattern, it specifies that the next element is a Lisp predicate to be
applied to the rest of the (instantiated) elements as arguments.
In general,
(lisp-value $\langle \textit{predicate}\rangle$ $\langle \textit{arg}_{1}\rangle$ $\ldots$ $\langle \textit{arg}_{n} \rangle$)
will be satisfied by assignments to the pattern variables for which the
$\langle \textit{predicate} \rangle$ applied
to the instantiated
$\langle \textit{arg}_{1} \rangle, \ldots, \langle \textit{arg}_{n}\rangle$
is true. For example, to find all people whose salary is greater than
$30,000 we could write[3]
(and (salary ?person ?amount)
(lisp-value > ?amount 30000))
The final combining form starts with
javascript_predicate and
contains a JavaScript predicate. In general,
javascript_predicate($predicate$)
will be satisfied by assignments to the pattern variables
in the $predicate$ for which the
instantiated
$predicate$ is true.
For example, to find all people whose salary is greater than
$50,000 we could write[4]
and(salary($person, $amount), javascript_predicate($amount > 50000))
Exercise 4.66
Formulate compound queries that retrieve the following information:
the names of all people who are supervised by Ben Bitdiddle, together
with their addresses;
all people whose salary is less than Ben Bitdiddle's, together
with their salary and Ben Bitdiddle's salary;
all people who are supervised by someone who is not in the computer
division, together with the supervisor's name and job.
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.
Rules
In addition to primitive queries and compound queries, the query
language provides means for
abstracting queries. These are given by
rules. The rule
specifies that two people live near each other if they live in the
same town. The final not clause prevents the
rule from saying that all people live near themselves. The
same relation is defined by a very simple
rule:[5]
Original
JavaScript
(rule (same ?x ?x))
rule(same($x, $x))
The following rule declares that a person is a wheel in an
organization if he supervises someone who is in turn a supervisor:
The general form of a rule is
(rule $\langle \textit{conclusion} \rangle$ $\langle \textit{body} \rangle$)
where $\langle \textit{conclusion}\rangle$ is
a pattern and $\langle \textit{body} \rangle$
is any query.[6]
The general form of a rule is
rule($conclusion$, $body$)
where $conclusion$ is a pattern and
$body$ is any query.[7]
We can think of a rule as representing a large (even
infinite) set of assertions, namely all instantiations of the rule conclusion
with variable assignments that satisfy the rule body. When we described
simple queries (patterns), we said that an assignment to variables satisfies
a pattern if the instantiated pattern is in the data base. But the pattern
needn't be explicitly in the data base as an assertion. It
can be an
implicit assertion implied by a rule. For example, the
query
As in the case of compound
procedures,functions,
rules can be used as parts of other rules (as we saw with the
lives-nearlives_near
rule above) or even be defined
recursively. For instance, the rule
says that a staff person is outranked by a boss in the organization if
the boss is the person's supervisor or (recursively) if the
person's supervisor is outranked by the boss.
Exercise 4.67
Define a rule that says that person 1 can replace person 2 if either
person 1 does the same job as person 2 or someone who does person 1's
job can also do person 2's job, and if person 1 and person 2
are not the same person. Using your rule, give queries that find the
following:
all people who can replace Cy D. Fect;
all people who can replace someone who is being paid more than they
are, together with the two salaries.
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.
Exercise 4.68
Define a rule that says that a person is a big shot in a
division if the person works in the division but does not have a supervisor
who works in the division.
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.
Exercise 4.69
Ben Bitdiddle has missed one meeting too many. Fearing that his habit of
forgetting meetings could cost him his job, Ben decides to do something about
it. He adds all the weekly meetings of the firm to the Gargle data base
by asserting the following:
Each of the above assertions is for a meeting of an entire division.
Ben also adds an entry for the company-wide meeting that spans all the
divisions. All of the company's employees attend this meeting.
On Friday morning, Ben wants to query the data base for all the meetings
that occur that day. What query should he use?
Alyssa P. Hacker is unimpressed. She thinks it would be much more
useful to be able to ask for her meetings by specifying her name. So
she designs a rule that says that a person's meetings include all
whole-company"whole-company"
meetings plus all meetings of that person's division.
Fill in the body of Alyssa's rule.
Alyssa arrives at work on Wednesday morning and wonders what meetings she
has to attend that day. Having defined the above rule, what query should
she make to find this out?
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.
Alyssa P. Hacker is able to find people who live near her, with whom
she can ride to work. On the other hand, when she tries to find all
pairs of people who live near each other by querying
Original
JavaScript
(lives-near ?person-1 ?person-2)
lives_near($person_1, $person_2)
she notices that each pair of people who live near each other is
listed twice; for example,
Why does this happen?
Is there a way to find a list of people who live near each other, in
which each pair appears only once? Explain.
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.
Logic as programs
We can regard a rule as a kind of logical implication: If an
assignment of values to pattern variables satisfies the body,
then it satisfies the conclusion. Consequently, we can regard the
query language as having the ability to perform logical
deductions based upon the rules. As an example, consider the
append operation described at the beginning of
section 4.4. As we said,
append can be characterized by the following
two rules:
For any list y, the empty list and
yappend to
form y.
For any u, v,
y, and z,
(cons u v)pair(u, v)
and yappend
to form
(cons u z)pair(u, z)
if v and yappend to form
z.
To express this in our query language, we define two rules for a relation
Original
JavaScript
(append-to-form x y z)
append_to_form(x, y, z)
which we can interpret to mean x and
yappend to
form z:
The first rule has
no body, which means that the conclusion holds for
any value of
?y.$y.
Note how the second rule makes use of
dotted-tail notation to name the
pair to name the
carhead
and
cdrtail
of a list.
Given these two rules, we can formulate queries that compute the
append of two lists:
Original
JavaScript
;;; Query input:
(append-to-form (a b) (c d) ?z)
;;; Query results:
(append-to-form (a b) (c d) (a b c d))
What is more striking, we can use the same rules to ask the question
Which list, when appended to
(a b), yields
(a b c d)?Which list, when appended to
list("a", "b"), yields
list("a", "b", "c", "d")?
This is done as follows:
Original
JavaScript
;;; Query input:
(append-to-form (a b) ?y (a b c d))
;;; Query results:
(append-to-form (a b) (c d) (a b c d))
We can
also
ask for all pairs of lists that
append to form
(a b c d):list("a", "b", "c", "d"):
Original
JavaScript
;;; Query input:
(append-to-form ?x ?y (a b c d))
;;; Query results:
(append-to-form () (a b c d) (a b c d))
(append-to-form (a) (b c d) (a b c d))
(append-to-form (a b) (c d) (a b c d))
(append-to-form (a b c) (d) (a b c d))
(append-to-form (a b c d) () (a b c d))
The query system may seem to exhibit quite a bit of intelligence in
using the rules to deduce the answers to the queries above. Actually,
as we will see in the next section, the system is following a
well-determined algorithm in unraveling the rules. Unfortunately,
although the system works impressively in the
append case, the general methods may break down
in more complex cases, as we will see
in section 4.4.3.
Exercise 4.71
The following rules implement a
next-tonext_to_in
relation that finds adjacent elements of a list:
Original
JavaScript
(rule (?x next-to ?y in (?x ?y . ?u)))
(rule (?x next-to ?y in (?v . ?z))
(?x next-to ?y in ?z))
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.
Exercise 4.72
Define rules to implement the
last-pairlast_pair
operation of exercise 2.17,
which returns a list
containing the last element of a nonempty list. Check your rules on
Original
JavaScript
queries such as
(last-pair (3) ?x),
(last-pair (1 2 3) ?x),
and
(last-pair (2 ?x) (3)).
the following queries:
last_pair(list(3), $x)
last_pair(list(1, 2, 3), $x)
last_pair(list(2, $x), list(3))
Do your rules work correctly on queries such as
(last-pair ?x (3))?last_pair($x, list(3))?
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.
Exercise 4.73
The following data base (see Genesis 4) traces the genealogy of the
descendants of
Ada back to Adam, by way of Cain:
Original
JavaScript
(son Adam Cain)
(son Cain Enoch)
(son Enoch Irad)
(son Irad Mehujael)
(son Mehujael Methushael)
(son Methushael Lamech)
(wife Lamech Ada)
(son Ada Jabal)
(son Ada Jubal)
Formulate rules such as If S is the son of F, and
F is the son of G, then S is the grandson of
G and If W is the wife of M, and
S is the son of W, then S is the son of
M (which was supposedly more true in biblical times than
today) that will enable the query system to find the grandson of Cain; the
sons of Lamech; the grandsons of Methushael.
(See
exercise 4.79
exercise 4.80
for some rules to deduce more complicated relationships.)
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.
[1]
This uses the dotted-tail
notation introduced in
exercise 2.20.
[2]
Actually, this description of
not is valid only for simple cases. The real
behavior of not is more complex. We will
examine not's peculiarities
in sections 4.4.2
and 4.4.3.
[3]
Lisp-value
should be used only to perform an operation not
provided in the query language. In particular, it should not
be used to
test equality (since that is what the matching in the
query language is designed to do) or inequality (since that can
be done with the same rule shown
below).
[4]
A query should use
javascript_predicate
only to perform an operation not
provided in the query language. In particular,
javascript_predicate
should not be used to
test equality (since that is what the matching in the
query language is designed to do) or inequality (since that can
be done with the same rule shown
below).
[5]
Notice that we do not need same
in order to make two things be the same: We just use the same pattern
variable for each—in effect, we have one thing instead of two things
in the first place. For example, see
?town$town
in the
lives-nearlives_near
rule and
?middle-manager$middle_manager
in the
wheel
rule below.
Same
The same relation
is useful when we want to force two things to be
different, such as
?person-1$person_1
and
?person-2$person_2
in the
lives-nearlives_near
rule. Although using the same pattern variable in two
parts of a query forces the same value to appear in both places, using
different pattern variables does not force different values to appear.
(The values assigned to different pattern variables may be the same or
different.)
[6]
We will also allow
rules without bodies, as in
same, and we will interpret such a rule to
mean that the rule conclusion is satisfied by any values of the
variables.
[7]
We will
also allow
rules without bodies, as in
same, and we will interpret such a rule to
mean that the rule conclusion is satisfied by any values of the
variables.