Declarative Logic Programming. Michael Kifer

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 2^k 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 now turn to top-down evaluation. This strategy starts with a query that is represented by one or more goal literals and compares each goal against the heads of the various rules in the program. If we get a match, possibly substituting for variables, then we replace the goal with new subgoals from the rule’s body (noting that the body is empty when matching against EDB facts). If all the subgoals are eventually dispatched, then the collection of all variable substitutions used in the process can provide an answer to the original query. By considering alternative matches to subgoals, we can generate additional answers to the query.

      For example, consider an EDB predicate cited that indicates that the person in the first argument has cited the person in the second argument. We also define an IDB predicate influenced that is the transitive closure of cited. (A more precise definition would consider the date of citation, but we do not do it here.)

      Suppose we have the query goal

      We can match this goal against the head of the first rule, substituting dm for P1 and X for P2. The new goal is

      Matching this goal against the cited-facts gives two query answers:

      The initial goal can also be matched against the second rule, with the same substitutions, yielding the goal list