Abstract Filters: Improving Bottom-up Execution of Logic Programs by Two-phase Abstract Interpretation

Byeong-Mo Chang Kwang-Moo Choe Korea Advanced Institute of Science and Technology Roberto Giacobazzi ^{∗} École Polytechnique

(Extended Abstract)

Abstract

Bottom-up evaluation of logic programs may be inefficient as it may generate many irrelevant facts to a given query. The filtering strategy prevents possible irrelevant facts from being processed in the bottom-up evaluation on system graphs. This paper defines the filtered bottom-up evaluation formally, and provides a new filter called abstract filter which is computed by two-phase abstract interpretation at compile time. The abstract filter is defined on a generic abstract domain. This framework is specialized on the depth k abstract domain of Sato and Tamaki. The abstract filter is shown to be at least as powerful as the static filter on the depth k abstract domain. Some performance results are provided. Keywords: abstract interpretation, bottom-up evaluation, filtering, logic programming.

1 Introduction

Because of a number of advantages, the bottom-up evaluation of logic programs has recently attracted much attention in logic programming and deductive database [8, 9, 10]. It guarantees logical completeness which strict top-down approaches sacrifice in favor of implementational efficiency as in Prolog. In particular, if the number of all possible facts is finite, the bottom-up evaluation terminates while strict top-down one like Prolog may not. In addition, the bottomup strategy is free from nonlogical features like backtracking. However, bottom-up query evaluation may be inefficient since it may generate many irrelevant facts to a given query. In order to overcome this drawback, a number of optimization strategies has been proposed, in particular for seminaive bottom-up evaluation [1, 2, 7, 8, 10]. For example, the program transformation strategy, like Magic Sets in [1], transforms original programs so that the transformed programs can compute call patterns (which are called magic sets in Magic Sets) and use them to reduce the generation of irrelevant facts during the bottom-up query evaluation. Another approach has been introduced to solve these problems: the filtering strategy. It prevents irrelevant facts from being generated at evaluation time by applying filters over the bottom-up evaluation on system graphs [7, 8]. A filter is a kind of selection attached on an arc of a system graph, which is able to restrict the data flow through the arc. The basic proposal is static filtering [7, 8]. It restricts data flow during evaluation by using static filters, which are computed at compile-time by propagating data-independent bindings (selections) in the query and rules. Static filters, however, have their own limit since they are always computed using only data-independent bindings. This drawback can be cured by dynamic filtering, which however incurs runtime overhead because dynamic filters are always computed during program evaluation [4, 7]. In this paper we introduce a new family of filters called abstract filters. They are obtained at compile time by abstract interpretation. The definition of abstract filter is presented for a generic abstract domain and provides a suitable generalization of the (static) filter notion. Because abstract filters are independent of the specific data abstraction, different abstract domains may provide different abstract filters at different layer of abstraction. However, because of the range of applications of abstract filters, we believe that type abstractions (e.g. depth k or type graphs) may provide more appropriate abstract filters. The precision of an abstract filter depends on the chosen abstract domain and on the way the analysis is performed. As a specialization, we compute abstract filters using a two-phase abstract interpretation. The two-phase abstract interpretation consists of a bottom-up phase followed by a top-down one, and it provides an approximation of success patterns of clauses which are relevant to a given query. We will specialize this framework by considering the depth k abstraction [11] as abstraction function. The abstract filter constructed from the two-phase analysis prevents facts not generated by the analysis (i.e. facts which are neither success patterns nor relevant to the query) from being processed in the bottom-up evaluation. From the theoretical point of view, the abstract filter is shown to be at least as powerful as the static filter on the depth k abstract domain. assumption. Both the two-phase abstract analyzer and the bottom-up evaluator have been implemented, providing some experimental results which further on compare the performances of the static and abstract filters. In particular we observed that: (1) the abstract filter does not incur runtime overhead except filter passing, while Magic Sets does, due to the computation of magic sets during evaluation, (2) due to the goal independence of the bottom-up abstract interpretation, the result of the bottom-up phase can be used for any query to the same program. This is a good property in program compilation, since many different queries are usually asked over the same program.

∗The work of R. Giacobazzi has been partly supported by the EEC Human Capital and Mobility individual grant: “Semantic Definitions, Abstract Interpretation and Constraint Reasoning”.

2 Logic programming

Let Π be a (finite) set of predicate symbols, Σ a set of function symbols, and V ar a denumerable set of variables. n-ary predicates or functions are denoted f/n. The set of all terms constructed from Σ and V ar is denoted T erm. An atom is a syntactic object of the form p(t_{1}, …, t_{n}) where p/n ∈ Π and t_{1}, …, t_{n} ∈ T erm. We denote Atoms the set of all atoms. We also associate a tuple ⟨t_{1}, ..., t_{n}⟩ with each atom p(t_{1}, ..., t_{n}). A clause has the form h ← b_{1}, …, b_{n} (n ≥ 0) where h is a head atom and b_{i}’s are body atoms. The set of clauses constructed from elements of Atoms is denoted Clause. If n = 0 then the clause is simply h and called an unit clause or fact . Otherwise it is called a rule . We consider atoms and facts as equivalent notions. The set of variables occurring in a syntactic object t (e.g. a term, atom, clause etc.) is denoted by var(t). Sequences of syntactic objects b are often denoted B̄. We abuse by treat sequences as sets. A rule is usually denoted by δ. A function pred(δ, i) is defined to be the i-th predicate symbol in the body of δ, and a function head(δ) is the predicate of the head of δ. In this case i is an index for δ. A query is a sequence of atoms, sometimes denoted ← G. Sometimes we abuse by calling query a clause of the form ans ← G where var(ans) = var(G). A logic program P is a finite set of clauses. A substitution is a mapping from V ar to T erm which acts as the identity almost everywhere. The set of idempotent substitutions is denoted by Sub. Following tradition, the application of a substitution θ to an object t will be written tθ rather than θ(t). We fix a partial function mgu which maps a pair of syntactic objects to an idempotent most general unifier of the objects if it exists. The relation ∼ is defined for any syntactic object as s ∼ t iff ∃ϑ, σ: sϑ = t ∧ tσ = s. Let B_{P} = Atoms/∼ where Atoms/_{∼} is the set of equivalence classes on Atoms with respect to ∼. The (bottom-up) semantics of a logic program P, characterizing computed answer substitutions is defined in [6] in terms of an immediate consequence operator T_{P} on the domain of interpretations ℘(B_{P}). In the following we omit equivalence classes in syntactic objects and for a syntactic object s and an interpretation I we denote by ⟨a_{1}, …, a_{n}⟩ < <_{s} I that a_{1}, …, a_{n} are representatives of elements of I renamed apart from s and from each other.

T_{P} (I) = \{ hϑ | \begin{matrix}c = h ← B̄ ∈ P, B̄′ < <_{c} I \\ ϑ = mgu(B̄, B̄′) \end{matrix} \} .

The semantics of a program P is lfp(T_{P}). It is known ([6]) that if G is a goal, ϑ is the substitution computed in a (SLD) refutation ([9]) of G in P iff there exists B̄ < <_{G} lfp(T_{P}) such that σ = mgu(G, B̄) and Gϑ ∼ Gσ.

3 Filtered bottom-up evaluation

3.1 Formalism A filter is usually a logical formula mapping tuples of terms into the truth values. It is assumed that a filter is defined for every body atom of every rule. The value of a filter function F on the i-th body atom of a rule δ, denoted by F (δ, i), is called the filter of that body atom. A filter F (δ, i) can also be denoted by F_{δ,i} for short. If (the tuple associated with) an atom b satisfies a filter F_{δ,i}, we write b ∈ F_{δ,i}. We formally define filtered bottom-up evaluations by modifying the T_{P} operator in [6].

Definition 1 Let P be a program and F be a filter. We define T_{P}^{F} : ℘(B_{P}) → ℘(B_{P}) such that

T_{P}^{F} (I) = \{ hϑ | \begin{matrix}c = h ← b_{1}, ..., b_{n} ∈ P \\ ⟨b′_{1}, ..., b′_{n}⟩ < <_{c} I, b′_{i} ∈ F_{C,i}(1 ≤ i ≤ n) \\ ϑ = mgu(⟨b_{1}, …, b_{n}⟩, ⟨b′_{1}, …, b′_{n}⟩) \end{matrix} \}

The filtered bottom-up evaluation computes the least fixpoint lfp(T_{P}^{F}) (the filtered fixpoint semantics), which is a subset of lfp(T_{P}). Indeed T_{P}^{F} instantiated with the always true filter corresponds to T_{P}. Notice that T_{P}^{F} is continuous.

Definition 2 Let P be a program and ans ← G be a query. For a filter F, lfp(T_{P}^{F}) is equivalent to lfp(T_{P}) with respect the query iff T_{{ans←G}}^{F}(lfp(T_{P}^{F})) = T_{{ans←G}}(lfp(T_{P})). In this case we say that lfp(T_{P}^{F}) is complete for P and G.

Equivalence means that the answers for the query are the same in both the fixpoint semantics.

3.2 Implementation on system graphs

The filtering on system graphs has been introduced as a tool for the filtered bottom-up evaluation [4, 7, 8]. It computes the least fixpoint lfp(T_{P}^{F}) in a seminaive manner. Let Arg V ar(δ, i) denote the argument variables of the i-th body atom of a rule δ. An argument variable is a variable ranging on T erm, which corresponds to an argument position of an atom. If an atom has an m-ary predicate p, its argument variables are P 1, …, P m, named after the predicate symbol. Let n_{δ} denote the number of body atoms in a rule δ.

Definition 3 A system graph for a program P is SG_{P} = (V_{p}, V_{r}, E_{p,r}, E_{r,p}, F) where V_{p} and V_{r} are the sets of predicates and rules in P respectively, E_{p,r} = {(p, δ)/i|p ∈ V_{p}, δ ∈ V_{r}, p = pred(δ, i), 1 ≤ i ≤ n_{δ}}, E_{r,p} = {(δ, p)|δ ∈ V_{r}, p ∈ V_{p}, p = head(δ)} and F is a filter function that associates a filter over Arg V ar(δ, i) with every arc (p, δ)/i ∈ E_{p,r}.

The slashed pair (p, δ)/i in E_{p,r} denotes the i-th input port (incoming arc) of a rule-node δ from the pred-node p, which is also an output port(outgoing arc) of the pred-node p. The value of a filter function F on a port (p, δ)/i, F ((p, δ)/i), is called the filter of that port and it represents a logical formula over Arg V ar(δ, i). A filter F ((p, δ)/i) is denoted by F_{δ,i} for short. We determine a filter function by computing filters for every input port of every rule-node. The filter of each port in E_{p,r} is used to restrict data flow through the port. The system graph with a filter function F for a program P is denoted by SG_{P}^{F}. The simplistic bottom-up evaluation evaluates a query in terms of bottom-up data flow on system graphs [4, 8]. In the following a pred-node is called a base pred-node if it does not have its input ports, and called a derived pred-node otherwise. Each base pred-node in P has its facts initially.

Algorithm the simplistic bottom-up evaluation on system graphs SG_{P}:

(1) initially each base pred-node in P sends its tuples to its output ports, repeat

(2) each rule-node stores new tuples from input ports into its local buffers associated with the ports, performs the unification and sends the newly generated facts via its output ports;

(3) each derived pred-node in P stores new tuples from its input ports, and sends them to its output ports.

until no new changes are produced on nodes in SG_{P}.

The algorithm can be easily modified so that the filter of each port in E_{p,r} restricts data flow through the port, by not passing facts or tuples if they do not satisfy the filter. The evaluation on SG_{P}^{F} computes lfp(T_{P}^{F}) in a seminaive manner. As an example, we briefly review the static filter computation in [8]. A level k subterm ([11]) is defined as follows: (1) For a given term t, t is a level 0 subterm of t. (2) If a level k subterm of t is f(t_{1}, …, t_{n}), then t_{i} is a level k + 1 subterm of t. The depth k abstract term of a term t is the term t′ which is obtained by substituting every level k subterm of t with a fresh variable. The k-signature of a term is defined in [8] which extends the depth k abstraction in [11]. The basic idea of the static filter computation is to simulate top-down execution on the system graph. It propagates bindings in the query backward on the system graph until no more new calling (binding) patterns are found, with every calling pattern being maintained in its k-signature form [8]. The abstraction by k-signature guarantees the termination of the algorithm.

Example 1 Consider the following program:

← p(X, f(f(b))).
δ_{1} : p(X, f(Y)) ← r(X, Z), p(Z, Y).
δ_{2} : p(X, Y) ← r(X, Y).

The selection P 2 = f(f(b)) in the query imposes a selection P 2 = f(b) on (p, δ_{1})/2 if pushed backward via the rule δ_{1}. The new selection P 2 = f(b) imposes a selection P 2 = b if pushed backward via δ_{1}. The selections P 2 = f(f(b)), P 2 = f(b) and P 2 = b can be pushed similarly via the rule δ_{2}. The static filters computed are SF_{δ_{1},2} = (P 2 = f(b) ∨ P 2 = b) and SF_{δ_{2},1} = (R2 = f(f(b)) ∨ R2 = f(b) ∨ R2 = b).

Theorem 1 Let SF be the static filter for a program P, and T_{P}^{SF} be the operator which is defined by replacing F with SF in Definition 1. lfp(T_{P}^{SF}) is equivalent to lfp(T_{P}) with respect to any query.

4 Abstract filters

Abstract interpretation can be used to define a general notion of abstract filter. An abstract interpretation of a program is an approximation of its standard semantics on an abstract (usually simpler) domain ([5]) so as to statically derive information about the runtime behavior of a program. The overall abstract interpretation methodology can be summarized as follows: (1) a concrete (collecting) semantics is selected which correctly characterizes the observable property of interest; (2) an abstract semantics is defined by providing approximated descriptions of semantic objects and operators. We assume that a concrete interpretation for a (logic) program P can be defined in terms of a monotone operator E_{P} : E → E on a concrete domain (E, ⊑). An abstract interpretation ((E, ⊑), E_{P} , (D, ⪯), D_{P} , α, γ) consists of a complete lattice (D, ⪯), a monotone operator D_{P} : D → D, a pair of monotone functions α : E → D and γ : D → E (abstraction and concretization) such that

(1) ((E, ⊑), α, (D, ⪯), γ) is a Galois insertion, i.e. for all d ∈ D, e ∈ E: d = α(γ(d)) and e ⊑ γ(α(e)), and

(2) E_{P} (γ(d)) ⊑ γ(D_{P} (d)) (correctness), specifying that D_{P} faithfully mimics E_{P}. ¿From the definition it follows that lfp(E_{P}) ⊑ γ(lfp(D_{P})) (see [5]).

We follow [3] by defining abstract interpretations as abstractions of concrete interpretations (i.e. subsets of B_{P}). Let P be a program and ((℘(B_{P}), ⊆), α, (H, ⊑), γ) be a Galois insertion. In this case, (H, ⊑) is a domain of abstract interpretations for P. In the following we abuse by calling abstract interpretation both such denotations and the well known static program analysis technique. Each abstract interpretation I^{A} represents the set of (concrete) atoms (i.e. a concrete interpretation): γ(I^{A}). Moreover, with each concrete interpretation I we can always associate an abstract interpretation α(I).

Definition 4 Let P be a program, δ be a rule and i be an index for δ. The abstract filter AF_{δ,i} is defined to be an abstract interpretation I^{A} for P, such that γ(I^{A}) contains only atoms with predicate pred(δ, i).

It is easy to see that static filters are abstract filters with ksignature abstraction. Let I^{A} be an abstract interpretation. We denote by I^{A}[p] the set of all abstract denotations in I^{A} representing the predicate p (i.e. the largest abstract interpretation J^{A} such that: J^{A} ⊑ I^{A}[p] and γ(J^{A}) contains only atoms with predicate p).

Definition 5 A (concrete) atom A is said to satisfy the abstract filter AF_{δ,i}, denoted by A ∈ AF_{δ,i}, iff A ∈ γ(AF_{δ,i}).

The notions of completeness and equivalence can be extended from filters to abstract filters in the obvious way. The operator T_{P}^{AF} and the system graph evaluation can be formally defined by replacing the filter F with an abstract filter AF in Definition 1. The precision of abstract filters depends on the abstract domains and program analyses. Let ((℘(B_{P}), ⊆), α, (H, ⊑), γ) and ((℘(B_{P}), ⊆), α′, (H′, ⊑′), γ′) be Galois insertions. We define an ordering relation among abstract filters such that given any two abstract filters AF_{1} and AF_{2} on H and H′ respectively: AF ⪯ AF′ iff for each rule δ and index i: γ(AF_{δ,i}) ⊆ γ′(AF′_{δ,i}). In this case we have that for any interpretation I: T_{P}^{AF} (I) ⊆ T_{P}^{AF′}(I). Thus, more precise is the analysis, and more filtering is performed at evaluation time. More precise AF can be obtained either by a more refined abstract interpretation technique or by a more precise (less abstract) abstract domain.

5 Two-phase abstract interpretation

In this section we will consider abstract filters on the simple depth k type abstraction (see [11]) and show that, in relation with static filters, the relatively more abstract domain of depth k abstractions can provide relevant filters once a more precise (two-phase) abstract interpretation process is considered.

5.1 Bottom-up phase

In this section we extend the bottom-up abstract interpretation framework in [3] in order to include clauses as well as atoms as semantic objects. Let ρ(t) be a function which maps a term t to its depth k abstract term. We define the abstract base B_{P}^{A} as Atoms^{A}/∼ where Atoms^{A} = {p(t̄^{A})|p ∈ Π, t̄^{A} ⊆ ρ(T erm)}. The abstraction function α_{a} : B_{P} → B_{P}^{A} is defined by α_{a}(p(t_{1}, …, t_{n})) = [p(ρ(t_{1}), …, ρ(t_{n}))]_{∼}. The abstraction function is lifted on interpretations by defining α_{a} : ℘(B_{P}) → ℘(B_{P}^{A}) such that α_{a}(I) = {α_{a}(a)|a ∈ I}. The corresponding concretization function γ_{a} : ℘(B_{P}^{A}) → ℘(B_{P}) is γ_{a}(I^{A}) = {a′ ∈ B_{P} |a^{A} ∈ I^{A}, α_{a}(a′) = a^{A}}, and provides a Galois insertion. An abstract substitution is a mapping from a given finite set of variables V ⊆ V ar into ρ(T erm) which acts as the identity almost everywhere. Likewise we define abstraction and concretization on substitutions: α_{S} and γ_{S}. The abstract operator T_{P}^{A} on ℘(B_{P}^{A}) can now be defined for depth k approximations of T_{P}:

T_{P}^{A}(I^{A}) = \{ α_{a}(hϑ^{A}) | \begin{matrix}c = h ← B̄ ∈ P, B̄^{A} < <_{c} I^{A} \\ ϑ^{A} = mgu^{A}(B̄, B̄^{A}) \end{matrix} \}

where mgu^{A} = α_{S}∘mgu. It is shown in [3] that T_{P}^{A} is correct i.e. γ_{a}(lfp(T_{P}^{A})) ⊇ lfp(T_{P}). The bottom-up phase is defined by extending the framework in [3] to deal with clauses as semantic objects. Let C be the set of (equivalence classes of) clauses up to renaming: i.e. Clause/_{∼}. The set of abstract clauses is defined by C^{A} = {α_{c}(C)|C ∈ C} where for any clause h ← b_{1}, …, b_{n}: α_{c}(h ← b_{1}, …, b_{n}) is [α_{a}(h) ← α_{a}(b_{1}), …, α_{a}(b_{n})]_{∼} The extended bottom-up abstract interpretation is:

((℘(B_{P}) × ℘(C), ⊆), U_{P} , (℘(B_{P}^{A}) × ℘(C^{A}), ⊆), U_{P}^{A}, α, γ).

where we extend T_{P} by introducing a concrete operator U_{P} : ℘(B_{P}) × ℘(C) → ℘(B_{P}) × ℘(C) such that U_{P} (I, J) = (T_{P} (I), J′) where

J′ = \{ cϑ | \begin{matrix}c = h ← B̄ ∈ P, B̄′ < <_{c} I \\ ϑ = mgu(B̄, B̄′) \end{matrix} \}

The concrete collecting semantics of a logic program P is determined by lfp(U_{P}). Its first part is denoted by lfp_{a}(U_{P}) and its second part by lfp_{c}(U_{P}). The abstraction function α : ℘(B_{P}) × ℘(C) → ℘(B_{P}^{A}) × ℘(C^{A}) is defined by α(I, J) = (α_{a}(I), α_{c}(J)). The concretization function γ : ℘(B_{P}^{A}) × ℘(C^{A}) → ℘(B_{P}) × ℘(C) is γ(I^{A}, J^{A}) = (γ_{a}(I^{A}), γ_{c}(J^{A})) where γ_{c}(J^{A}) = {c|c^{A} ∈ J^{A}, α_{c}(c) = c^{A}}. They form a Galois insertion. The abstract operator U_{P}^{A} : ℘(B_{P}^{A})×℘(C^{A}) → ℘(B_{P}^{A})×℘(C^{A}) is defined by extending T_{P}^{A} in a similar way: U_{P}^{A}(I^{A}, J^{A}) = (T_{P}^{A}(I^{A}), J^{A′}) where

J^{A′} = \{ α_{c}(cϑ^{A}) | \begin{matrix}c = h ← B̄ ∈ P, B̄^{A} < <_{c} I^{A}, \\ ϑ^{A} = mgu^{A}(B̄, B̄^{A}) \end{matrix} \}

The abstract semantics is defined as the least fixed point lfp(U_{P}^{A}). The first part of lfp(U_{P}^{A}) is denoted by lfp_{a}(U_{P}^{A}) which is the same as lfp(T_{P}^{A}), while the second part is lfp_{c}(U_{P}^{A}) which contains all abstract clauses whose body goals are in lfp(T_{P}^{A}). lfp_{c}(U_{P}^{A}) provides the approximated success patterns of each (program) clause. Because the abstract domain is finite, lfp(U_{P}^{A}) terminates. Moreover, the bottom-up phase is correct, i.e. γ(lfp(U_{P}^{A})) ⊇ lfp(U_{P}).

5.2 Top-down phase The bottom-up phase computes approximated success patterns without regard to the query. Therefore, many of them are not relevant to the given query. The following top-down analysis is based on the result of the bottom-up phase and it is designed to collect a subset of lfp_{c}(U_{P}^{A}) which consists of abstract success patterns of program clauses relevant to the query. An abstract clause h^{A} ← B̄^{A} ∈ lfp(U_{P}^{A}) is relevant to a query Q iff h^{A} is unifiable with some atoms in Q, or h^{A} is unifiable with some body atom of some abstract clause relevant to Q. The top-down phase is an abstract interpretation:

((℘(lfp_{c}(U_{P})), ⊆), D_{P} , (℘(lfp_{c}(U_{P}^{A})), ⊆), D_{P}^{A}, α_{c}, γ_{c})

where the concrete operator D_{P} : ℘(lfp_{c}(U_{P})) → ℘(lfp_{c}(U_{P})) is defined for a program P and query Q and J ∈ ℘(lfp_{c}(U_{P})):

D_{P} (J) = \{ c | \begin{matrix}c = h ← B̄ ∈ lfp_{c}(U_{P}) \\ h′ ∈ body atoms(\{Q\} ∪ J), ∃mgu(h, h′) \end{matrix} \}

Here body atoms(J) is the set of body atoms of clauses in J. The concrete collecting semantics for the top-down phase is determined by lfp(D_{P}). Analogously, the abstract operator D_{P}^{A} : ℘(lfp_{c}(U_{P}^{A})) → ℘(lfp_{c}(U_{P}^{A})) is defined for the topdown phase:

D_{P}^{A}(J^{A}) = \{ c^{A} | \begin{matrix}c^{A} = h^{A} ← B̄^{A} ∈ lfp_{c}(U_{P}^{A}) \\ h^{A′} ∈ body atoms(\{Q\} ∪ J^{A}) \\ ∃mgu^{A}(h^{A}, h^{A′}) \end{matrix} \}

It is straightforward to prove that both D_{P} and D_{P}^{A} are monotonic functions and D_{P}^{A} is correct (i.e. γ_{c}(lfp(D_{P}^{A})) ⊇ lfp(D_{P})). Moreover ℘(B_{P}^{A}) is a finite lattice, thus the least fixpoint computation lfp(D_{P}^{A}) terminates. It contains all the abstract clauses in lfp(U_{P}^{A}) which are relevant to the query.

Example 2 Let P be the following logic program

δ_{1} : path(X, [X|P]) ← arc(X, N), path(N, P).
δ_{2} : path(X, [X]) ← final(X).
final(f).
arc(a, b). arc(a, c). arc(c, b). arc(c, d). arc(d, f).
arc(e, c). arc(e, f). arc(g, e).

Consider a query of the form p(a, Z). The result of the twophase abstract interpretation (i.e. lfp(D_{P}^{A})) is:

\{ \begin{matrix}path(a, [a| ]) ← arc(a, c), path(c, [c| ])., \\ path(c, [c| ]) ← arc(c, d), path(d, [d| ])., \\ path(d, [f| ]) ← arc(d, f), path(f, [f])., \\ path(f, [f]) ← final(f)., \\ final(f)., arc(a, c)., arc(c, d)., arc(d, f). \end{matrix} \}

6 Depth k abstract filters

The bottom-up phase provides the approximated success patterns for every clause. The atoms that do not participate in the approximated success patterns will not be considered in the query evaluation because they will not participate in some real success patterns. In addition, the top-down phase finds only the approximated success patterns relevant to a given query. The atoms that do not participate in the approximated success patterns relevant to the query will not be considered in the real query evaluation, as they are not relevant to a given query even though it can participate in some real success patterns. By correctness the abstract interpretation lfp(D_{P}^{A}) constitutes a suitable base for the definition of a corresponding complete abstract filter. In the following, the set of all (abstract) instances of a rule δ in lfp(D_{P}^{A}) is denoted by lfp(D_{P}^{A})[δ], while the set of all (abstract) instances of the i-th body atom in lfp(D_{P}^{A})[δ] is denoted by lfp(D_{P}^{A})[δ][i]. Notice that if the i-th body atom of δ is A, then lfp(D_{P}^{A})[δ][i] contains (abstract) instances of A.

Definition 6 Let P be a program, δ be a rule and i be an index for δ. The abstract filter AF_{δ,i} is defined by AF_{δ,i} = lfp(D_{P}^{A})[δ][i].

In case of input ports for the given query Q, we can define abstract filters by using J_{query}^{A}(Q), where

J_{query}^{A}(Q) = \{ α_{c}(Qϑ^{A}) | \begin{matrix}B̄^{A} < <_{Q} lfp(T_{P}^{A}), \\ ϑ^{A} = mgu^{A}(Q, B̄^{A}) \end{matrix} \}

Example 3 The abstract filters with depth 2 for the program in Example 2 are computed using lfp(D_{P}^{A}): AF_{δ_{1},1} = {arc(a, c), arc(c, d), arc(d, f)} and AF_{δ_{1},2} = {path(f, [f]), path(d, [d| ]), path(c, [c| ])}. In the system graph evaluation with the abstract filters, the rule δ_{1} generates 3 facts, namely: path(d, [d, f]), path(c, [c, d, f]) and path(a, [a, c, d, f]). On the other hand, the static filters can not give any restrictions to the input ports of δ_{1}, so the evaluation with them degenerates to the naive evaluation, in which case the rule δ_{1} generates 7 facts.

In general, the difference between abstract filters and static filters is due to the fact that the bottom-up phase provides an approximation of all success patterns by considering data-dependent bindings in their (depth k) abstracted form, while the static filter computation does not consider any data-dependent binding. This is a typical example showing the power of the bottom-up analysis and the difference between the static filter and abstract filter. Let T_{P}^{AF} be the operator defined as in Definition 1. The completeness of the abstract filter with respect to a given query is a consequence of the following theorem.

Theorem 2 Let P be a program and Q be a query. Let AF be computed as above for P and Q. Then, lfp(T_{P}^{AF}) is equivalent to lfp(T_{P}) with respect to the query Q.

Strictly speaking, the abstract filter can not be compared with the static filter since static filters are computed by the depth k signature, which extends the depth k abstraction. We can associate with the notion of static filter an abstract filter based on depth k signatures instead of the more abstract depth k abstraction. A simpler way to show that abstract filters are at least as powerful as the static filters is under the assumptions that static filters and abstract filters are both computed using the same (more simple) depth k abstraction. We denote a static filter on depth k abstraction as SF^{k}.

Theorem 3 lfp(T_{P}^{AF}) ⊆ lfp(T_{P}^{SF^{k}}) for any program P.

7 Experiments

The two-phase abstract interpreter has been implemented based on the simple depth-k abstract domain on SPARC station-2. It provides an abstract filter for each input port of every rule-node. The bottom-up evaluator reads (abstract or static) filters and finds solutions by the system graph evaluation with the filters. The abstract filtering has been compared with the Kifer’s static filtering [8]. We use two measures: the number of generated tuples κ and the number of filtered tuples during evaluation ρ, which is a measure of the total traffic through ports. The performance of the evaluation is largely dominated by them. The following performance results for the abstraction of depth 2, 3 and 4 show effects of the depth k abstraction as k becomes higher. In the following table, in the cases of rev and ackerman programs, we represent the numbers until the first solution is found. The abstract filtering generates only about 30 percentage of the tuples generated by the static filtering for the program parser in [12], which also optimizes the naive system graph evaluation considerably. For the program rev, both the static filtering and abstract filtering make almost no improvement. It is, however, a matter of course since every atom generated during the evaluation is necessary for answering a given query. The program path/sd is a path program with a single destination node (like the program in Example 2) which contains a graph G = (V, E) such that |V | = 33 and |E| = 44. The abstract filtering optimizes the bottom-up evaluation considerably for the program, while the static filtering falls into the naive evaluation. For the program path/md with multiple destinations in [12], the abstract filtering generates about half of the tuples generated by the static filtering, which also optimizes the naive system graph evaluation considerably. We can see through the table that the abstract filtering is useful in optimizing nondeterministic program rather than deterministic programs like the program rev. Due to the page limit, we cannot include the tables for the depth 2 and 4. However, notice that the depth 4 abstraction make almost no further improvement (only for parser, the abstract filtering is slightly improved to κ = 26 and ρ = 37) , while for the depth 2 we get similar results, except that (1) for parser, the static filtering is κ = 91 and ρ = 69 and the abstract filtering is κ = 39

depth 3  seminaive  static f.  abstract f.
parser  κ 1027 (11.2) 91 (1.00) 39 (0.42)
ρ 1058 (15.33) 69 (1.00) 38 (0.55)
rev* κ 42 (1.00) 42 (1.00) 42 (1.00)
ρ 84 (1.31)  64 (1.00) 64 (1.00)
path/sd κ 41 (1.00) 41 (1.00) 21 (0.51)
ρ 125 (1.00)  125 (1.00) 40 (0.32)
path/md κ 369 (9.20)  40 (1.00) 20 (0.50)
ρ 824 (9.69)  85 (1.00) 38 (0.44)
ackerman* κ 28 (1.12)  25 (1.00) 25 (1.00)
ρ 116 (2.52)  46 (1.00) 44 (0.95)

and ρ = 38; (2) for ackerman, the static filtering is κ = 25 and ρ = 46 and the abstract filtering is κ = 25 and ρ = 44. Therefore, small depth of abstraction may be very useful in optimization.

8 Other related works

There have been two main approaches, static filtering and dynamic filtering, in filtering the bottom-up evaluation on system graphs. The basic idea of the static filter computation is to simulate top-down execution on system graphs. It may be be considered as a top-down phase without a bottom-up phase. Dynamic filters are computed at run-time by sideways information propagation and backward information propagation which propagate actual data generated during the evaluation [4, 7]. Roughly speaking, the abstract filters approximate dynamic filters. The bottom-up phase can be compared to the sideways information propagation while the top-down phase corresponds to the backward information propagation. However, since an approximation of all success patterns are known by the bottom-up phase before the top-down phase, it is possible that the abstract filter gives better optimization effects for some programs than the dynamic filtering and the magic set based methods. See Example 4 for details. Magic Sets in [1] transforms original programs so that they can compute call patterns of atoms (which is called magic sets) and can reduce the generation of irrelevant facts using them. The transformed program computes the magic sets by simulating the sideways information passing of a top-down evaluation during the evaluation, and reduce the amount of potentially relevant data using them. The behavior of the transformed rule by Magic Sets is very similar to that of the dynamic filtering, if the same sideway passing graph is assumed. Magic Sets and the dynamic filtering, however, incur some runtime overhead for the computation of magic predicates and dynamic filters, respectively, while the static filter and abstract filter does not except filter passing. We will not consider the dynamic filtering in the following comparison, because it shows a very similar behavior to Magic Sets based methods. We have already presented a typical example to show the difference between the static filter and abstract filter in Example 3. Even though Magic Sets computes calling patterns in the course of the query evaluation, it may create some facts which can not participate in any success pattern of a clause. This may happen also in our approach. The abstract filter, however, can prevent some programs from generating unnecessary facts which are generated by Magic Sets.

Example 4 Consider the following program P and its transformed program by Magic Sets.

← p(f(a), X).
δ_{1} : p(X, f(Y)) ← r(X, Z), p(Z, Y).
δ_{2} : r(X, f(Y)) ← r(X, Y).

r(f(a), a). p(a, b).
δ′_{1} : p(X, f(Y)) ← magic p(X), r(X, Z), p(Z, Y).
δ′_{2} : r(X, f(Y)) ← magic r(X), r(X, Y).
r(f(a), a). p(a, b).
magic r(X) ← magic p(X). (from δ_{1})
magic p(Z) ← magic p(X), r(X, Z). (from δ_{1})
magic r(X) ← magic r(X). (from δ_{2})
magic p(f(a)). (from the query)

The rule δ′_{2} generates infinite facts in the query evaluation, and magic p(Z) and magic r(X) does infinite facts such as magic p(f(a)), magic p(f(f(a))), and so on. The static filtering degenerates to the naive evaluation and generates infinite facts by the rule δ_{2}. On the other hand, when the depth of abstraction is 2, the abstract filters are as follows:

AF_{δ_{1},1} = {r(f(a), a), r(f(a), f(a))}

AF_{δ_{1},2} = {p(a, b), p(f(a), b), p(f(a), f(b)), p(f(a), f(f( )))} AF_{δ_{2},1} = {r(f(a), a), r(f(a), f(a))}

The evaluation with the abstract filter generates only r(f(a), a) and r(f(a), f(a)) by δ_{2}.

Magic Set could be more effective in many cases, but it should be noted that even though the abstract filter is computed at compile time, the optimization can be more effective for some programs than the magic set based methods.

9 Discussion

Consider the rules in Example 2 and suppose a graph G = (V, E) is represented by facts in the program. In the abstract interpretation, when the depth of abstraction is k, the number of instances of path(X, [X|P) in lfp_{a}(U_{P}^{A}) is bounded by |V |^{k−1} and that of the rule δ_{1} in lfp_{c}(U_{P}^{A}) by |E| × |V |^{k−2}, whether the graph is acyclic or not. In case the depth of abstraction is 2, the numbers are linear in |V | and |E|, respectively. On the other hand, in the real execution, when the graph is acyclic, the number of instances of path(X, [X|P]) in lfp(T_{P}) is bounded by (|V |)!, and may be infinite when the graph is cyclic. In addition, it should be noted that, as shown in the experiment, small depth of abstraction is very useful in filtering nondeterministic programs. Moreover, the proposed approach has merit in the sense that, due to the goal independence of the bottom-up abstract interpretation, the result of the bottom-up phase can be used for any query to the same program. Since many different queries are usually asked over the same program, it is a good property.

Address:

• Byeong-Mo Chang and Kwang-Moo Choe Department of Computer Science, KAIST 373-1, Kusung-dong, Yusung-ku, Taejon 305-701,

     South Korea, {chang,choe}@plhae.kaist.ac.kr;

• Roberto Giacobazzi LIX, École Polytechnique, 91128 Palaiseau cedex,

     France, giaco@lix.polytechnique.fr

References

[1] Bancilhon, F., Maier, D., Sagiv, Y. and Ullman, J.D , Magic sets and other strange ways to implement logic programs, Proc. ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, 1986, pp. 1–15.

[2] Bancilhon, F. and Ramakrishnan, R., An amateur’s introduction to recursive query processing strategies, Proc. SIGMOD Int. Conf. on Management of Data, 1986, pp. 16–52.

[3] Barbuti, R., Giacobazzi R., and Levi, G. A general framework for semantics-based bottom-up abstract interpretation of logic programs, ACM Transactions on Programming Languages and Systems, 15:133–181 (1993).

[4] Chang, B.-M., Choe, K.-M., and Han., T. Optimized bottom-up evaluation of function-free logic programs with dynamic filtering: an incremental approach. Technical Report, CS-TR-92-66, Dept. of Computer Science, KAIST, Feb. 1992.

[5] Cousot, P., and Cousot., R. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixed points, Proc. of Fourth ACM Symp. Principles of Programming Languages, 1977, pp. 238-252.

[6] Falaschi, M., Levi, G., Palamidessi, C. and Martelli, M., Declarative modeling of the operational behavior of logic languages, Theoretical Computer Science, 69:289– 318 (1989).

[7] Kifer, M., and Lozinskii., E. L., A framework for an efficient implementation of deductive databases. In Proc. of the 6-th Advanced Database Symposium, 1986.

[8] Kifer, M., and Lozinskii., E. L., SYGRAF: Implementing logic programs in a database style. IEEE Trans. on Soft. Eng., 1988, pp. 922–935.

[9] Lloyd, J.W., Foundation of Logic Programming, Springer-Verlag, 1984.

[10] Ramakrishnan, R., Magic Templates: A spellbinding approach to logic programs, Proc. of the 1988 International Conference and Symposium on Logic Programming (Seattle), 1988, pp.140–159.

[11] Sato, T., and Tamaki, H., Enumeration of success patterns in logic programs, Theoretical Computer Science, 34:227–240 (1984).

[12] Sterling, L., and Shapiro, E., The art of Prolog. The MIT Press, 1986.