存储和检索

9.2.3 存储和检索

用来通知和询问知识库的TELL和ASK函数的下层是更原始的STORE和FETCH函数。STORE(s)将语句 s存储到知识库中，FETCH(q)返回所有合一者，这些合一者能使查询 q与知识库中的某些语句合一。我们用于说明合一的问题——找出所有与Knows(John,x)合一的事实——就是FETCH的一个实例。

实现STORE和FETCH最简单的方法就是将知识库中的所有事实都保存在一个长列表中；然后，已知查询q，对列表中每个语句s调用UNIFY(q, s)。该过程效率很低，却是可行的，知道这一点就可以理解本章其余部分了。本节的剩余内容将勾勒一些使检索效率更高的方法，读者在首次阅读时可以跳过这些内容。

我们可以通过保证只对那些有某些机会合一成功的语句尝试进行合一，从而提高FETCH的效率。例如，试图让Knows(John, x)和Brother(Richard, John)合一是没有任何意义的。通过标引（indexing）知识库中的事实，我们可以避免进行这样的合一。一种简单的方案是谓词标引，它将所有Knows事实放到一个存储桶中，所有 Brother 事实放到另一个存储桶中。为了提高访问效率，这些存储桶可以存放到一个哈希表里。[29]

当存在大量的谓词符号，而每个符号只有很少量子句时，谓词标引很有用处。然而，在某些应用中，一个给定的谓词符号有大量的子句。例如，假设税务部门希望利用谓词Employs(x, y)记录谁聘用了谁。这将是一个非常巨大的存储桶，可能包括数百万个雇主和数千万的雇员。利用谓词标引回答诸如Employs(x, y)的查询可能需要扫描整个存储桶。

对这类特殊的查询，如果不仅根据谓词而且还根据次要参数对事实建立索引（也许采用组合哈希表关键字），可能会有帮助。然后我们可以简单地从查询构造关键字，并准确地检索那些与查询合一的事实。对其它查询，诸如Employs(AIMA.org, y)，我们可能需要结合谓词和第一个参数，对事实建立索引。因此，可以在多个索引关键字下存储事实，以一种对于可能与它们合一的各种查询而言是可以立刻访问的方式表示它们。

给定要存储的语句，为所有可能与该语句合一的查询构造索引是可能的。对于事实Employs(AIMA.org, Richard)，查询为：

Employs(AIMA.org,Richard)　　　　　 AIMA.org雇佣Richard了吗？

Employs(x,Richard)　　　　　　　　 谁雇佣了Richard？

Employs(AIMA.org,y)　　　　　　　 AIMA.org雇佣了谁？

Employs(x,y)　　　　　　　　　　　谁雇佣了谁？

这些查询构成了一个包容格，如图9.2（a）所示。包容格具有一些有趣的属性。例如，格中任何节点的子节点都可以通过单一置换从它的父节点获得；任意两个节点的“最高”公共后代就是应用它们的最一般合一者的结果。任何建立在基础事实之上的格的部分都可以被系统化地构建（习题9.5）。包含重复常量的语句具有稍微不同的格，如图9.2（b）所示。待存储的语句中的函数符号和变量还引入了更多有趣的格结构。

图9.2 （a）最低一层节点为语句Employs(AIMA.org,Richard)的包容格。（b）语句Employs(John,John)的包容格

只要格所包含的节点是少量的，那么我们描述的方案就能很好地工作。对于有n个参数的谓词，格包含了O(2n)个节点。如果允许有函数符号，那么节点的数量同样是待存储语句所包含的项数量的指数级。这将导致大量的索引。在某个平衡点，索引所带来的好处将被存储和维护所有这些索引的开销所抵消。作为对策，我们可以采用固定的策略，比如只维护由谓词加上每个参数组成的索引键值，或者采用自适应策略，创建满足所提各类查询要求的索引。对大多数 AI 系统来说，它们存储的事实数量足够少，可以认为有效的索引是一个已经解决的问题。对工业和商用数据库而言，这个问题的技术解决方法已经取得实质的发展。