4.4.1 Deductive Information Retrieval

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 Microshaft, 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.

Subheading: A sample data base

为了说明查询系统的功能，我们将展示如何用它管理 Microshaft 公司的人事档案数据库——Microshaft 是波士顿地区一家蒸蒸日上的高科技公司。该语言提供对人事信息的模式驱动访问，并能利用通用规则进行逻辑推导。

小节：一个示例数据库

The personnel data base for Microshaft contains

assertions about

company personnel. Here is the information about Ben Bitdiddle, the resident

computer wizard:

Microshaft 的人事数据库包含关于公司员工的断言 (assertions)。以下是关于驻场计算机奇才 Ben Bitdiddle 的信息：

Each assertion is a list (in this case a triple) whose elements can themselves

be lists.

每条断言都是一个表（此处为三元组），其元素本身也可以是表。

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:

作为驻场奇才，Ben 负责公司的计算机部门，并监管两名程序员和一名技术员。以下是关于他们的信息：

There is also a programmer trainee, who is supervised by Alyssa:

还有一名程序员实习生，由 Alyssa 监管：

All of these people are in the computer division, as indicated by the word

computer as the first item in their job descriptions.

这些人都隶属于计算机部门，这从他们职位描述中首项均为 computer 一词可以看出。

Ben is a high-level employee. His supervisor is the company’s big wheel

himself:

Ben 是一名高级员工，他的上司正是公司的大人物本人：

Besides the computer division supervised by Ben, the company has an accounting

division, consisting of a chief accountant and his assistant:

除 Ben 监管的计算机部门外，公司还设有一个会计部门，由首席会计师及其助理组成：

There is also a secretary for the big wheel:

另有一名为大人物服务的秘书：

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:

数据库还包含关于哪些职位的人可以胜任其他职位工作的断言。例如，一名计算机奇才既可以胜任计算机程序员的工作，也可以胜任计算机技术员的工作：

A computer programmer could fill in for a trainee:

一名计算机程序员可以顶替实习生：

Also, as is well known,

此外，众所周知，

Subheading: Simple queries

小节：简单查询

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 system will respond with the following items:

系统将返回以下条目：

The input query specifies that we are looking for entries in the data base that

match a certain

pattern. 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.” 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

输入的查询指定了我们希望在数据库中查找匹配某个模式 (pattern) 的条目。在这个例子中，该模式指定的条目由三项组成：第一项是字面符号 job，第二项可以是任意内容，第三项是字面表 (computer programmer)。匹配表中第二项可以是"任意内容"，由模式变量 (pattern variable) ?x 来表示。模式变量的一般形式是一个符号，作为该变量的名字，前面加一个问号。我们将在下面看到，为何给模式变量指定名字，而非单纯地在模式中放入 ? 来表示"任意内容"，是有实际意义的。系统对简单查询的响应是显示数据库中所有与指定模式匹配的条目。一个模式可以包含多个变量。例如，查询

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,

同一个模式变量可以在查询中出现多次，表示在每个位置必须出现相同的"任意内容"。这正是变量要有名字的原因。例如，

finds all people who supervise themselves (though there are no such assertions

in our sample data base).

The query

可以找出所有自我监管的人（尽管在我们的示例数据库中不存在这样的断言）。查询

matches all job entries whose third item is a two-element list whose first item

is computer:

匹配所有第三项为以 computer 开头的两元素表的职位条目：

This same pattern does not match

同样的模式不匹配

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

因为该条目的第三项是一个三元素的表，而模式的第三项要求恰好只有两个元素。若要修改模式，使第三项可以是任何以 computer 开头的表，可以指定

For example,

例如，

matches the data

匹配数据

with ?type as the list (programmer trainee). It also

matches the data

其中 ?type 被绑定为表 (programmer trainee)。它还与以下数据匹配：

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

其中 ?type 被绑定为表 (programmer)，以及与以下数据匹配：

with ?type as the empty list ().

We can describe the query language’s processing of simple queries as follows:

其中 ?type 被绑定为空表 ()。我们可以如下描述查询语言处理简单查询的过程：

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.

注意，如果模式中不含变量，查询就退化为判断该模式是否存在于数据库中。若存在，空赋值——即不为任何变量赋值的方案——即满足该数据库中的该模式。