Exercise 4.55 · 习题

Exercise 4.55: 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.

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:

(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ₙ⟩)

is satisfied by all sets of values for the pattern variables that
simultaneously satisfy ⟨

q
u
e
r

y
1

⟩ … ⟨

q
u
e
r

y
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ₙ⟩)

is satisfied by all sets of values for the pattern variables that satisfy at
least one of ⟨

q
u
e
r

y
1

⟩ … ⟨

q
u
e
r

y
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
⟨

q
u
e
r

y
1

⟩.

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ₙ⟩)

will be satisfied by assignments to the pattern variables for which the
⟨predicate⟩ applied to the instantiated ⟨

a
r

g
1

⟩ …
⟨

a
r

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

练习 4.55：给出能从数据库中检索以下信息的简单查询：

所有由 Ben Bitdiddle 监管的人员；

财务部门所有人员的姓名与职务；

所有居住在 Slumerville 的人员的姓名与地址。

复合查询

简单查询构成查询语言的基本操作。为了构成复合操作，查询语言提供了组合的方法。使查询语言成为逻辑式程序设计语言的原因之一，是其组合的方法与构成逻辑表达式所用的组合方法相对应：and、or 与 not。（这里的 and、or 和 not 并非 Lisp 的基本元素，而是内置于查询语言中的操作。）

我们可以使用 and 如下方式查找所有计算机程序员的地址：

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

得到的输出是：

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

一般而言，

(and ⟨query₁⟩ ⟨query₂⟩ … ⟨queryₙ⟩)

由同时满足 ⟨query₁⟩ … ⟨queryₙ⟩ 的所有模式变量赋值所满足。

与简单查询的处理方式相同，系统通过找出所有满足该查询的模式变量赋值来处理复合查询，然后以这些值将查询实例化并显示出来。

构造复合查询的另一种方式是通过 or。例如，

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

将找出所有由 Ben Bitdiddle 或 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)))

一般而言，

(or ⟨query₁⟩ ⟨query₂⟩ … ⟨queryₙ⟩)

由至少满足 ⟨query₁⟩ … ⟨queryₙ⟩ 中一个的所有模式变量赋值所满足。

复合查询也可以用 not 构成。例如，

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

找出所有由 Ben Bitdiddle 监管但不是计算机程序员的人员。一般而言，

(not ⟨query₁⟩)

由所有不满足 ⟨query₁⟩ 的模式变量赋值所满足。

最后一种组合形式称为 lisp-value。当 lisp-value 是模式的第一个元素时，它指定下一个元素是一个 Lisp 谓词，将以其余（已实例化的）元素作为参数加以应用。一般而言，

(lisp-value ⟨predicate⟩ ⟨arg₁⟩ … ⟨argₙ⟩)

由使得 ⟨predicate⟩ 应用于已实例化的 ⟨arg₁⟩ … ⟨argₙ⟩ 结果为真的模式变量赋值所满足。例如，要找出所有薪资高于 30,000 美元的人员，可以写：

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