Our implementation of
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
elements, and a typical query produces a number of output frames proportional to
), then scanning the data base for each frame produced by the first query will require
calls to the pattern matcher. Another approach would be to process the two clauses of the
separately, then look for all pairs of output frames that are compatible. If each query produces
output frames, then this means that we must perform
compatibility checks -- a factor of
fewer than the number of matches required in our current method.
Devise an implementation of
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.
Figure 4.5: The and combination of two queries is produced by operating on the stream of frames in series.
There are no comments yet.
You must log in to post a comment.Login