Structure and Interpretation of Computer Programs (83 page)

(computer programmer)

with
?type
as the list
(programmer)
, and matches the data

(computer)

with
?type
as the empty list
()
.

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.55.
  Give simple queries that retrieve the following information from the
data base:

a. all people supervised by Ben Bitdiddle;

b. the names and jobs of all people in the accounting division;

c. the names and addresses of all people who live
in Slumerville.

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:

(and (job ?person (computer programmer))
     (address ?person ?where))

The resulting output is

(and (job (Hacker Alyssa P) (computer programmer))
     (address (Hacker Alyssa P) (Cambridge (Mass Ave) 78)))
(and (job (Fect Cy D) (computer programmer))
     (address (Fect Cy D) (Cambridge (Ames Street) 3)))

In general,

(and <
query
₁
> <
query
₂
> 
...
<
query
_n
>)

is satisfied by all sets of values for the pattern variables that
simultaneously satisfy <
query
₁
>
...
<
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,

(or (supervisor ?x (Bitdiddle Ben))
    (supervisor ?x (Hacker Alyssa P)))

will find all employees supervised by Ben Bitdiddle or Alyssa P.
Hacker:

(or (supervisor (Hacker Alyssa P) (Bitdiddle Ben))
    (supervisor (Hacker Alyssa P) (Hacker Alyssa P)))
(or (supervisor (Fect Cy D) (Bitdiddle Ben))
    (supervisor (Fect Cy D) (Hacker Alyssa P)))
(or (supervisor (Tweakit Lem E) (Bitdiddle Ben))
    (supervisor (Tweakit Lem E) (Hacker Alyssa P)))
(or (supervisor (Reasoner Louis) (Bitdiddle Ben))
    (supervisor (Reasoner Louis) (Hacker Alyssa P)))

In general,

(or <
query
₁
> <
query
₂
> 
...
<
query
_n
>)

is satisfied by all sets of values for the pattern variables that
satisfy at least one of <
query
₁
>
...
<
query
_n
>.

Compound queries can also be formed with
not
. For example,

(and (supervisor ?x (Bitdiddle Ben))
     (not (job ?x (computer programmer))))

finds all people supervised by Ben Bitdiddle who are not computer
programmers. In general,

(not <
query
₁
>)

is satisfied by all assignments to the pattern variables that do not
satisfy <
query
₁
>.
⁶³

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 <
predicate
> <
arg
₁
> 
...
<
arg
_n
>)

will be satisfied by assignments to the pattern variables for which the
<
predicate
> applied to the instantiated
<
arg
₁
>
...
<
arg
_n
>
is true. For example, to find all people whose salary is greater than
$30,000 we could write
⁶⁴

(and (salary ?person ?amount)
     (lisp-value > ?amount 30000))

Exercise 4.56.
  Formulate compound queries that retrieve the following information:

a. the names of all people who are supervised by Ben Bitdiddle, together
with their addresses;

b. all people whose salary is less than Ben Bitdiddle's, together with
their salary and Ben Bitdiddle's salary;

c. all people who are supervised by someone who is not in the computer
division, together with the supervisor's name and job.

In addition to primitive queries and compound queries, the query
language provides means for abstracting queries. These are given by
rules
. The rule

(rule (lives-near ?person-1 ?person-2)
      (and (address ?person-1 (?town . ?rest-1))
           (address ?person-2 (?town . ?rest-2))
           (not (same ?person-1 ?person-2))))

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:
⁶⁵

(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:

(rule (wheel ?person)
      (and (supervisor ?middle-manager ?person)
           (supervisor ?x ?middle-manager)))

The general form of a rule is

(rule <
conclusion
> <
body
>)

where <
conclusion
> is a pattern and <
body
> is any
query.
⁶⁶
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

(lives-near ?x (Bitdiddle Ben))

results in

(lives-near (Reasoner Louis) (Bitdiddle Ben))
(lives-near (Aull DeWitt) (Bitdiddle Ben))

To find all computer programmers who live near Ben Bitdiddle, we can
ask

(and (job ?x (computer programmer))
     (lives-near ?x (Bitdiddle Ben)))

As in the case of compound procedures, rules can be used as parts of
other rules (as we saw with the
lives-near
rule above)
or even be defined recursively. For instance, the rule

(rule (outranked-by ?staff-person ?boss)
      (or (supervisor ?staff-person ?boss)
          (and (supervisor ?staff-person ?middle-manager)
               (outranked-by ?middle-manager ?boss))))

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.57.
  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:

a.  all people who can replace Cy D. Fect;

b.  all people who can replace someone who is being paid more than they
are, together with the two salaries.

Exercise 4.58.
  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.

Exercise 4.59.
  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 Microshaft data base by
asserting the following:

(meeting accounting (Monday 9am))
(meeting administration (Monday 10am))
(meeting computer (Wednesday 3pm))
(meeting administration (Friday 1pm))

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.

(meeting whole-company (Wednesday 4pm))

a. On Friday morning, Ben wants to query the data base for all the meetings
that occur that day. What query should he use?

b. 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
meetings plus all meetings of that person's division.
Fill in the body of Alyssa's rule.

(rule (meeting-time ?person ?day-and-time)
      <
rule-body
>)

c. 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?

Exercise 4.60.
  
By giving the query

(lives-near ?person (Hacker Alyssa P))

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

(lives-near ?person-1 ?person-2)

she notices that each pair of people who live near each other is
listed twice; for example,

(lives-near (Hacker Alyssa P) (Fect Cy D))
(lives-near (Fect Cy D) (Hacker Alyssa P))

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.

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
  y
  append
  to form
  y
  .
  
• For any
  u
  ,
  v
  ,
  y
  , and
  z
  ,
  (cons u v)
  and
  y
  append
  to form
  (cons u z)
  if
  v
  and
  y
  append
  to form
  z
  .
  

To express this in our query language, we define two rules for a
relation

(append-to-form x y z)

which we can interpret to mean “
x
and
y
append
to
form
z
”:

(rule (append-to-form () ?y ?y))
(rule (append-to-form (?u . ?v) ?y (?u . ?z))
      (append-to-form ?v ?y ?z))

The first rule has no body, which means that the conclusion holds for
any value of
?y
. Note how the second rule makes use of
dotted-tail notation to name the
car
and
cdr
of a list.

Given these two rules, we can formulate queries that compute the
append
of two lists:

;;; 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
append
ed to
(a b)
, yields
(a b c d)
?”
This is done as follows:

;;; 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)
:

;;; 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))