Chain-Split Evaluation in Deductive Databases.
AbstractMany popularly studied recursions in deductive databases can be compiled into one or a set of highly regular chain generating paths, each of which consists of one or a set of connected predicates. Previous studies on chain-based query evaluation in deductive databases take a chain generating path as an inseparable unit in the evaluation. However, some recursions, especially many functional recursions whose compiled chain consists of infinitely evaluable function(s), should be evaluated by chain-split evaluation, which splits a chain generating path into two portions in the evaluation: an immediately evaluable portion and a delayed-evaluation portion. In this paper, the necessity of chain-split evaluation is examined from the points of view of both efficiency and finite evaluation, and three chain-split evaluation techniques: magic sets, buffered evaluation, and partial evaluation are developed. Our study shows that chain-split evaluation is a primitive recursive query evaluation technique for different kinds of recursions, and it can be implemented efficiently in deductive databases by extensions to the existing recursive query evaluation methods.
Introduction
regular chain forms [8, 9, 21]. Interesting recursive query evaluation techniques [2], such as transitive closure
algorithms [10], magic sets and counting [1], can be applied to the efficient evaluation of compiled chains in
deductive databases. However, it is interesting to observe that some recursions, especially many recursions
containing function symbols, may often be evaluated appropriately by a different evaluation technique: chain-
split evaluation.
Like many researchers [2, 21], we assume that a deductive database consists of three parts: (i) an extensional
database (EDB) (a set of data relations), (ii) an intensional database (IDB) (a set of Horn-clause rules), and (iii)
a set of integrity constraints (ICs).
Definition 1.1 A predicate s is said to imply a predicate r (s ) r) if there is a Horn clause in IDB with
predicate r as the head and s in the body, or there is a predicate t such that s ) t and t ) r (transitivity). A
predicate r is recursive if r ) r. If r ) s and s and s are mutually recursive and are at the same
deduction level. Otherwise, if r ) s but not s r is at a lower deduction level than s.
Definition 1.2 A rule is linearly recursive if its body contains exactly one recursive predicate, and that predicate
is defined at the same deduction level as that of the head predicate. A rule is nested linearly recursive
if its body contains more than one recursive predicate but there is only one defined at the same deduction level as
that of the head predicate. A rule is nonlinearly recursive if it is recursive but it does not belong to the above
two categories.
Definition 1.3 A recursion is (single) linear if all of its recursive predicates are at the same deduction level
and every recursive predicate is defined by one linearly recursive rule and possibly some nonrecursive (exit) rules.
A recursion is multiple linear if all of its recursive predicates are at the same deduction level and every recursive
This work was supported in part by the Natural Sciences and Engineering Research Council of Canada under the grant OPG-
3723 and a research grant from the Centre for Systems Science of Simon Fraser University. A preliminary version of the paper
appeared in the Proceedings of the 8th International Conference on Data Engineering, Tempe, AZ, February 1992.
y The author is with the School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6
predicate is defined by one or more linearly recursive rules (but at least one is defined by multiple linearly recursive
rules) and possibly some nonrecursive rules. A recursion is nested linear if every recursive predicate in the
recursion is defined by one linearly or nested linearly recursive rule (but at least one is defined by a nested linearly
recursive rule) and possibly some nonrecursive rules. A recursion is nonlinear if it contains some nonlinearly
recursive rule(s). A recursion is function-free if it does not contain function symbols; otherwise, it is function-
bearing, or functional.
Example 1.1 The rule set f(1.1), (1.2)g defines a popular function-free linear recursion, sg, which indicates that
and Y are same generation relatives if they are siblings or their parents are same generation relatives. The
notations adopted here are similar to Datalog [21].
The recursion can be compiled into a highly regular compiled chain form [9] as shown in (1.3). 2
(parent i (X
where [ denotes disjunction, and parent i (X
parent i (X
ae
true
parent
Definition 1.4 A chain of length k (k ? 1) is a sequence of k predicates with the following properties: (1) all
predicates have the same name, say p, and the l-th p of the chain is denoted as p (l) , (2) there is at least one
identical variable in every two consecutive predicates, and if i is the variable position in the first predicate, j the
variable position in the second, and the variables at the two positions are identical, then the i-th variable of p (l)
is identical to the j-th variable of p (l+1) for every l where 1 - l - k \Gamma 1. Each predicate p l is called a chain
predicate or a chain generating path if it consists of a sequence of connected predicates (i.e., predicates
which contain shared variables). A unit-length chain is trivially a chain generating path, and a 0-length chain is
defined as a tautology.
linear recursion is an n-chain recursion if for any positive integer K, there exists a k-th
expansion of the recursion consisting of one chain (when synchronous (of the same length) chains
(when each with the length greater than K, and possibly some other predicates which do not form a
nontrivial chain. It is a single-chain recursion when or a multi-chain recursion otherwise. A
recursion is bounded if it is equivalent to a set of nonrecursive rules.
A compiled n-chain recursion can be rewritten into the form of a normalized linear recursion [9], which
consists of a set of exit rules and one normalized recursive rule in the form of (1.4), where X i and Y i (for
are variable vectors, and each c i (for 1 - i - n) is a chain predicate. Notice that a chain-predicate c i for some i
may be null in the sense that there is no c i predicate and Y is an exit variable if Y i
otherwise, it is a chain variable for chain predicate c i .
The rule set f(1.1), (1.2)g is in the normalized form. Recursive rules with complex variable connections can
be normalized by a compilation process [9]. Normalization greatly facilitates systematic analysis of recursions on
their binding propagation and other regularities.
Previous studies [8, 9] show that a linear recursion can be compiled into a bounded recursion or an n-chain
recursion, and many other kinds of recursions can also be compiled into chain forms. A compiled chain form
can be viewed alternatively as one or a set of normalized recursions. This study is focused on the chain-split
evaluation of compiled or normalized recursions.
1.1 Chain-split for efficient evaluation
Usually, a single-chain recursion is evaluated efficiently by a transitive closure algorithm [10], and a multi-chain
recursion by magic sets or counting [1, 2]. One may have wondered whether queries on multi-chain recursions can
be evaluated efficiently by merging multiple chain generating paths into one and then applying transitive closure
algorithms [11]. However, since such multiple paths do not share variables, the merge of them implies iterative
processing on the cross-product(s) of several relations, each corresponding to a path. It is terribly inefficient to
perform iterative evaluation on the cross-product of two or more database relations [14].
In contrast to merging multiple chains, one may split a chain into multiple chains in the evaluation. Such
a split implies that an n-chain recursion will be evaluated by a more sophisticated (n
evaluation technique. Can chain-split improve the performance of query evaluation? We examine an example.
Example 1.2 Suppose the recursion scsg (same-country same-generation relatives) is defined by the rule set
f(1.5), (1.6), (1.7)g. The definition is similar to sg [2] except that the parents of each pair of scsg must be born
in the same country.
same
birth
merged parents(X; Y;
(merged parents i (X
Since same country connects two parent-predicates in (1.5), the three predicates can be merged into one,
merged parents, as shown in (1.8), and the compilation derives a single-chain as shown in (1.9). Because the
same country predicate provides very weak restriction, the relation merged parents is not much smaller than the
cross-product of two parent relations. Obviously, it would be efficient to split merged parents into two subchains
in the evaluation of query (1.10).
The magic sets method encounters the same problem on this recursion. Since same country links two parent-
predicates in the body of the recursive rule, the binding propagation merges all the nonrecursive predicates
into one [21], and the derivation of magic sets requires iterative computation on the cross-product-like relation,
merged parents. This can be easily seen from the adorned rules (1.11) and (1.12) [2]. 2
parent bf (X; parent fb (Y; Y 1 ); scsg bb (X
parent bf (X; parent bb (Y; Y 1 ); scsg bb (X
1.2 Chain-split for finite evaluation
For recursions containing functions or evaluable predicates, chain-split evaluation may play another important
role: transforming an infinitely evaluable program into a finitely evaluable one.
To facilitate the analysis of functional recursions, a function-predicate transformation is performed which
maps a function together with its functional variable to a predicate (called functional predicate), where the
functional variable is the variable which unifies the returned value(s) of the function. That is, each function of
arity n is transformed to a predicate of with the last argument representing the functional variable.
For example, transformed to f(X similar transformation has also been
discussed by other researchers [12, 15, 17].
Since the transformation maps a functional logical rule to a function-free one, the analysis of a functional
recursion can be performed in the framework of a function-free one. Notice that the transformation converts
constructors to predicates. Since constructors mainly serve as constraints in the unification process, and the
transformation merely delays such constraint solving (in unification), the transformation is theoretically sound.
However, a transformed functional predicate usually represents a potentially infinite relation constructible by the
corresponding term/list construction function, such as cons, etc., or computable by the corresponding computational
function, such as sum, etc. Such a relation cannot be represented by a finite EDB relation. Thus the
evaluation of a functional predicate still relies on its corresponding function definition.
To facilitate the compilation and analysis of logic programs, rules in different forms should be rectified [21].
The rules for a predicate p are rectified if all the functions in the rules are mapped to the corresponding functional
predicates by the function-predicate transformation, and all the heads of the rules are identical and of the form
Example 1.3 A functional linear recursion, append, is defined by the rule set (1.13) and (1.14), where [XjL 1
denotes a list construction function, or a corresponding functional predicate, cons(X; L 1 ; L), which represents
that a resulting list L is formed by taking X as the head and L 1 as the remaining of the resulting list.
The rule set can be rectified into f(1.15), (1.16)g and compiled into (1.17) [9], where cons is the functional
predicate for the list construction function "[]". Notice that the rectified rule set is also the normalized rule set
for this recursion [9].
append(U;
append(U;
append(U;
cons
where
cons
ae
true
cons
Since two cons predicates are connected in the body of (1.16), they can
be merged into one, merged cons, as shown in (1.18).
merged
When both U and W are instantiated in a query, such as "? \Gamma append([a; b]; V; [a; b; c])", the iterative evaluation
on the merged cons proceeds successfully. However, if one of U and W is not instantiated, the evaluation
on the merged cons cannot proceed since it will encounter infinitely evaluable predicates. Take query "? \Gamma
append([a; b]; [c]; W )" as an example. In the evaluation of the first chain generating path
the first cons, "cons(X finitely evaluable with the instantiation, It derives "X
a". Unfortunately, the second cons, "cons(X 1 )", is not finitely evaluable with the only instantiation
However, if the chain predicate merged cons is split into two sub-chains
)", the first sub-chain can be evaluated first, the result can be passed via the body of the exit
rule (1.15) to instantiate the second argument of the second sub-chain, and so on. Thus, the recursion is finitely
evaluable by chain-split evaluation. 2
Since chain-split evaluation may lead to efficient and/or finite query evaluation, it is worthwhile to study the
chain-split evaluation techniques. The remaining of the paper is organized as follows. The conditions when a
query requires chain-split evaluation are examined in Section 2. The techniques for chain-split evaluation are
studied in Section 3. An extension to the chain-split evaluation techniques for complex classes of recursions is
examined in Section 4. Our discussion is summarized in Section 5.
When Chain-Split Evaluation Should Be Applied?
Section 1 shows that chain-split may sometimes lead to efficient and/or finite evaluation. It is interesting to
examine at what conditions the chain-split evaluation should be applied. Our discussion is based on the analysis
of two different kinds of chain split: efficiency-based chain-split and finiteness-based chain-split.
2.1 Efficiency-based chain-split
When a chain generating path contains neither functions nor evaluable predicates, chain-split evaluation should
be performed if the split may lead to more efficient query evaluation plans than evaluating all the components
of a chain together (i.e., chain-following). In general, such a decision should be made based on the quantitative
analysis of competitive query evaluation plans (such as chain-following vs. chain-split) based upon the size of
potential intermediate relations, the available accessing paths, cost estimation functions and database statistics
[13, 18].
The following quantitative measurements are introduced in our discussion.
Definition 2.1 The propagation ratio, ff X!W , in relation P defined as the ratio of the number
of distinct values in the attribute W (denoted as nW ) over that in the attribute X (denoted as nX ) in data relation
. That is,
The join expansion ratio, fi XY , for a join expression is the join attribute
(the variable vector shared by both predicates p and q), is the potential number of distinct hX; Y i pairs which can
be generated from each (distinct) W in the join.
In general, we have
The formula (2.2) is derived based on the following reasoning: One distinct W value corresponds on average
to ff W!X distinct X's in relation P and ff W!Y distinct Y 's in relation Q, and W is the join attribute of relations
P and Q. The join of the two relations pairs all the distinct X's and Y 's according to the definition of join.
Thus, the potential number of distinct hX; Y i pairs which can be generated from each W in the join should be
ff W!X \Theta ff W!Y . Notice that this does not imply that the number of tuples of the relation -XY (P 1 Q) will be
nW \Theta fi XY because different W 's may share the same hX; Y i pairs. Nevertheless, fi XY is a good indicator of the
approximate size of the join relation.
Example 2.1 The predicate same country(X; Y ) is defined in Example 1.2 as below,
same
Suppose the corresponding data relation for birth country(X; W ) is B(X;W ). Let nX be 100,000 and nW
be 50. The propagation ratio, ff 2,000. The join expansion ratio, fi
ff W!X \Thetaff This indicates that the join of two predicates "birth country(X; W )"
and "birth country(Y; W )" may expect to generate about 4 million tuples for each distinct W . One cannot expect
that such weak binding propagation may lead to efficient processing. 2
In general, suppose that in the compiled form of an n-chain recursion (2.3), one chain generating path is in
the form of "p(X two predicates p and q are connected via a set of predicates,
and each predicate has a pair of variables, such as X i\Gamma1 and X i , linking to the corresponding variables of the
consecutive chain generating paths in the chain.
As a notational convention, P represents the relation for the predicate p, and jP j the size of a relation P
measured by the number of tuples in the relation, etc. We examine when and how the chain generating path
should be split in the evaluation.
For the efficiency-based chain-split, we have the following heuristic.
Heuristic (efficiency-based chain-split). The following evaluation strategy should be adopted in the evaluation
of a chain generating path, "p(X in the compiled form (2.3).
should be performed if
1. the chain is being evaluated after the evaluation of exit portion (the body of the exit rule);
2. instantiations of X 0 and Y 0 are both highly selective; or
3. fi X0Y0 - 1.
ffl Case 2: Otherwise, chain-split evaluation should be performed if X 0 or Y 0 is highly selective, and fi X0Y0 AE 1.
ffl Case 3: Otherwise, perform a detailed cost analysis to determine whether the chain-split benefits the
evaluation.
Rationale. Chain-split evaluation splits the chain into two (connected) subchains, with one evaluated first and the
other buffered until the evaluation of the exit portion passes more bindings to the buffered chain. Obviously, no
chain-split should be performed if the chain is a down-chain (i.e., the chain is being evaluated after the evaluation
of the exit portion) [2].
Suppose the evaluation starts at a chain with the path "(p; instantiated and proceeds towards
the exit portion e and then the other chains in the compiled recursion. For efficient evaluation, it is important to
examine the size of the chain relation, "P (X the size of (i.e., the number
of tuples in) the chain relation cannot be beneficial; similarly when
both X 0 and Y 0 are highly selective. If the evaluation of the entire chain generating path generates a very large
relation (when only one of X 0 and Y 0 is highly selective and fi X0Y0 AE 1: Case 2), such as the merged parents
relation in Example 1.2, chain-split evaluation should be performed because the evaluation of the split chain, such
as will lead to relatively efficient evaluation. Otherwise, it is not obvious which method (chain-split
or chain-following) is more efficient (Case 3), and a detailed cost estimation should be performed to compare the
approximate size and cost for the evaluation of "P 1 vs. that of "(P 1
This can be accomplished by a quantitative analysis of two expressions with the incorporation of the available
accessing structures and database statistics, etc. [13]. 2
The heuristic indicates that it is easy to judge in some obvious cases whether a chain-split evaluation should be
applied based on the join expansion ratio and the selectivity of the provided query constants. However, detailed
quantitative analysis should be performed for most non-obvious cases. Such an analysis is similar to the query
plan generation and access path selection developed in the studies of relational and deductive query processing
[21, 13], which is not to be presented in detail in this study.
2.2 Finiteness-based chain-split
In a compiled functional recursion, a chain generating path may contain functions or evaluable predicates defined
on infinite domains. To ensure that the evaluation generates all the answers and terminates, three issues should
be examined: (1) finite evaluability, that is, the evaluation of every i-th formula in the compiled form generates
finite intermediate relations, (2) chain-level finite evaluability, that is, the evaluation of a chain generating
path generates finite intermediate relations, and (3) termination, that is, the evaluation generates all the answers
and terminates at a finite number of iterations. The finiteness-based chain-split is based on the analysis of the
first two issues.
The justification of finite evaluability relies on both query information and finiteness constraints. A finiteness
constraint predicate r implies that each value of attribute X corresponds to a finite set of
Y values in r [6]. Finiteness constraint is strictly weaker than the functional dependency studied in database
theory [21]. It holds trivially for all finite predicates. Since all the EDB relations are finite, all the arguments in
EDB relations satisfy the finiteness constraint. In a functional predicate f(X all the domains for
arguments are finite, V must be finite no matter whether f is a single- or a multiple-valued function,
that is, (X
Specific finiteness constraints should be explored for specific functions. In many cases, one argument of a
function can be computed from the values of the other arguments and the value of the function. For example, in the
functional predicate sum(X;Y;Z), any argument can be finitely computed if the other two arguments are finite.
Such a relationship can be represented by a set of finiteness constraints, such as "(X; Z) ! Y ", and "(Y; Z) ! X".
An interesting finiteness constraint, "Z ! (X; Y )", holds in the functional predicate "cons(X; Y; Z)", which
indicates if the list Z is finite, there is only a finite number of choices of X and Y .
Since query constants may bind some infinite domains of variables to finite ones, the analysis of finite evalua-
bility should incorporate query instantiation information. Similar to the notations used in the magic sets transformation
[2, 21], a superscript b or f is used to adorn a variable to indicate the variable being bound (finite) or
a string of b's and f's is used to adorn a predicate to indicate the bindings of its corresponding
arguments.
Algorithm 2.1 Testing the finite evaluability of a query in an n-chain recursion.
Input: (1) An n-chain recursion consisting of an n-chain recursive rule and a set of exit rules, (2) a set of finiteness
constraints, and (3) query instantiation information.
Output: An assertion of whether the query is finitely evaluable.
ffl Initialization: A variable is finite if it is in an EDB predicate or is equivalent to one or a set of constants.
ffl Test the finite evaluability of (1) the exit rule set, and (2) the first expanded exit rule set (the rule set
obtained by unifying the n-chain recursive rule with the exit rule set). This is done by pushing the query
binding information into the rules being tested and propagating the finiteness bindings iteratively based on
the following two finiteness propagation rules:
1. if there is a finiteness constraint "(X
2. if
ffl Return yes if every variable in the two sets of rules being tested is finite after the finiteness binding propagation
or no otherwise.
Remark 2.1 Algorithm 2.1 correctly tests the finite evaluability of an n-chain recursion in O(k 2 ) time in the
worst case, where k is the number of predicates in the recursion.
Rationale. By initialization and query constant propagation, the variables in the EDB predicates or those equivalent
to one or a set of constants (including query constants and constants in the body of the rule) are finite.
Propagate the finiteness bindings in the body of the (recursive or exit) rule according to the two finiteness propagation
rules in the algorithm. If every variable in a predicate p i is finite by such a propagation, p i is removed
from the list of predicates to be tested. At each iteration, at least one such predicate will be removed from the
list of predicates to be tested. Otherwise, the rule is not finitely evaluable. Since there are initially k predicates
in the body of the rule, the second iteration will need to test at most predicates, and so on, the total
number of predicates to be tested in the worst case is \Sigma i=0
1)=2. Thus the worst case time complexity
of the algorithm is O(k 2 ). Notice when both recursive rules and exit rules are finitely evaluable, the recursion is
finite evaluable by induction (since the n-th iteration may treat those derived in the previous (i \Gamma 1) iterations as
a finite base relation in its derivation). 2
Algorithm 2.2 Finiteness-based chain-split for a chain generating path in an n-chain recursion.
Input: (1) A chain generating path in a compiled n-chain recursion, (2) a set of finiteness constraints, and (3)
query instantiation information.
Output: A finiteness-based chain-split evaluation plan for a compiled chain in an n-chain recursion.
ffl Application of Algorithm 2.1. The query is not finitely evaluable if Algorithm 2.1 returns no. Otherwise,
proceed to the following steps.
ffl Initialization: A variable is finite if (i) it is in an EDB predicate, or (ii) it is equivalent to one or a set of
constants.
ffl Propagation of the finiteness bindings on the chain generating path according to the same two finiteness
propagation rules as in Algorithm 2.1. If every variable in the chain generating path is finite after the
finiteness binding propagation, it is chain-level finitely evaluable. Otherwise, the path is split into two,
A-portion and B-portion. The former consists of the set of predicates in which every variable is finite; and
the latter consists of the remaining set of predicates in the chain generating path. The chain-split evaluation
should be performed by first evaluating the sub-chain formed by the A-portion, and then the B-portions
after evaluating the exit portion.
Remark 2.2 Algorithm 2.2 determines correctly whether a chain-split evaluation should be performed based on
finite evaluability and, if it should, how the chain-generating path should split.
Rationale. If a query is not finitely evaluable, no iterative evaluation should be performed. Thus, step 1 is
necessary. When a query is finitely evaluable but a chain generating path is not, the chain generating path should
be split into two portions: the immediately evaluable portion and the buffered portion. After the evaluation of
the evaluable portion of the chain and the exit portion, the binding so obtained must make the buffered portion
finitely evaluable (otherwise, the query is not finitely evaluable). Thus, we have the above algorithm. 2
Example 2.2 For the predicate append(U; V; W ), there are 2 possible query binding patterns: bbb, bbf ,
bfb, bff , fbb, fbf , ffb, and fff . Among these eight patterns, bff , fbf and fff are not finitely evaluable; bbf ,
fbb, and ffb require chain-split; and the remaining two do not require chain-split. One such case is presented
here.
The query with the binding pattern ffb, such as "? \Gamma append(U; V; [a; b]):", is finitely evaluable because all of
the variables in the exit rule and the first expanded exit rule are adorned with b after binding propagation. The
adornment transformation by the binding propagation in the first expanded exit rule is presented in (2.4), where
the notation for the adornment "ffb ! bbb" indicates that the initial adornment ffb is changed to bbb by the
binding propagation.
append ffb!bbb (U; V; W ) /
The binding propagation proceeds as follows:
1. U 1 and W are adorned with b according to the instantiations in the exit rule and the query;
2. X 1 and W 1 are adorned with b because W b and there exists a finiteness constraint: "W
3. V is adorned with b since finally,
4. U is adorned with b because X b
Since every variable in the rule is adorned with b after the binding propagation, the query is finitely evaluable.
Furthermore, Algorithm 2.2 asserts that chain-split evaluation should be performed on the chain generating
path, )". This is because W b makes "cons(X 1 finitely evaluable but
not shown below,
cons ffb (X 1 cons bff (X 1
Therefore, the chain should be split into two with evaluated first and the other cons-predicate
delayed until the first sub-chain and the exit portion have been evaluated. The adorned normalized linear recursive
rule can be written in the chain-split form as follows.
append ffb (U; V; W ) /
cons ffb (X 1 cons bbf (X 1
The rewritten rule indicates that the double-cons chain should be split into two subchains with one subchain
represented by "cons(X 1 evaluated first and the other "cons(X 1 delayed until the exit rule is
evaluated. 2
3 Chain-Split Evaluation Techniques
There are two typical evaluation methods, magic sets and counting [2], in the evaluation of n-chain recursions
without chain-split. With appropriate modifications, these methods are applicable to chain-split evaluation.
3.1 Efficiency-based chain-split magic sets evaluation
Example 1.2 shows that undesirably large magic sets could be derived by strictly enforcing the binding propagation
rules without consideration of the size of intermediate relations [21]. Since the binding propagation rules do not
distinguish strong linkages (those effectively reducing the size of relevant sets) from weak ones (those involving
huge, cross-product like relations), some bindings, like the one in "same country bf (X; Y )", can still be passed to
the next subgoal in the body of the rule via a weak linkage. Obviously, if a restriction is enforced to confine the
passing of bindings to be via strong linkages only, effective magic sets can still be derived for efficient semi-naive
evaluation. This is the idea of efficiency-based chain-split magic sets evaluation.
Example 3.1 We re-examine the magic sets evaluation of the query "? \Gamma scsg(john; Y )" in Example 1.2. For
the merged parents chain, the binding X b is propagated as,
parent bf (X; parent fb (Y; Y 1
Suppose on average a person has 2 parents and less than 5 children, and more than 2,000 persons share the
same country in the database. We have,
1. for parent bf (X; X 1 2.
2. for same country bf (X
3. for parent fb (Y; Y 1 5.
Clearly, fi ? 4; 000; 000 indicates a weak linkage. Thus, the binding propagation from X 1 to Y 1 should be
prohibited via such a linkage. The merged parent should be split into two subchains, (i) parent(X;
"same with the first one evaluated first and second one delayed until the exit
rule is evaluated. Such binding passing generates,
parent bf (X; parent fb (Y; Y 1
This binding propagation derives the same magic sets as the sg recursion on which the semi-naive evaluation
can be performed efficiently. 2
The join expansion ratio can be used as a simple judgement of whether a particular binding should be
propagated to another subgoal in the binding propagation. A relatively large number, such as 100, can be set as
a chain-split threshold. If the join expansion ratio is greater than this threshold, the binding propagation cannot
proceed. On the other hand, a relatively small number, such as 10, can be set as a chain-following threshold. If
the join expansion ratio is smaller than this threshold, the binding propagation proceeds. These two thresholds
can be tuned based on experimental results and system behavior. However, when the join expansion ratio is
greater than the chain-following threshold but less than the chain-split threshold, it is still necessary to perform
a detailed quantitative analysis based on chain characteristics and database statistics and compare the relative
costs of chain-following vs. chain-split in order to make an appropriate decision. Thus, we have,
Algorithm 3.1 Efficiency-based chain-split magic sets evaluation of a function-free linear recursion.
Input: A query and a compiled function-free linear recursion.
Output: An efficiency-based chain-split magic sets query evaluation plan.
ffl In the derivation of magic sets, the binding propagation rule [1] is modified as follows: If the join expansion
ratio for hX; Y i is above the chain-split threshold, the binding will not be propagated from X to Y ; if it
is below the chain-following threshold, the binding will be propagated from X to Y ; otherwise, a detailed
quantitative analysis is performed to determine whether a chain-split is beneficial.
ffl Based on the modified binding propagation rules, the magic set(s) are derived, and the semi-naive evaluation
[1] is performed on the sets of relevant facts. 2
Based on the reasoning presented before the example, it is easy to see that Algorithm 3.1 derives a more
efficient query evaluation plan than the method which relies on blind binding passing without distinction of
strong linkages from weak ones.
3.2 Buffered chain-split evaluation
A chain-split evaluation can be implemented by another technique: buffered chain-split evaluation, which
splits a chain generating path into two portions in the evaluation: (1) A-portion, which is the set of predicates
being evaluated, and (2) B-portion, which is the set of predicates being buffered. The buffered portion will not
be evaluated until the exit portion (the body of the exit rule) is evaluated. The variable values shared between
the A- and B- portions are buffered in the evaluation of the A-portion for later use in the evaluation of the
corresponding B-portion.
a) Chain-merged processing
processing

Figure

1: chain-following vs. chain-split evaluation.
Fig. 1 shows the distinction between a) chain-following evaluation, and b) buffered chain-split evaluation.
In the chain-following evaluation, A and B are treated as one (merged) predicate. In the buffered chain-split
evaluation, A-portion is first evaluated, with the shared value(s) buffered. After the evaluation of the exit portion
E, the B-portion obtains sufficient binding information. Thus, the evaluation proceeds in a way similar to the
evaluation of a regular multi-chain recursion except that the corresponding buffered values are patched to the
corresponding variables in the evaluation of the buffered-portion. Therefore, we have the name, buffered chain-split
evaluation.
Example 3.2 According to the discussion in Example 2.2, "? \Gamma append(U; V; [a; b])", should be evaluated by
chain-split. The chain generating path "cons(X partitioned into two portions:
the U-predicate "cons(X and the W -predicate As shown in Fig. 2, when
the evaluation essentially passes through the exit portion and derives the first set of answers:
the U-predicate is not finitely evaluable. The evaluation proceeds along
the W -predicate only, which derives "W buffered, and W 1
is passed to the exit portion, making []". Then the U-predicate is evaluable since
are available. It derives )". Thus, the second set of answer is
Similarly, the evaluation may proceed on the W -predicate further, which derives "W
and buffered, and W 2 is passed to the exit portion, making
and "U []". Then the U-predicate is evaluable, which derives
Thus, the third set of answer is
cons
cons
cons
cons
cons

Figure

2: Evaluation of "? \Gamma append(U; V; [a; b])".
In general, the following algorithm presents the buffered chain-split evaluation of a single-chain recursion,
where buffering is based on chain-level finite evaluability or evaluation efficiency. The algorithm can be easily
generalized to multi-chain recursions.
Algorithm 3.2 Buffered chain-split evaluation of a single-chain recursion.
Input: A query and a compiled functional single-chain recursion.
Output: A query evaluation plan which applies the buffered chain-split evaluation.
Suppose the chain generating path is partitioned into two portions according to the available query bindings:
a being evaluated portion A and a buffered portion B. The partition can be based on chain-level finite evaluability
or evaluation efficiency. Suppose in the i-th chain generating path of the compiled form, A and B share a variable
shares a variable U i with the (i 1)-st A, and B shares a variable W i with the (i 1)-st B.
ffl First, suppose the query instantiates U 0 . At the i-th iteration, based on the available binding U
is evaluated which derives U i and buffers the corresponding X i value. The iteration terminates when it
satisfies the termination condition (e.g., when the list shrinks to empty or when the cyclic counting method
determines its termination condition). Suppose that it terminates at the k-th iteration.
ffl Evaluate the exit portion of the compiled form.
ffl Pass the bindings obtained in the processing of the exit portion to B. Based on the available binding W i and
the buffered X i , B is evaluated which derives W i\Gamma1 at the (k \Gamma i)-th iteration. The evaluation terminates
at the k-th iteration or when there is no W i\Gamma1 derivable at an iteration. 2
Remark 3.1 The buffered chain-split evaluation performed by Algorithm 3.2 correctly evaluates a compiled single-chain
recursion.
Rationale. The algorithm is similar to counting [1] except that the values of variable X i 's are buffered in the
processing of the being evaluated portion of a chain generating path and reused in the processing of its buffered
portion. Notice that if there were no linking the two portions in the recursion, there would be two chains in
the compiled recursion to which counting applies. Since the being evaluated portion is linked to the corresponding
buffered portion via X i in the chain generating path, it is necessary to buffer X i and reuse it in the evaluation
of the buffered portion. After the evaluation of the exit portion, the buffered portion must be finitely evaluable
based on the finite evaluability of the recursion. Therefore, the chain-split evaluation derives correct and complete
answers in the query processing. 2
Notice that the termination of buffered chain-split evaluation should be judged carefully. For a function-free
recursion, the evaluation terminates easily on acyclic data. For cyclic data, the method can be extended in a
way similar to cyclic counting algorithms (such as [5]). For a functional recursion, termination is often based on
the monotonicity of certain arguments [6]. The partial evaluation method also contributes to the termination of
chain-split evaluation which will be discussed in the next subsection.
3.3 Chain-split partial evaluation
In the buffered chain-split evaluation, every intermediate value shared between the split portions of a chain is
buffered. Along the derivation path of a split chain, there will be a sequence of buffered values associated with
each derived intermediate value. In the evaluation of the buffered portion, patching is performed by popping the
buffered value in reverse sequence. When the derivation sequence grows, such buffering and patching could be
quite costly.
As an improvement to the simple buffering scheme, partial evaluation can be performed on the buffered
values for many functional recursions as follows: Instead of storing a sequence of buffered values, the sequence
of buffered values should be evaluated as much as possible, and the partially evaluated values should be carried
along the evaluation path. Such partial evaluation reduces the complexity of patching the buffered values and
often facilitates the pushing of query constraints and the judgement of termination.
Example 3.3 A recursion travel defined by a rule set f(3.2), (3.3)g represents flights or a sequence of connected
flights, leaving a departure city Dep at DTime, arriving at a destination city Arr at ATime, with a total fare
equals to Fare.
travel([F no]; Dep; DTime;Arr;ATime;Fare) /
f light(F no; Dep; DTime;Arr;ATime;Fare): (3.2)
travel([F nojL]; Dep; DTime;Arr;ATime;Fare) /
The rule set is rectified into f(3.4), (3.5)g, where sum is a functional predicate for the arithmetic function
"+", and cons is a functional predicate for the corresponding list construction function. According to [9], the
rectified rule set is in the normalized form, and its compiled form is (3.6), which consists of one chain with three
connected predicates, flight, sum, and cons.
Suppose a query is to find the sequences of connected flights from Vancouver to Ottawa, departing between 8
to 9 am, with the fare less than 600.
Dtime - 8; Dtime - 9; Fare - 600: (3.7)
It is difficult to apply the magic sets method in the evaluation because the query involves a functional recursion
and the semi-naive evaluation cannot terminate on such recursions (since Fare and the length of FnoList keep
growing).
The chain-based evaluation can be performed as follows. Since the query provides more selective information
at the departure end rather than at the arrival end, the processing should start at the departure end. Then
the departure airport "vancouver" is treated as a query constant, and similarly, the departure time constraint
"Dtime - 8; Dtime - 9" is a query constraint to be pushed at the departure end. The other constraints,
and "F are - 600", will be pushed during the query processing based on the constraint-
pushing principles [6].
The propagation of the binding "departure = vancouver" in the normalized recursive rule is shown below.
travel fbfff (L; D;DT; A; AT; F ) /
f light fbfff
travel
sum bbf cons bbf
When the evaluation starts at the departure end, the two functional predicates sum and cons are not finitely
evaluable because S i is uninstantiated in the sequence of functional predicates sum,
and L i is uninstantiated in the sequence of functional predicates cons,
The buffered chain-split evaluation may proceed by buffering a sequence of F i and Fno i values. That is, when
are buffered (for each generated tuple); and when 2, the corresponding F 2 and
are buffered, and so on. After it reaches Ottawa, we have S Then the corresponding
buffered values are patched in the evaluation of sum(F i
However, it is preferable to partially compute the buffered values in the evaluation. When the buffered
predicates are sum(F 1
Fno 1 are the instantiated values. When 2, the buffered predicates are sum(F 2
that is, S are the instantiated values. Therefore, we have
In general, S are partially
evaluable. When the f light relation is being evaluated,
are computed. The evaluation of the buffered portion is trivial when it reaches Ottawa. At this point, S
and
Furthermore, since S and length(L) are monotonic functions, they can be used in the determination of
termination and constraint pushing [6]. When S ? 600, the continued search following this intermediate tuple
will be hopeless and such intermediate tuple should be pruned from the intermediate result buffer. That is, the
constraint Fare - 600 can be transformed into S - 600 because and be pushed into
the iteration. 2
Algorithm 3.3 Chain-split partial evaluation of a compiled functional single-chain recursion.
Input: A compiled functional single-chain recursion, a set of integrity constraints, a query predicate, and a set
of query constraints.
Output: A query evaluation plan which incorporates query constraints and implements chain-split partial evaluation

ffl Test whether the query is finitely evaluable and terminable. If it is not, stop and inform the user.
ffl Determine the start end of the chain processing based on the relative selectivity of the query constraints at
both ends of the compiled chain. Apply the query constraints belonging to this end as query instantiations
to reduce the size of the initial set.
ffl For the compiled chain, determine whether the chain-split evaluation should be performed based on the
chain-level finite evaluability and evaluation efficiency. If the chain-split evaluation should be performed,
determine (i) the partition of the being-evaluated portion and the buffered portion, and (ii) the partial
evaluation plan, if possible, for the buffered portion. The partial evaluation is performed by evaluating the
buffered portion partially. That is, evaluate them as much as possible using the instantiated values and
leave only the uninstantiated portion buffered and carried to the next stage.
ffl Instantiate the termination constraints based on the monotonicity constraints and the remaining query
constraints. Push the termination constraints into the chain for iterative chain evaluation [6]. 2
Remark 3.2 Algorithm 3.3 correctly incorporates query constraints and implements chain-split partial evaluation
in the evaluation of compiled functional single-chain recursions.
Rationale. Step 1 is necessary since a query must be finitely evaluable and terminate. Step 2 is necessary and
correct since the most selective information should be pushed into the compiled chain for initial processing [3].
Step 3 is correct since if the chain-split evaluation is to be performed, partial evaluation should be explored. Step
4 is correct based on the study of constraint-based query processing in deductive databases [6]. 2
A similar algorithm can be derived for constraint-enforced chain-split partial evaluation of multi-chain recursions

4 Chain-Split Evaluation of Complex Logic Programs
Chain-split evaluation is not confined to (single) linear recursions. Since similar binding propagation rules may
suffer from the same kind of inefficiency and/or infinite evaluation problems in complex classes of logic programs,
chain-split should be applied to such programs as well. In this section, chain-split evaluation in complex classes of
recursive programs is examined, which demonstrates that chain-split and chain-following are two basic recursive
query evaluation techniques.
4.1 Evaluation of nested linear recursions
According to the definition of nested linear recursion, if every lower level IDB predicate in a nested linear recursion
is treated like an EDB predicate, the recursion at each level can still be viewed as a (single) linear recursion.
Thus, the recursion at each level can be normalized independently, and query analysis can be performed on each
normalized recursion.
Example 4.1 The insertion sort recursion, isort, defined by the following program [20] is a nested linear recursion
because the predicate insert in the body of the recursive rule (4.1) is in turn defined by a linear recursion.
It can be rectified into the following program in which every recursive rule is normalized [9].
Treating insert like an EDB predicate, the recursion isort, (4.6) and (4.7), is a normalized single-chain
recursion. The recursion insert, f(4.8) - (4.10)g, is also a normalized single chain-recursion.
Query analysis can be performed on the normalized recursion at each level. Taking the query "?\Gammaisort([5; 7; 1]; Y s):"
as an example, the analysis proceeds as follows.
The adorned query predicate is isort bf . The query binding propagation leads to the following adorned program,
where the notation Y indicates that in the built-in predicate "=", the first argument Y s is free and the
second one [] is bound.
isort bf (XXs;Y s) / cons ffb (X; Xs; XXs); isort bf (Xs; Zs);
insert bbf (X; Zs; Y s): (4.11)
isort
insert bbf (X; Y Y s; Y Zs) cons bbf (X; []; Y Zs): (4.13)
insert bbf (X; Y Y s; Y Zs) / cons ffb (Y; Y s; Y Y s); X - bb Y; cons bbf (X; Y Y s; Y Zs): (4.14)
insert bbf (X; Y Y s; Y Zs) / cons ffb (Y; Y s; Y Y
insert bbf (X; Y s; Zs); cons bbf (Y; Zs; Y Zs): (4.15)
In comparison with the normalized but not adorned program, some predicates in the adorned program are
reordered based on the analysis of finite evaluability. For example, the two predicates isort and insert in the
normalized rule (4.6) are swapped in the adorned rule (4.11). This is because the query binding propagation
following the original ordering will lead to a nonfinitely evaluable adorned predicate insert bff . The predicate
ordering in (4.11) makes every predicate finitely evaluable. Since the two predicates, "cons(X; Xs; XXs)" and
"insert(X; Zs; Y s)", in the chain generating path share a variable X, chain-split evaluation should be performed
on the recursion isort bf . Similarly, chain-split evaluation should be performed on the recursion insert bbf .
The evaluation of query "? \Gamma isort([5; 7; 1]; Y s):" proceeds as follows. The evaluation of (4.11) leads to
(which is buffered) and "Xs = [7; 1]", and then a call "isort([7; 1]; Zs)" which in turn leads to "X
7" (which is buffered) and "Xs and a call "isort([1]; Zs 0 )". This leads to "X (which is also
buffered) and "Xs and a call "isort([]; Zs 00 )". This call executes (4.12) and results in Zs
executes a sequence of calls (with the buffered values popped in the reverse sequence), that is, "insert(1; []; Zs 0 ),
s)". The evaluation of this sequence of calls is performed as follows. First,
"insert(1; []; Zs 0 )" results in "Zs since it can only execute (4.13). Second, "insert(7; [1]; Zs)" leads to "Zs
[1, 7]" since it executes (4.15) which in turn calls "insert(1; [7]; Zs)" and then executes the rule (4.15). Third,
"insert(5; [1; 7]; Y s)" calls "insert(5; [7]; Zs); cons(1; Zs; Y s)". This leads to the final answer, "Y
This example demonstrates that chain-split evaluation is a popular technique in the evaluation of nested linear
recursions. Similarly, it can be shown that chain-split evaluation is a primitive query evaluation technique for
multiple linear recursions.
4.2 Evaluation of nonlinear recursions
Finally, we demonstrate that chain-split evaluation should also be a primitive query evaluation technique for
nonlinear recursions. Since many nonlinear recursions cannot be compiled into highly regular chain forms, "chain-
split" is a misnomer. However, the split of a set of connected EDB and/or lower-level IDB predicates in the
evaluation of a nonlinear recursion shares the same spirit as the chain-split evaluation in a linear recursion. Thus,
it can still be called "chain-split evaluation". One such example is examined in this subsection.
Example 4.2 The quick sort recursion, qsort, defined by the following program [20] is a nonlinear recursion
because the recursive rule (4.16) is a nonlinear recursive rule.
It is rectified into the following program.
qsort(Littles; Ls); qsort(Bigs; Bs); append(Ls; XBs;Y s);
Treating the lower-level predicates partition and append as EDB predicates, the recursion qsort, (4.21) and
(4.22), is a nonlinear recursion; whereas the lower-level recursion partition is a multiple linear recursion, and
append is a (single) linear recursion. Query analysis can be performed at each level of the recursions.
Taking the query "? \Gamma qsort([4; 9; 5]; Y s):" as an example, the analysis proceeds as follows.
The adorned query predicate is qsort bf . The query binding propagation leads to the following adorned
program.
qsort bf (XXs;Y s) / cons ffb (X; Xs; XXs); partition bbff (Xs; X; Littles; Bigs);
qsort bf (Littles; Ls); qsort bf (Bigs; Bs);
cons bbf (X; Bs; XBs); append bbf (Ls; XBs;Y s): (4.26)
qsort
partition bbff (XXs;Y;XLs;XBs) / cons ffb (X; Xs; XXs);X - bb Y;
partition bbff (Xs; Y; Ls; XBs); cons bbf (X; Ls; XLs): (4.28)
partition bbff (XXs;Y;XLs;XBs) / cons ffb (X; Xs; XXs);X ? bb Y;
partition bbff (Xs; Y; XLs;Bs); cons bbf (X; Bs; XBs): (4.29)
partition bbff (XXs;Y;XLs;XBs) /
Notice that all of the transformed primitive predicates and the low-level IDB predicates in the rectified rule
(4.21) are connected together by shared variables. However, this set of connected predicates are split into two
portions in the adorned rule (4.26) to facilitate finite evaluation. Similar chain-split is performed in the adorned
rules (4.28) and (4.29) for the recursion partition. Chain-split is also performed in the evaluation of append bbf ,
which is similar to the process demonstrated in Example 3.2.
The evaluation of query "? \Gamma qsort([4; 9; 5]; Y s):" proceeds as follows.
ffl The evaluation of (4.26) leads to
qsort(Littles; Ls); qsort(Bigs; Bs);
ffl The evaluation of "partition([9; 5]; 4; Littles; Bigs)" leads to
ffl This leads to the evaluation of "partition bbff ([5]; 4; XLs;Bs)":
ffl The evaluation of "partition([]; 4; XLs;Bs 0 )" applying rule (4.30) derives It in
turn derives (4.32). (4.31) now
becomes
ffl The evaluation of "qsort([]; Ls)" applying the rule (4.27) derives "Ls = []", and the evaluation of qsort([9; 5]; Bs)
leads to "Bs = [5; 9]" by a similar process applying the rule (4.26). Finally, "cons(4; [5; 9]; [4; 5; 9]),
append([]; [4; 5; 9]; Y s)" leads to "Y
From this example, it is not difficult to see that chain-split is a primitive and frequently-applied evaluation
technique in the processing of many nonlinear recursions as well. To illustrate further the importance of chain-
split evaluation in the evaluation of nonlinear recursions, we examine a nonlinear recursion in the form of f(4.35),
(4.36)g.
Let the query be in the form of p b:::f . Usually, the binding on X can be passed from predicate a 1 to a 2 via
the variable W . However, if the binding passing via W is weak or leads to an infinitely evaluable predicate a 2 ,
chain-split should be performed by buffering the intermediate value of W , delaying the evaluation of a 2 by first
evaluating the first recursive predicate p in the body. After the evaluation of this p, a 2 can be evaluated efficiently
or finitely with the availability of an additional binding W 1 . A similar chain-split process can be performed for
the connected predicates b 1 and b 2 with respect to the second p in the body. Thus, chain-split is a commonly
used technique in the evaluation of nonlinear recursions.
Conclusions
An interesting recursive query evaluation technique, chain-split evaluation, is investigated in this study. Chain-
split evaluation splits a chain generating path (a set of connected EDB and/or lower-level IDB predicates) into
two portions in the evaluation: an immediately evaluable portion and a delayed-evaluation portion. Chain-split
evaluation should be applied when the split reduces the size of intermediate relations and/or transforms an
infinitely evaluable subprogram into a finitely evaluable one.
Our study demonstrates that chain-split evaluation is an important query evaluation technique. It is especially
useful for many functional recursions whose compiled chains consist of infinitely evaluable functions. The necessity
of chain-split evaluation and the judgement of when a chain needs split based on chain-level finite evaluability
and/or evaluation efficiency are studied. Three chain-split evaluation techniques: magic sets, buffered evaluation
and partial evaluation, are developed. The magic sets chain-split evaluation technique blocks the binding propagation
via unpromising paths during the magic rule rewriting, which leads to the derivation of efficient magic sets.
The buffered chain-split evaluation buffers the shared values in the evaluation of one split subchain and patches
back the buffered values in a later evaluation. Partial evaluation is a refinement to the buffered evaluation by
evaluating as many buffered functional predicates as possible to reduce the cost of maintaining the sequences of
buffered values and facilitates the termination judgement and constraint pushing.
A set of frequently-encountered, interesting examples are analyzed in our study. Such an analysis demonstrates
that chain-split evaluation, together with the chain-following evaluation, forms two primitive evaluation techniques
in the evaluation of different classes of recursions. Furthermore, the evaluation should be integrated with existence
checking and constraint-based query evaluation techniques [6] to achieve high performance in the evaluation of
sophisticated logic programs.
To the best of our knowledge, no detailed study on chain-split evaluation was performed in previous deductive
database research [4, 16, 21, 23, 22]. Many deductive database system projects, such as LDL [4], EKS-V1
[23], CORAL [16, 19], etc. have been focused on the evaluation of function-free recursions; whereas chain-split
evaluation is frequently encountered in functional recursions, as demonstrated in this study. Recent studies
[4, 16, 19] have extended the Datalog data model to handle function symbols to a limited extent, however, based
on our knowledge, no chain-split evaluation has been performed in those projects.
Our analysis demonstrates that a large set of logic programs with different classes of recursions can be implemented
efficiently using a compilation-based query analysis and optimization technique originated from the
deductive database research. In comparison with other logic programming implementation techniques, the deductive
database approach derives efficient query evaluation plans based on compilation, normalization, program
transformation and query analysis. The effectiveness and completeness of query evaluation in deductive databases
is independent of predicate ordering in rules, independent of the ordering of rules and facts in logic programs,
and independent of different query forms. Such flexibility in the analysis of logic programs leads to powerful and
efficient query evaluation mechanisms for both data-intensive and logic-intensive programs and may represent an
interesting direction towards fully declarative programming of logic programs.
We are currently implementing a sophisticated query analyzer and query evaluator as a part of the LogicBase
project [7]. The LogicBase deductive database system consists of two major components: a rule compiler and a
query evaluator. The former classifies different kinds of recursions and compiles linear and nested linear recursions
into their normalized forms [9]; whereas the latter integrates chain-following, chain-split and constraint-based
evaluation techniques in deductive query evaluation. A preliminary version of the LogicBase system has been
implemented in the UNIX system using LEX, YACC and C, and has been successfully tested on many interesting
recursions, such as append, travel, isort, nqueens, etc. Queries with different input/output mode combinations
can be evaluated correctly and efficiently on such recursions, independent of predicate ordering or rule ordering
in logic programs.
Our current implementation of chain-based query evaluation in LogicBase is confined to logic programs consisting
of linear and nest linear recursions. A scan of the example programs in most logic programming textbooks
will discover that a majority of frequently-used logic programs belong to this category. Many sophisticated logic
programs beyond linear and nested linear recursions cannot be compiled into highly regular chain forms. How-
ever, similar chain-based evaluation techniques may still apply as demonstrated in our analysis of the quick sort
program. More systematic study should be performed on the analysis and evaluation of such complex recursive
programs, which may lead to a general and efficient query analysis and evaluation technique for deductive
database and logic programming systems.

Acknowledgement

The author would like to express his thanks to Ling Liu and Zhaohui Xie for their implementation of the method
in the LogicBase project and anonymous referees for their constructive comments which improved the quality of
the paper.



--R

Magic sets and other strange ways to implement logic programs.
An amateur's introduction to recursive query processing strategies.
Bounds on the propagation of selection into logic programs.
The LDL system prototype.
A counting algorithm for a cyclic binary query.

A system prototype for deductive query evaluation.
Asynchronous chain recursions.
Automatic generation of compiled forms for linear recursions.
Efficient transitive closure algorithms.
A study of transitive closure as a recursion mechanism.
A framework for testing safety and effective computability of extended datalog.
Optimization in a logic based language for knowledge and data intensive applications.

Safety of recursive Horn clauses with infinite relations.

On testing effective computability of magic programs.
Access path selection in a relational database management system.
Pushing constraint selections.
The Art of Prolog.
Principles of Database and Knowledge-Base Systems
An introduction to the ADITI deductive database system.
In AAAI-90 Workshop on Knowledge Base Management Systems
--TR

--CTR
Yangjun Chen, On the Graph Traversal and Linear Binary-Chain Programs, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.573-596, March
query optimization;deductive database;recursive query evaluation;query analysis;logic programming;query processing