[1] Because matching is generally very expensive, we would like to avoid applying the full matcher to every element of the data base. This is usually arranged by breaking up the process into a fast, coarse match and the final match. The coarse match filters the data base to produce a small set of candidates for the final match. With care, we can arrange our data base so that some of the work of coarse matching can be done when the data base is constructed rather then when we want to select the candidates. This is called indexing the data base. There is a vast technology built around data-base-indexing schemes. Our implementation, described in section 4.4.4, contains a simpleminded form of such an optimization.
[2] But this kind of exponential explosion is not common in and queries because the added conditions tend to reduce rather than expand the number of frames produced.
[3] There is a large literature on data-base-management systems that is concerned with how to handle complex queries efficiently.
[4] There is a subtle difference between this filter implementation of not and the usual meaning of not in mathematical logic. See section 4.4.3.
[5] In one-sided pattern matching, all the equations that contain pattern variables are explicit and already solved for the unknown (the pattern variable).
[6] Another way to think of unification is that it generates the most general pattern that is a specialization of the two input patterns. That is, the unification of (?x a) This means that the unification of list($x, "a") and ((b ?y) ?z) list(list("b", $y), $z) is ((b ?y) a), list(list("b", $y), "a") and that the unification of (?x a ?y) list($x, "a", $y) and (?y ?z a), list($y, $z, "a"), discussed above, is (a a a). list("a", "a", "a"). For our implementation, it is more convenient to think of the result of unification as a frame rather than a pattern.
[7] Since unification is a generalization of matching, we could simplify the system by using the unifier to produce both streams. Treating the easy case with the simple matcher, however, illustrates how matching (as opposed to full-blown unification) can be useful in its own right.
[8] The reason we use streams (rather than lists) of frames is that the recursive application of rules can generate infinite numbers of values that satisfy a query. The delayed evaluation embodied in streams is crucial here: The system will print responses one by one as they are generated, regardless of whether there are a finite or infinite number of responses.
4.4.2   How the Query System Works