Exercise 4.56 · 习题

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

Rules

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.

练习 4.56：给出能检索以下信息的复合查询：

所有由 Ben Bitdiddle 监管的人员的姓名及其地址；

所有薪资低于 Ben Bitdiddle 的人员，以及他们的薪资和 Ben Bitdiddle 的薪资；

所有由计算机部门以外的人员监管的员工，以及该监管者的姓名和职务。

规则

除基本查询和复合查询外，查询语言还提供了对查询进行抽象的方法，这便是规则 (rules)。规则

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

规定：如果两个人住在同一城镇，则他们彼此相邻而居。末尾的 not 子句防止规则声称所有人都与自己相邻而居。same 关系由一条非常简单的规则定义：

(rule (same ?x ?x))

下面这条规则声明，如果一个人监管了某位中层管理者，而该中层管理者又监管了他人，则此人是组织中的"核心人物"（wheel）：

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

规则的一般形式为

(rule ⟨conclusion⟩ ⟨body⟩)

其中 ⟨conclusion⟩ 是一个模式，⟨body⟩ 是任意查询。我们可以把一条规则理解为表示一个大型（甚至无限的）断言集合，即所有满足规则体的变量赋值对规则结论的实例化。当我们描述简单查询（模式）时，曾说过若实例化后的模式在数据库中，则变量赋值满足该模式。但模式不必以断言的形式显式出现在数据库中，它也可以是一条规则所蕴含的隐式断言。例如，查询

(lives-near ?x (Bitdiddle Ben))

的结果为

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

要找出所有住在 Ben Bitdiddle 附近的计算机程序员，可以询问：

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

与复合过程的情形一样，规则可以作为其他规则的组成部分使用（如上面的 lives-near 规则所示），甚至可以递归地定义。例如，规则

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

表示：在组织中，若上司是某员工的直接主管，或者（递归地）该员工的直接主管被上司所凌驾，则该员工被上司所凌驾。