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 n
2
/
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 n
2
/
k
2 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.
练习 4.76：我们将 and 实现为查询的串行组合（图 4.5），这种做法优雅，但效率不高，因为在处理 and 的第二个查询时，必须对第一个查询产生的每个框架扫描一遍数据库。若数据库有 n 个元素，且典型查询产生的输出框架数与 n 成正比（设为 n/k），则为第一个查询产生的每个框架扫描数据库将需要 n²/k 次模式匹配器调用。另一种方法是分别处理 and 的两个子句，然后查找所有相互兼容的输出框架对。若每个查询产生 n/k 个输出框架，则需要进行 n²/k² 次兼容性检查——比当前方法所需的匹配次数少了 k 倍。
请设计一种使用这一策略的 and 实现。你必须实现一个过程，以两个框架为输入，检查其中的绑定是否兼容，若兼容则产生合并两组绑定后的框架。此操作类似于合一 (unification)。