读完了《逻辑编程导论》，这本书比较偏向理论，定义了很多概念。感觉书中的安全性、分析、优化等内容，读了后有一些收获。想对其中的一些内容做一些笔记，写写我的想法。书中所用的语言是Epilog，我转写成Prolog吧。
先说说查询的评估与优化吧。
原书相关章节：
http://logicprogramming.stanford.edu/notes/chapter_05.html
http://logicprogramming.stanford.edu/notes/chapter_06.html
评估
感觉书中所说的评估算法有点像大O表示法，它们都不在意数据的具体规模，通常也都考虑的是最坏的情况。当数据量越大、越极端，好的算法的优势会更明显。当然，在实际情况中，数据量通常是有限的，也有自身特点，理论上的好的算法，实际效率未必比普通的高。要根据实际情况选择合适的算法。
这是书中的第1个例子：
goal(a, c) :- p(a, Y), p(Y, c).
书中对此所做的分析：“我们假设一个标准的从左到右的查询实现，不对数据集进行索引，并且在计算结果之后不对结果进行缓存。……在最坏的情况下，数据库中有n^2个事实，其中n是我们语言中的基本术语的数量。因此，我们需要n^2个步骤来评估第一个合取项。最多有n个事实以a作为第一个参数。对于每一个，我们研究第二个合取项的n种可能性。计算实例的成本如下……n^2 + n * n^2 = n^2 + n^3”
书中的文字比较拗口，一些细节也有些含糊。我的感觉是，所查询的只有p这一种谓词，这个谓词中只有2个元，假设每个元对应的数据都特别多，各有n种，那组合搭配后有n^2个情况。查询时，先对第1个规则p(a, Y)进行查询，得逐个查询n^2个事实，判断是否匹配规则。a是常量，Y是变量，查询完第1个规则后，最极端的情况下，以a为第1个参数，有n个事实能匹配得了Y。在这n种情况下，分别继续考查第2个规则，就得逐个查询n^2个事实，在这个阶段中，得查询n * n^2次。总共是n^2 + n^3次。
这种结果是不符合正常思维，因为书里已经提前说过，不进行索引和缓存。要是能进行索引，提前根据名称等属性组织好数据，就能像查词典一样，即使数据很多，也能很快找到，不用一个一个查询。要是能缓存、对语句提前进行分析，就更像正常人的做法。明明只有一种谓词，干嘛还分两个阶段查询，查询每个事实时，如果符合第1个规则，再用第2个规则判断那个事实，如果都符合要求，就记录结果，那只需查询n^2次。
这是书中的第2个例子：
goal(X, Z) :- p(X, Y), p(Y, Z).
成本为：n^2 + n^2 * n^2 = n^2 + n^4
类似第1个例子，所查询的只有一种2元谓词p，最多有n^2个事实。查询完第1个规则，结果是X与Y的组合，最多有n^2个结果。对于每个结果，分别继续考查第2个规则。
然后以书中的一道习题作为例子：
goal(X, Y):- p(X, Y), q(Y), q(Z).
同样是写出其评估算法的表达式。答案是：2n^4 + 2n^3 + n^2 + n。
感觉这个与上面的例子不同的是，这个查询中有2种谓词，2元谓词p和1元谓词q，最坏情况下有n^2 + n个事实。对这3个规则依次查询，成本分别为n^2 + n、n^2(n^2 + n)、n^2(n^2 + n)，加到一起为2n^4 + 2n^3 + n^2 + n。
优化
子目标排序
以这个查询为例：
goal(X, Y) :- p(X), r(X, Y), q(X).
查询对象有3种谓词，数据库有n^2 + 2n个事实。对这3个规则依次进行查询，成本分别为n^2 + 2n、n(n^2 + 2n)、n^2(n^2 + 2n)。加到一起为n^4 + 3n^3 + 3n^2。
实际上，条件q应置于条件r前。如下所示：
goal(X, Y) :- p(X), q(X), r(X, Y).
而此时，虽然同样共有n^2 + 2n个事实，但对这3个规则依次进行查询，成本分别为n^2 + 2n、n(n^2 + 2n)、n(n^2 + 2n)，加到一起为2n^3 + 5n^2 + 2n。
同大O表示法类似，第一个查询的最坏情况是n^4，而第二个只有n^3。
此外，书中还表示：“在存在索引的情况下，两种排序的渐近复杂度是相同的。然而，第二次排序的低阶项表明它仍然是更好的排序。此外，可以证明，在所有可能的数据库上取平均值，第二个查询比第一个更好。”
感觉进行这种优化的思路是，尽量让许多可能性产生之
前排
除它们。当看到书中的经过优化的密码算术代码，一下子想起之前看过一些Prolog代码，看起来也像阶梯一般，当时不理解为什么要这么写，而不是写得整齐一些，将相同谓词的代码放到一块儿？因为要先尽量约束少量变量，减少可能性，再查询其他变量。因此，越到下面，变量越多，变量之间纠缠程度越高，语句也就越长，像阶梯一样。
此外，感觉这样的优化方式，也想起了在学C语言时，书中提到过，出于性能考虑，在编写多重循环时，如果可行，最好将循环次数少的放在外层，多的放在内层。都是一层一层，越到里面变量、可能性越多。有点异曲同工之妙。
子目标移除
效率低下的另一个常见原因是查询中存在冗余的子目标。
以这个查询为例：
goal(X, Y) :- p(X), q(Y), q(Z).
在这里，q(Z)是多余的。如果变量Y的值能使q(Y)为真，那Z为同样的值，也能使q(Z)为真。完全可以删除q(Z)这个子目标。
很容易检查某些冗余子目标。如果某些变量只出现过一次，很有可能就是冗余（如果是出于不关注变量具体的值的目的，可以用空变量_代替它）。一些编辑器、解释器也能自动检测这种情况，并给出警告。
但这个方法不完备。当多余子目标共享会阻止该方法检测冗余变量。比如：
goal(X, Y) :- p(X, Y), q(X, Y), p(X, Z), q(X, Z).
检测这种冗余会更麻烦，花费也会更多。
规则移除
以这个代码为例：
goal(X) :- p(X, b), q(b), r(Z).goal(X) :- p(X, Y), q(Y)
由第一个规则产生的任何答案，也会由第二个规则产生，因此第一个规则是多余的。