rules into a stand-alone imperative program. The generated program does a minimum addition of one fact at a time, incrementally maintains the results of expensive computations after each addition, and uses a combination of indexed and linked data structures to ensure that each firing of a rule takes worst-case constant time in the size of the data.
Irrelevant Derivation. The variants of bottom-up we have described so far generate the entire virtual database before turning to determining which results match the goal. Some facts that are non-goal results are nevertheless needed in order to establish facts that are goal-facts. But there can be facts in the virtual database that neither match the goal nor are required to derive the goal facts. For example, suppose the related predicate had only the first two rules:
and the goal is related(P, ks). Then any derived fact related(a, b) where b ≠ ks will not be in the result, nor will it be useful in deriving goal facts. Aho and Ullman [1979] point out that in certain cases optimizations used for relational databases are applicable. For example, we can use “selection push-down” to move the restriction that P2 = ks into the rule bodies to get
Note that this strategy works because the bound value stays in the same position. However, if our goal were related(ks, P), the binding in the goal does not directly restrict the binding in the rule body. Notice, however, that the bindings for the recursive call to related(B, P2) in the second rule are not totally unrestricted. If we think about the top-down evaluation of this rule, we see that the only useful facts for related(B, P2) are those where B is an ancestor of ks. In the genealogy database, the set of ancestors of a single person is likely a much smaller set than the set of all known people in the EDB. Thus, for example, if we computed
initially, to find all the ancestors of ks, we could modify the second rule to be
With bottom-up evaluation, this rule would only establish facts where B is an ancestor of ks, effectively eliminating the derivation of many of the irrelevant facts. This idea of deriving an auxiliary predicate that mimics the propagation of topdown bindings (but which can be evaluated bottom up) is the basis of the Magic Sets approach [Bancilhon et al. 1986]. Magic Sets tries to avoid derivation of irrelevant facts by limiting bindings based on constants in the final goal. It might be seen as top-down direction of bottom-up evaluation. The full Magic Sets method is more complicated than the example above, as it has to track binding propagation through all the rules of a program, and different occurrences of the same predicate in a program may be constrained differently. In the worst case, this variation may lead to an exponential blow-up in the number of intermediate rules that Magic Sets might generate in order to track all such bindings.
Optimization of the bottom-up evaluation with respect to the goal has been studied extensively—both as generalizations of selection push-down and as variants of the Magic Sets ideas discussed above. Selection push-down is a specific instance of the general idea of propagating constants in the queries or in the rules so that only the relevant facts are derived, if possible. This strategy is analogous to partial evaluation in the programming languages literature [Jones et al. 1993]. Other evaluation methods include static filtering [Kifer and Lozinskii 1990] and dynamic filtering [Kifer and Lozinskii 1987, Kifer and Lozinskii 1988], which limit the facts being processed during evaluation, as well as rewrite methods such as specialization [Tekle et al. 2008], which rewrites the program to achieve the same effect given any evaluation strategy.
As briefly described above, Magic Sets [Bancilhon et al. 1986] limits inference during bottom-up evaluation by introducing magic predicates that infer a relevant subset of values for arguments of predicates by using the binding of variables in other goals in a rule, an example of sideways information passing. In the years following the initial work on Magic Sets, many variants have been developed including supplementary Magic Sets [Saccà and Zaniolo 1986b], which saves space and time by introducing intermediate predicates that can be reused, generalized counting [Beeri and Ramakrishnan 1991, Saccà and Zaniolo 1986a], which optimizes rules by keeping track of which rules were used to infer a particular fact, and Magic Templates [Ramakrishnan 1991], which generalize to Horn clauses with function symbols. Beeri and Ramakrishnan [1991] provide a formal discussion of these methods.
One serious problem with Magic Sets and its derivatives is that the same fact may be manifested an exponential number of times in several variants of the same predicate, since Magic Sets introduces a new copy of each original predicate for every possible binding pattern for the arguments of that original predicate. For example, consider the reachability rules from Section 1.4.1 and a query with both arguments bound (such as reachable(a, b)). Magic Sets would produce the following rules and a fact, where reachable_bb is a copy of reachable created for the calls where both arguments are bound, and reachable_bf is a copy for the calls where the first argument is bound and the is second free, and so forth.
It can be seen that the same reachability fact may be associated with both reachable_bf and reachable_bb. In general, one predicate may get blown up into as many as 2k variants, where k is the number of arguments of the predicate (for different sequences of b’s and f’s), and so the same fact may be represented an exponential number of times. In addition, note that this method can generate spurious rules that infer no facts, such as the second-to-last rule. This situation arises from hypotheses that generate no “new” magic facts, analogous to the generation of a subquery that is isomorphically equivalent to the head of a rule in top-down evaluation.
More recently, a novel method, called demand transformation [Tekle and Liu 2010], has been introduced, which solves the problem of propagating top-down bindings cleanly, including avoiding the problem above and in other Magic Sets variants.
Demand transformation avoids the blow-up by storing facts for the same predicate together, and using an incremental evaluation strategy with carefully selected data structures to ensure that each firing of a rule takes constant time [Liu and Stoller 2009]. It has also been shown that bottom-up evaluation of rules generated by demand transformation has the same time complexity as the top-down evaluation with variant tabling as implemented in various systems, including XSB [Swift and Warren 2011] and YAP [Costa et al. 2012]. Variant tabling reuses answers from previous queries that are identical to the current query up to variable renaming—see Section 1.5.2.1. In contrast to variant tabling, subsumptive tabling, also implemented in XSB, reuses answers from previous queries that subsume (i.e., are more general than) the current query. A method that has the same performance characteristic as the top-down evaluation with subsumptive tabling, called subsumptive demand transformation [Tekle and Liu 2011], has also been developed.
What distinguishes Demand Transformation (and Subsumptive Demand Transformation) from Magic Sets and variants is not just that it is simpler, but more importantly, that it provides precise time and space complexity guarantees [Tekle and Liu 2010, Tekle and Liu 2011]. In particular, it improves over Magic Sets asymptotically, even exponentially.
1.5.2 Top-Down Evaluation
We
