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.
Answer:
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 line in Slumerville.
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.
Answer:
a.
b.
c.
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.
Answer:
a.
b.
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.
Answer:
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:
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.
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.
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?
Answer:
a.
b.
c.
Exercise 4.60. By giving the query
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
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.
Answer:
Lives-near works by showing all entries in the database that matches a certain pattern. If
person1 and
person2 match the pattern by virtue of being neighbors then the reverse is also true and therefore
person2 and
person1 also meet the pattern. There is no way to prevent this given the current definition of the rule.
The rule can be changed to add an artificial constraint to avoid the names being printed twice. For instance we can compare the lengths of the names of the people and print only those results where the name of
person1 is longer than the name of
person2.
String>? is a built in operator which compares strings according to the order of the characters they contain.
Exercise 4.61. The following rules implement a next-to relation that finds adjacent elements of a list:
What will the response be to the following queries?
Answer:
Exercise 4.62. Define rules to implement the last-pair operation of exercise 2.17, which returns a list containing the last element of a nonempty list. Check your rules on queries such as (last-pair (3) ?x), (last-pair (1 2 3) ?x), and (last-pair (2 ?x) (3)). Do your rules work correctly on queries such as (last-pair ?x (3)) ?
Answer:
Exercise 4.63. The following data base (see Genesis 4) traces the genealogy of the descendants of Ada back to Adam, by way of Cain:
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.69 for some rules to deduce more complicated relationships.)
Answer:
Exercise 4.64. Louis Reasoner mistakenly deletes the outranked-by rule (section 4.4.1) from the data base. When he realizes this, he quickly reinstalls it. Unfortunately, he makes a slight change in the rule, and types it in as
Just after Louis types this information into the system, DeWitt Aull comes by to find out who outranks Ben Bitdiddle. He issues the query
After answering, the system goes into an infinite loop. Explain why.
Answer:
I'll use the procedure explained in section 4.4.2 (pg. 460) to explore how this query is executed.
1. Unify query with the conclusion of the rule to form, if successful, an extension of the original frame. By unifying the query
(outranked-by (Bitiddle Ben) ?who) with the conclusion of the rule
(outranked-by ?staff-person ?boss) we get a frame where
?staff-person and
?boss are bound to
(Bitiddle Ben) and
?who respectively.
2. Relative to the extended frame, evaluate the query formed by the body of the rule. The query formed by the body of the rule in this case is:
The first argument to or immediately produces a match from the database:
(supervisor (Bitiddle Ben) (Warbucks Oliver)). This result is printed. The second argument to or is the and sub-query, the first part of which uses the
outranked-by rule. This leads the interpreter to again evaluate the rule body resulting in a frame where
?staff-person and
?boss are bound to to
?middle-manager and
?who respectively. This once again leads to the evaluation of
outranked-by and so on infinitely.
I can see how the infinite loop is triggered. What I don't understand is how the first part of or, i.e.,
(superior ?staff-person ?boss) is not matched in these infinite calls and their results printed (like how the first result got printed). Perhaps I'll be able to explain it once I study how the query interpreter is implemented.
Exercise 4.65. Cy D. Fect, looking forward to the day when he will rise in the organization, gives a query to find all the wheels (using the wheel rule of section 4.4.1):
To his surprise, the system responds
Why is Oliver Warbucks listed four times?
Answer:
Once again I'll use the procedure explained in section 4.4.2 (pg. 460) to explore how this query is executed.
1. Unify query with the conclusion of the rule to form, if successful, an extension of the original frame. By unifying the query
(wheel ?who) with the conclusion of the rule
(wheel ?person) we get a frame where
?person is bound to
?who.
2. Relative to the extended frame, evaluate the query formed by the body of the rule. The query formed by the body of the rule in this case is:
This query produces multiple matches, one each for every instance of a supervisor-employee pair where the supervisor reports to
?person.
The rule conclusion is instantiated with the value for
?person for every result produced by the query. Therefore we find that Oliver Warbuck's name pops up four times.
Exercise 4.66. Ben has been generalizing the query system to provide statistics about the company. For example, to find the total salaries of all the computer programmers one will be able to say
In general, Ben's new system allows expressions of the form
where accumulation-function can be things like sum, average, or maximum. Ben reasons that it should be a cinch to implement this. He will simply feed the query pattern to qeval. This will produce a stream of frames. He will then pass this stream through a mapping function that extracts the value of the designated variable from each frame in the stream and feed the resulting stream of values to the accumulation function. Just as Ben completes the implementation and is about to try it out, Cy walks by, still puzzling over the wheel query result in exercise 4.65. When Cy shows Ben the system's response, Ben groans, ``Oh, no, my simple accumulation scheme won't work!''
What has Ben just realized? Outline a method he can use to salvage the situation.
Answer:
Consider the following application of Ben's new system:
This query is meant to calculate the sum of the salaries paid to "wheels". As we saw in exercise 4.65 the
(wheel ?who) query will repeat Oliver Warbuck's name. Consequently his salary will be added up multiple times. This is the error Ben has realized - that queries can repeat the results.
One way to solve Ben's problem would be to ensure that the query pattern produces unique results. This can be done by implementing the equivalent of
distinct? for the query results.
Exercise 4.68. Define rules to implement the reverse operation of exercise 2.18, which returns a list containing the same elements as a given list in reverse order. (Hint: Use append-to-form.) Can your rules answer both (reverse (1 2 3) ?x) and (reverse ?x (1 2 3)) ?
Answer:
(reverse (1 2 3) ?x) returns
(reverse (1 2 3) (3 2 1)).
(reverse ?x (1 2 3)) prints
(reverse (3 2 1) (1 2 3)) and goes into an infinite loop if the order of the reverse rules is as shown. If the second rule is added first then the evaluator goes into infinite loop without printing any result.
Exercise 4.69. Beginning with the data base and the rules you formulated in exercise 4.63, devise a rule for adding ``greats'' to 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 ((great grandson) Adam Irad). Write rules that determine if a list ends in the word grandson. Use this to express a rule that allows one to derive the relationship ((great . ?rel) ?x ?y), where ?rel is a list ending in grandson.) Check your rules on queries such as ((great grandson) ?g ?ggs) and (?relationship Adam Irad).
Answer:
Exercise 4.70. What is the purpose of the let bindings in the procedures add-assertion! and add-rule! ? What would be wrong with the following implementation of add-assertion! ? Hint: Recall the definition of the infinite stream of ones in section 3.5.2: (define ones (cons-stream 1 ones)).
Answer:
The implementation given in the question uses
THE-ASSERTIONS in the
cons-stream operation. This defines
THE-ASSERTIONS recursively as a combination of the given assertion and
THE-ASSERTIONS. Such a definition would make
THE-ASSERTIONS an infinite stream (whose
stream-car is the new assertion) rather than a finite stream of assertions. The original definition creates a finite stream by joining the given assertion with the empty stream.
Exercise 4.71. Louis Reasoner wonders why the simple-query and disjoin procedures (section 4.4.4.2) are implemented using explicit delay operations, rather than being defined as follows:
Can you give examples of queries where these simpler definitions would lead to undesirable behavior?
Answer:
The call to
delay application of rules will prevent infinite looping in cases where the rules recursively rely on themselves and/or assertions. In such cases the
delay will ensure that results matching the assertions in the database are printed before the rules get evaluated rather than going into an infinite loop immediately.
Exercise 4.72. Why do disjoin and stream-flatmap interleave the streams rather than simply append them? Give examples that illustrate why interleaving works better. (Hint: Why did we use interleave in section 3.5.3?)
Answer:
The hint is sufficient to get you started towards the answer. Interleaving was originally introduced to handle multiple infinite streams. Interleaving prevented any one stream being explored infinitely and ensured that values from all component streams were explored in turn. These reasons are still valid here in the case of
stream-flatmap and
disjoin.
Exercise 4.73. Why does flatten-stream use delay explicitly? What would be wrong with defining it as follows:
Answer:
Flatten-stream internally calls the
interleave procedure. The first argument to
interleave is the
stream-car of the input stream. The second argument is the result of flattening the
stream-cdr of the input stream. In the absence of an explicit
delay the second argument is evaluated before being passed to
interleave. As the second argument recursively calls
flatten-stream this leads to a loop. The loop will not terminate until the input stream is exhausted. In case of infinite streams this leads to an infinite loop.
Exercise 4.74. Alyssa P. Hacker proposes to use a simpler version of stream-flatmap in negate, lisp-value, and find-assertions. She observes that the procedure that is mapped over the frame stream in these cases always produces either the empty stream or a singleton stream, so no interleaving is needed when combining these streams.
a. Fill in the missing expressions in Alyssa's program.
b. Does the query system's behavior change if we change it in this way?
Answer:
a.
b. The changes will not affect the behavior of the query system. The end result of
simple-stream-flatmap remains a stream of singleton streams in the same order as before the changes. Therefore the overall behavior should remain unchanged.
Exercise 4.75. Implement for the query language a new special form called unique. Unique should succeed if there is precisely one item in the data base satisfying a specified query. For example,
should print the one-item stream
since Ben is the only computer wizard, and
should print the empty stream, since there is more than one computer programmer. Moreover,
should list all the jobs that are filled by only one person, and the people who fill them.
There are two parts to implementing unique. The first is to write a procedure that handles this special form, and the second is to make qeval dispatch to that procedure. The second part is trivial, since qeval does its dispatching in a data-directed way. If your procedure is called uniquely-asserted, all you need to do is
and qeval will dispatch to this procedure for every query whose type (car) is the symbol unique.
The real problem is to write the procedure uniquely-asserted. This should take as input the contents (cdr) of the unique query, together with a stream of frames. For each frame in the stream, it should use qeval to find the stream of all extensions to the frame that satisfy the given query. Any stream that does not have exactly one item in it should be eliminated. The remaining streams should be passed back to be accumulated into one big stream that is the result of the unique query. This is similar to the implementation of the not special form.
Test your implementation by forming a query that lists all people who supervise precisely one person.
Answer:
Exercise 4.76. Our implementation of and as a series combination of queries (figure 4.5) is elegant, but it is inefficient because in processing the second query of the and we must scan the data base for each frame produced by the first query. If the data base has N elements, and a typical query produces a number of output frames proportional to N (say N/k), then scanning the data base for each frame produced by the first query will require N2/k calls to the pattern matcher. Another approach would be to process the two clauses of the and separately, then look for all pairs of output frames that are compatible. If each query produces N/k output frames, then this means that we must perform N2/k2 compatibility checks -- a factor of k fewer than the number of matches required in our current method.
Devise an implementation of and that uses this strategy. You must implement a procedure that takes two frames as inputs, checks whether the bindings in the frames are compatible, and, if so, produces a frame that merges the two sets of bindings. This operation is similar to unification.
Answer:
Note: I am skipping the last three problems of this chapter and moving on to Chapter 5. I will revisit them after completing Chapter 5.
Posts
