查询系统是如何工作的
从高层视角解释查询系统的总体结构：模式匹配、框架流、合一以及规则的应用。
导言
本节给出一个概览，解释系统的总体结构，不涉及底层实现细节。在描述了实现之后，我们将能够理解它的一些局限性，以及查询语言的逻辑运算与数学逻辑运算之间的一些细微差别。
显然，查询求值器必须执行某种搜索，才能把查询与数据库中的事实和规则匹配起来。一种做法是把查询系统实现为一个非确定性程序（你不用担心这种方式）。另一种可能是借助流来管理搜索。我们的实现采用第二种做法。
查询系统围绕两个核心操作组织起来：模式匹配（pattern matching）和合一（unification）。我们先描述模式匹配，并说明这个操作如何与按框架流组织信息的方式相结合，使我们既能实现简单查询，也能实现复合查询。
接下来我们讨论合一，它是模式匹配的推广，为实现规则所必需。最后，我们展示整个查询解释器如何通过一个过程组合成一个整体，这个过程以类似于 eval 对元循环求值器中表达式进行分类的方式对表达式进行分类。
模式匹配
模式匹配器（pattern matcher）是一个程序，它检验某个数据是否符合指定的模式。例如，数据表 ((a b) c (a b)) 匹配模式 (?x c ?x)，此时模式变量 ?x 绑定（bind）到 (a b)。同一数据表也匹配模式 (?x ?y ?z)，此时 ?x 和 ?z 都绑定到 (a b)，?y 绑定到 c。它还匹配模式 ((?x ?y) c (?x ?y))，此时 ?x 绑定到 a，?y 绑定到 b。但是，它不匹配模式 (?x a ?y)，因为该模式规定表的第二个元素是符号 a。
查询系统使用的模式匹配器的输入是一个模式（例如 (?x c ?x)）、一个数据（例如 ((a b) c (a b))）和一个框架（frame），框架规定各模式变量的各种绑定。它检查数据是否以与框架中已有绑相一致的方式匹配该模式。如果一致，它返回给定的框架加上匹配所确定的任何绑定而扩展后的框架。否则，它表明匹配失败。
例如，用模式 (?x ?y ?x) 在空框架下匹配数据 (a b a)，将返回一个规定 ?x 绑定到 a、?y 绑定到 b 的框架。用同一模式、同一数据，但在一个规定 ?y 绑定到 a 的框架下尝试匹配，将会失败。用同一模式、同一数据，但在一个 ?y 绑定到 b 而 ?x 未绑定的框架下尝试匹配，将返回给定框架加上 ?x 绑定到 a 而扩展后的框架。
模式匹配器就是处理不涉及规则的简单查询所需的全部机制。例如，为处理查询
(job ?x (computer programmer))我们扫描数据库中的所有断言，选出那些在初始空框架下匹配该模式的断言。对找到的每个匹配，我们用匹配返回的框架来实例化模式，给出 ?x 的值。
框架流
对框架的模式测试是通过使用流来组织的。给定单个框架，匹配过程逐个遍历数据库条目。对每个数据库条目，匹配器要么生成一个表明匹配失败的特殊符号，要么生成框架的一个扩展。所有数据库条目的结果被收集到一个流中，该流经过一个过滤（filter）器剔除失败者。结果就是一个流，包含通过与数据库中某条断言匹配而扩展给定框架的所有框架。
在我们的系统中，一个查询接收一个框架输入流，并对流中每个框架执行上述匹配操作，如下图所示。也就是说，对输入流中的每个框架，查询生成一个新流，由该框架通过与数据库中断言匹配得到的所有扩展组成。然后所有这些流合并成一个巨大的流，其中包含输入流中每个框架的所有可能扩展。这个流就是查询的输出。
为回答一个简单查询，我们用一个由单个空框架组成的输入流来调用查询。得到的输出流包含空框架的所有扩展（即我们查询的所有答案）。这个框架流随后被用来生成一个流，其中原始查询模式的副本的变量由各框架中的值实例化，而这个流就是最终打印出来的内容。
复合查询
按框架流实现的真正优雅之处，在我们处理复合查询时显现出来。复合查询的处理利用了匹配器要求匹配与指定框架相一致的能力。例如，为处理两个查询的 and，例如
(and (can-do-job ?x (computer programmer trainee))
(job ?person ?x))（通俗地说，“找出所有能做程序员实习生工作的人”），我们先找出所有匹配模式
(can-do-job ?x (computer programmer trainee))的条目。这产生一个框架流，其中每个框架都包含 ?x 的一个绑定。然后对流中每个框架，我们找出所有以与 ?x 的给定绑定相一致的方式匹配
(job ?person ?x)的条目。每个这样的匹配都将产生一个包含 ?x 和 ?person 绑定的框架。两个查询的 and 可以看作这两个成员查询的串联组合，如下图所示。通过第一个查询过滤的框架被第二个查询过滤并进一步扩展。
两个查询的 and 组合是通过串联操作框架流产生的。
下图显示了计算两个查询的 or 的类似方法，即把两个成员查询作并联组合。输入框架流分别由每个查询扩展。然后将得到的两个流合并，产生最终的输出流。
两个查询的 or 组合是通过并联操作框架流并合并结果产生的。
即便从这段高层描述也能看出，复合查询的处理可能很慢。例如，由于一个查询可能为每个输入框架产生多个输出框架，而 and 中每个查询的输入框架又来自前一个查询，因此一个 and 查询在最坏情况下可能需要执行数量随查询个数呈指数增长（exponential）的匹配。虽然只处理简单查询的系统相当实用，但处理复杂查询极其困难。
从框架流的观点看，某个查询的 not 起过滤器的作用，剔除该查询能被满足的所有框架。例如，给定模式
(not (job ?x (computer programmer)))我们尝试为输入流中的每个框架生成满足 (job ?x (computer programmer)) 的扩展框架。我们从输入流中剔除所有存在这类扩展的框架。结果是一个流，只包含其中 ?x 的绑定不满足 (job ?x (computer programmer)) 的那些框架。例如，在处理查询
(and (supervisor ?x ?y)
(not (job ?x (computer programmer))))时，第一个子句将生成带 ?x 和 ?y 绑定的框架。然后 not 子句过滤这些框架，剔除 ?x 的绑定满足”?x 是计算机程序员”这一限制的所有框架。
lisp-value 特殊形式实现为框架流上类似的过滤器。我们用流中每个框架实例化模式中的任何变量，然后应用 Lisp 谓词。我们从输入流中剔除谓词失败的所有框架。
合一
为在查询语言中处理规则，我们必须能找到结论与给定查询模式匹配的规则。规则结论与断言类似，只是它们可以包含变量，所以我们将需要模式匹配的一种推广——称为合一（unification）——其中”模式”和”数据”都可以包含变量。
合一器（unifier）接收两个各自包含常量和变量的模式，确定是否可能给变量赋值使两个模式相等。如果可能，它返回一个包含这些绑定的框架。例如，合一 (?x a ?y) 和 (?y ?z a) 将规定一个框架，其中 ?x、?y 和 ?z 都必须绑定到 a。另一方面，合一 (?x ?y a) 和 (?x b ?y) 将失败，因为不存在能使两个模式相等的 ?y 值。（要让模式的第二个元素相等，?y 必须是 b；然而要让第三个元素相等，?y 又必须是 a。）查询系统中使用的合一器与模式匹配器一样，接收一个框架作为输入，并执行与该框架一致的合一。
合一算法是查询系统中技术上最困难的部分。对于复杂模式，执行合一可能看起来需要演绎。例如，为合一 (?x ?x) 和 ((a ?y c) (a b ?z))，算法必须推断 ?x 应该是 (a b c)，?y 应该是 b，?z 应该是 c。我们可以把这一过程看作求解模式各成分之间的一组方程。一般地，这些是联立方程（simultaneous equations），求解可能需要大量的推演。例如，合一 (?x ?x) 和 ((a ?y c) (a b ?z)) 可以看作是规定联立方程
?x = (a ?y c)
?x = (a b ?z)这些方程蕴含
(a ?y c) = (a b ?z)后者又蕴含
a = a, ?y = b, c = ?z,于是有
?x = (a b c)在成功的模式匹配中，所有模式变量都会被绑定，且它们被绑定的值只包含常量。到目前为止我们看到的所有合一例子也是如此。然而一般地，一次成功的合一可能无法完全确定变量的值；有些变量可能仍未绑定，另一些则可能被绑定到包含变量的值。
考虑 (?x a) 和 ((b ?y) ?z) 的合一。我们可以推出 ?x = (b ?y) 和 a = ?z，但无法进一步解出 ?x 或 ?y。合一并未失败，因为给 ?x 和 ?y 赋值确实能使两个模式相等。由于这个匹配完全不限制 ?y 能取的值，结果框架中不放入 ?y 的绑定。但匹配确实限制了 ?x 的值。无论 ?y 取什么值，?x 都必须是 (b ?y)。因此框架中放入 ?x 绑定到模式 (b ?y) 的绑定。如果 ?y 的值后来被确定并加入框架（通过与另一模式匹配或合一，且要求与该框架一致），先前绑定的 ?x 将引用这个值。
应用规则
合一是查询系统中依据规则进行推理的那个组件的关键。为弄清这是如何做到的，考虑处理一个涉及应用规则的查询，例如
(lives-near ?x (Hacker Alyssa P))为处理这个查询，我们先用上面描述的普通模式匹配过程，看数据库中是否有断言匹配这个模式。（这种情况下不会有，因为我们的数据库不包含关于谁住得离谁近的直接断言。）下一步是尝试把查询模式与每条规则的结论合一。我们发现该模式与规则
(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))))的结论合一，产生一个规定 ?person-2 绑定到 (Hacker Alyssa P)、?x 应绑定到（即取与 ?person-1 相同的值）的框架。现在，相对于这个框架，我们求值由规则体给出的复合查询。成功的匹配将通过提供 ?person-1 的绑定来扩展这个框架，从而给出 ?x 的值，我们可以用它来实例化原始查询模式。
一般地，查询求值器在尝试于一个为某些模式变量规定绑定的框架中确立一个查询模式时，用以下方法应用规则：
- 将查询与规则的结论合一，如果成功，形成原始框架的一个扩展。
- 相对于扩展后的框架，求值由规则体形成的查询。
请注意这与在 Lisp 的 eval/apply 求值器中应用过程的方法有多相似：
- 把过程的形参绑定到它的实参，形成一个扩展原始过程环境的框架。
- 相对于扩展后的环境，求值由过程体形成的表达式。
两个求值器之间的相似之处毫不令人意外。正如过程定义是 Lisp 中的抽象手段，规则定义是查询语言中的抽象手段。在两种情况下，我们都通过创建适当的绑定，并相对于这些绑定求值规则体或过程体来展开抽象。
简单查询
我们在本节前面看到了在没有规则的情况下如何求值简单查询。既然已经看过如何应用规则，我们就可以描述如何同时使用规则和断言来求值简单查询了。
给定查询模式和一个框架流，我们为输入流中的每个框架产生两个流：
- 一个由把模式与数据库中所有断言匹配（用模式匹配器）得到的扩展框架组成的流，以及
- 一个由应用所有可能的规则（用合一器）得到的扩展框架组成的流。
把这两个流拼接到一起，产生一个流，包含给定模式在与原始框架一致的前提下被满足的所有方式。这些流（输入流中每个框架各一个）现在全部合并成一个大流，因此包含原始输入流中任何框架能被扩展以产生与给定模式匹配的所有方式。
查询求值器与驱动循环
尽管底层匹配操作很复杂，系统的组织方式却很像任何语言的求值器。协调匹配操作的过程叫 qeval，它扮演的角色类似于 Lisp 的 eval 过程。qeval 的输入是一个查询和一个框架流。它的输出是一个框架流，包含与查询模式成功匹配的、扩展了输入流中某个框架的那些框架。与 eval 一样，qeval 对不同类型表达式（查询）进行分类，并分派给相应的过程。每个特殊形式（and、or、not 和 lisp-value）各有一个过程，简单查询也有一个。
驱动循环（driver loop）类似于本章其他求值器中的 driver-loop 过程，它从终端读取查询。对每个查询，它用该查询和由单个空框架组成的流调用 qeval。这将产生包含所有可能匹配（空框架的所有可能扩展）的流。对结果流中的每个框架，它用框架中找到的变量的值实例化原始查询。这个实例化查询的流随后被打印出来。
驱动循环还检查特殊命令 assert!，它表明输入不是一个查询，而是要加入数据库的断言或规则。例如，
(assert! (job (Bitdiddle Ben) (computer wizard)))
(assert! (rule (wheel ?person)
(and (supervisor ?middle-manager ?person)
(supervisor ?x ?middle-manager))))一个例子
下面是一个部分追踪的例子：
;;; Query input:
(assert! (rule (append () ?y ?y)))
;;; Query input:
(assert! (rule (append (?u . ?v) ?y (?u . ?z))
(append ?v ?y ?z)))
;;; Query input:
(append ?a ?b (aa bb))
(unify-match (append ?a ?b (aa bb)) ; 把原始查询与……
(append () ?1y ?1y) ; 基本情况规则匹配
()) ; 无约束
RETURNS: ((?1y . (aa bb)) (?b . ?1y) (?a . ()))
PRINTS: (append () (aa bb) (aa bb))由于基本情况规则没有规则体，一旦匹配成功，我们就可以打印一个成功结果。（打印前，我们必须在环境中查找变量，这样打印出来的东西才不含变量。）
现在我们把原始查询与另一条规则的结论合一：
(unify-match (append ?a ?b (aa bb)) ; 把原始查询与……
(append (?2u . ?2v) ?2y (?2u . ?2z)) ; 递归规则匹配
() ; 无约束
RETURNS: ((?2z . (bb)) (?2u . aa) (?b . ?2y) (?a . (?2u . ?2v)))
[记为 F1]这成功了，但我们还不能打印任何东西，因为我们现在必须把那条规则的规则体作为一个新查询。注意这里的缩进表示这次 unify-match 调用在待处理规则内部。
(unify-match (append ?2v ?2y ?2z) ; 把递归规则的规则体与……
(append () ?3y ?3y) ; 基本情况规则匹配
F1) ; 带来自 F1 的约束
RETURNS: ((?3y . (bb)) (?2y . ?3y) (?2v . ()) [加上 F1])
PRINTS: (append (aa) (bb) (aa bb))
(unify-match (append ?2v ?2y ?2z) ; 把同一规则体与……
(append (?4u . ?4v) ?4y (?4u . ?4z)) ; 递归规则匹配
F1) ; 带 F1 的约束
RETURNS: ((?4z . ()) (?4u . bb) (?2y . ?4y) (?2v . (?4u . ?4v))
[加上 F1]) [记为 F2]
(unify-match (append ?4v ?4y ?4z) ; 把新找到的匹配的规则体与……
(append () ?5y ?5y) ; 基本情况规则匹配
F2) ; 带新找到的约束
RETURNS: ((?5y . ()) (?4y . ?5y) (?4v . ()) [加上 F2])
PRINTS: (append (aa bb) () (aa bb))
(unify-match (append ?4v ?4y ?4z) ; 把同一规则体与……
(append (?6u . ?6v) ?6y (?6u . ?6z)) ; 递归规则匹配
F2) ; 相同约束
RETURNS: () ; 但这次失败要点
以下是本小节的几个要点：
- 简单查询用模式匹配器处理。
- 为处理复合查询，模式匹配器需要检查匹配是否与指定框架一致。
- 规则用合一处理。
接下来
下一小节，我们将讨论逻辑编程与数学逻辑之间的关系。