\documentstyle[defpaper]{article}
\setnormaldefaults
\input{psfig}

\renewcommand{\ifff}{\mbox{$ :- $}}

\title{Rule Ordering in Bottom-Up Fixpoint Evaluation of 
Logic Programs
\footnotetext{This work was supported by a David and Lucile Packard
Foundation Fellowship in Science and Engineering, a Presidential Young
Investigator Award, with matching grants from Digital Equipment Corporation,
Tandem and Xerox, NSF grants IRI-8804319 and IRI-9011563, and
an IBM Faculty Development Award.}
\footnotetext{The authors are with the Computer Sciences Department, 
University of Wisconsin-Madison, WI 53706, U.S.A.
The authors' e-mail addresses are \{raghu,divesh,sudarsha\}@cs.wisc.edu.}
\footnotetext{A preliminary version of this paper appeared
in the Proceedings of the Sixteenth International Conference on Very
Large Data Bases, Brisbane, Australia, 1990.}}
\author{Raghu Ramakrishnan
\and Divesh Srivastava
\and S. Sudarshan
}

\date{}

\begin{document}
\bibliographystyle{abbrv}

\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstract}
{\small
Logic programs can be evaluated bottom-up by repeatedly applying all rules,
in ``iterations'', until the fixpoint is reached.  However, it is often
desirable---and in some cases, e.g.\ programs with stratified negation,
even necessary to guarantee the semantics---to apply the rules in some
order.

A desirable property of a fixpoint evaluation algorithm is that it
does not repeat inferences.
We say that such an algorithm has the non-repetition property, and the
``semi-naive'' algorithms in the literature have this property.
However, these algorithms 
do not address the issue of how to apply rules in a specified order while
retaining the non-repetition property.  
We present two algorithms that address this issue.
One of them (GSN) is
capable of dealing with a wide range of rule orderings but with a little
more overhead than the usual semi-naive algorithm (which we call BSN).
The other (PSN) handles a smaller class of rule
orderings, but with no overheads beyond those in BSN.  
%%%%%%%%%
%% This smaller class is sufficiently powerful to enforce the ordering 
%% required to implement stratified programs.
%%%%%%%%%

We also demonstrate that by choosing a good ordering, we can reduce the 
number of rule applications (and thus joins).
We present a theoretical analysis of rule orderings. In particular,
we identify a class of orderings, called cycle-preserving orderings,
that minimize the number of rule applications (for all possible instances of
the base relations) with respect to a class of orderings called
fair orderings. 
We also show that while non-fair orderings may do a little better on some 
data sets, they can do much worse on others.
This suggests that it is advisable to consider
only fair orderings in the absence of additional information that
could guide the choice of a non-fair ordering.

We conclude by presenting performance results that bear out our 
theoretical analysis.
}
\end {abstract}

\noindent{\bf Index Terms:} Bottom-up Evaluation, Control Expression,
Cyclic Ordering, Deductive Database, Query Evaluation, Logic Programming, 
Rule Ordering, Semi-naive Evaluation.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}
\label{intro}

Bottom-up evaluation of logic programs is an important issue
in deductive database applications.
Bottom-up evaluation proceeds by starting with the facts in the 
database and repeatedly applying all the rules of the program,
in iterations, to compute new facts.
The evaluation terminates once we have reached a fixpoint, i.e.\ when
no new facts are computed by any of the rule applications.
One of the main concerns is the duplication of inferences, which
could considerably decrease the efficiency of bottom-up evaluation.
Algorithms which do not repeat inferences are considered 
desirable and said to have the {\em non-repetition\/} property.
There are essentially two components to fixpoint algorithms that have the 
non-repetition property.

\begin{enumerate}
\item The first is a rewriting of the program that
defines ``differential'' versions of predicates,
in order to distinguish facts that have been newly generated (and not yet
used in inferences) from older facts.

\item The second component is a technique to apply the rewritten rules
to generate facts, and update these differentials, ensuring that
all derivations are made exactly once.
\end{enumerate}

Semi-naive algorithms have been proposed by several
researchers (e.g.,~\cite{b:nai,br:adijlp}), and these algorithms
have the non-repetition property.
These algorithms evaluate the fixpoint in an iterative
fashion, with every rule applied once in each iteration.
In these algorithms, facts generated in an iteration can be used
to generate other facts only in subsequent iterations.
Unfortunately, these algorithms do not address the issue of 
how to apply rules in a specified order while retaining the
non-repetition property.
Rule orderings are significant for several reasons.

\begin{itemize}
\item First, they are sometimes required to compute the answers correctly.  

For example, in programs with stratified negation, lower strata 
must be evaluated before higher strata, and this simple ordering 
can become much more complex once we rewrite the program using 
Magic Sets~\cite{rlk:the,bmsu:mag,br:ont,r:mag} (which is an important 
technique used widely to avoid inferences that are not
``relevant'' to the query).

\item Second, rule ordering can result in increased efficiency.  

For example, in an SCC-by-SCC evaluation of a program, 
rules in lower SCCs do not need to be considered while applying
rules in higher SCCs; this can improve the efficiency of evaluation.
This is a simple form of rule ordering which has been implemented using
existing semi-naive algorithms.

An important contribution of this paper is to demonstrate
that ordering rules {\em within\/} an SCC can also improve 
efficiency by further reducing the number of rule applications.  
Although the orderings we consider for this purpose do not affect the
number of inferences made, the processing becomes more set-oriented, 
with each rule application generating more tuples.

\item Finally, rule orderings have been proposed to
prune redundant derivations and to allow the user to specify a
desired semantics~\cite{h:ind,h:det,in88:control}.
\end{itemize}
In this paper, we use regular expressions over rules to specify orderings 
of the application of rules; we call these {\em control expressions}.

In the first part of our paper, we present two fixpoint algorithms
that address the issue of how to apply rules in a specified order 
while retaining the non-repetition property.
One of them, General Semi-Naive (GSN), applies a rule to produce new 
facts, and then immediately makes these facts available to subsequent 
applications of other rules (possibly in the same iteration).
The GSN algorithm can deal with a large set of control expressions,
and is described in Section~\ref{gen:sn}.
The other algorithm we present, Predicate Semi-Naive (PSN),
can utilize facts produced for a predicate $p$ in the same iteration
they have been derived in, although not always in the immediately 
following rule application; this is described in Section~\ref{pred:sn}.
It handles a more restricted set of control expressions compared
to GSN, but is cheaper than GSN.
Indeed, it has no additional overheads compared to traditional
semi-naive algorithms.

Each of the algorithms we present is a 
technique to apply (semi-naive rewritten) rules and update the
differentials.
These algorithms can use any of the semi-naive rewriting 
techniques proposed earlier (e.g.,~\cite{b:nai,br:adijlp}) with minor 
modifications.
The algorithms we describe in this paper are 
independent of program rewriting optimization techniques such as 
Magic Sets that also seek to reduce the number of derivations.
We can apply such techniques (and other techniques such as those
described in \cite{h:ind,h:det}
that generate control expressions on rule applications) on a given
program, and then evaluate the resultant program using our
algorithms.

In the second part of our paper, in Section~\ref{rule:pred:order},
we study rule orderings in detail,
and establish a close connection between cycles
in rule graphs (which are a variant of rule/goal graphs defined in
\cite{br:ana,ull:vol1and2}) and orderings that minimize the number 
of iterations and rule applications.
We define what it means for a rule ordering to preserve a simple cycle, and
show that a rule ordering that preserves all simple cycles in the rule
graph (if such an ordering exists) is optimal within a certain class of rule
orderings, in minimizing the number of iterations, and hence the number of 
rule applications and joins.

In the third part of our paper, in Section~\ref{performance},
we present a performance study 
that underscores the importance of utilizing facts early, and choosing a 
good rule ordering, in reducing the number of iterations, rule applications
and joins.
The performance metrics used in this section include number of joins,
number of rule applications, number of iterations, 
join costs (without overheads) and duplicate elimination costs.
We also discuss related work, which uses total elapsed time on a disk-based
deductive database system as the metric, to show the benefits of using
PSN over BSN.
The terminology used in the rest of this paper is introduced 
in Section~\ref{background}, and related work is presented in 
Section~\ref{related:work}.

\section{Background}
\label{background}

\subsection{Definitions}
\label{defns}

The language considered in this paper is that of Horn logic.
Such a language has a countably infinite set of variables and countable
sets of function and predicate symbols, these sets being pairwise
disjoint.
We adopt the Prolog convention of denoting variables by strings
of characters starting with an upper case letter (e.g.\ $X, Y1$);
function and predicate symbols are strings of characters starting
with a lower case letter.
It is assumed, without loss of generality, that with each function
symbol $f$ and each predicate symbol $p$ is associated a unique
natural number $n$, referred to as the {\em arity\/} of the symbol;
$f$ and $p$ are then said to be $n$-ary symbols.
A $0$-ary function symbol is referred to as a {\em constant}.

A {\em term\/} in such a language is a variable, a constant, or a compound
term $f(t_1, \ldots, t_n)$ where $f$ is an $n$-ary function symbol
and the $t_i$ are terms.
A {\em tuple\/} of terms is sometimes denoted simply by the use
of an overbar, e.g.\ $\overline{t}$.
A {\em literal\/} (or {\em predicate occurrence}) in such a language
is of the form $p (t_1, \ldots, t_n)$ (a positive literal) 
or $\neg p (t_1, \ldots, t_n)$ (a negative literal),
where $p$ is an $n$-ary predicate symbol and the $t_i$ are terms.
Predicates in such a language are also referred to as 
{\em relations}. 
However, the two are interpreted differently;
a relation is interpreted by a set of tuples and a predicate
by a {\bf true}/{\bf false} function.

A substitution is a mapping from the set of variables
of the language under consideration to the set of terms.
Substitutions are denoted by lower case Greek letters $\theta, \sigma, 
\varphi$, etc.
A substitution $\sigma$ is {\em more general\/} than a substitution 
$\theta$ if there is a substitution $\varphi$ such that
$\theta = \sigma [\varphi]$ .
Two terms $t_1$ and $t_2$ are said to be {\em unifiable\/} if there
is a substitution $\sigma$ such that $t_1 [\sigma] = t_2 [\sigma] $;
$\sigma$ is said to be a {\em unifier\/} of $t_1$ and $t_2$.
Note that if two terms have a unifier, they have a most general
unifier ({\em mgu}) that is unique up to renaming of variables.

A {\em clause\/} is the disjunction of a finite number of literals,
and is said to be a Horn clause if it has at most one positive literal.
A Horn clause with exactly one positive literal is referred to as 
a {\em definite clause}.
The positive literal in a definite clause is its {\em head},
and the remaining literals, if any, constitute its {\em body}.
Following the syntax of Prolog, definite clauses (or {\em rules})
are written as:
\logicprog{
\lrule {} {p} {q_1, \ldots, q_n}
}
This is read declaratively as $q_1$ and $\ldots$ and $q_n$ implies $p$.
A predicate definition consists of a set of definite clauses,
whose heads all have the same predicate symbol;
a goal is a set of negative literals.
We consider a logic program to be a pair $<P,Q>$ where $P$ is a 
set of predicate definitions and $Q$ is the input, consisting
of a query, or goal, and a (possibly empty) set of facts for 
``database predicates'' appearing in the program.\footnote{
Our definitions and results can be extended to handle features
such as negation, set grouping and aggregation~\cite{bnrst:set}.}

We follow the convention in deductive database literature of separating
the set of rules with non-empty bodies from the set of 
facts, or unit clauses, which appears in $P$.
The set of facts is called the {\em database}.
Predicates appearing in the heads of rules with non-empty bodies are 
referred to as {\em derived\/} predicates, and predicates appearing in 
database facts are referred to as {\em base\/} predicates.
The program can be normalized to make the set of base predicates
disjoint from the set of derived predicates, and we assume that
this has been done.
The motivation for separating the program from the database 
is that optimizations are applied only to the program,
and not to the database.
This is important in the database context since the set of facts
can be very large.
However, the distinction is artificial, and we may choose to 
consider (a subset of) facts to be rules if we wish.

The meaning of a logic program is given by its least Herbrand 
model~\cite{ek:the}.
From \cite{ek:the}, this is equivalent to the least fixpoint semantics.
A derived predicate $p$ in a program $P$ is said to be {\em safe} if,
given any finite extension for each of the base predicates, $p$ has 
a finite extension in the least Herbrand model of $P$.

We use the notion of derivation trees and derivation steps in 
several proofs.
\begin{nameddefinition} {Derivation tree}
Given a program $P$ with database $D$, derivation trees in $<P,D>$ are
defined as follows:
\begin{itemize}
\item Every fact $h$ in $D$ is a derivation tree for itself, consisting
of a single node with label $h$.
\item Let $R$ be a rule: \mbox{$p \ifff q_1, \ldots, q_n$} in $P$,
let $d_i, 1 \leq i \leq n$, be facts with derivation trees $T_i$,
and let $\theta$ be the {\em mgu\/} of $(q_1, \ldots, q_n)$ and
$(d_1, \ldots, d_n)$.
Then the following is a derivation tree for $p [\theta]$: the
root is a node labeled with $p [\theta]$ and $R$, and each 
$T_i, 1 \leq i \leq n$, is a child of the root. 
\end{itemize}

A {\em derivation step\/} for fact $p [\theta]$ consists of a rule 
\mbox{$R: p \ifff q_1, \ldots, q_n$}, and facts $d_i, 1 \leq i \leq n$,
with derivation trees, such that $\theta$ is the {\em mgu\/} of 
$(q_1, \ldots, q_n)$ and $(d_1, \ldots, d_n)$.
Thus, a derivation step consists of a non-leaf node and all its 
children in a derivation tree.
\end{nameddefinition}

Note that the substitution $\theta$ is not applied to the children of 
$p [\theta]$ in the second part of the above definition.
Thus, a derivation tree records which set of (previously generated)
facts is used to generate a new fact using a rule, rather than
the set of substitution instances of these facts that instantiated
the rule.
Derivation trees are important due to the following well-known 
property~(see for example \cite{mr:dej})

\begin{proposition}.
For every fact $t$ in the least Herbrand model, there is a derivation tree
with root $r$, and a substitution $\sigma$ such that $t = r [\sigma]$,
and for every fact $r'$ that is the root of a derivation tree, 
each fact $t'$ that is a ground instance of $r'$ is in the least 
Herbrand model.
\end{proposition}

\begin{nameddefinition} {Derivation height}
\label{def:deriv:height}
The {\em height\/} of a derivation tree is defined to be the number
of nodes in the longest path in the tree
(which is always from the root to a leaf).

The {\em derivation height\/} of a fact is defined as the minimum
among the heights of its derivation trees.
\end{nameddefinition}

\begin{nameddefinition} {Rule application}
The {\em application\/} of a rule $ R $, using a given set of facts $D$, 
denoted by $R (D)$, produces the set of {\em all\/} facts that can be derived 
in a single derivation step, using $ R $ and only the facts in $D$.
\end{nameddefinition}

We define an {\em evaluation\/} as a sequence of rule applications.

\begin{nameddefinition} {Non-repetition property}
An evaluation is said to have the {\em non-repetition property\/} if
no derivation step is repeated in the evaluation.
\end{nameddefinition}
Note that this definition intentionally does not distinguish between
top-down and bottom-up algorithms.
%%%%%%%%%%
% QSQR~\cite{v:qsqr}, a memoing top-down algorithm, and the traditional
% ``semi-naive'' bottom-up algorithms both have this property.
%%%%%%%%%%

A fact is said to have been {\em seen\/} by a rule $R$ if the fact 
was available to an application of $R$.
The {\em independent\/} application of a set of rules 
$\{R_1, \ldots, R_n \}$ on a set of facts $D$ is defined as
$R_1(D) \cup \ldots \cup R_n(D)$;
i.e.\ each rule is applied once but the facts produced using a particular rule
application are not seen by any of the other rules in the set.
The {\em closure\/} of a set of rules $ {\cal R} = \{R_1, \ldots, R_n\}$ 
using a given set of facts $D$ refers to 
the derivation of all facts that can be computed using the given facts,
and any number of applications of the rules, i.e.\ 
\[ closure ({\cal R}, D) = D \cup F (D) \cup F^2 (D) \cup F^3 (D) \cup \ldots \]
where $F(D) = R_1(D) \cup \ldots \cup R_n (D)$.

We also use some terminology from graph theory.
A directed graph $G = (V,E)$ (where $V$ is the vertex set and
$E$ is the edge set) is said to be {\em strongly connected\/} if every 
vertex in $V$ is reachable (using the directed edges in $E$) from 
every other vertex in $V$.
Given a directed graph $G$, a subgraph $G1$ of $G$ is said to be 
a {\em strongly connected component\/} (SCC) of $G$ if $G1$ is
a maximal subgraph in $G$ that is strongly connected.
Note that the SCCs of a directed graph $G$ partition the vertices of $G$.
Define the {\em reduction\/} of $G$ wrt the SCCs as the graph
$G' = (V',E')$ obtained with vertex set $V'$ being the set of SCCs 
$\{ S_1, \ldots, S_k \}$ of $G$.
An edge $( S_i, S_j ), i \neq j, \in E'$ if there is an edge 
$(V_k, V_l) \in E$, where $V_k$ is a vertex in $S_i$ and 
$V_l$ is a vertex in $S_j$.
The reduction $G'$ of $G$ reflects the SCC structure of $G$, and is acyclic.
An SCC $S_1$ is said to be {\em lower\/} than SCC $S_2$ in $G$ if
there is a (non-trivial) path from $S_1$ to $S_2$ in $G'$.

\begin{nameddefinition} {Rule (predicate) graph}
Given a program $P$ with rules $ {\cal R} = 
\{ R_{1} , R_{2} , \ldots , R_{n} \} $,
we define the {\em rule graph\/} of $P$ as the directed graph
$ G = ( {\cal R} , E ) $, where $ ( R_{i} , R_{j} ) \in E $ iff the head of 
$ R_{i} $ unifies with a predicate occurrence in the body of $ R_{j} $.
We refer to SCCs in the rule graph as {\em Rule-SCCs}.

Given a program $P$ with predicates 
$Pred = \{ p_{1} , p_{2} , \ldots , p_{n} \}$,
we define the {\em predicate graph\/} of $P$ as the directed graph
$ G = ( Pred , E ) $, where $ ( p_{i} , p_{j} ) \in E $ iff 
$ p_{i} $ occurs in the body of a rule defining $ p_{j} $.
We refer to SCCs in the predicate graph as {\em Pred-SCCs}.
\end{nameddefinition}
Where the distinction is not relevant, we refer to Rule-SCCs and 
Pred-SCCs as SCCs.

Given a program $P$, Pred-SCCs $S_1, \ldots, S_m$ are
said to be in {\em topological order}, if whenever $S_i$ contains
a predicate used in $S_j$, then $i \leq j$.

\subsection{Basic Semi-Naive Evaluation}
\label{basic:sn}

Given a program $P$ with an input database $D$, the
{\em Naive evaluation\/} of $<P,D>$ proceeds in iterations.
In each iteration, each of the rules in the program is independently
applied on the set of available facts, and the set of available facts
is updated at the end of the iteration.
The Naive evaluation terminates when no new facts can be computed for
any of the derived predicates of the program.
The database $D$ constitutes the initial set of available facts.
This evaluation strategy can be refined by evaluating one strongly
connected component (SCC) of the rule graph at a time, in a topological 
ordering of the Rule-SCCs.
The Naive evaluation of a program on a database is extremely inefficient
since it repeats a lot of derivations;
each derivation step made in an application of a rule is repeated 
in every subsequent application of the same rule.
Example~\ref{ex:n:sn} below illustrates this.

\begin{example}
\label{ex:n:sn}
Consider the following program $<P,Q>$:
\logicprog{
\lfact {F1:} {par(1,2)} \\
\lfact {F2:} {par(2,3)} \\
\lfact {F3:} {par(4,5)} \\
\lrule {R1:} {anc(X,Y)} {par(X,Y)} \\
\lrule {R2:} {anc(X,Y)} {par(X,Z), anc(Z,Y)} \\
\lrule {R3:} {anc(X,Y)} {anc(X,Z), anc(Z,Y)} \\
\lquery {anc(1,X)}
}

\begin{table}
\centerline{
\begin{tabular}{|c|l|} \hline
{\em Iteration} & {\em Derivations made} \\ \hline
1 & $\{ {\bf R1:anc(1,2)}, {\bf R1:anc(2,3)}, {\bf R1:anc(4,5)} \}$ \\ \hline
2 & $\{ {\bf R2:anc(1,3)}, {\bf R3:anc(1,3)}, R1:anc(1,2), 
R1:anc(2,3), R1:anc(4,5) \} $ \\ \hline
3 & $\{ R2:anc(1,3), R3:anc(1,3), R1:anc(1,2), R1:anc(2,3), R1:anc(4,5) \} $
\\ \hline
\end{tabular}
}
\caption{Derivations in a Naive Evaluation of $P$}
\label{table:naive}
\end{table}

A naive bottom-up evaluation (\cite{b:nai}) of $<P,Q>$ would result in the 
derivations of $anc$ facts as shown in Table~\ref{table:naive}.
(The rule used to derive a fact is also indicated, and new derivations 
are shown in bold-face.)
Only $anc(1,2)$ and $anc(1,3)$ are answers to the query.
Note that each derivation made in an iteration of naive evaluation 
is repeated in subsequent iterations.
\end{example}

Recall that an evaluation is said to have the non-repetition property if no 
derivation step is repeated in the evaluation.
A number of researchers including \cite{b:nai,b85:qeddb:sn,br:adijlp}
independently proposed an evaluation technique, which we call 
{\em Basic Semi-Naive}, or BSN, that has the non-repetition property.
Given a program $ P $, the {\em Basic Semi-Naive\/} (BSN) evaluation 
of $P$ proceeds a Pred-SCC at a time in a topological ordering
of the SCCs.
There are essentially two components to the BSN evaluation of a Pred-SCC.

\begin{enumerate}
\item The first is a rewriting of the Pred-SCC $S$ that
defines ``differential'' versions of predicates,
in order to distinguish facts that have been newly generated (and not yet
used in inferences) from older facts.

For each predicate $p$ defined in $S$, we have four predicates
$p, p^{old}, \delta p^{old}$ and $\delta p^{new}$.
For each rule in $S$ of the form:
\logicprog{
\lrule {R:} {p} {q_{1} , \ldots , q_{m}}
}
where $ q_{1} , \ldots q_{m} $ are all non-recursive to $p$,
the following semi-naive rewritten rule is obtained (\cite{br:adijlp}) 
from $R$:
\logicprog{
\lrule {R_1:} {\delta p^{new}} {q_{1} , \ldots , q_{m}}
}
We call such rules {\em non-recursive\/} semi-naive rules.

For each rule in $S$ of the form:
\logicprog{
\lrule {R:} {p} {p_{1} , \ldots , p_{n} , q_{1} , \ldots , q_{m}}
}
where $ p_{1} , \ldots , p_{n} $ ($n>0$) are mutually
recursive to $ p $ and $ q_{1} , \ldots q_{m} $ are not, the following
$n$ semi-naive rewritten rules are obtained (\cite{br:adijlp}) from $R$:
\logicprog{
\lrule {R_1:} {\delta p^{new}} {\delta p_1^{old}, 
p_2, \ldots, p_n, q_{1} , \ldots , q_{m}} \\
\lrule {R_2:} {\delta p^{new}} {p_1^{old}, \delta p_2^{old}, 
p_3, \ldots, p_n, q_{1} , \ldots , q_{m}} \\
 & \vdots \\
\lrule {R_n:} {\delta p^{new}} {p_1^{old}, p_2^{old}, \ldots,
p_{n-1}^{old}, \delta p_{n}^{old}, q_{1} , \ldots , q_{m}}
}
We call such rules {\em recursive\/} semi-naive rules.

\item The second component is a technique to apply the rewritten rules
and update these differentials, ensuring that
all derivations are made exactly once.

In evaluating $ S $, the first iteration consists of applying 
each of the semi-naive (both non-recursive and recursive)
rewritten rules in $ S $.
Subsequent iterations consist of applying only the recursive semi-naive rules.
The evaluation of $ S $ proceeds by iterating until no new facts are 
computed for any of the predicates defined in $ S $.
After applying the semi-naive rules in an iteration, 
the extensions of the semi-naive relations for each $ p_{i} $ are
updated using Procedure {\sf SN\_Update} below.
(Note that the operators ``$ - $'' and ``$\cup$'' involve
subsumption checks if non-ground facts are generated.)
\end{enumerate}

\algorithm{
\> procedure SN\_Update($ p_{i} $) \\
\> $\{$ \\
\> \> $ p_{i}^{old} := p_{i}^{old} \cup \delta p_{i}^{old} $. \\
\> \> $ \delta p_{i}^{old} := \delta p_{i}^{new} - p_{i}^{old} $. \\
\> \> $ p_i := p_i^{old} \cup \delta p_i^{old}$. \\
\> \> $ \delta p_{i}^{new} := \phi $. \\
\> $\}$ \\
\> end SN\_Update
}

At every stage of the evaluation, the set of relations $ p_{i}^{old} $, 
for all $ i $, has the property that every derivation that uses only 
these facts has been made.
This can be seen from the nature of the 
$\delta$ terms in rule bodies, and the order of updates of the 
various semi-naive relations.

\begin{table}
\centerline{
\begin{tabular}{|c|l|} \hline
{\em Iteration} & {\em Derivations made} \\ \hline
1 & $\{ {\bf R1:anc(1,2)}, {\bf R1:anc(2,3)}, {\bf R1:anc(4,5)} \}$ \\ \hline
2 & $\{ {\bf R2:anc(1,3)}, {\bf R3:anc(1,3)} \} $ \\ \hline
3 & $\{ \} $ \\ \hline
\end{tabular}
}
\caption{Derivations in a BSN Evaluation of $P$}
\label{table:semi-naive}
\end{table}

\begin{example}
Consider again the program $P$ of Example~\ref{ex:n:sn}.
Using BSN, the sequence of derivations made is shown 
in Table~\ref{table:semi-naive}.
Note that each derivation made in the naive evaluation is also made in 
the BSN evaluation.
However, the BSN evaluation does not repeat any derivations.
But if a fact ($anc(1,3)$ in this case) is derived by two 
{\em different\/} derivations, each of these derivations is made in the
BSN evaluation.

Such ``redundant'' derivations can be avoided by recognizing
that every fact derived using rule $r2$ is also derived using $r3$ 
and vice versa.
Consequently, a scheme that prunes redundant derivations (\cite{h:det}, for
instance) could recognize this and never apply rule $R3$;
the derivation of $R3:anc(1,3)$ is not made in such a case.
Given a program that has redundant derivations, its evaluation using
BSN does {\em not\/} eliminate such derivations.

Rewriting the program $P$ of Example~\ref{ex:n:sn} using Magic Sets,
and evaluating the rewritten program also
results in avoiding the derivation of $anc(4,5)$, since
this is ``irrelevant'' to computing the answers to the query.
Refer to \cite{br:ont,r:mag} for more details.
\end{example}

\subsection{Control Expressions}
\label{control}

Helm~\cite{h:ind,h:det} introduced the notion of control on 
the bottom-up evaluation of logic programs using control expressions, and 
also looked at control as a way of increasing the efficiency of evaluation 
by eliminating some redundant derivations.
Control expressions have also been proposed to let the user specify 
a desired semantics in the presence of negation (\cite{in88:control}),
as well as evaluate the Magic Sets transformation of stratified logic 
programs (\cite{brss89:strat}).
While applications of control expressions have been considered, not much
attention has been given to efficient implementation of control expressions.

Let $ R_{1}, \ldots, R_{n} $ denote the rules of a program.
The syntax of our control expressions is given by the following grammar.
\begin{eqnarray*}
S & \rightarrow & T \\
T & \rightarrow & F \mid F + T \mid F \oplus T \mid F \cdot T \\
F & \rightarrow & R_{i} \mid ( T ) \mid F^{\ast} \mid F^{\bullet}
\end{eqnarray*}
where $S$ is the start symbol of the grammar.

A control expression $\alpha$ is a (non-deterministic)
mapping ${\cal D} \rightarrow {\cal D}$, where $\cal D$ is the set of all
database states. (A database state is a set of facts for the base
and derived predicates.)
The initial database state consists of the set of all given facts
for the base predicates.
The following equations recursively define the semantics
of control expressions.

\begin{enumerate}
\item If $\alpha = R_i$, $\alpha (D) = D \cup R_i (D)$.

\item If $\alpha = \alpha_1 \cdot \alpha_2$,
$\alpha (D) = \alpha_2 ( \alpha_1 (D))$.

\item If $\alpha = \alpha_1 \oplus \alpha_2$,
non-deterministically choose $ \alpha_1$ or $ \alpha_2$ and call it
$ \beta_1 $ and call the other $ \beta_2$.
if $\beta_1 (D) \neq D$, $\alpha (D) = \beta_1(D)$,
else $ \alpha (D) = \beta_2(D)$.

\item $\alpha = \alpha_1^{\bullet}$,
$\alpha (D) = \alpha_1^i (D)$, for some arbitrary choice of $ i \geq 0 $,
where $\alpha^0 (D) = D$ and $\alpha^{j+1}(D) = \alpha (\alpha^j(D)),
j \geq 0$.

\item If $\alpha = \alpha_1^{\ast}$, $\alpha(D) = \alpha_1^i (D), i > 0$,
such that $\alpha_1^{i+1} (D) = \alpha_1^i (D)$,
where $\alpha^0 (D) = D$ and $\alpha^{j+1}(D) = \alpha (\alpha^j(D)),
j \geq 0$.

\item If $\alpha = \alpha_1 + \alpha_2$,
$\alpha (D) = \alpha_1(D) \cup \alpha_2 (D)$.
\end{enumerate}
The semantics of the control operators that we consider
are different from those considered by Helm and we do not discuss the
evaluation of Helm's control operators in this paper.

The control expressions we use form a superset of those used by 
Imielinski and Naqvi~\cite{in88:control}.
It follows from \cite{in88:control} that our control expressions can be 
used to specify the inflationary semantics for negation~(\cite{kp88:inflate}).
Our control expressions also form a superset of those used by
Beeri et al.~\cite{brss89:strat}.

%%%%%%%%%%%%%%%
% An inflationary mapping $\alpha: {\cal D} \rightarrow {\cal D}$ is 
% such that $\forall D \in {\cal D},~\alpha (D) \supseteq D$.
% \begin{proposition}
% \label{prop:ce:infl}
% Control expressions are inflationary mappings
% from database states to database states.
% \end{proposition}
%%%%%%%%%%%%%%%

\section{Related Work}
\label{related:work}

The idea of semi-naive evaluation (also referred to as differential evaluation)
dates back several years and has been independently rediscovered many times.
The concept appears in Fong and Ullman~\cite{fu76:indvar:sn}
and in Paige and Schwartz~\cite{ps77:red:sn}.
In the area of deductive database systems the idea appears independently in 
Bayer~\cite{b85:qeddb:sn}, Bancilhon~\cite{b:nai} and 
Balbin and Ramamohanarao~\cite{br:adijlp}.
Apt~\cite{apt88:ecfix:sn} sets up fixpoint computation in a formal setting,
and systematically derives the Basic Semi-Naive algorithm.

Gonzalez-Rubio, Rohmer and Bradier~\cite{grb87:ddc} present a technique
for parallelizing semi-naive evaluation.
Their technique has some interesting connections to one of 
our techniques (GSN).
We defer a discussion of the connections until Section~\ref{sec:gsn:rw}
so that we can refer to details of GSN evaluation in the discussion.

Schmidt et al.~\cite{skgb87:sloppy} present a scheme for ordering facts 
in a semi-naive evaluation. 
In some contexts it is beneficial to prioritize the use of facts.
For instance, when evaluating Quantitative logic programs~\cite{shap83:quant},
it is beneficial to use facts with higher certainities first, and delay the
use of other facts until there is no unused fact with higher certainity.
The idea behind semi-naive evaluation is to partition facts in each
relation $ p $ into those
that have been ``seen'' by all rules (the $p^{old}$ relations)
and those that have not been used in
some rule applications yet (i.e, the $ \delta p $ relations).
The Sloppy Delta iteration technique of 
Schmidt et al., instead partitions each relation $ p $ into three parts.
There is a $ p^{old} $ as before, the $ \delta p $ relation holds a set of 
facts that has not yet been used in some rule application, but will
be used in rule applications during the current iteration, and there is a 
third set of facts that are ``hidden'' and cannot be used until they
are made visible (by some meta-level control).
When a hidden $ p $ fact is made visible, it is moved into the 
$ \delta p$ relation as if it was newly derived.
This technique is orthogonal to the ordering of rules, and can be 
used in conjunction with the techniques described in this paper.

Transitive closure is an important special case of recursion in deductive 
databases.
Ioannidis \cite{i86:tc} and Valduriez and Boral \cite{vb86:tc}
present algorithms for computing the transitive closure 
that perform significantly fewer joins and take fewer iterations
than the traditional iterative algorithm, without performing
redundant computation.
Valduriez and Khoshafian \cite{vk88:tc} present a technique for 
parallelizing a differential computation of the transitive closure
without performing redundant computation.
Lu~\cite{lu:tc} and Kabler et al.~\cite{kabler:tc}
considered how facts could be (partially) utilized in the
same iteration that they were generated, in the context of transitive
closure algorithms, and noted that this reduced the number of disk accesses.
However, all these papers make use of special properties of transitive
closure.
For example, the ``Smart'' algorithm of \cite{i86:tc,vb86:tc} 
does not permit selections in the rules that define the transitive closure. 
It is not clear whether it is possible to or how to generalize these 
algorithms beyond transitive closure.

Schmidt~\cite{schmidt91:metacontrol} presents an evaluation technique 
that allows for some ordering of rules; however, this technique lacks 
the non-repetition property, and repeats derivations.
This can adversely affect performance. 
Further, it makes the algorithm inapplicable
when the non-repetition property is used to perform further optimizations.
(For example, if a program has the {\em duplicate-freedom\/} property,
a fixpoint algorithm with the non-repetition property can be modified easily
to eliminate run-time checks for duplicates \cite{mr:dej}.)

Kuittinen et al.~\cite{sippu90:eval} 
proposed a fixpoint evaluation algorithm for logic programs
based on the immediate utilization of facts.
Their algorithm also reduces the number of iterations, and is
dependent upon a choice of rule orderings. 
They present a performance study of the effects of rule orderings, 
although they do not analyze the effect of rule orderings theoretically.
The results presented in our paper and in \cite{sippu90:eval} were
obtained independently. 
(However, we have drawn upon and extended their performance evaluation.)
Although the technique of Kuittinen et al.\ avoids repeating most derivations, 
it does not have the non-repetition property since it is possible for some 
derivations to be repeated.
Further, their technique handles only a subset of the rule orderings that 
GSN can handle.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{General Semi-Naive Evaluation}
\label{gen:sn}

We now present a technique, {\em General Semi-Naive\/}, or GSN, evaluation,
that makes facts computed by an application of a rule $R$ available to
{\em all\/} other rule applications immediately after the application of $R$,
while maintaining the non-repetition property.
We first look at how to apply a single rule using the GSN technique.
Then, in Section~\ref{gensn:control}, we look at how to evaluate 
general control expressions using this technique.
Finally, in Section \ref{gsn:prog}, we look at a specific
form of control expression to evaluate a program Pred-SCC by Pred-SCC,
in a topological ordering of the Pred-SCCs.

\subsection{GSN for a Rule}
\label{gsn:rule}

Consider any rule $R_i$ in the program:
\logicprog{
\lrule {R_i:} {p_h(\overline{t})} {p_1(\overline{t_1}), \ldots, 
p_n(\overline{t_n})}
}
where $p_h, p_1, \ldots, p_n$ are not necessarily distinct.
Similar to BSN evaluation, the GSN evaluation of a rule consists of
two components.

\begin{enumerate}
\item The first is the semi-naive rewriting that defines the 
``differential'' versions of predicates.

Associated with each rule $ R_{i} $ of the program, and each
(non-recursive as well as recursive) predicate $ p_{j} $ that occurs 
in the body of $ R_{i} $, we maintain a relation $ p_{j,R_{i}}^{old} $.
(Even if a predicate occurs more than once in the body of $R_i$, only
one copy of the relation needs to be maintained per rule.)
The set of relations $ p_{j,R_{i}}^{old} $,
$1 \leq j \leq n$, has the property that every derivation that can be made
by an application of $ R_{i} $ using only these facts has already been made.
(In this respect, it is similar to the $p^{old}$ relations 
maintained by BSN.)

Associated with each predicate $ p_{j} $, we also maintain its complete
extension; only one copy of $p_j$ needs to be maintained independent of the 
number of rules $p_j$ occurs in.
We also have ``temporary'' relations $ \delta p_{j}^{new} $ and
$ \delta p_{j}^{old} $ associated with each derived predicate $ p_{j} $
that appears in the program.
These $\delta$ relations are used to keep track of ``new'' facts;
facts which have not been seen by a rule application.

The semi-naive rewriting for GSN is obtained as follows.
Each predicate $p_j$ in the body of $R_i$ is treated as being
recursive to the head.
The semi-naive rewriting described for BSN (in Section~\ref{basic:sn})
is modified by replacing each predicate occurrence $ p_{j}^{old} $
in the body of the semi-naive rewritten versions of rule $ R_{i} $
by $ p_{j,R_{i}}^{old} $.

\item The second is a technique to apply the rewritten rules
and update these differentials in the order specified for rule
applications, ensuring that all derivations are
made exactly once.
Procedure {\sf GSN\_Rule} below describes the application of a rule $R_i$
on a set of facts $D$.
\end{enumerate}

\algorithm{
\> procedure GSN\_Rule($ R_i,D $) \\
\> $\{$ \\
\> \> /* All relations mentioned below are part of $D$. */ \\
\> \> Let $ p_{h} $ be the predicate defined by rule $ R_i $. \\
\> \> (1) For every predicate $ p_{j} $ in the body of $ R_i $ \\
\> \> \> $ \delta p_{j}^{old} := p_{j} - p_{j,R_i}^{old} $. \\
\> \> (2) $ \delta p_{h}^{new} := \phi $. \\
\> \> (3) Apply each semi-naive rewritten version of $ R_i $ \\
\> \> \> (modified as described earlier) independently. \\
\> \> (4) For every predicate $ p_{j} $ in the body of $ R_i $, ~~~
$ p_{j,R_i}^{old} := p_{j} $. \\
\> \> (5) $p_h := p_h \cup \delta p_{h}^{new}$. \\
\> \> (6) return $\delta p_{h}^{new} $. \\
\> $\}$ \\
\> end GSN\_Rule 
}

\begin{example}
Consider rule $R3$ from $P$ in Example~\ref{ex:n:sn}.
\logicprog{
\lrule {R3:} {anc(X,Y)} {anc(X,Z), anc(Z,Y)}
}
The semi-naive rewriting of this rule for GSN evaluation is given by:
\logicprog{
\lrule {R3':} {\delta anc^{new}(X,Y)} {\delta anc^{old} (X,Z), anc(Z,Y)} \\
\lrule {R3'':} {\delta anc^{new}(X,Y)} {anc_{R_3}^{old} (X,Z), 
\delta anc^{old}(Z,Y)}
}
Prior to the application of these rules, $\delta anc^{old}$
is initialized to $anc - anc_{R_3}^{old}$, i.e.\ the tuples
that have not been seen as yet by an application of $R_3$.
The relation $\delta anc^{new}$ is initialized to $\phi$.
Application of rules $R3'$ and $R3''$ (potentially) results in
adding facts to the $\delta anc^{new}$ relation.
After the application of this rule, each fact in
$\delta anc^{old}$ also has been seen by $R_3$.
Consequently, the $anc_{R_3}^{old}$ relation is updated to reflect this.
The newly generated facts are also added to the $anc$ relation.

Example~\ref{ex:n:sn:gsn} describes the order in which rules are
applied (and relations updated) in the GSN evaluation of program $P$.
\end{example}

\subsection{Efficient Implementation of GSN}
\label{gsn:efficient}

The description of General Semi-Naive above suggests that each rule has to
separately maintain an extension for each predicate that occurs in its body
and would thus appear to be inefficient in terms of the storage used.
However, it has a simple implementation in which 
each relation is maintained as a list of tuples.
The new facts produced by a rule application are appended to the extension of
the predicate. 
(In the case of generalized tuples, if a new fact
subsumes an existing fact then the existing fact may have to be deleted.)

In step (4) of {\sf GSN\_Rule($R_i,D$)}, every fact 
in a relation $p_j$ becomes part of $ p_{j,R_{i}}^{old} $.
Since the tuples in each relation $p_j$ are ordered by ``time'' of 
insertion, a pointer to the end of the extension of $p_j$ at step (4)
has the following property:
every $p_j$ fact preceding the pointer is part of $ p_{j,R_{i}}^{old} $,
and every $p_j$ fact occurring after the pointer has not been 
seen by rule $R_i$ yet.
Hence, the extension of each $ p_{j,R_{i}}^{old} $ is replaced by a 
pointer into the extension of $ p_{j} $.
Similarly, we replace the extension of each
$ \delta p_{j}^{old} $ by another pointer into the extension of $ p_{j} $
such that the set of facts between the pointers for $ p_{j,R_{i}}^{old} $ and
$ \delta p_{j}^{old} $ constitutes the extension for $ \delta p_{j}^{old} $.
The set of facts beyond the pointer for $ \delta p_{j}^{old} $ constitutes
the extension of $ \delta p_{j}^{new} $.
Thus, separate extensions of a predicate do not have to be maintained
for each rule, and the need for set difference to compute the
$ \delta p_{j}^{old} $ relations is also eliminated.

Indices are important for efficiently accessing a relation during evaluation.
The pointers into the extent of a relation $ p_j $ partition it
based on the order of insertion of tuples.
Each of the relations $p_{j,R_{i}}^{old}$, $\delta p_{j,R_{i}}^{old}$
and $\delta p_j^{new}$ is the union of a contiguous set of these partitions.
To index any of these relations, we index in turn
each partition that is contained in it.
Since there is at most one pointer per rule into $ p_j $, the number of
partitions is bounded by the number of rules in the program.
There are two operations on pointers into the relation.
The first is the creation of a new pointer to the end of a relation,
and the second is the deletion of a pointer into a relation.
In the first case a new partition is created (and is initially
empty), and in the second case two existing partitions get merged.
This involves moving tuples from the indices of one partition to the
indices of the other.
However, each tuple is moved in this fashion only a constant number of times,
and hence this will not increase the time complexity of evaluation.
Thus, this indexing technique can be expected to provide efficient access
to tuples.
(Alternatively, we could index each of the relations
$p_{j,R_{i}}^{old}$, $\delta p_{j,R_{i}}^{old}$ and $\delta p_j^{new}$
separately.  This could result in each tuple being indexed multiple
times.)

\subsection{Implementing Control Expressions Using GSN}
\label{gensn:control}

The semantics of control expressions was described (using 
recursive equations) in Section~\ref{control}.
This description also suggests a straightforward way of evaluating 
control expressions, and Procedure~{\sf Simple\_CE($\alpha, D$)} below 
describes this.
In this evaluation, every fact produced by a rule application on a 
given database is immediately added to the database, and made 
available to subsequent rule applications.
Unfortunately, such an evaluation does not have the non-repetition 
property, and can be extremely inefficient.

\algorithm{
\> procedure Simple\_CE($\alpha, D$) \+ \\
$\{$ \+ \\
/* We need to evaluate control expression $\alpha$ on database $D$. */ \\
case \+ \\
(1) $\alpha = R_i$: \> \> \> /* the exit case */ \+ \+ \\
  return $D \cup R_i (D).$ \- \- \\
(2) $\alpha = \alpha_1 \cdot \alpha_2$: \+ \+ \\
  return Simple\_CE($\alpha_2$, Simple\_CE($\alpha_1, D$)). \- \- \\
(3) $\alpha = \alpha_1 \oplus \alpha_2$: \+ \+ \\
  Non-deterministically choose $ \alpha_1$ or $ \alpha_2$ and call it
  $ \beta_1 $ and call the other $ \beta_2$.\\
  if Simple\_CE($\beta_1, D$) $\neq D$, 
  return Simple\_CE($\beta_1, D$) \\
  else return Simple\_CE($ \beta_2, D$). \- \- \\
(4) $\alpha = \alpha_1^{\bullet}$: \+ \+ \\
  Choose $n \geq 0$ non-deterministically. \\
  for $i = 1$ to $n$ do \+ \\
    Let $D$ denote the result of evaluating Simple\_CE($\alpha_1, D$). \- \\
  end for \\
  return $D$. \- \- \\
(5) $\alpha = \alpha_1^{\ast}$: \+ \+ \\
  repeat \+ \\
    Let $D'$ denote $D$ at this stage. \\
    Let $D$ denote the result of evaluating Simple\_CE($\alpha_1, D$). \- \\
  until ($D = D'$) \\
  return $D$. \- \- \\
(6) $\alpha = \alpha_1 + \alpha_2$: \+ \+ \\
  return Simple\_CE($\alpha_1, D$) $\cup$ Simple\_CE($\alpha_2 ,D$). \- \- \- \\
end case \- \\
$\}$ \\
end Simple\_CE \-
}
Note that Procedure~{\sf Simple\_CE} is non-deterministic in that
the final database state may not be uniquely determined if 
the control expression contains $\oplus$ or $^{\bullet}$.

Since a control expression is a non-deterministic mapping,
we use $\{ {\sf Semantics} (\alpha, D) \}$ to denote the set of all
possible database states that are results of $\alpha (D)$.
Similarly, we use $ \{ {\sf Simple\_CE}(\alpha,D) \} $ to 
denote the set of all possible results of the procedure
$ {\sf Simple\_CE}(\alpha,D)$.

\begin{theorem}
\label{thm:sem:simple:ce}
For all databases $D$, and control expressions $\alpha$,
\[ \{ {\sf Simple\_CE} (\alpha,D) \} = \{ {\sf Semantics} (\alpha, D) \} \] 
\end{theorem}

\begin{proof}
The proof follows in a straightforward manner from the direct correspondence 
between each case in the semantics of control expressions and 
Procedure~{\sf Simple\_CE}.
\end{proof}

Consider the restricted set of control expressions generated by the grammar
described in Section~\ref{control} without the production that uses the
``$+$'' operator.
Procedure~{\sf GSN\_CE ($\alpha, D$)} below describes how we can 
evaluate such a control expression while preserving the 
non-repetition property.

\algorithm{
\> procedure GSN\_CE($\alpha, D$) \+ \\
$\{$ \+ \\
$\alpha$ is a control expression and $D$ is an initial database. \\
/* $D$ contains the $p_j$ as well as all $p_{j,R_i}^{old}$ relations. */ \\
case \+ \\
(1) $\alpha = R_i$: \\
\> \> return $D \cup {\sf~GSN\_Rule}(R_i, D)$. \\
\vdots \\
\> /* Cases (2)-(5) remain unchanged from Simple\_CE($\alpha, D$). */ \- \\
end case \- \\
$\}$ \\
end GSN\_CE \-
}

The updates to the various differential relations (corresponding
to the predicates occurring in the head and body of rule $R_i$) performed by
{\sf GSN\_Rule} maintain the set of facts that have been used by the 
rule $R_i$ in previous applications of $R_i$.
This ensures that in subsequent applications of $R_i$, none of the 
previous derivations is repeated.
Intuitively, each rule in the program individually ensures that 
its applications have the non-repetition property;
we prove this claim formally in Theorem~\ref{thm:gsnce:cor}.
First we need the following proposition and its corollary.

\begin{proposition}
\label{prop:nce:seq}
Suppose a control expression $ \alpha $ does not use the operator ``$+$''. 
Given a database $ D $, any evaluation of {\sf Simple\_CE}$(\alpha,D) $
performs a sequence of rule applications; 
each rule application in the sequence takes as input the 
set of all facts derived up to the previous rule application in the 
sequence. 
\noBox
\end{proposition}

\begin{proof}
We prove this by induction on the size of the control expression.
For the base case, when the control expression consists of a single rule, 
this is trivial.
For the induction step, assume that this is true for all control expressions
of size less than $ n $, and consider a control expression $ \alpha $
of size $ n $.
The evaluation of $ \alpha $ can be according to one of
cases (2), (3), (4) or (5) of Procedure {\sf Simple\_CE}.
In each of the cases, it is easily seen from the induction hypothesis that 
the claim is true of $ \alpha $.
This proves the claim. 
\end{proof}

As a corollary to the above proposition, we have the following:
\begin{corollary}
\label{cor:gsnce:seq}
Suppose a control expression $ \alpha $ does not use the operator ``$+$''.
Given a database $ D $, any evaluation of {\sf GSN\_CE}$(\alpha,D) $
performs a sequence of calls to {\sf GSN\_Rule};
each call takes as input the set of all facts derived up to the previous 
call in the sequence.
$\Box$
\end{corollary}

Since {\sf GSN\_CE} is a non-deterministic procedure, we use 
$ \{ {\sf GSN\_CE} (\alpha,D) \} $ to denote the set of all 
possible results of $ {\sf GSN\_CE} (\alpha,D) $.

\begin{theorem}
\label{thm:gsnce:cor}
For all databases $D$, and control expressions $\alpha$
that have no occurrence of the ``$+$'' operator, 
\[
\{ {\sf GSN\_CE} (\alpha,D) \} = \{ {\sf Simple\_CE} (\alpha,D) \} 
\]
Further, evaluations of {\sf GSN\_CE} have the non-repetition property.
\end{theorem}

\begin{proof}
By Proposition~\ref{prop:nce:seq} and Corollary~\ref{cor:gsnce:seq}, 
{\sf Simple\_CE} (resp.\  {\sf GSN\_CE})
evaluations of control expressions that do not contain ``$+$''
perform a sequence of rule applications (resp.\ calls  to
{\sf GSN\_Rule}).

We first prove three properties of a sequence of calls to {\sf GSN\_Rule}.
Consider a particular call to {\sf GSN\_Rule}$(R_{i},D) $ in this
sequence of calls.\\
{\bf P1.} Before step (3) of {\sf GSN\_Rule}, for each predicate
$ p_{j} $ occurring in the body of $ R_{i} $, the set of facts
$ \delta p_{j}^{old} = p_{j} - p_{j,R_{i}}^{old} $ has not been seen by
$ R_{i} $.\\
{\bf P2.} Before step (3) of {\sf GSN\_Rule}, every derivation that could be
made by an application of $ R_{i} $ using only the facts in the set of 
relations $ p_{j,R_{i}}^{old} $, for all $ j $, has already been made.\\
{\bf P3.} After step (3) (but before step (5) where $p_h$ is updated)
of {\sf GSN\_Rule}, every derivation that could
be made using $ R_i $ and only the facts in the set of relations 
$ p_{j} $, for all $ j $, has been made. 

We prove these by induction on the number of times {\sf GSN\_Rule($R_i, \_$)}
is called.
Before the first call to {\sf GSN\_Rule($R_i, \_$)},
$ p_{j,R_{i}}^{old} $ is empty for all $ p_{j} $ in the body of $ R_{i} $.
The call to {\sf GSN\_Rule($R_i, \_$)} computes all facts that can be derived
from the given set of facts for the body predicates.
Hence, {\bf P1} and {\bf P2} are true before step (3) and {\bf P3} is
true after step (3), and the basis holds.

For the induction step, assume that {\bf P1}, {\bf P2}, and {\bf P3} hold
up to the $ k $th call to {\sf GSN\_Rule($R_i, \_$)}, and consider 
the $ k + 1 $th call to {\sf GSN\_Rule($R_i, \_$)}.
Steps (4) and (5) of {\sf GSN\_Rule} in the $ k $th call to
{\sf GSN\_Rule($R_i, \_$)}, and step (1) in the $ k + 1 $th 
call to {\sf GSN\_Rule($R_i, \_$)} ensures {\bf P1}.
Since {\bf P3} holds in the $ k $th call to 
{\sf GSN\_Rule($R_i, \_$)}, step (4) guarantees that {\bf P2} holds 
in the $ k + 1 $th call to {\sf GSN\_Rule($R_i, \_$)}.
Since {\bf P2} holds in the $ k+1$th call to {\sf GSN\_Rule($R_i, \_$)}, 
step (1) and the correctness 
of semi-naive rewriting ensures that {\bf P3} holds in the $ k+1$th 
call to {\sf GSN\_Rule($R_i, \_$)}.
This completes the proof of {\bf P1}, {\bf P2}, and {\bf P3}.

The GSN evaluation of a control expression without any occurrence of the 
``$ + $'' operator proceeds sequentially and does not have any parallel
branches;
databases never need to be merged and, hence, for each predicate 
$ p $ and each rule $ R $
that uses $ p $, the relations $ p^{old}_R $ and $ \delta p^{old} $ are
well defined.
Property {\bf P1} then ensures that no derivations using any rule $ R $ are 
repeated and hence evaluations of {\sf GSN\_CE} (for control expressions
without the ``$+$'' operator) have the non-repetition property.

\noindent {\bf Claim 1:}
Consider a particular evaluation of {\sf Simple\_CE}$(\alpha,D)$
(where the choices, if any, due to occurrences of the $\oplus$ 
or $^{\bullet}$ operators, have been made).
Then, there is an equivalent evaluation of {\sf GSN\_CE}$(\alpha,D)$.

\noindent
{\bf Proof of Claim 1:}
By Proposition~\ref{prop:nce:seq}, the evaluation of 
{\sf Simple\_CE}$(\alpha,D)$ performs a 
sequence of rule applications.
Now replace each rule application $ R_i(D) $ in this sequence by a call to
${\sf GSN\_Rule}(R_i,D)$.
By property {\bf P3} above, after the call every derivation that could be 
made using $ R_i $ and only the facts in $D $ has been made.
Therefore, at this point, every fact that would be derived by $ R_i(D) $ has 
already been derived.
Hence, at each point in the modified evaluation, 
the set of facts that has been derived is exactly the same as that derived
by the evaluation of {\sf Simple\_CE}$(\alpha,D)$.

We claim that the modified evaluation is a possible evaluation 
of {\sf GSN\_CE}$(\alpha,D)$.
After each call to {\sf GSN\_Rule} the set of available facts is the
same as the set of facts available after the corresponding 
rule application in the evaluation of {\sf Simple\_CE}.
Hence, whatever choice was made by {\sf Simple\_CE} at any point in the
evaluation can also be made by an evaluation of {\sf GSN\_CE}.
Hence, the resultant evaluation is a valid evaluation of 
{\sf GSN\_CE}$(\alpha,D)$.

\noindent {\bf Claim 2:}
Consider a particular evaluation of {\sf GSN\_CE}$(\alpha,D)$
(where the choices, if any, due to occurrences of the $\oplus$
or $^{\bullet}$ operators, have been made).
Then, there is an equivalent evaluation of {\sf Simple\_CE}$(\alpha,D)$.

\noindent{\bf Proof of Claim 2:}
The proof proceeds exactly the same as the proof of Claim 1, and we omit the
details.

This ends the proof of the theorem.
\end{proof}

Evaluating control expressions that contain the ``$ + $'' operator using
the GSN evaluation technique presents some difficulties.
Recall that the evaluation of the ``$ + $'' operator involved
merging the two databases obtained by evaluating the operands of the
``$ + $'' operator independently on the input database.
Merging the $ p_{j,R_{i}}^{old} $ relations produced by the two
operands of the ``$ + $'' cannot in general be done consistently.
In the special case that the two operands of a ``$ + $'' operator do not have 
any rule in common, we can merge the databases consistently, by merely 
taking the union of the two.
This handles the case of control expressions of the form
$ ( R_{1} + R_{2} + \ldots + R_{m} )^{\ast} $, which simulate
Basic Semi-Naive evaluation, as well as control expressions in the
class $PCE(P)$ (described in Section~\ref{predsn:control}), which can
be evaluated using Predicate Semi-Naive evaluation.

\subsection{GSN for a Program}
\label{gsn:prog}

Consider a program $P$.
With each Pred-SCC $S$ in $P$, we can associate all the 
(non-recursive and recursive) rules defining the predicates in $S$.
The evaluation of a $S$ consists of repeated application
of the rules associated with $S$, and the program $P$ can be 
evaluated Pred-SCC by Pred-SCC in a topological ordering of 
the Pred-SCCs of $P$.
Procedure {\sf GSN\_Prog} below describes such a GSN evaluation of a 
program.
The GSN evaluation of a single Pred-SCC is as described by {\sf GSN\_SCC}.

\algorithm{
\> procedure GSN\_Prog($P$) \+ \\
$\{$ \+ \\
Let $S_1, \ldots, S_m$ be a topological ordering of the Pred-SCCs of $P$. \\
\> /* $S_0$ is assumed to contain all the base predicates. */ \\
for $j = 1$ to $m$ do ~~~ GSN\_SCC($S_j$) \- \\
$\}$ \\
end GSN\_Prog \- \\
\\
\> procedure GSN\_SCC($ S_i $) \\
\> $\{$ \\
\> \> Let the ordering of the non-recursive rules for the predicates 
in $S_i$ be $E_i^1, \ldots, E_i^m$. \\
\> \> Let the ordering of the recursive rules for the predicates 
in $ S_i $ be $ R_i^1, \ldots, R_i^n $. \\
\> \> if no predicate in $S_i$ has any recursive rule defining it, then \\
\> \> \> Evaluate the following control expression: \\
\> \> \> $ (E_i^1 \cdot ~~~ \ldots ~~~ \cdot E_i^m) $ using GSN\_CE. \\
\> \> else ~~ /* at least one of the predicates in $S_i$ has a recursive rule
defining it */ \\
\> \> \> Evaluate the control expression \\
\> \> \> $ (E_i^1 \cdot ~~~ \ldots ~~~ \cdot E_i^m) \cdot 
( R_i^1 \cdot ~~~ \ldots ~~~ \cdot R_i^n )^{\ast} $ using GSN\_CE. \\
\> $\}$ \\
\> end GSN\_SCC
}

In the evaluation of a Pred-SCC $S$ of program $P$, the non-recursive rules 
are applied once, followed by the repeated application of the recursive 
rules of $S$.
The Pred-SCC structure of $P$ ensures that each non-recursive rule 
$E$ in $S$ only has body predicates that are in ``lower'' Pred-SCCs of $P$.
Consequently, the facts produced by the application of any of
the non-recursive rules cannot be used by any of the other non-recursive
rules in $S$; thus, the order of application of the non-recursive rules
in {\sf GSN\_SCC} is irrelevant.

\begin{theorem}
\label{thm:gsn}
Procedure {\sf GSN\_Prog} has the non-repetition property, is sound and,
if all the predicates defined in the program are safe, is complete
wrt the least fixpoint semantics.
\end{theorem}

\begin{proof}
Let $<$ be a topological ordering of Pred-SCCs such that
$S_i < S_j$, if $S_i$ contains a predicate used in a rule in $S_j$.
The proof is by induction on this ordering $<$.

As the basis, consider $S_0$.
It contains only base predicates and the theorem holds trivially.
Suppose it holds for $S_i$.
Consider evaluation of Pred-SCC $S_{i+1}$.
Since each predicate defined in the program is safe, the set of 
facts in Pred-SCCs $S_0, \ldots, S_i$ are all enumerated before evaluation
of $S_{i+1}$ begins, by the induction hypothesis.
From Theorem~\ref{thm:gsnce:cor}, the evaluation of $S_{i+1}$
has the non-repetition property.
Also, it is sound and complete wrt the control expression semantics
of $ (E_{i+1}^1 \cdot ~~~ \ldots ~~~ \cdot E_{i+1}^m) \cdot 
( R_{i+1}^1 \cdot ~~~ \ldots ~~~ \cdot R_{i+1}^n )^{\ast} $.

A simple induction shows that the set of facts generated with this 
control expression includes all facts for which a derivation tree exists.
Since all lower Pred-SCCs have been fully evaluated, let us treat
the set of facts for these (lower) Pred-SCCs to be base facts, of 
derivation height $0$.
Since each of the non-recursive rules is applied once in the 
control expression $ (E_{i+1}^1 \cdot ~~~ \ldots ~~~ \cdot E_{i+1}^m) $,
any fact with a derivation height of $1$ is derived during the 
evaluation of this control expression.
We show by induction on the derivation heights of facts in this 
Pred-SCC that each fact with a derivation height of $h, h > 0$ will 
be derived in or before the ${h-1}^{th}$ iteration of the control expression
$ ( R_{i+1}^1 \cdot ~~~ \ldots ~~~ \cdot R_{i+1}^n )^{\ast} $.
For the basis case, facts of derivation height $1$ are derived
using the control expression
 $ (E_{i+1}^1 \cdot ~~~ \ldots ~~~ \cdot E_{i+1}^m) $, and hence
are derived before any iteration of the control expression
$ ( R_{i+1}^1 \cdot ~~~ \ldots ~~~ \cdot R_{i+1}^n )^{\ast} $.
For the induction step, suppose the hypothesis holds for facts with 
derivation height $h$.
Since every recursive rule in $S_{i+1}$ is applied in iteration $h$,
any fact with derivation height $h+1$ is derived in or before the 
$h^{th}$ iteration of the control expression 
$ ( R_{i+1}^1 \cdot ~~~ \ldots ~~~ \cdot R_{i+1}^n )^{\ast} $.
This completes the induction and the proof of the theorem.
\end{proof}

We illustrate {\sf GSN\_Prog} using an example.

\begin{example}
\label{ex:n:sn:gsn}
Consider again program $P$ of Example~\ref{ex:n:sn}.
\logicprog{
\lfact {F1:} {par(1,2)} \\
\lfact {F2:} {par(2,3)} \\
\lfact {F3:} {par(4,5)} \\
\lrule {R1:} {anc(X,Y)} {par(X,Y)} \\
\lrule {R2:} {anc(X,Y)} {par(X,Z), anc(Z,Y)} \\
\lrule {R3:} {anc(X,Y)} {anc(X,Z), anc(Z,Y)} 
}
Facts $F1, F2$ and $F3$ are in $S_0$.
Rules $R1, R2$ and $R3$ are all in Pred-SCC $S_1$.
A Pred-SCC by Pred-SCC evaluation of $P$ using {\sf GSN\_Prog}
would proceed as follows.

$S_1$ contains only one non-recursive rule, $R1$.
Assume the ordering of recursive rules in $S_1$ to be $R2, R3$.
(Alternatively, $R3,R2$ could be the rule order assumed, and subsequent
details worked through.)
Consequently, the evaluation of $S_1$ requires evaluation of the
control expression $(R1) \cdot (R2 \cdot R3)^{\ast}$.
Table~\ref{table:gsn} describes the facts in the various relations
during the {\sf GSN\_Prog} evaluation of $P$ using this control expression.

Only the relevant relations that affect and are affected by the 
rule application are shown.
Other relations remain unchanged from the previous step.
Initially, $par$ contains $\{ F1:par(1,2), F2:par(2,3), F3:par(4,5) \}$,
and all other relations are empty.
Iteration $0$ refers to the evaluation of the control expression $(R1)$.
Subsequent iterations refer to the evaluation of the control expression
$(R2 \cdot R3)^{\ast}$.

\begin{table}
\centerline{
\begin{tabular}{|c|l|l|} \hline
{\em Iter/Rule} & {\em Relation} & 
{\em Facts in relation at end of rule application $($New facts in bold-face$)$}
\\ \hline
0/$R1$ & $anc$ & $\{ {\bf R1:anc(1,2)}, {\bf R1:anc(2,3)}, 
    {\bf R1:anc(4,5)} \}$ \\ \cline{2-3}
  & $par$ & $\{ F1:par(1,2), F2:par(2,3), F3:par(4,5) \}$ \\ \cline{2-3}
  & $par_{R1}^{old}$ & $\{ {\bf F1:par(1,2)}, {\bf F2:par(2,3)}, 
				{\bf F3:par(4,5)} \} $ \\ \hline
1/$R2$ & $anc$ & $\{ R1:anc(1,2), R1:anc(2,3), R1:anc(4,5), 
			{\bf R2:anc(1,3)} \}$ \\ \cline{2-3}
  & $anc_{R2}^{old}$ & $ \{ {\bf R1:anc(1,2)}, {\bf R1:anc(2,3)},
				{\bf R1:anc(4,5)} \} $ \\ \cline{2-3}
  & $par$ & $\{ F1:par(1,2), F2:par(2,3), F3:par(4,5) \}$ \\ \cline{2-3}
  & $par_{R2}^{old}$ & $\{ {\bf F1:par(1,2)}, {\bf F2:par(2,3)},
				{\bf F3:par(4,5)} \} $ \\ \hline
1/$R3$ & $anc$ & $\{ R1:anc(1,2), R1:anc(2,3), R1:anc(4,5), 
			R2:anc(1,3), {\bf R3:anc(1,3)} \}$ \\ \cline{2-3}
  & $anc_{R3}^{old}$ & $ \{ {\bf R1:anc(1,2)}, {\bf R1:anc(2,3)},
				{\bf R1:anc(4,5)}, {\bf R2:anc(1,3)} \} $ 
				\\ \hline
2/$R2$ & $anc$ & $\{ R1:anc(1,2), R1:anc(2,3), R1:anc(4,5), 
			R2:anc(1,3), R3:anc(1,3) \}$ \\ \cline{2-3}
  & $anc_{R2}^{old}$ & $ \{ R1:anc(1,2), R1:anc(2,3), R1:anc(4,5), 
				{\bf R2:anc(1,3)}, {\bf R3:anc(1,3)} \} $ 
				\\ \cline{2-3}
  & $par$ & $\{ F1:par(1,2), F2:par(2,3), F3:par(4,5) \}$ \\ \cline{2-3}
  & $par_{R2}^{old}$ & $\{ F1:par(1,2), F2:par(2,3), 
				F3:par(4,5) \} $ \\ \hline
2/$R3$ & $anc$ & $\{ R1:anc(1,2), R1:anc(2,3), R1:anc(4,5), 
			R2:anc(1,3), R3:anc(1,3) \}$ \\ \cline{2-3}
  & $anc_{R3}^{old}$ & $ \{ R1:anc(1,2), R1:anc(2,3), R1:anc(4,5), 
				R2:anc(1,3), {\bf R3:anc(1,3)} \} $ \\ \hline
\end{tabular}
}
\caption{Derivations in a GSN Evaluation of $P$}
\label{table:gsn}
\end{table}

Note that the {\em same\/} derivations are made in the GSN evaluation
of $P$ as in the BSN evaluation of $P$ (Table~\ref{table:semi-naive}).
\end{example}

We discuss the issues involved in selecting an ordering of rules in 
Section~\ref{rule:pred:order}.

\subsection{Related Work}
\label{sec:gsn:rw}

The parallel evaluation technique of 
Gonzalez-Rubio, Rohmer and Bradier~\cite{grb87:ddc} has some similarity
to GSN evaluation.
The idea behind their technique is to run the a copy of the 
BSN algorithm on each of a number of processors.
When a fact is derived it is transmitted to some of the other processors (and
may in some cases not be used locally).
Their parallelization technique provides the mechanics of where to 
send/use facts, and is interesting in its own right, but it does 
not concern us in this paper.
When a fact is received at a processor it is treated exactly as if it
was derived locally during an iteration - it is saved in a $ \delta $ relation
and used in the next iteration.

In the algorithm of Gonzalez-Rubio et al., each processor runs a copy
of the entire program.
However, suppose we instead assigned one rule to each processor, and used
the following scheme for transmitting facts: transmit a fact to any processor
that could use it in the body of its rule.
Then the relations $ p_j^{old} $ and $ \delta p_j^{old} $ in the BSN
algorithm used in the processor with rule $ R_i$ would 
correspond to the relations $ p_{j,R_i}^{old} $ and $ \delta p_j^{old} $
in GSN.
Their technique does not order the rules, and the rules
would be applied repeatedly asynchronously.
However we could conceivably run the processors one at a time in a 
desired order to achieve rule ordering.
Thus, while the techniques of Gonzalez-Rubio et al.\ cannot handle rule
orderings, it could provide a basis for deriving GSN evaluation.
Our work was done independently of theirs.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Predicate Semi-Naive Evaluation}
\label{pred:sn}

We now present a technique, {\em Predicate Semi-Naive}, or PSN, evaluation
that has the non-repetition property and can utilize facts produced 
by a rule application in the same iteration they have been derived in,
though not immediately.\footnote{Although we describe just two evaluation 
strategies, a gradation is possible between GSN and PSN evaluation of 
SCCs, resulting in a range of evaluation strategies.
Some set of predicates may be evaluated according to the strategy 
used by GSN, and other predicates evaluated according to PSN.
We do not elaborate further on this.}.
This technique maintains just one version of the extension of 
each predicate and incurs no additional overheads compared to BSN 
evaluation.
We first look at how to evaluate a restricted set of control expressions
for evaluating a program using this technique.
Then, in Section~\ref{predsn:prog}, we look at a specific form
of control expression to evaluate a program Pred-SCC by Pred-SCC
in a topological ordering of the Pred-SCCs.

Similar to BSN (and GSN) evaluation, there are two components to
PSN evaluation.

\begin{enumerate}
\item The first is the semi-naive rewriting 
that defines ``differential'' versions of predicates.

Similar to BSN evaluation, we maintain three relations
$p^{old}, \delta p^{old}$ and $\delta p^{new}$ for each predicate $p$
defined in the program.
The semi-naive rewriting is identical to the rewriting described for
BSN evaluation.

\item The second component is a technique to apply the rewritten rules
and update these differentials, ensuring that all derivations are 
made exactly once.
Procedure~{\sf PSN\_CE} describes this component for a restricted
class of control expressions for a program.
\end{enumerate}

\subsection{Implementing Control Expressions Using PSN}
\label{predsn:control}

Using PSN, we can evaluate a restricted class of control expressions 
while obtaining the non-repetition property.
For a program $P$, this class of control expressions is given by $PCE(P)$.

\begin{description}
\item [The class $PCE(P)$]:

Consider a program $P$.
The class of expressions $PCE(P)$ is as follows.
Let $S_1, \ldots, S_k$ be any 
topological ordering of the Pred-SCCs of $P$.
Then, the expression $(PCE(S_1) \cdot ~~~ \ldots ~~~ \cdot PCE(S_k))$ is 
in the class $PCE(P)$.

\item [The class $PCE(S)$]:

Consider a Pred-SCC $S$.
The class of expressions $PCE(S)$ is as follows.
Let $p_1, \ldots, p_m$ be some (not necessarily all) of the predicates in $S$.
Let $s_1, \ldots, s_n$ be any partitioning of the predicates 
$p_1, \ldots, p_m$.
Let $ E_{s_i}^1, \ldots, E_{s_i}^{a_i} $ be the non-recursive rules
defining predicates in $s_i$, and let $ R_{s_i}^1, \ldots, R_{s_i}^{b_i} $
be the recursive rules defining predicates in $s_i, 1 \leq i \leq n$.
Let $E_{s_i}$ stand for the control expression
$ E_{s_i}^1 + \ldots + E_{s_i}^{a_i} $, and let $R_{s_i}$ stand for the 
control expression $ R_{s_i}^1 + \ldots + R_{s_i}^{b_i} $.
If none of $p_1, \ldots, p_m$ has any recursive rule 
defining it, then
\[ (E_{s_1}) \cdot ~~~ \ldots ~~~ \cdot (E_{s_n}) \]
is in $PCE(S)$.
If at least one of $p_1, \ldots, p_m$ has a recursive rule
defining it, then
\[ (E_{s_1} + R_{s_1}) \cdot ~~~ \ldots ~~~ \cdot 
(E_{s_n} + R_{s_n})  \cdot ( R_{s_1} \cdot ~~~ \ldots ~~~ \cdot 
R_{s_n})^{\ast} \]
is in $PCE(S)$.
\end{description}

Procedure~{\sf PSN\_CE($\alpha, D$)} below describes the PSN
evaluation of a restricted set of control expressions, without occurrences 
of the ``$\oplus$'' and the ``${}^{\bullet}$'' operators.
Note that the absence of these operators means that each control 
expression is a deterministic mapping.

\algorithm{
\> procedure PSN\_CE($\alpha, D$) \+ \\
$\{$ \+ \\
/* We need to evaluate control expression $\alpha$ on database $D$. */ \\
case \+ \\
(1) $\alpha = R_1 + \ldots + R_n$: \> \> \> \> \> \> 
/* the exit case */ \+ \+ \\
  for $i = 1$ to $n$ do \+ \\
    Apply each semi-naive rewritten version of $R_i$ on database $D$. \\
    Let $D$ denote the resulting database. \- \\
  end for \\
  for every predicate $p_j$ defined by a rule in $\alpha$,
  call SN\_Update($p_j$). \- \- \\
(2) $\alpha = \alpha_1 \cdot \alpha_2$: \+ \+ \\
  Evaluate PSN\_CE($\alpha_1, D$). \\
  Let $D'$ denote the resulting database. \\
  Evaluate PSN\_CE($\alpha_2, D'$). \- \- \\
(3) $\alpha = (\alpha_1)^{\ast}$: \+ \+ \\
  repeat \+ \\
    Let $D'$ denote $D$ at this stage. \\
    Evaluate PSN\_CE($\alpha_1, D$). \\
    Let $D$ denote the resulting database. \- \\
  until ($D = D'$) \- \- \- \\
end case \- \\
$\}$ \\
end PSN\_CE \-
}

The {\sf Simple\_CE} evaluation of a control expression
in $PCE(S)$ first applies the rules in $(E_{s_1} + R_{s_1})$ independently.
All facts computed are then added to the database.
This is followed by applying the rules in $(E_{s_i} + R_{s_i})$ independently,
adding facts computed to the database,
for successive values of $i$ until $i=n$.
The {\sf Simple\_CE} evaluation then applies the rules in
$R_{s_j}$ independently, adding facts computed to the database,
for $j = 1 \ldots n$, and repeats this until nothing new is derived.

The {\sf PSN\_CE} evaluation of a control expression 
in $PCE(S)$ is very similar.
It first applies the (semi-naive versions of the) rules in 
$(E_{s_i} + R_{s_i})$, followed by an {\sf SN\_Update} of the 
predicates in the partition $s_i$, for successive values of $i$ 
until $i=n$.
The {\sf PSN\_CE} evaluation then applies the rules in
$R_{s_j}$ followed by an {\sf SN\_Update} of the predicates
in the partition $s_j$ for $j = 1 \ldots n$, and repeats this
until nothing new is derived.

In the proof of subsequent results, we often use a numbering of the 
rule applications in the {\sf PSN\_CE} evaluation of a control
expression in $PCE(S)$.
We number rule applications using successive integers starting from 1
as follows.
Each rule application in the control expression
$ (E_{s_1} + R_{s_1}) $ is numbered 1; each rule application in
the control expression $ (E_{s_2} + R_{s_2}) $ is numbered 2, and so
on until each rule application in the control expression
$ (E_{s_n} + R_{s_n}) $ is numbered $n$.
Applications of (recursive) rules $R_{s_1}$ in
the first iteration of $( R_{s_1} \cdot ~~~ \ldots ~~~ \cdot
R_{s_n})^{\ast}$ are numbered $n+1$, and applications of 
rules in successive $ R_{s_i} $
are given successive integer numbers.
Thus, applications of rules in $R_{s_1}$ in the 
second iteration of $( R_{s_1} \cdot ~~~ \ldots ~~~ \cdot
R_{s_n})^{\ast}$ are numbered $2*n+1$ and so on.
The same numbering of rule applications
can also be used for the {\sf Simple\_CE} evaluation of $\alpha$.

\eat{
%%%%%%%%%%%%%%%%%%%%%%
\begin{proposition}
\label{prop:psnce:num}
Consider a program $P$, and a control expression $\alpha$ in the 
class $PCE(P)$.
A non-recursive rule in $P$, if present, is present once in $\alpha$,
and a recursive rule, if present, is present twice in $\alpha$.
\noBox
\end{proposition}

\begin{proof}
Each control expression $\alpha$ in $PCE(P)$ is of the form:
$PCE(S_1) \cdot ~~~ \ldots ~~~ \cdot PCE(S_k)$s, where 
each $PCE(S)$ is of the form:
$(E_{s_1} + R_{s_1}) \cdot ~~~ \ldots ~~~ \cdot
(E_{s_n} + R_{s_n})  \cdot ( R_{s_1} \cdot ~~~ \ldots ~~~ \cdot
R_{s_n})^{\ast}$.
Since the $s_j$'s partition the predicates chosen from $S$, 
the proof follows from the definition of the $E_{s_j}$'s and the 
$R_{s_j}$'s.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%
}

\eat{
%%%%%%%%%%%%%%%%
\begin{lemma}
\label{lm:psnce:update}
Consider a Pred-SCC $S$, a database $D$, and a control expression 
$\alpha = \beta_1 \cdot ~~~ \ldots ~~~ \cdot \beta_n \cdot 
(\beta_{n+1})^{\ast}$ in the class $PCE(S)$.
Let $p_1, \ldots, p_m$ be all the predicates in $S$ whose rules occur
in $\alpha$.
For each $p_i, 1 \leq i \leq m$, {\sf SN\_Update($p_i$)} is applied 
once before the first evaluation of $\beta_{n+1}$, and once
in each ``iteration'' of the evaluation of $(\beta_{n+1})^{\ast}$, in the 
application of {\sf PSN\_CE($\alpha, D$)}.
\end{lemma}

\begin{proof}
A control expression $\alpha$ in the class $PCE(S)$ is of the form:
$(E_{s_1} + R_{s_1}) \cdot ~~~ \ldots ~~~ \cdot
(E_{s_n} + R_{s_n})  \cdot ( R_{s_1} \cdot ~~~ \ldots ~~~ \cdot
R_{s_n})^{\ast}$.

We first consider that part of the evaluation of 
{\sf PSN\_CE($\alpha, D$)} prior to the {\sf PSN\_CE} evaluation 
of $( R_{s_1} \cdot ~~~ \ldots ~~~ \cdot R_{s_n})^{\ast}$.
The right associativity of the ``$\cdot$'' operator ensures that
immediately following the application of all rules numbered 
$i, 1 \leq i \leq n$, only the predicates in the partition $s_i$ will
be updated using {\sf SN\_Update}.
Since $s_1, \ldots, s_n$ partition the predicates $p_1, \ldots, p_m$,
each {\sf SN\_Update($p_j$)}, $1 \leq j \leq m$, is applied once
before the first evaluation of 
$\beta_{n+1} = R_{s_1} \cdot ~~~ \ldots ~~~ \cdot R_{s_n}$.
This completes the proof of the first part of the lemma.

Now, consider the {\sf PSN\_CE} evaluation of 
$( R_{s_1} \cdot ~~~ \ldots ~~~ \cdot R_{s_n})^{\ast}$.
Again, the right associativity of the ``$\cdot$'' operator ensures that
immediately following the application of all rules numbered
$i, i > n$, only the predicates defined by rules whose applications
are numbered $i$ will be updated using {\sf SN\_Update}.
Since the $s_j$'s partition the predicates $p_1, \ldots, p_m$,
between rule applications numbered $ k*n +1$ to $(k+1)*n +1$,
each $p_j, 1 \leq j \leq m$ is updated using {\sf SN\_Update($p_j$)}
exactly once.
This completes the proof of the second part of the lemma.
\end{proof}
%%%%%%%%%%%%%%%%
}

\begin{lemma}
\label{lm:psnce:scc}
Consider a Pred-SCC $S$, a database $D$, and a control expression
$\alpha$ in the class $PCE(S)$.
The resulting database after evaluating {\sf PSN\_CE($\alpha, D$)} is
the same as {\sf Simple\_CE($\alpha, D$)}.
Further, this evaluation has the non-repetition property.
\end{lemma}

\begin{proof}
A control expression $\alpha$ in the class $PCE(S)$ is either of the form:
$(E_{s_1}) \cdot ~~~ \ldots ~~~ \cdot (E_{s_n})$ or of the form:
$(E_{s_1} + R_{s_1}) \cdot ~~~ \ldots ~~~ \cdot
(E_{s_n} + R_{s_n})  \cdot ( R_{s_1} \cdot ~~~ \ldots ~~~ \cdot
R_{s_n})^{\ast}$.
Let $p_1, \ldots, p_m$ be all the predicates whose rules occur in $\alpha$.

We first prove that the resulting database after evaluating 
{\sf PSN\_CE($\alpha, D$)} is the same as {\sf Simple\_CE($\alpha, D$)}.
We prove this using the following claim: a derivation of a fact 
in the evaluation of {\sf Simple\_CE($\alpha, D$)} is made for the
first time in a rule application numbered $i$ iff that derivation is made 
in a rule application numbered $i$ of {\sf PSN\_CE($\alpha, D$)}.
We prove this claim by induction on the numbering of the rule applications 
(which is the same for {\sf PSN\_CE($\alpha, D$)} and 
{\sf Simple\_CE($\alpha, D$)}).

As a basis, the claim holds trivially prior to rule applications
numbered $1$, i.e.\ for base facts.
Let us assume that the claim holds prior to rule applications
numbered $i$.
Now consider the rule applications numbered $i$, and the subsequent
update operation (the operations performed prior to
rule applications numbered $i+1$) in the {\sf PSN\_CE} evaluation.
In the {\sf PSN\_CE} evaluation, each rule application 
numbered $i$ affects only some $\delta p^{new}$
relation, and no $\delta p^{new}$ relation occurs
in the body of any semi-naive rewritten rule in $S$.
Hence, the sequential evaluation of each of the (semi-naive rewritten)
rule applications numbered $i$ is equivalent to the independent 
application of these rules (without adding any facts to the database).
Immediately following the rule applications numbered
$i, i \geq 1$, only the differential relations of the
predicates defined by the rules whose applications are numbered $i$ will
be updated using {\sf SN\_Update}.

We first show the ``only if'' part of the claim
for the case when at least one of the predicates in one of the 
$s_i, 1 \leq i \leq n$ has a recursive rule defining it.
Consider a fact $p(\overline{a})$ derived in the {\sf Simple\_CE} 
evaluation, and the associated derivation $ T $ that is made for 
the first time in rule application numbered $i$.
Let the set of facts used in the derivation be denoted by $SF$, and let the
rule used in the derivation be $ R $.
At least one of the facts in $SF$ must have been derived in a rule
application numbered $j, i-n \leq j < i$, since otherwise 
there is an application
of rule $R$ numbered $i-n$ that would have performed derivation $T$
in the {\sf Simple\_CE} evaluation (if $i>n$).
Let one such fact be $ p_{i1}(\overline{a})$.
From rule applications numbered  $j+1$ until rule applications
numbered $ j+n $, $ p_{i1}(\overline{a}) $ is present in the relation
$ \delta p_{i1}^{old} $, and all the other facts in $SF$ are present either
in relations of the form $ \delta p_{i2}^{old} $ or in relations of the
form $ p_{i2}^{old} $.
From the form of the {\sf PSN\_CE} evaluation, the semi-naive
versions of $ R $ are used in rule application $ i$.
By construction of the semi-naive rewritten rules,
$ p(\overline{a}) $ will be derived (using derivation $ T $)
when the application of $ R $ numbered $ i $ is made.
Showing the ``only if'' part of the claim is very similar when
no predicate in any of the $s_i, 1 \leq i \leq n$ has a recursive rule
defining it.
This completes the ``only if'' part of the claim.

We next show the ``if'' part of the claim
for the case when at least one of the predicates in one of the
$s_i, 1 \leq i \leq n$ has a recursive rule defining it.
Consider a fact $p(\overline{a})$ derived in the {\sf PSN\_CE}
evaluation, and the associated derivation $ T $ which is made 
in rule application numbered $i$.
Let the set of facts used in the derivation be denoted by $SF$, and let the
rule used in the derivation be $ R $.
From the form of the {\sf PSN\_CE} evaluation, the semi-naive
versions of $ R $ are used in rule application $i$.
Hence, at least one of the facts, say $ p_{i1}(\overline{a})$,
in $SF$ must be in a relation of the form $ \delta p_{i1}^{old} $.
(Other facts in $SF$ are present either in relations of the form 
$ \delta p_{i2}^{old} $ or in relations of the form $ p_{i2}^{old} $.)
$ p_{i1}(\overline{a})$ could not have been derived in a rule application
numbered $j < i-n$, since then it would have been moved into
the relation $ p_{i1}^{old} $ by an {\sf SN\_Update} prior to rule
applications numbered $i$.
Hence, $p_{i1}(\overline{a})$ was derived for the first time in
a rule application numbered $j, i-n \leq j < i$ of {\sf PSN\_CE}.
By the induction hypothesis, all facts in $SF$ are available 
to rule applications numbered $i$ in {\sf Simple\_CE}.
Hence, derivation $T$ is made by the {\sf Simple\_CE} evaluation in a rule
application numbered $i$.
This is the first time this derivation is made since, 
by the induction hypothesis,
$ p_{i1}(\overline{a})$ is not available to any application of 
rule $R$ prior to this application of 
rule $R$ in the {\sf Simple\_CE} evaluation.
Showing the ``if'' part of the claim is very similar when
no predicate in any of the $s_i, 1 \leq i \leq n$ has a recursive rule
defining it.
This finishes the induction step.

We next prove that the {\sf PSN\_CE} evaluation has the 
non-repetition property.
First consider the case  when at least one of the predicates in one of the
$s_i, 1 \leq i \leq n$ has a recursive rule defining it.
Consider a derivation step $ T $, and let the set of facts used in the
derivation be $SF$.
Define the {\em application number} of a fact to be the least
$ i $ such that the fact is derived by a rule application numbered $ i $.
Let the greatest application number among facts in $ SF $ be $ j_S $.
Thus, all facts in $SF$ are derived in or before rule applications
numbered $ j_S $.
Suppose derivation $ T$ is made in some rule application numbered $ i_T $.
We must have $ i_T > j_S $, for before $ j_S $ not all facts
needed for $ T $ were available.

A new fact generated by a rule application numbered $ j_S $
becomes part of some relation $ \delta p_{i}^{old} $ immediately after all
rules applications numbered $ j_S $ are completed.
After a complete iteration, i.e., after rule applications numbered
$ j_S+n$, facts in $ \delta p_{i}^{old} $ are moved to $ p_{i}^{old} $
due to {\sf SN\_Update($p_i$)}.
Thus, after rule applications numbered $ j_S + n $,
all the facts in $ SF $ are in relations of the form $ p_{k}^{old} $.
{\sf SN\_Update($p_k$)} ensures that
once a fact is present in $p_k^{old}$, it will not appear in 
$\delta p_k^{old}$ again.
By the construction of semi-naive rewritten rules,
derivation $ T $ cannot be made after this point.
Hence we must have $ i \leq j_S +n $.
But between $ j_S $ and $ j_S + n $, each rule $ R $ is applied at most once.
Hence derivation $ T$ can be made at most once.
Showing that the {\sf PSN\_CE} evaluation of a control expression in 
$PSN(S)$ has the non-repetition property when
no predicate in any of the $s_i, 1 \leq i \leq n$ has a recursive rule
defining it is very similar.
This finishes the proof of the non-repetition property,
and the proof of the lemma.
\end{proof}

\begin{theorem}
\label{thm:psnce}
Consider a program $P$, a database $D$, and a control expression 
$\alpha$ in the class $PCE(P)$.
The resulting database after evaluating {\sf PSN\_CE($\alpha, D$)} is 
the same as {\sf Simple\_CE($\alpha, D$)}.
Further, evaluations of {\sf PSN\_CE} have the non-repetition property.
\end{theorem}

\begin{proof}
Let $<$ be a topological ordering of Pred-SCCs in $P$ such that
$S_i < S_j$ if $S_i$ contains a predicate used in a rule in $S_j$.
Each control expression $\alpha$ in $PCE(P)$ is of the form:
$PCE(S_1) \cdot ~~~ \ldots ~~~ \cdot PCE(S_k)$,
where the $S_i$ are in topological order.
The proof is by induction on this ordering $<$.

As a basis, consider $S_0$.
It contains only base predicates and the theorem holds trivially.
Let us suppose that it holds for $S_i$, i.e.\ 
the resulting database after evaluating {\sf PSN\_CE($\alpha_1, D$)}
is the same as {\sf Simple\_CE($\alpha_1, D$)}, where 
$\alpha_1$ is in the class $PCE(S_1) \cdot ~~~ \ldots ~~~ \cdot PCE(S_i)$.
Consider the {\sf PSN\_CE} evaluation of a control expression $\beta$ in
$PCE(S_{i+1})$ on the database given by {\sf Simple\_CE($\alpha_1, D$)}.

Lemma~\ref{lm:psnce:scc} shows that the resulting database
after evaluation of this control expression is the same as 
{\sf Simple\_CE($\beta$, Simple\_CE($\alpha_1, D$))}.
Lemma~\ref{lm:psnce:scc} also shows that the 
{\sf PSN\_CE} evaluation of $\beta$ has the non-repetition property.
Since predicates in $S_0, \ldots, S_i$ are treated as base predicates
in the semi-naive rewriting of $\beta$,
the resulting database after the {\sf PSN\_CE} evaluation of
$\alpha_2 = \alpha_1 \cdot \beta$ is the same as 
{\sf Simple\_CE($\alpha_2, D$)}.
This completes the proof of the equivalence of the {\sf PSN\_CE} 
evaluation to the {\sf Simple\_CE} evaluation.
Since each rule in $P$ is present in at most one Pred-SCC,
and each Pred-SCC is evaluated only once,
the {\sf PSN\_CE} evaluation of $\alpha$ has the non-repetition property.
This completes the proof of the theorem.
\end{proof}

\subsection{PSN for a Program}
\label{predsn:prog}

Consider a program $P$.
With each Pred-SCC $S$ in $P$, we can associate all the
(non-recursive and recursive) rules defining the predicates in $S$.
The PSN evaluation of $S$ consists of repeated applications
of the rules associated with $S$, and the program $P$ can be
evaluated Pred-SCC by Pred-SCC in a topological ordering of
the Pred-SCCs of $P$.
Procedure {\sf PSN\_Prog} below describes the PSN evaluation of a
program $P$, using a control expression in the class $PCE(P)$
where in each Pred-SCC of $P$ each predicate is in a partition by itself.

\algorithm{
\> procedure PSN\_Prog($P$) \+ \\
$\{$ \+ \\
Let $S_1, \ldots, S_m$ be a topological ordering of the Pred-SCCs of $P$. \\
\> /* $S_0$ is assumed to contain all the base predicates. */ \\
for $j = 1$ to $m$ do ~~~ PSN\_SCC($S_j$) \- \\
$\}$ \\
end PSN\_Prog \- \\
\\
\> procedure PSN\_SCC($S$) \\
\> $\{$ \\
\> \> Let the ordering of predicates in $ S $ be $ p_1, \ldots, p_k $. \\
\> \> Let $ E_{p_i}^1, \ldots, E_{p_i}^{a_i} $ be the non-recursive rules
defining $p_i$, and \\
\> \> \> let $ R_{p_i}^1, \ldots, R_{p_i}^{b_i} $ be the recursive rules 
defining $p_i, 1 \leq i \leq k$. \\
\> \> Let $E_{p_i}$ stand for the control expression
$ E_{p_i}^1 + \ldots + E_{p_i}^{a_i} $, and \\
\> \> \> let $R_{p_i}$ stand for the control expression
$ R_{p_i}^1 + \ldots + R_{p_i}^{b_i} $. \\
\> \> if no predicate in $S$ has any recursive rule defining it, then \\ 
\> \> \> Evaluate the following control expression: \\
\> \> \> $ (E_{p_1}) \cdot ~~~ \ldots ~~~ \cdot (E_{p_k}) $ using PSN\_CE \\
\> \> else ~~ /* at least one of the predicates in $S$ has a recursive rule
defining it */ \\
\> \> \> Evaluate the following control expression: \\
\> \> \> $ (E_{p_1} + R_{p_1}) \cdot ~~~ \ldots ~~~ \cdot 
(E_{p_k} + R_{p_k}) \cdot ( R_{p_1} \cdot ~~~ \ldots ~~~ \cdot
R_{p_k})^{\ast} $ using PSN\_CE. \\
\> $\}$ \\
\> end PSN\_SCC
}

\begin{theorem}
\label{thm:psn}
Procedure {\sf PSN\_Prog} has the non-repetition property, 
is sound and, if all the predicates defined in the program are safe, is
complete wrt the least fixpoint semantics.
\end{theorem}

\begin{proof}
Let $<$ be a topological ordering of Pred-SCCs such that
$S_i < S_j$, if $S_i$ contains a predicate used in a rule in $S_j$.
The proof is by induction on this ordering $<$.

As the basis, consider $S_0$.
It contains only base predicates and the theorem holds trivially.
Suppose it holds for $S_i$.
Consider evaluation of Pred-SCC $S_{i+1}$.
We prove the soundness of PSN evaluation of $S_{i+1}$ 
using induction on the number of rule applications in the PSN evaluation.
If the given set of facts is sound, then the set of facts 
produced by a rule application is also sound.
The hypothesis holds trivially for the first rule application,
and hence the proof of soundness follows.

Theorem~\ref{thm:psnce} ensures that the PSN evaluation of 
$S_{i+1}$ has the non-repetition property.
We now prove that PSN evaluation of $S_{i+1}$ 
is complete wrt the least fixpoint semantics. 

Since all lower Pred-SCCs have been fully evaluated, let us treat
the set of facts for these (lower) Pred-SCCs to be base facts, of
derivation height $0$.
We prove completeness of the {\sf Simple\_CE} evaluation of the
control expression (wrt the least fixpoint semantics)
using induction on the derivation heights of facts.
Theorem~\ref{thm:psnce}, which shows the equivalence of the {\sf Simple\_CE}
evaluation to the {\sf PSN\_CE} evaluation, can then be used
to show that the {\sf PSN\_CE} evaluation is complete wrt the least
fixpoint semantics.
As the basis case, facts with derivation heights of 1 are derived by 
non-recursive rules, and these are clearly derived in the course of 
{\sf Simple\_CE} evaluation.
Assume inductively that facts with derivation heights up to $ h $ are 
derived using {\sf Simple\_CE} evaluation.
Consider a fact $ p(\overline{a}) $ with derivation height $ h+1 $, 
and the associated derivation $ T $.
Let the set of facts used in the derivation be denoted by $SF$, and let the
rule used in the derivation be $ R $.
All the facts in $ SF $ have derivation indices less than or equal to $ h $.
By the induction hypothesis these are derived during the 
{\sf Simple\_CE} evaluation.

Consider now the least $ i $ such that all the facts in
$ SF $ are derived in rule applications with numbers less than or equal to
$ i $.
Clearly at least one of the facts in $ SF $ must be derived in a rule 
application numbered $ i $.
From the form of the iterative loops in the {\sf Simple\_CE} evaluation
of the control expression, $ R $ is used in some rule application 
$ j1 $ such that $ i+1 \leq j1 \leq i+k $, and derivation $T$ will be
made when the application of $ R $ numbered $ j1 $ is made.
From Theorem~\ref{thm:psnce}, derivation $T$ for
$ p(\overline{a}) $ will be made by the {\sf PSN\_CE} evaluation
of the control expression.
This finishes the proof of completeness, as well as the 
proof of the theorem.
\end{proof}

PSN can be generalized as follows:
\begin{enumerate}
\item Apply each semi-naive version of each
recursive rule in a Pred-SCC exactly once in each iteration.

\item Perform the updates of the differential relations according to 
{\sf SN\_Update} for each predicate $ p $ exactly once at the same 
point (not necessarily immediately after applying the recursive rules 
for predicate $p$) in each iteration, and 

\item Iterate till no new facts are computed in a complete iteration.
\end{enumerate}
A result similar to Theorem~\ref{thm:psn} also holds for
this generalization of PSN.
The proof of the result follows from simple modifications of the proof
of the above theorem.

Much as the ordering of rules could affect the performance of 
GSN, ordering of predicates could affect the performance
of PSN.
The results of Section~\ref{rule:pred:order} can be used to obtain
good predicate orderings for the PSN evaluation of a program.

In a sequential evaluation of a program, PSN evaluation is {\em always\/}
preferable to BSN 
evaluation, since it can be implemented with the same overheads per iteration,
but can do better in terms of the number of iterations.
The performance results of Leask et al.~\cite{lrs:par:aditi} (described in
Section~\ref{sec:perf:rel:work}) support this claim.
PSN may not be able to utilize facts as early as GSN can,
but the overheads associated with GSN could be
higher, and the choice of which strategy to choose is not always obvious.

%%%%%%%%%
% However, if arbitrary control expressions are specified,
% PSN may no longer be applicable.
% In general, it is not possible to use PSN to 
% evaluate control expressions, whereas GSN can always be used,
% as discussed in Section~\ref{gensn:control}.
%%%%%%%%%

The following example illustrates the differences between BSN, PSN,
and GSN evaluation of a program.
\begin{example}
Consider the following program $P$:
\logicprog{
\lfact {F_1:} {b_1(4,5)} \\
\lfact {F_2:} {b_2(3,4)} \\
\lfact {F_3:} {b_3(2,3)} \\
\lfact {F_4:} {b_4(1,2)} \\
\lrule {R_1:} {p(X,Y)} {b_1(X,Y)} \\
\lrule {R_2:} {q(X,Y)} {b_2(X,Z), p(Z,Y)} \\
\lrule {R_3:} {p(X,Y)} {b_3(X,Z), q(Z,Y)} \\
\lrule {R_4:} {p(X,Y)} {b_4(X,Z), p(Z,Y)} \\
\lquery {p(1,X)}
}
For the above program, BSN as well as GSN and PSN would evaluate the 
non-recursive rule, $R_1$ exactly once (in the beginning) to 
produce $p(4,5)$.

Evaluating the rules $ (R_2, R_3, R_4) $ repeatedly in this order,
using GSN, would make the facts produced using an application of
rule $ R_2 $ ($q(3,5)$ in the first iteration) immediately available to 
applications of $ R_3 $ and $ R_4 $ in the same iteration.
Similarly, the facts produced using an application of $ R_3 $ 
($p(2,5)$ in the first iteration) would be available to applications of $ R_4 $ 
(in the same iteration), and $R_2$ (in the subsequent iteration).
Thus, the answer, $p(1,5)$, to the query would be produced 
at the end of the first iteration itself using GSN evaluation of $P$.

If the predicate ordering chosen for PSN is $(q, p)$,
the rule defining $q$ ($R_2$) is applied first, and the 
fact ($q(3,5)$ in the first iteration) produced would be immediately 
available to applications of $R_3$ and $R_4$, in the same iteration.
The application of $R_2$ is followed by the independent application 
of the rules defining $p$ ($R_3$ and $R_4$).
Consequently, the fact produced using $R_3$ ($p(2,5)$ in the first iteration)
would be available to $R_4$ only in the next iteration.
Thus, the answer, $p(1,5)$, to the query would be produced
at the end of the second iteration using PSN evaluation of $P$.

If BSN evaluation is used instead, facts produced
by a rule application would not be available to any other rule application
in the same iteration.
Consequently, $q(3,5)$ would be produced in the first iteration,
$p(2,5)$ in the second iteration, and $p(1,5)$ (the answer to the query)
would be produced only in the third iteration.
\end{example}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Rule Orderings that Minimize Rule Applications}
\label{rule:pred:order}

\begin{example}
Let $ q $ and $ r $ be base relations.
Consider the following program $P$:
\logicprog{
\lrule {R_0:} {p_{k} ( X )} {q ( X ) }\\
\lrule {R_1:} {p_{1} ( f_{1} ( X ) )} {p_{k} ( X )} \\
\lrule {R_2:} {p_2 (f_2 (X))} {p_1 (X)} \\
 & \vdots \\
\lrule {R_{k-1}:} {p_{k-1} (f_{k-1} (X))} {p_{k-2} (X)} \\
\lrule {R_k:} {p_{k} ( f_{k} ( X ) )} {p_{k - 1} ( X ) , r ( X )}
}

The non-recursive rule $R_0$ is the first rule to be applied in a 
BSN evaluation of $P$.
In an iteration of a Basic Semi-Naive evaluation, all the recursive 
rules (i.e.\ $R_1, \ldots, R_k$) of the program are applied independently.
Rule $ R_{k} $ will be successfully applied for the first time only in the 
$ k^{th} $ iteration.
However, it would be possible to successfully apply rule $ R_{k} $ in the
first iteration itself if the rules are applied in the order shown,
i.e.\ $ (R_1, R_2, \ldots, R_k)$, and
the facts produced by each rule application are immediately made available to
subsequent rule applications.
If the computation of a fact using this technique (and the given 
ordering of rules) took $ n $ iterations, then computation of the 
same fact using the
BSN evaluation strategy could take up to $k*n$ iterations.

If, instead, the rules are applied in the opposite order, i.e.\ 
$ (R_{k} , R_{k-1} , \ldots , R_{1}) $, the number of iterations taken is
the same as BSN evaluation, even if facts produced by a 
rule application are made available immediately after the rule is 
applied.
Thus we see the importance of a good ordering of rules.
\end{example}

In this section, we provide a theoretical analysis of how the number of rule 
applications (and iterations) in fixpoint algorithms, that have
the non-repetition property and apply a rule using GSN,
can be reduced through the use of rule ordering. 
Our results are significant in that they indicate how this number can be
minimized, independent of the data in base relations, over
a significant class of rule orderings (Section \ref{ord:preserve}).
We also present results which suggest that only this class of rule orderings 
should be considered in the absence of additional semantic information
(Section \ref{non:fair}).

The techniques described in this section deal with rule orderings,
but can be extended, in a straight forward fashion, to deal with predicate
orderings, and can obtain good orderings for PSN evaluation.

\subsection{Benefits of Rule Ordering}
\label{rule:ord:eff}

Besides implementing desired semantics,
ordering of rules can also be used to reduce the cost of bottom-up evaluation 
of logic programs.

The number of inferences has been widely used as a cost metric
in the evaluation of logic programs.
However, any evaluation technique that has the non-repetition property 
makes each inference (that can be made) exactly once, and hence all the 
techniques we study are equivalent under this criterion.
Algorithms having the non-repetition property differ in how
inferences are distributed across iterations.
However, the cost measure of the number of inferences hides many 
implementation costs, 
and we desire more accurate cost criteria that refine the criterion of 
the number of inferences.

One of the advantages of bottom-up evaluation of logic
programs is the increased degree of set-at-a-time computation.
Given that the total number of inferences made by two different 
evaluation techniques is identical, the technique that performs more 
set-at-a-time computation is expected to perform better.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Is there any reference to this in old literature??????? Ask Raghu
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
If more inferences are made using the set of tuples in a page fetched from
disk, the number of I/O operations can be expected to reduce considerably.
This can be seen from the results of Lu~\cite{lu:tc}, who considered how 
facts could be (partially) utilized in the same iteration that they were 
generated (thus reducing the total number of iterations and hence increasing
the set-at-a-time computation in each iteration), in the context of transitive
closure algorithms, and noted that this reduced the number of disk accesses.
Thus, the greater the number of inferences made in a single rule application, 
the fewer are the number of I/O operations expected (given that the total 
number of inferences made does not change).

The fixpoint evaluation techniques we describe (GSN and PSN) 
use facts produced by a rule application in the application of
other rules within the same iteration, while preserving the non-repetition 
property.
Our theoretical analysis and performance results show that 
these techniques can greatly reduce the number of rule applications, 
iterations, and thus the number of joins needed to reach the fixpoint 
in a sequential computation.
Since the number of inferences made by each of the evaluation strategies is
the same while the number of joins is reduced, the degree of set-orientedness 
in the processing of the program is increased by these techniques
and hence, the I/O costs can be expected to reduce.

Associated with each join are several fixed overheads, e.g., possible
accessing from (and storing to) secondary storage the relations involved 
in the join.
With each iteration there are other overheads, e.g., updating 
the various predicate extensions.
The reduction in the number of rule applications, iterations and joins can 
be expected to reduce the costs due to the various fixed overheads 
associated with each iteration and with each join.
The reduction in cost due to ordering of rules is orthogonal to other 
techniques such as efficient join and indexing strategies, and
duplicate elimination techniques---none of these is made inapplicable by
ordering rules.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% talk of iterations and join costs and how they may be related.
% diff. techniques of measuring join costs

% One of the most basic operations in the bottom-up evaluation of a logic 
% program is the join, and it is also expected to be the costliest.
% The cost of joining two relations depends on the specific join technique used,
% the sizes of the relations participating in the join, the size of the 
% result of the join, and the cost of accessing and storing these relations.
% The cost of accessing a relation depends on whether the relation (or parts of
% it) are already present in the main memory buffers, and hence is a function
% of the cost of fetching relations from secondary storage, buffer space 
% available, the buffering strategies used, etc.
% There may also be a fixed overhead for setting up a join operation.

% For a single rule application, the cost is the sum of the costs of the 
% joins involved in the rule application, along with overheads including
% possible materializations of temporary relations, updating indices of 
% relations, duplicate elimination, etc.
% Similar to joins, there may also be a fixed overhead for each rule
% application. Thus, the cost of rule applications can
% be viewed as having a fixed component,
% and a variable component that depends on the number of
% inferences and sizes of the relations being joined. 
% All the algorithms that we consider have the non-repetition property.
% Algorithms having the non-repetition property differ only in how
% inferences are distributed across iterations; the total number
% of inferences is the same. The exact effect of this distribution
% on the variable component of the cost of rule applications is
% dependent upon the join and access methods, and is difficult to
% estimate without either a detailed simulation or actual
% implementation. We note, however, that reducing the number of
% rule applications while keeping the total number of inferences
% constant has the effect of generating larger sets of new facts.
% We expect that this will tend to reduce the variable component
% of the cost in most situations.

% The effect of reducing the number of rule applications on the fixed
% component of the cost is easier to estimate. The fixed component is directly
% proportional to the number of rule applications, for two reasons.
% First, the measure of the number of non-null joins, rule 
% applications and iterations taken to compute the closure of an SCC is a 
% good estimator of the fixed overheads associated with these operations.
% Second, our performance results in Section~\ref{performance} indicate that 
% the number of rule applications and iterations closely parallels the 
% number of non-null joins.

% The performance results that we present in Section~\ref{performance} 
% indicate that the number of iterations and rule applications taken to compute 
% the closure of an SCC by each of two evaluation techniques 
% is a good measure of their relative
% costs, given that the number of inferences made by the two techniques 
% is the same.
% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Class of Orderings Considered}
\label{class:order}

\begin{nameddefinition} {Fair, static orderings}
Let the rules of a Rule-SCC $ S $ be $ R_{1} , \ldots , R_{n} $.
A {\em fair, static ordering\/} is
an ordering of the form $ ( R_{i_{1}}, \ldots, R_{i_{n}} ) $,
where $ i_{1} , \ldots , i_{n} $ is a permutation of $ 1 , \ldots , n $.
\end{nameddefinition}

We consider such orderings in Section~\ref{ord:preserve}.
Such an ordering is referred to as a {\em static\/} ordering
since the same ordering is used in each iteration.
In such static orderings no rule is applied more often than other rules.
Such orderings are referred to as {\em fair\/} orderings since
in the absence of any prior knowledge of the frequency with which different 
rules are used, or other semantic information, we have no basis for applying 
some rules more often than others.
In order to compute the closure of an SCC $ S $, using a fair ordering, 
we apply the rules in the given order in each iteration, repeatedly, making 
the facts produced by a rule application available to all subsequent 
rule applications, till no more facts can be computed.
Independent applications of rules are not considered, since making the
facts produced by a rule application available to other rule applications may
significantly reduce the number of rule applications needed to compute
the fixpoint, and can never increase it in a sequential evaluation.

In Section~\ref{non:fair} we consider static orderings in which some rules 
can be applied more often than other rules.
Such orderings are referred to as {\em non-fair\/} orderings.
This class includes the class of nested orderings, such as those 
considered by Kuittinen et al.~\cite{sippu90:eval}.
Non-fair orderings may perform somewhat better than fair orderings on 
some data sets, but, as we show in Section~\ref{non:fair}, such
orderings may also perform considerably worse on other data sets.
Hence, in the absence of any information about the kind of data sets, 
fair orderings are preferable.

We do not consider orderings where the next rule to be applied is chosen
dynamically.
Although {\em dynamic\/} orderings may be better than static 
orderings in terms of the
cost criteria described in Section~\ref{rule:ord:eff}, determining which
rule to apply may be difficult and involve considerable overheads.
While dynamic orderings may be worth investigating, we do not consider them
in this paper.

\subsection{Fair Orderings}
\label{ord:preserve}

% do generalized tuples and their derivation trees make a difference?

\begin{nameddefinition} {Order sequence}
Let $ O $ be any ordering $ ( R_{i_{1}} , \ldots , R_{i_{n}} ) $.
An {\em order sequence\/} $ S = O^{m} $
denotes the string formed by repeating $ O $, $ m $ times.

We use the notation $S[k], 1 \leq k \leq m*n$ to denote the 
$k^{th}$ rule in $S$.
\end{nameddefinition}

A sequence $S_1$ of length $n$ is said to be a {\em subsequence\/} of 
a sequence $S_2$ of length $m \geq n$, if there exist 
$n$ numbers $1 \leq k_1 < k_2 < \ldots < k_n \leq m$, such that
$S_1[i] = S_2[k_i], 1 \leq i \leq n$.
For example, $ (R_{1} , R_{3} , R_{5}) $ is a subsequence of 
$ ( R_{1} , R_{2} , R_{3} , R_{4} , R_{5} ) $.

\begin{nameddefinition} {Cycle preserving fair orderings}
Consider an SCC $ S $, and let the rules in $ S $ be $ {\cal R}
= \{ R_{1} , \ldots ,
R_{n} \} $.
Let $ G = ( {\cal R}, E ) $ be the rule graph for the given SCC.
Let $O$ be any fair ordering $ ( R_{i_{1}} , \ldots , R_{i_{n}} ) $
of the rules in $R$.
Let $ C $ be any simple cycle
$ R_{j_{1}} , \ldots , R_{j_{m}} $ in $ G $.\footnote{
Though cycles have the same initial and final vertex, we omit the final
vertex in our representation, for convenience.}

We say that a fair ordering $ O $ {\em preserves\/} a cycle $ C $, if there 
is a cyclic permutation $ O_{1} $ of $ O $ such that $ C $ forms a
subsequence of $O_1$.
A fair ordering $ O $ on $ G $ is a {\em cycle preserving fair ordering\/} if 
for every simple cycle $ C $ in $ G $, $ O $ preserves $ C $.
\end{nameddefinition}

A fair ordering $ O $ that does not preserve a cycle $ C $ is said to break it.
A cycle $ C $ is {\em broken by degree\/} $ B ( C , O ) = i $, by a fair 
ordering $ O $, if $ i $ is the least number such that for some cyclic 
permutation $ O_{1} $ of $ O $, $ C $ is a subsequence of $ O_{1}^{i} $.
Thus a fair ordering that preserves a cycle can be said to break it 
by degree one.

We define a relation $ \lhd $ on the class of fair orderings.
Given two fair orderings $ O_{1} $ and $ O_{2} $ on a rule graph $ G $, 
$ O_{1} \lhd O_{2} $ if for every simple cycle $ C $ in $ G $, 
$ B ( C, O_{1} ) \leq B ( C , O_{2} ) $.
If we have $ O_{1} \lhd O_{2} $ and $ O_{2} \lhd O_{1} $, we say that the
two orderings are {\em equivalent}.
The use of this relation will be seen in Section~\ref{cycles:opt}, where we
show in Theorem~\ref{thm:main} that if $ O_{1} \lhd O_{2} $ and the two are
not equivalent, then given any database, $ O_{1} $ is better than $ O_{2} $
based on the number of iterations needed to compute the closure of an SCC.
We also show that if $ O_{1} $ and $ O_{2} $ are equivalent, the number
of iterations needed by each to compute the closure of an SCC differ by at 
most a data-independent constant.
Thus, we show that an ordering that preserves all cycles is optimal in the 
class of fair orderings, under this cost
criterion.  From the definition of the relation $ \lhd $ we have:

\begin{itemize}
\item Cyclic permutations of a fair ordering are equivalent under $ \lhd $, and
\item Any two cycle preserving fair orderings are  equivalent under $ \lhd $.
\end{itemize}

\begin{figure}
\centerline{\psfig{figure=figures/multcycles.ps,height=3.0cm,bbllx=237pt,bblly=671pt,bburx=581pt,bbury=862pt}}
\caption{An Example Rule Graph}
\label{mult:cycles}
\end{figure}

\begin{example}
Consider the rule graph shown in Figure~\ref{mult:cycles}.
The simple cycle $ 1 , 3 , 2 , 6 $ is preserved by the ordering
$ ( 2 , 6 , 4 , 1 , 3 , 5 ) $ because the ordering has a cyclic permutation 
$ ( 1 , 3 , 5 , 2 , 6 , 4 ) $ which has the simple cycle as a subsequence.
However, this ordering breaks the simple cycle $ 1 , 4 , 2 , 5 $
by degree $ 3 $.
\end{example}

\begin{lemma}
\label {minperm:end}
Consider a cycle $ C = R_{1} \ldots R_{m} $ and a fair ordering $ O $.
Let $ O_{1} $ be the cyclic permutation of $ O $ that ends with $ R_{m} $.
Then $ C $ forms a subsequence of $ O_{1}^{i} $ for $ i = { B ( C , O ) } $,
but not for any smaller $ i $.
\end{lemma}
\begin{proof}
By definition of $ B ( C , O ) $, for some cyclic permutation $ O_{r} $ of 
$ O $, $ C $ is a subsequence of $ O_{r}^{B ( C , O )} $.
Consider now $ R_{m} $, the last rule in $ C $.
It must be mapped to the occurrence of $ R_{m} $ in the last repetition
of $ O_{r} $ in $ O_{r}^{B ( C , O )} $.
Now move the elements of $ O_{r} $ that follow $ R_{m} $ to the head of the
$ O_{r}^{B ( C , O )} $.
Clearly $ C $ is a subsequence of the result of this transposition, and 
the result is equal to $ O_{1}^{B ( C , O )} $.
That $ C $ is not a subsequence of $ O_{1}^{i} $ for any $ i < B ( C , O ) $
follows from the definition of $ B ( C , O ) $.
\end{proof}

The use of this lemma will be seen in subsequent sections.

For the class of fair orderings, we next show that cycle preserving fair
orderings are optimal under the cost criterion of the number of iterations 
needed to compute the closure of an SCC, with an immediate update strategy.
Since the number of rule applications is constant within an iteration
in a fair ordering,
the optimality result carries over for the cost criterion of number
of rule applications.

\subsubsection{Optimality of Cycle Preserving Orderings}
\label{cycles:opt}

\begin{nameddefinition} {Derivation path}
A {\em derivation path\/} for a fact is a path in a derivation tree for 
the fact, starting from a leaf node.
We represent such a path concisely by listing the rules labeling the
nodes in the derivation path in order, starting from the parent of the leaf.
\end{nameddefinition}
Note that two different paths may have the same representation, but that 
does not affect our analysis.

\begin{nameddefinition} {Derivation index}
Let $ O $ denote a fair ordering of rules in the program and $ T $ denote
a particular derivation tree for $ p ( \overline{c} ) $.
Consider the rule application sequence $ {\cal O} ' = O^{j} $, for
arbitrarily large $ j $.
With each node in the derivation tree $ T $, we associate a {\em derivation 
index\/}, which is an index into the sequence $ {\cal O} ' $, 

Leaf nodes (corresponding to base facts) are associated with the derivation
index zero. 
The derivation index of each internal node $ n ' $, labeled with a derived
fact $ p ' $ and a rule $ R ' $, is the minimum possible $ k $ such that,
$ {\cal O} ' [ k ] = R ' $ and the derivation indices of the children nodes
of $ n ' $ are less than $ k $.
\end{nameddefinition}

\begin{nameddefinition} {Iteration height}
Let $ O $ denote a fair ordering of rules in the program and $ T $ denote
a particular derivation tree for $ p ( \overline{c} ) $.
With each node in the derivation tree we associate an {\em iteration 
height} \mbox{$ \lceil k / m \rceil $} where
$ k $ is the derivation index of that node, and $m$ is the length
of $O$.

A derivation tree is said to be {\em computed\/} by $ O $ using $ n $ iterations
if the iteration height of the root of the tree under $ O $ is $ n $.
\end{nameddefinition}
The iteration height of a node is defined syntactically but has the
following semantic interpretation.
If the iteration height of the root of a derivation 
tree $ T $ is $ n $, then the corresponding fact $ p ( \overline{c} ) $
is computed in or before the $ n $th iteration of the application of rules
according to the ordering $ O $.
If the fact is computed in the $ n $th iteration, there is a derivation tree
with iteration height $ n $ for the fact.

\begin{nameddefinition} {Iteration count}
The {\em iteration count\/} of a fact, for a given fair ordering, is defined to
be the minimum of the iteration heights under the given ordering,
of derivation trees for this fact. 
\end{nameddefinition}
This gives us the earliest iteration in which the fact is derived.
This link between the semantic notion of the number of iterations needed
to compute a fact, and the iteration heights of derivation trees for the
fact enables us to argue about the computation of facts using purely
syntactic criteria.

\begin{nameddefinition} {Iteration length}
Consider a derivation tree $T$ for a fact, and a fair ordering $O$.
Given a derivation path $ s $ in $ T $, the {\em iteration length\/}
$ L ( s , O ) $ of the path is the minimum $ n $, such that
the path forms a subsequence of $ O^{n} $.

The {\em minimum length order sequence\/} for $ s $ is defined to be 
$ O^{L(s,O)} $.
\end{nameddefinition}
We next show the relationship between the notion of the iteration length of 
a path, and the iteration height of a tree.
For a tree $ T $, if $ T $ has no internal nodes, define $ L ( T , O ) = 0 $.
Otherwise define $ L ( T , O ) = 
\max \{ L ( s , O ) \mid s $ is a path in $ T \} $.

The following lemma permits us to argue about the number of iterations 
it takes to compute a derivation tree based on the iteration lengths of the 
derivation paths in the tree.

\begin{lemma}
\label{lm:itern:ht}
Given a derivation tree $ T $ for a fact $ p ( \overline{c} ) $, and a fair
ordering $ O $,
the derivation tree can be computed by a bottom-up fixpoint evaluation
using rule ordering $ O $ in $ L ( T , O ) $ iterations.
$ L ( T , O ) $ is thus also the iteration height of $ T $.
\end{lemma}
\begin{proof}
We prove by induction on the height of a tree that the iteration height of 
a node is the same as the maximum of the iteration lengths of paths from the 
leaves of the tree to that node.
As a basis, note that the iteration height of a leaf node is zero.

For an internal node $ n $, let $ m ( n ) $ denote the maximum of the
iteration lengths of derivation paths from the leaves to $ n $ and let
$ s ( n ) $ denote one such path with iteration length $ m ( n ) $.

Consider any internal node $ n $, and assume inductively that for every child
$ n_{i} $ of $ n $, the iteration height of $ n_{i} $ is the same as 
$ m ( n_{i} ) $.
Clearly the iteration length, $ m ( n ) $ must be greater than 
or equal to every $ m ( n_{i} ) $.

Let the rule corresponding to node $ n $ be $ R $.
Consider any child node $ n_{j} $ of $ n $, that has iteration height 
$ m ( n_{j} ) = m ( n ) $, if such a node exists.
Assume that the rule, say $ R_{j} $ corresponding to node $ n_{j} $,
occurs after $ R $ in the ordering.
But then we can use the path $ s ( n_{j} ) $ with $ R $ appended to it, 
and this path would have an iteration length of $ m ( n ) + 1 $, which is not 
possible by maximality of the iteration length $ m ( n ) $. 
Thus the iteration height of each child node of $ n $ is either less than 
$ m ( n ) $, or it is equal to $ m ( n ) $ and the rule that labels the child
node occurs before $ R $ in the ordering.
Hence, by the definition of iteration heights, the iteration height of 
$ n $ is $ m ( n ) $.
This completes the induction.
\end{proof}

Every derivation path has a certain structure which is described in the
next lemma, and which we use to prove the result in
Theorem~\ref{path:length}.

\begin{lemma}
\label{path:cycle}
For every derivation path $ s $, there exists a sequence $ s_{0} , 
\ldots , s_{n} $ of paths in the rule graph $ G $, such that,
(1) $ s = s_{n} $.
(2) $ s_{0} $ is an acyclic path in $ G $.
(3) For each $ i > 0 $, $ s_{i} $ can be constructed 
from $ s_{i-1} $ as follows:
Choose a rule $ R_{j_{k}} $ in $ s_{i-1} $, and
a simple cycle $ C_{i} = R_{j_{1}} , \ldots , R_{j_{k}} $ in $ G $,
and insert the cycle just after $ R_{j_{k}} $.
\end{lemma}
\begin{proof}
We prove by induction that such a path exists.
As a basis, any path $ s $ of length one is acyclic, and thus has such a 
sequence $ s_{0} = s $.

Consider a path $ s $ of length $ k $ and assume inductively that for
all paths of length less than $ k $ such a sequence exists.
If in the path $ s $ there is no rule that occurs twice, $ s $ is 
acyclic, and we set $ s_{0} = s $, and we are done.
If there is a rule that occurs twice in $ s $, for each rule $ R_{i} $
consider every pair of occurrences of $ R_{i} $.
Choose a pair of occurrences (of any rule) that is separated by the least 
distance, in the path $ s $, and let the rule chosen be $ R_{l} $.
Let the path between the two occurrences be $ R_{j} , \ldots , R_{p} $.
This path cannot contain two occurrences of any rule.
Further, for each pair of consecutive rules $ R_{i_{1}} , R_{i_{2}} $ in 
the derivation path, there must be an edge $ ( R_{i_{1}} , R_{i_{2}} ) $ in 
the rule graph.
Thus, $ R_{j} , \ldots , R_{p} , R_{l} $ must be a simple cycle in the rule 
graph.
Deleting this cycle from $ s $ we get a path of length less than $ k $, 
and by the induction hypothesis there is a sequence $ s_{0} , s_{1} , \ldots ,
s_{i} $ for this subpath.
If we let $ C_{i+1} = R_{j} , \ldots , R_{p} , R_{l} $, 
we get a sequence for $ s $.
\end{proof}

For any derivation path $ s $, such a sequence $ s_{0} , \ldots , s_{n} $
is called a {\em construction sequence\/} for $ s $.
Intuitively, we can create a construction sequence in reverse order by 
successively deleting simple cycles from a derivation path.
A derivation path may not have a unique construction sequence
as the following example shows.

\begin{example}
Consider the rule graph shown in Figure~\ref{mult:cycles}.
The derivation path $ 1 , 4 , \lbok 2 , 5 ,\lbok  1 , 3 ,\lbok  2 , 6 $
has the following two construction sequences associated with it,
\begin{enumerate}
\item $ ( 1 , 3 , 2 , 6 ) $, $ ( 1 , 4 , 2 , 5 , 1 , 3 , 2 , 6 ) $.
This involves the insertion of the simple cycle $ 4 , 2 , 5 , 1 $ in the
acyclic path $ 1 , 3 , 2 , 6 $ just after $ 1 $.
\item $ ( 1 , 4 , 2 , 6 ) $, $ ( 1 , 4 , 2 , 5 , 1 , 3 , 2 , 6 ) $.
This involves the insertion of the simple cycle $ 5 , 1 , 3 , 2  $ in the
acyclic path $ 1 , 4 , 2 , 6 $ just after $ 2 $.
$ \Box $
\end{enumerate}
\noBox
\end{example}

\begin{figure}
\centerline{\psfig{figure=figures/diffnocycles.ps,height=4.0cm,bbllx=276pt,bblly=467.91pt,bburx=532pt,bbury=677pt}}
\caption{Path with Two Alternative Cycle Sequence Lengths}
\label{diff:no:cycles}
\end{figure}

Also, two such construction sequences may have different lengths
as the following example shows.
\begin{example}
Consider the graph shown in Figure~\ref{diff:no:cycles}.
The derivation path $ 1 , 2 , 3 , 1 , 3 , 2 $ has the following two
construction sequences associated with it,
\begin{enumerate}
\item $ ( 1 , 3 , 2 ) $, $ ( 1 , 2 , 3 , 1 , 3 , 2 ) $.
\item $ ( 1 , 2 ) $, $ ( 1 , 2 , 3 , 2 ) $, $ ( 1 , 2 , 3 , 1 , 3 , 2 ) $.
$ \Box $
\end{enumerate}
\noBox
\end{example}

Given a fair ordering $ O $, we now relate the iteration length of a derivation 
path $ s $ with the length of the construction sequence for $ s $ and the 
degree by which the given ordering breaks each of the cycles inserted.

\begin{figure}
\centerline{\psfig{figure=figures/pathord.ps,height=3.0cm,bbllx=144pt,bblly=414pt,bburx=616.74pt,bbury=628pt}}
\caption{Relating Derivation Paths to Order Sequences}
\label{fig:pathord}
\end{figure}

\begin{figure}
\centerline{\psfig{figure=figures/cycleinsert.ps,height=3.0cm,bbllx=150pt,bblly=424pt,bburx=661.38pt,bbury=650pt}}
\caption{Order Sequences After Insertion of a Cycle in a Path}
\label{fig:cycleinsert}
\end{figure}

\begin{theorem}
\label{path:length}
Consider any derivation path $ s $ and a construction sequence 
$ s_{0} , \ldots , s_{n} $ for $ s $ as defined in Lemma \ref{path:cycle}.
Let $ C_{i} $ be the cycle inserted in obtaining $ s_{i} $ from $ s_{i-1} $.
For every fair ordering $ O $, the iteration length of $ s $ under $ O $ 
is given by
$ L ( s , O ) = L ( s_{0} , O ) + \sum_{i=1}^{n} B ( C_{i} , O ) $.
Further, $ L ( s_{0} , O ) $ is bounded by the length of the longest acyclic 
path in the rule graph of the SCC.
\end{theorem}
\begin{proof}
We prove this by induction on the length of the construction sequence for
a derivation path $ s $.
As a basis, note that all construction sequences of length one  have only one
element $ s_{0} $, and it follows that, $ L ( s , O ) = L ( s_{0} , O ) $.
Note that $ L ( s_{0} , O ) $ is data-independent.

Assume inductively that for all paths $ s $ that have a construction sequence 
of length less than or equal to $ k $, 
$ L ( s , O ) = L ( s_{0} , O ) + \sum_{i=1}^{n} B ( C_{i} , O ) $, where 
there is a construction sequence $ s_{0} , \ldots , s_{n} $ for $ s $,
$ n < k $.
Recall that $ L ( s , O ) $ is the minimum number $ i $ such that 
$ s $ forms a subsequence of $ O^{i} $.
Corresponding to each rule occurrence in $ s $, we have a rule occurrence in
some repetition of $ O $ in $ O^{i} $.
Figure~\ref{fig:pathord} depicts this pictorially.

Consider now a path that has no construction sequence of length less than or
equal to $ k $, but has a construction sequence of length $ k+1 $.
Let the last cycle inserted in the sequence be $ C_{k} = R_{s} , \ldots , 
R_{l} $.
$ s_{k-1} $ has a construction sequence of length $ k $, and therefore by the 
induction hypothesis, 
$ L ( s_{k-1} , O ) = L ( s_{0} , O ) + \sum_{i=1}^{k-1} B ( C_{i} , O ) $.
For the path $ s_{k-1} $ we have the corresponding (minimal length)
order sequence, 
$ {\cal O}_{1} = O^{ L ( s_{k-1} , O ) } $, such that $ s_{k-1} $ is a 
subsequence of $ {\cal O}_{1} $.
Similarly, for the path $ s_{k} $ we have the corresponding (minimal length)
order sequence $ {\cal O}_{2} = O^{ L ( s_{k} , O ) } $.
Figure~\ref{fig:cycleinsert} shows $ {\cal O}_{1} $ and $ {\cal O}_{2} $.

Let the point of insertion of $ C_{k} $ in $ s_{k-1} $ be after an occurrence 
of rule $ R_{l} $.
Let this occurrence of $ R_{l} $ be called $ R_{l}^{1} $.
$ R_{l}^{1} $ corresponds to the the (unique) occurrence of $ R_{l} $ 
(labeled $ 1 $ in Figure~\ref{fig:cycleinsert}) in some occurrence 
of $ O $ in $ {\cal O}_{1} $.
Similarly, for $ {\cal O}_{2} $, $ R_{l}^{1} $ corresponds to the 
occurrence of $ R_{l} $ at Point $ 2 $ in $ {\cal O}_{2} $.
Let the occurrence of $ R_{l} $ in the newly inserted cycle be labeled 
$ R_{l}^{2} $.
$ R_{l}^{2} $ corresponds to the (unique) occurrence of $ R_{l} $ 
(labeled $ 3 $ in Figure~\ref{fig:cycleinsert}) in some occurrence
of $ O $ in $ {\cal O}_{2} $.

We claim that the initial part of $ {\cal O}_{1} $ up to (and including) $ 1 $
is the same as the initial part of $ {\cal O}_{2} $ up to (and including) 
$ 2 $, and further, the part of $ {\cal O}_{1} $ after $ 1 $ is the same 
as the part of $ {\cal O}_{2} $ after $ 3 $.
Once we have shown this, we show that the part of $ {\cal O}_{2} $ between 
$ 2 $ and $ 3 $ has exactly $ B ( C_{k} , O ) $ repetitions of $ O $,
which proves the result.

Point $ 1 $ and Point $ 3 $ both correspond to occurrences of rule $ R_{l} $.
Since there is only one occurrence of each rule within $ O $,
Point $ 1 $ is at the same position within a repetition of $ O $ in 
$ {\cal O}_{1} $ as Point $ 3 $ is in a repetition of $ O $ in 
$ {\cal O}_{2} $.
The part of $ s_{k} $ after $ R_{l}^{2} $ and the part of $ s_{k-1} $ 
after $ R_{l}^{1} $ are the same, since $ s_{k} $ is derived from $ s_{k-1} $
by inserting a cycle at $ R_{l}^{1} $, and this cycle ends at $ R_{l}^{2} $.
Call this part of $ s_{k} $ as $ s_{tail} $.

Since $ {\cal O}_{1} $ is a minimal length order sequence for the 
path $ s_{k-1} $, the part of $ {\cal O}_{1} $ after Point $ 1 $ must 
correspond to a minimal length order sequence for the path $ s_{tail} $.
Similarly the part of $ {\cal O}_{1} $ after Point $ 3 $ must also
correspond to a minimal length order sequence for $ s_{tail} $.
Further, Points $ 1 $ and $ 3 $ both correspond to occurrences of $ R_{l} $.
Hence, it follows that the part of $ {\cal O}_{2} $ after Point $ 3 $ must 
be the same as the part of $ {\cal O}_{1} $ after $ 1 $.
By reasoning similar to the above, we can show that the part of $ {\cal O}_{1} $
up to Point $ 1 $ is the same as the part of $ {\cal O}_{2} $ up to 
Point $ 2 $.

Each rule occurs exactly once in each repetition of $ O $, and Points 
$ 2 $ as well as $ 3 $ (in $ {\cal O}_{2} $) correspond to occurrences of rule
$ R_{l} $. 
Thus the part of $ {\cal O}_{2} $ between Points $ 2 $ and $ 3 $ 
(including $ 3 $, but not $ 2 $) corresponds to an integral number of 
repetitions of the cyclic permutation $ O_{r} $ of $ O $ that ends with 
rule $ R_{l} $. 
Since both $ O_{r} $ and $ C_{k} $ end with $ R_{l} $, and $ O_{r} $ is a 
cyclic permutation of $ O $, it follows from Lemma~\ref{minperm:end} that 
$ C_{k} $ forms a subsequence of $ O_{r}^{i} $ for $ i = B ( C_{k} , O ) $, 
but not for any smaller $ i $.
Thus the number of repetitions of $ O_{r} $ between $ 2 $ and $ 3 $ is 
$ B ( C_{k} , O ) $, and the proof is complete.
\end{proof}

Note the interesting fact that the above theorem is true for any construction
sequence.
Since the actual iteration length of a path does not depend on the 
construction sequence chosen, this tells us that, in a certain sense, all
construction sequences are equivalent.
For any cycle preserving fair ordering $ O $ with a construction sequence
$ t_{0} , \ldots , t_{n} $, $ L ( t_n , O ) = L ( t_{0} , O ) + n $.

Consider a rule graph $ G $, and two fair orderings $ O_{1} $ and $ O_{2} $ 
such that $ O_{1} \lhd O_{2} $.
We define 
\[ MaxR ( O_{1} , O_{2} , G ) =  max 
\{ B ( C , O_{2} ) / B ( C , O_{1} ) \mid C {\rm~is~a~simple~cycle~in~} G \}. \]
This serves as a bound on how much costlier, based on the number of 
iterations, $ O_{2} $ can be compared to $ O_{1} $.

Given any two fair orderings that are related by the $ \lhd $ relation, we 
wish to compare the number of iterations taken to compute the closure of
an SCC by the two orderings.
To this end, we first compare the iteration lengths of derivation paths.
This is used to compare the iteration heights of derivation trees for a 
fact.
We then argue about the number of iterations taken
to derive a fact by the two orderings, by comparing the iteration counts of
the fact.
This leads finally to our main result, stated in Theorem~\ref{thm:main}, 
that relates the number of iterations taken to compute the closure of the 
SCC by the two fair orderings.

\begin{lemma}
\label{ord:path}
Consider any two fair orderings $ O_{1} $ and $ O_{2} $ for a graph $ G $, such 
that $ O_{1} \lhd O_{2} $.
For any derivation path $ s $, the iteration lengths of $ s $ under the
two orderings are related as 
$ L ( s , O_{1} ) - k \leq L ( s , O_{2} ) \leq 
MaxR( O_{1} , O_{2}, G ) \cdot L ( s , O_{1} ) + k $,
where $ k $ is bounded by the length of the longest acyclic path in $ G $.
\end{lemma}
\begin{proof}
Since $ O_{1} \lhd O_{2} $, for each cycle $ C $, we have 
$ B ( C , O_{1} ) \leq B ( C , O_{2} ) $.
By definition of $ MaxR ( O_{1} , O_{2} , G ) $, we have 
$ B ( C , O_{2} ) \leq MaxR( O_{1} , O_{2} , G ) \cdot B ( C , O_{1} ) $.

Consider any construction sequence $ s_{0} , \ldots , s_{n} $ for $ s $.
By Theorem~\ref{path:length}, the  iteration lengths of $ s $ under 
$ O_{1} $ and $ O_{2} $ are given by 
$ L ( s , O_{1} ) = L ( s_{0} , O_{1} ) + \sum_{i=1}^{n} B ( C_{i} , O_{1} ) $
and 
$ L ( s , O_{2} ) = L ( s_{0} , O_{2} ) + \sum_{i=1}^{n} B ( C_{i} , O_{2} ) $.

For any fair ordering $ O $ and derivation path $ s $, $ L ( s , O ) $ 
is clearly bounded by the length of path $ s $.
Thus the difference between $ L ( s_{0} , O_{1} ) $ and $ L ( s_{0} , O_{2} ) $
is bounded by the length of the longest acyclic path in $ G $, since
$ s_{0} $ is acyclic.
The lemma follows from the above.
\end{proof}

\begin{lemma}
\label{ord:trees}
Consider any two fair orderings $ O_{1} $ and $ O_{2} $ for a graph $ G $, such 
that $ O_{1} \lhd O_{2} $.
For any derivation tree $ T $, the iteration heights of $ T $ under the
two orderings are related as 
$ L ( T , O_{1} ) - k \leq L ( T , O_{2} ) \leq 
MaxR( O_{1} , O_{2}, G ) \cdot L ( T , O_{1} ) + k $,
where $ k $ is bounded by the length of the longest acyclic path in $ G $.
\end{lemma}
\begin{proof}
Lemma~\ref{lm:itern:ht} shows that the iteration height of $ T $ is given 
by the maximum of the iteration lengths of the paths in $ T $.
Consider the path in $ T $ that has the maximum iteration 
length under $ O_{1} $, and call this path $ s $.
We have $ L ( T , O_{1} ) = L ( s , O_{1} ) $.
By Lemma~\ref{ord:path}, the iteration length of this path under $ O_{2} $ is
bounded from below as $ L ( s , O_{1} ) - k \leq L ( s , O_{2} ) $.
Clearly the maximum of the iteration lengths of paths in $ T $ under ordering
$ O_{2} $ must be greater than or equal to $ L ( s , O_{2} ) $, and thus we
have $ L ( T , O_{1} ) - k \leq L ( T , O_{2} ) $.

For the other side of the inequality, consider the path $ s $ in $ T $ that
has maximum iteration length under $ O_{2} $.
By Lemma~\ref{ord:path}, 
$ L ( s , O_{2} ) \leq MaxR( O_{1} , O_{2}, G ) \cdot L ( s , O_{1} ) + k $.
Since $ L ( s , O_{1} ) \leq L ( T , O_{1} ) $, and 
$ L ( s , O_{2} ) = L ( T , O_{2} ) $, we have 
$ L ( T , O_{2} ) \leq MaxR( O_{1} , O_{2}, G ) \cdot L ( T , O_{1} ) + k $.
\end{proof}

\begin{lemma}
\label{ord:facts}
Given any fact $ p ( \overline{c} ) $, and any two fair orderings,
$ O_{1} $ and $ O_{2} $ such that $ O_{1} \lhd O_{2} $, let the
iteration counts of $ p ( \overline{c} ) $, for $ O_{1} $ and $ O_{2} $,
be $ n_{1} $ and $ n_{2} $, respectively.
$ n_{1} $ and $ n_{2} $ are related as 
$ n_{1} - k \leq n_{2} \leq MaxR( O_{1} , O_{2}, G ) \cdot n_{1} + k $,
where $ k $ is bounded by the length of the longest acyclic path in the
rule graph for the SCC.
\end{lemma}
\begin{proof}
A fact $ p ( \overline{c} ) $ can have several derivation trees.
Consider the derivation tree $ T $ for $ p ( \overline{c} ) $ that has the 
least iteration height under $ O_{2} $.
We have $ L ( T , O_{2} ) = n_{2} $.
By Lemma~\ref{ord:trees}, $ L ( T , O_{1} ) - k \leq L ( T , O_{2} ) $.
The iteration count of $ p ( \overline{c} ) $ under ordering $ O_{1} $ must be 
less than or equal to $ L ( T , O_{1} ) $, and hence we have 
$ n_{1} - k \leq n_{2} $.

Consider now the derivation tree $ T ' $ for $ p ( \overline{c} ) $, that 
has the least iteration height under $ O_{1} $.
By Lemma~\ref{ord:trees}, we must have 
$ L ( T ' , O_{2} ) \leq MaxR( O_{1} , O_{2}, G ) \cdot L ( T ' , O_{1} ) + k $.
The iteration count $ n_{2} $ of $ p ( \overline{c} ) $ under $ O_{2} $ must
be less than or equal to $ L ( T ' , O_{2} ) $, and $ n_{1} = 
L ( T ' , O_{1} ) $, and thus we have
$ n_{2} \leq MaxR( O_{1} , O_{2}, G ) \cdot n_{1} + k $.
\end{proof}

\begin{theorem}
\label{thm:main}
Given an SCC $ S $, any two fair orderings $ O_{1} $ and $ O_{2} $, such that
$ O_{1} \lhd O_{2} $; and any set of base facts, let the number of 
iterations required to compute the closure of $ S $ by bottom-up fixpoint 
evaluations using rule orderings $ O_{1} $ and $ O_{2} $ be
$ n_{1} $ and $ n_{2} $ respectively.
$ n_{1} $ and $ n_{2} $ are related as 
$ n_{1} - k \leq n_{2} \leq MaxR( O_{1} , O_{2} , G ) \cdot n_{1} + k $,
where $ k $ is bounded by the length of the longest acyclic path in the
rule graph for the SCC.
\end{theorem}
\begin{proof}
Consider the fact that is computed last, when the closure of $ S $ is
computed using ordering $ O_{2} $, and call this fact $ p ( \overline{c} ) $.
Clearly $ n_{2} $ iterations are needed to compute this fact.
By Lemma~\ref{ord:facts} this fact will be computed using ordering $ O_{1} $
in $ r_{1} $ iterations, where
$ n_{2} \leq MaxR( O_{1} , O_{2}, G ) \cdot r_{1} + k $.
Further, $ n_{1} \geq r_{1} $, and hence we have 
$ n_{2} \leq MaxR( O_{1} , O_{2}, G ) \cdot n_{1} + k $.

Next consider the fact that is computed last when the closure of $ S $ is
done using ordering $ O_{1} $, and call this fact $ p ' ( \overline{c '} ) $.
This fact needs $ n_{1} $ iterations to compute.
By Lemma~\ref{ord:facts}, this fact is computed using ordering $ O_{2} $ in 
$ r_{2} $ iterations, with $ n_{1} - k \leq r_{2} $.
Further $ n_{2} \geq r_{2} $, and hence we have $ n_{1} - k \leq n_{2} $.
\end{proof}

\begin{corollary}
Given any two cycle preserving fair orderings, the number of iterations required
to compute the closure of an SCC by bottom-up fixpoint evaluations using
the two orderings differ by at most a (data-independent) constant.
Also, the number of rule applications required by the two orderings 
differ by at most a (data-independent) constant.
$ \Box $
\end{corollary}

\subsubsection{Generating Cycle Preserving Fair Orderings}

In the previous section, we have shown the optimality of cycle preserving fair
orderings under the cost criterion of number of iterations needed to compute
the closure of an SCC.
However, there are SCCs that do not have any cycle preserving fair orderings.
For instance, the SCC whose rule graph is a complete directed graph 
with three vertices is one such SCC.
If an SCC has a simple cycle that has some subsequence $ x , y , z $ and
another simple cycle in the same SCC has the subsequence $ z , y , x $,
then no fair ordering can preserve both these cycles.
Thus this SCC has no cycle preserving fair ordering.

An SCC with $ n $ rules could have an exponential number of simple cycles.
A naive algorithm would examine all $ O ( n ! ) $ orderings and all simple 
cycles to check if the ordering preserves every simple cycle.
However, this would be very inefficient, and
an important open problem is to find an efficient algorithm that checks
whether an SCC has a cycle preserving fair ordering and if so, produces it.
A more general open problem is to find a fair ordering such that the 
maximum degree to which it breaks any cycle is minimized, in case there 
is no cycle preserving fair ordering.
Finding what complexity classes these problems belong to is also an
interesting open problem.

As a heuristic, we suggest the reverse of a depth-first search pop-out order 
of the rule graph.
We call this ordering the {\em ReversePopout\/} ordering.
This produces a fair ordering that often preserves cycles in an SCC.
However, this procedure does not guarantee that all cycles are preserved, even
if the SCC has a cycle preserving fair ordering, and in the worst case this 
procedure could break the cycles in the rule graph to a high degree.

\begin{example}
Consider the graph in Figure~\ref{mult:cycles}.
One possible ReversePopout ordering is $ ( 1, 4, 3, 2, 6, 5 ) $, and this 
is a cycle preserving fair ordering.
On this example, every ReversePopout ordering is cycle preserving.
\end{example}

\begin{figure}
\centerline{\psfig{figure=figures/breakpopout.ps,height=2.0cm,bbllx=283.08pt,bblly=700.99pt,bburx=492.38pt,bbury=797.91pt}}
\caption{Graph on which ReversePopout May Not Work}
\label{break:popout}
\end{figure}

\begin{example}
On the other hand, consider the graph in Figure~\ref{break:popout}.
On this graph, if the node $ 1 $ is chosen as the starting node for the 
depth-first search, the ReversePopout ordering produced is the cycle preserving 
fair ordering $ ( 1 , 2 , 3 , 4 , 5 ) $.
However, if node $ 5 $ is chosen as the starting node, the fair ordering
$ ( 5 , 4 , 3 , 2 , 1 ) $ could be produced, which does not preserve the cycle
$ 1 , 2 , 3 , 4 , 5 $.
\end{example}

%%%%%%%%%%%%%%%%%%%%
% NP - HARDNESS Results ??
%%%%%%%%%%%%%%%%%%%%
% \begin{theorem}
% The problem of finding a cycle preserving ordering on directed graph is
% NP-Hard.
% \end{theorem}
%%%%%%%%%%%%%%%%%%%%

\subsection{Non-Fair Orderings}
\label{non:fair}

In this section we consider static orderings in which some rules may be 
applied more often than other rules.
We divide this class into the class of flat orderings and the class of 
non-flat nested orderings.

\begin{nameddefinition} {Nested ordering}
A {\em nested ordering\/} is an ordering $ O $ of the form $ ( O1 ) $, 
where $ O1 $ is generated by the grammar 
\[ O1 \rightarrow R_{1} \mid \ldots \mid R_{n} \mid O1 \cdot O1 \mid ( O1 ) ^{\ast} \]
where $ R_{1} , \ldots , R_{n} $ are the rules of an SCC $ S $ of the 
rule graph, such that each rule in the SCC occurs at least once in 
the ordering $ O $.
\end{nameddefinition}
An example is the ordering $ ( R_{1} \cdot R_{2} \cdot ( R_{3} \cdot R_{4} ) ^{\ast} \cdot R_{5} ) ^{\ast} $.
Note that a nested ordering can have more than one occurrence of any
rule in the SCC.

\begin{nameddefinition} {Flat ordering}
A {\em flat ordering\/} is a nested ordering that has parentheses only at
the outermost level.
\end{nameddefinition}
The {\em nesting level\/} of nested orderings is defined in the obvious
manner, where a flat ordering is defined to have a nesting level of one.

\begin{proposition}
\label{prop:opt:flat}
Consider an SCC $ S $, and any flat ordering $ O $ of the rules in $ S $.
Let $ k_{1} $ be the number of rule occurrences in $ O $.
Let $ n_{opt} $ be the minimum number of rule applications needed to compute 
the closure of $ S $ on a given database, using a sequential evaluation 
with immediate updates.
If $ n_{O} $ denotes the number of rule applications needed to compute the 
closure of $ S $ on the same database, using the ordering $ O $,
then $ n_{O} \leq n_{opt} \cdot k_{1} $.
\noBox
\end{proposition}
\begin{proof}
Consider the sequence of rule applications used to compute the 
closure of $ S $ using $ n_{opt} $ rule applications.
Replacing every occurrence of each rule in this sequence by the 
entire flat ordering $ O $, we get a sequence of $ n_{opt} $ occurrences
of $ O $ that computes the closure of $ S $.
Since there are $ n_{opt} \cdot k_{1} $ rule applications in this 
sequence, we are guaranteed that the closure of $ S $ using the flat 
ordering $ O $ will take at most $ n_{opt} \cdot k_{1} $ rule applications.
\end{proof}

We now compare flat orderings with nested orderings.

%**** Discuss how to make a flat ordering with repeats perform badly.
%****  Talk of cycles w/out rule repetition being pumped.

\begin{lemma}
\label{lm:bsn:nest}
Consider an SCC $ S $, and let $ O $ be any nested ordering with $ k_{1} $
rule occurrences and a nesting level of $ s $.
Let $ iter_{bsn} $ be the number of iterations needed to compute 
the closure of $ S $ using BSN.
If $ n_{O} $ denotes the number of rule applications needed to compute the 
closure of $ S $ using the ordering $ O $,
then $ n_{O} \leq (iter_{bsn})^{s}\cdot k_{1} $.
\end{lemma}
\begin{proof}
Consider the outermost level of nesting in $ O $.
On each iteration of this level, each rule in the SCC is applied at least
once.
Thus we can have at most $ iter_{bsn} $ iterations of this level, before
a fixpoint is reached.
Consider any nested subexpression at the next level of nesting.
This expression is encountered once for each iteration of the outermost
level of nesting.
The fixpoint of the entire program using BSN takes at most $ iter_{bsn} $ 
iterations, hence there is no derivation path of length greater than
$ iter_{bsn} $.
Thus, each time this subexpression is encountered, it can iterate at most 
$ iter_{bsn} $ times.
Proceeding inductively, we note that the innermost level of nesting 
iterates at most $ (iter_{bsn})^{s} $ times.
Thus no rule occurrence in $ O_{n} $ is applied more than $ (iter_{bsn})^{s} $
times.
Since there are $ k_{1} $ rule occurrences in $ O_{n} $, the result of the
lemma is established.
\end{proof}

The following theorem summarizes our comparison of flat and nested orderings.

\begin{theorem}
\label{thm:nested}
Consider an SCC $ S $, and any flat ordering $ O_{f} $ and any nested 
ordering $ O_{n} $ on $ S $.
Let $ iter_{bsn} $ be number of iterations needed to compute 
the closure of $ S $ using BSN.
If $ n_{f} $ and $ n_{n} $ denote the number of rule 
applications needed to compute the closure of $ S $ using $ O_{f} $ and 
$ O_{n} $ respectively, then 
$ n_{f} / k \leq n_{n} \leq (iter_{bsn})^{s} \cdot k_{1} $, where
$ k $ is the number of rule occurrences in $ O_{f} $, $ k_{1} $ is the
number of rule occurrences in $ O_{n} $, and $ s $ is the 
nesting level of $ O_{n} $.
\end{theorem}
\begin{proof}
The number of rule applications using any flat ordering is bounded as
$ iter_{bsn} \leq n_{f} $, where $ iter_{bsn} $ is the number of iterations 
needed to compute the closure of $ S $ using BSN.
Clearly $ n_{opt} \leq n_{n} $, and the theorem follows from 
Proposition~\ref{prop:opt:flat} and Lemma~\ref{lm:bsn:nest}.
\end{proof}

Since an optimal fair ordering must take at least as many rule applications as
an optimal rule ordering, the above theorem also directly bounds how 
much worse an arbitrary flat ordering can be compared to an optimal 
fair ordering.

Note that every fair ordering is also a flat ordering, and hence the above 
theorem applies when we compare fair orderings with nested orderings.
The worst case performance of nested orderings is bounded, as shown above.
In Section~\ref{performance} we describe an example where the performance
of a nested ordering is indeed as bad (to within a small constant factor)
as the above upper bound allows (Program $P2$, data set $S64$).
Thus, although a nested ordering can perform somewhat better 
(i.e.\ $n_f = c * n_n$, $1 < c \leq k$) than fair 
orderings on some data sets, it is possible for it to perform much worse 
(when $n_n = (iter_{bsn})^s . k_1$)
on other data sets.
Note also that $ iter_{bsn} \geq n_{f} / k $.

%*** General proofs about worst case nested orderings in here
%*** Link up in a clean fashion to comparison of fair with flat orderings.

\section{Performance Results}
\label{performance}

In this section we describe results of a performance study 
of the benefits of immediate availability of facts, and the benefits of 
ordering rules as described in Section~\ref{rule:pred:order}.
These results bear out the theoretical analysis presented in earlier 
sections.
We then compare fair orderings with nested orderings, and show that for some 
data sets, nested orderings outperform fair orderings, whereas for other data
sets they perform much worse.
We also consider several possible join strategies, and for each of these
we compare the relative join costs (ignoring fixed overheads associated with
each join) of the different evaluation techniques.
Our performance study draws upon and extends the work of 
Kuittinen et al.~\cite{sippu90:eval}.
We also discuss work by Leask et al.~\cite{lrs:par:aditi}, which 
uses total elapsed time on a disk-based
deductive database system as the metric, to show the benefits of using
PSN over BSN.

We consider two programs, referred to as $ P1 $ and $ P2 $ in this 
section.\footnote{$ P1 $ is the 
same program that was used in \cite{sippu90:eval}.} 
These programs and corresponding data sets are presented in 
Appendix~\ref{progs}.

The semi-naive rewriting used is the version proposed in \cite{br:adijlp},
and described in Section~\ref{basic:sn}.
The above programs were hand-coded for each of the evaluation techniques, and 
measurements were made by running the resultant programs on the data sets
described.
There is a cycle preserving fair ordering for each SCC of $ P1 $ and
$ P2 $, and the column ``General 1'' of the tables is for a 
GSN evaluation using such an ordering.
The column ``General 2'' in the tables for $ P1 $ corresponds to a 
GSN evaluation of $ P1 $ using a fair ordering that breaks a cycle to 
degree six.
The column ``Nested'' in the tables for $ P2 $ corresponds to the nested 
ordering described in Appendix~\ref{progs}.
Column ``Basic'' corresponds to a Basic Semi-Naive evaluation, and 
column ``Pred'' is for a Predicate Semi-Naive evaluation
using a cycle preserving fair ordering based on the predicate graph.

For $ P1 $ we use the data sets $ A10, B64 $, and $ F10 $.
Data set $ A10 $ results in no duplicate derivations with $ P1 $, but takes 
a large number of iterations.
Data set $ B64 $ is large, takes a moderate number of iterations, and 
results in a moderate number of duplicates.
Data set $ F10 $ results in a large number of duplicate derivations, but
a fewer number of iterations.

For $ P2 $ we use two data sets, $ C16 $ and $ S64 $.
$ C16 $ is designed such that the nested ordering we consider performs well,
and $ S64 $ is designed such that the nested ordering performs very badly
compared to the cycle preserving fair ordering.

\begin{table}
\centerline{
\begin{tabular}{|l|r|r|r|r|} \hline
Data Set & \multicolumn{1}{c|}{Basic} & \multicolumn{1}{c|}{Pred} &
    \multicolumn{1}{c|}{General 1} & \multicolumn{1}{c|}{General 2} \\
	\hline
$ A10 $ & 	3579 & 	1535 & 	1023 & 	2812 \\ 
$ B64 $ &	146	 &	73	 &	68	 &	80	\\
$ F10 $ &	23   &	10	 &	7    &	18	\\
\hline
\end{tabular}
}
\caption{Program $ P1 $: Number of Iterations}
\label{table:iter}
\end{table}

Table~\ref{table:iter} shows the number of iterations taken by each evaluation
strategy on $ P1 $.
It should be noted that the total number of rule applications (considered)
is directly proportional to the number of iterations taken.
PSN outperforms BSN on this measure.
It improves over the performance of BSN by over $ 50 \% $ on all data 
sets considered.
GSN with a cycle preserving fair ordering outperforms PSN by about $ 30 \% $
(on $ A10 $ and $ F10 $) and performs about $ 50 \% $ to $ 70 \% $ better 
than BSN.
GSN with a bad fair ordering performs much worse than GSN with a good fair
ordering (although it can never be worse than BSN), and this clearly 
brings out the benefits of good fair orderings.

\begin{table*}
\centerline{
\begin{tabular}{|l|r|r|r|r|r|r|r|r|} \hline
Data Set & \multicolumn{2}{c|}{Basic} & \multicolumn{2}{c|}{Pred} &
    \multicolumn{2}{c|}{General 1} & \multicolumn{2}{c|}{General 2} \\
	\hline
& Non-Nl & Null & Non-Nl & Null & Non-Nl & Null & Non-Nl & Null \\ 
    \hline
$ A10 $ & 6126 & 14835 & 	6126 & 4615 & 	5230 & 2693 & 	6126 & 11000 \\
$ B64 $ & 1066 & 196   &	549	 & 88	& 	588  &	14	&	596	 &	96	\\
$ F10 $ & 73 & 78 & 		57 & 17 & 		45 & 10 & 		73 & 53 \\
\hline
\end{tabular}
}
\caption{Program $ P1 $: Number of Joins (Non-Null and Null)}
\label{table:joins}
\end{table*}

If one of the relations in the join is empty, the result of the join is null,
and we call such a join a {\em null join}.
We may be able to detect this condition at run time without incurring 
much cost.
Table~\ref{table:joins} shows the number of joins used by each evaluation
strategy on $ P1 $, divided into the number of null joins, and the 
number of non-null joins.
The total number of joins taken by General 1 is better
than PSN, which in turn is better than BSN.
If we count only non-null joins, this is not strictly true.
PSN always performs no worse than BSN, and on $ B64 $ performs about $ 50 \% $
fewer non-null joins.
General 1 performs $ 15 \% $ to $ 45 \% $ better than BSN on this count.
On one data set, $ B64 $, PSN is slightly better (less than $ 7 \% $) 
than General 1.
However, on the other two data sets, General 1 outperforms PSN by about
$ 15 \% $ to $ 20 \% $.

\begin{table}
\centerline{
\begin{tabular}{|l|l|r|r|r|r|r|} \hline
Data Set & Eval.\ Tech.\ & \multicolumn{1}{c|}{Non-Nl Joins} & 
	\multicolumn{1}{c|}{Hashed} &
    \multicolumn{1}{c|}{Constant} & \multicolumn{1}{c|}{Logarithmic} & 
	\multicolumn{1}{c|}{Linear} \\ \hline
$ A10 $ & Basic & 6126 & 1 & 1 & 1 & 1 \\
$ A10 $ & Pred & 6126 & 1.000 & 1.000 & 1.000 & 1.000 \\
$ A10 $ & General 1 & 5230 & 0.856 & 1.000 & 1.000 & 1.000 \\ \hline
$ B64 $ & Basic & 1066 & 1 &	1 & 1 & 1 \\
$ B64 $ & Pred & 549 & 0.525 & 1.000 & 0.999 & 1.000 \\
$ B64 $ & General 1 & 588 & 0.542 & 1.000 & 0.997 & 1.000 \\ \hline
$ F10 $ & Basic & 73 & 1 & 1 & 1 & 1 \\
$ F10 $ & Pred & 57 & 0.900 & 1.000 & 1.004 & 1.001 \\
$ F10 $ & General 1 & 45 & 0.822 & 1.003 & 1.013 & 1.025 \\
\hline
\end{tabular}
}
\caption{Program $ P1 $: Normalized Joins Costs (Without Overheads) Under 
Various Assumptions}
\label{table:joincosts}
\end{table}

The cost of a single join can be modeled in different ways, depending on the
join strategy used.
In Tables~\ref{table:joincosts} and \ref{table:nest:joincosts}, 
we present the portion of the join cost that excludes the per-join
overhead.
To get the full join cost, we must add the overhead per join times the 
number of (non-null) joins.
In these tables, the column ``Hashed'' is a measure of the join cost 
(excluding overheads) using the hash join technique.
The column ``Constant'' corresponds to a nested loop join with indices that can
be accessed in constant time (for instance, a hash index), the column 
``Logarithmic'' corresponds to nested loops join with a logarithmic access 
time index (for instance, a B-tree index), and
the column ``Linear'' corresponds to  a nested loop join without indices (which 
is equivalent to an index with access time linear in the size of the 
relation).
All these costs are normalized (with Basic $ = 1 $ for each technique and 
data set) order of magnitude estimates derived directly from 
the sizes of the relations.
The size of the result of the join is included in the join cost.
Note the following important points:

\begin{itemize}
\item I/O costs and overhead costs for joins are not measured in these tables. 
The number of non-null joins may be used to estimate the total overhead
and this should be added to the cost in the table.
Since the overheads are implementation dependent and we currently lack an
actual system to measure the overheads, we do not present the total cost.
Some results comparing PSN with BSN using total elapsed time on
a disk based system are presented in \cite{lrs:par:aditi}.
We discuss these results later in this section.

\item The only comparisons that may be made from this table are the 
differences between the different evaluation strategies.
These numbers should not be used to directly compare different join 
techniques (i.e.\ the numbers in a single row of the table should not
be compared).
\end{itemize}
The performance study of Kuittinen et al.~\cite{sippu90:eval} only models
the join cost in one way, the hashed join method.

The performance results in Table~\ref{table:joincosts} indicate that
for the hash join strategy the total
join cost closely parallels the number of non-null joins.
PSN and GSN do consistently better than BSN under this metric.
The performance results also indicate that under other join cost assumptions
(nested loops without indices, and with constant or logarithmic access time
indices), the total join costs apart from the I/O costs and
other overheads associated with 
each join, are practically the same for each of the fixpoint evaluation
strategies we study (BSN, PSN, and GSN).
In these cases the number of non-null joins becomes the significant factor.

\begin{table}
\centerline{
\begin{tabular}{|l|l|r|r|r|} \hline
Data Set & Eval.\ Tech.\ & \multicolumn{1}{c|}{Constant} & 
	\multicolumn{1}{c|}{Logarithmic} & 
	\multicolumn{1}{c|}{Linear} \\ \hline
$ A10 $ & Basic & 1 & 1 & 1 \\
$ A10 $ & Pred & 1.000 & 1.000 & 1.000 \\
$ A10 $ & General 1 & 1.000 & 1.000 & 1.000 \\ \hline
$ B64 $ & Basic & 1 & 1 & 1 \\
$ B64 $ & Pred & 1.000 & 1.023 & 1.007 \\
$ B64 $ & General 1 & 1.000 & 0.998 & 1.004 \\ \hline
$ F10 $ & Basic & 1 & 1 & 1 \\
$ F10 $ & Pred & 1.000 & 1.012 & 1.017 \\
$ F10 $ & General 1 & 1.009 & 1.024 & 1.049 \\
\hline
\end{tabular}
}
\caption{Program $ P1 $: Duplicate Elimination Costs}
\label{table:dupcosts}
\end{table}

The cost of checking for and eliminating duplicates could form 
a significant part of the total cost of evaluation.
In our analysis of duplicate elimination costs, we measure these costs as a
function of the sizes of the relations involved and as before do not
measure I/O costs.
As before, these values are normalized order of magnitude estimates and 
should not be used to compare different duplicate elimination techniques.
In Tables~\ref{table:dupcosts} and \ref{table:nest:dupcosts}, the
column ``Constant'' refers to the cost of duplicate elimination assuming the
availability of a constant access time index, the column ``Logarithmic'' 
assumes the availability of a logarithmic access time index and the column
``Linear'' assumes that no index is available.

The performance results in Table~\ref{table:dupcosts} indicate that 
the duplicate elimination costs for each of the evaluation strategies
(BSN, PSN and GSN) is approximately the same, for each of the indexing
strategies used.
Thus, the relative costs of the evaluation techniques should not depend on
the duplicate elimination costs.

\begin{table}
\centerline{
\begin{tabular}{|l|r|r|r|r|} \hline
Data Set & \multicolumn{1}{c|}{Basic} & \multicolumn{1}{c|}{Pred} &
    \multicolumn{1}{c|}{General 1} & \multicolumn{1}{c|}{Nested} \\
	\hline
$ C16 $ & 	282 & 	221 & 	207 & 	179 \\ 
$ S64 $ &	1717	&	588	 &	583	 &	2536	\\
\hline
\end{tabular}
}
\caption{Program $ P2 $: Number of Rule Applications}
\label{table:nest:rule}
\end{table}

Table~\ref{table:nest:rule} shows the number of rule applications taken
by each evaluation strategy on $ P2 $.
It can be seen that for $ C16 $, Nested is better than
the fair ordering indicated by General 1.
However, for $ S64 $ Nested performs much worse than any
of the other evaluation strategies.
Both PSN and General 1 are about $ 20 \% $ to $ 65 \% $ better than BSN.

\begin{table*}
\centerline{
\begin{tabular}{|l|r|r|r|r|r|r|r|r|} \hline
Data Set & \multicolumn{2}{c|}{Basic} & \multicolumn{2}{c|}{Pred} &
    \multicolumn{2}{c|}{General 1} & \multicolumn{2}{c|}{Nested} \\
	\hline
& Non-Nl & Null & Non-Nl & Null & Non-Nl & Null & Non-Nl & Null \\ 
    \hline
$ C16 $ & 459 & 203 & 	372 & 162 & 	364 & 139 & 	304 & 30 \\
$ S64 $ & 2002 & 1016   &	1386	 & 389	& 	1447  &	323	&	5230 &	446	\\
\hline
\end{tabular}
}
\caption{Program $ P2 $: Number of Joins (Non-Null and Null)}
\label{table:nest:joins}
\end{table*}

Table~\ref{table:nest:joins} shows the number of joins used by each
evaluation strategy on $ P2 $.
Again, the number of joins taken by Nested is better than
the fair ordering indicated by General 1 for the data set $ C16 $.
However, Nested performs very badly on the data set $ S64 $ compared to
each of the other evaluation strategies.
General 1 and PSN are about $ 20 \% $ to $ 30 \% $ better than BSN.

\begin{table}
\centerline{
\begin{tabular}{|l|l|r|r|r|r|r|} \hline
Data Set & Eval.\ Tech.\ & \multicolumn{1}{c|}{Non-Nl Joins} & 
	\multicolumn{1}{c|}{Hashed} &
    \multicolumn{1}{c|}{Constant} & \multicolumn{1}{c|}{Logarithmic} & 
	\multicolumn{1}{c|}{Linear} \\ \hline
$ C16 $ & Basic & 459 & 1 & 1 & 1 & 1 \\
$ C16 $ & Pred & 372 & 0.899 & 1.119 & 1.110 & 1.063 \\
$ C16 $ & General 1 & 364 & 0.900 & 1.118 & 1.117 & 1.045 \\
$ C16 $ & Nested & 304 & 0.582 & 0.867 & 0.852 & 0.857 \\ \hline
$ S64 $ & Basic & 2002 & 1 & 1 & 1 &	1 \\
$ S64 $ & Pred & 1386 & 0.631 & 0.977 & 1.002 &	0.977 \\
$ S64 $ & General 1 & 1447 & 0.764 & 0.977 &	1.001 &	0.977 \\ 
$ S64 $ & Nested & 5230 & 4.827 & 0.973 & 0.940 & 0.977 \\
\hline
\end{tabular}
}
\caption{Program $ P2 $: Joins Costs Under Various Assumptions}
\label{table:nest:joincosts}
\end{table}

\begin{table}
\centerline{
\begin{tabular}{|l|l|r|r|r|} \hline
Data Set & Eval. Tech.\ & \multicolumn{1}{c|}{Constant} & 
	\multicolumn{1}{c|}{Logarithmic} & 
	\multicolumn{1}{c|}{Linear} \\ \hline
$ C16 $ & Basic & 1 & 1 & 1 \\
$ C16 $ & Pred & 1.110 & 1.175 & 1.337 \\
$ C16 $ & General 1 & 1.095 & 1.163 & 1.329 \\
$ C16 $ & Nested & 0.882 & 0.971 & 1.251 \\ \hline
$ S64 $ & Basic & 1 & 1 & 1 \\
$ S64 $ & Pred & 0.974 & 1.129 & 1.081 \\
$ S64 $ & General 1 & 0.974 & 1.116 & 1.075 \\
$ S64 $ & Nested & 0.974 & 0.894 & 1.002 \\
\hline
\end{tabular}
}
\caption{Program $ P2 $: Duplicate Elimination Costs}
\label{table:nest:dupcosts}
\end{table}

The performance results in Table~\ref{table:nest:joincosts} are similar
to those in Table~\ref{table:joincosts} for the BSN, PSN and GSN evaluation
strategies.
It should be noted that using the hashed join strategy,
the nested evaluation ordering performs slightly better on one data set
(namely, $ C16 $), but performs considerably worse on $ S64 $.

Our performance results underscore the theoretical results 
described in earlier sections.
The benefits of immediate availability of facts is indicated by the fact 
that GSN is in general better than PSN, which, in turn, is in general
better than BSN, under the cost criterion of number of rule applications and
iterations.
Further, our results clearly bring out the advantages of cycle preserving
fair orderings.
Our results also indicate that nested orderings may perform better than fair
orderings on some data sets, but can perform much worse on others.

%%%%%%%
% that the number of rule applications
% and the number of iterations is a 
% good measure of the total cost (join costs and overheads) of evaluating
% the closure of an SCC, under any of the above assumptions about the cost
% of a single join.
% This gives us a good justification for the choice of number of rule 
% applications (and hence the number of iterations for fair orderings) as 
% the cost measure in our theoretical analysis.
%%%%%%%

\subsection{Related Work}
\label{sec:perf:rel:work}

Leask et al.~\cite{lrs:par:aditi} investigate the parallelism
that is available in answering queries bottom-up when the logic
program is compiled into a relational language.
While their main results are on parallelism, their results also
shed light on the relative performance of BSN and PSN.

PSN can be implemented with the same overheads per iteration as BSN, 
but can do better in terms of the number of iterations taken.
Our performance results also indicate that PSN is always preferable
to BSN on this metric.
However, our performance results do not compare the {\em total\/} cost 
of evaluation using the various strategies
described; in particular, the I/O costs and the fixed overhead 
incurred in performing
a join, a rule application, or an iteration is not included in the
relative cost estimates.
Consequently, our results do not quantify the relative advantage
of PSN over BSN.

Leask et al.~\cite{lrs:par:aditi} use two programs---one which admits
of a good fair ordering, and one which does not---to compare the 
various evaluation strategies.
The join strategy used was sort-merge.
The performance metric they used was total elapsed time;
this includes the cost of accessing relations, as well as the various
overheads incurred in a bottom-up evaluation, and is a 
realistic cost estimate for comparing the performance of the various
strategies.
On each of the two programs, PSN considerably outperforms BSN.
For the program which admits of a good fair ordering,
PSN reduces the total time taken by about a half,
while on the other program, the improvement is about $15\%$.

The results of \cite{lrs:par:aditi} also indicate that 
PSN is the evaluation strategy of choice, in the absence
of semantic information about the data in the base relations,
even when compared with the parallel evaluation strategies 
described in \cite{lrs:par:aditi}.

\section{Conclusion}
\label{concl}

In this paper, we studied several aspects of rule ordering in the bottom-up
evaluation of logic programs.
Rule orderings are necessary for ensuring a desired semantics, such as
the evaluation of the magic rewritten versions of stratified programs.
We presented two evaluation algorithms, GSN and PSN, that could be used
for evaluating such rule orderings, while preserving the non-repetition 
property, and discussed cases where each was useful.
%%%%%%%%
% Whereas PSN was shown to suffice to evaluate stratified programs, GSN is
% a more general evaluation strategy and can handle arbitrary control 
% expressions.
%%%%%%%%

We studied rule orderings theoretically, and 
showed that for the class of fair orderings, cycle preserving orderings
were optimal and, in the absence of additional information, fair orderings
are to be preferred to non-fair orderings.
An important open problem is to find an efficient algorithm that checks
whether an SCC has a cycle preserving fair ordering and if so, produces it.

We also presented a performance study to support 
our theoretical analyses.
Rule orderings were also shown to be useful for improving the total cost
of sequential evaluation of logic programs.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Acknowledgements}

We would like to thank the referees for their comments, which helped 
improve the presentation of the paper.  We would also like to thank them
for pointing out some related work.

% \pagebreak[4]

\appendix

\section{Programs}
\label{progs}

\logicprogfig{Program $ P1 $}{
\lfact{1:} {msg(1)} \\
\lrule{2:} {supm2( X,X1)} {msg(X), up(X,X1)} \\
\lrule{3:} {supm3(X,X2)} {supm2(X,X1), sg(X1,X2)}  \\
\lrule{4:} {supm4(X,Y2)} {supm3(X,X2), flat(X2, Y2)} \\
\lrule{5:} {sg(X,Y)} {msg(X), flat(X,Y)} \\
\lrule{6:} {sg(X,Y)} {supm4(X,Y2), sg(Y2, Y1), \lbok down(Y2,Y)} \\
\lrule{7:} {msg(X1)} {supm2( X, X1)} \\
\lrule{8:} {msg(Y2)} {supm4(X, Y2)} \\
\lrule{9:} {query(Y)} {sg(1,Y)}
}

In $ P1 $, rules $ 1 $ and $ 9 $ are in separate Rule-SCCs, and the other 
seven rules are in one SCC of the rule graph.
The cycle preserving fair ordering for this program is 
$ 1 \cdot ( 2 \cdot 7 \cdot 5 \cdot 6 \cdot 3 \cdot 4 \cdot 8) \cdot 9 $.
The ordering $ 1 \cdot ( 2 \cdot 8 \cdot 4 \cdot 3 \cdot 6 \cdot 5 \cdot 7) 
\cdot 9 $ breaks a cycle to a degree six, and is used in General 2.

\logicprogfig{Program $ P2 $}{
\lrule{1:} {anc ( X , Y , 1 )} {manc( X ) , up ( X , Y )} \\
\lrule{2:} {anc ( X , Y , N )} {N > 1, manc(X), \lbok anc(X,Z, N-1), \lbok
up ( Z , Y )} \\
\lrule{3:} {desc ( X , Y , 1 )} {mdesc(X, 1), down ( X , Y )} \\
\lrule{4:} {desc (X,Y,N)} {\mbox{$ N > 1$}, mdesc(X,N), \lbok desc(X,Z,N-1),
\lbok down ( Z , Y )} \\
\lrule{5:} {sg ( X , Y )} {msg(X), flat( X , Y )} \\
\lrule{6:} {sg ( X , Y )} {msg(X), anc ( X, X1, N ), \lbok flat (X1,X2 ), 
sg ( X2 , Y2 ) ,\lbok flat ( Y2 , Y1 ) ,\lbok desc ( Y1 , Y , N )} \\
\lrule{7:} {manc ( X )} {msg(X)} \\
\lrule{8:} {msg ( X2 )} {msg(X), anc(X,X1,N) , \lbok flat ( X1 , X2 )} \\
\lrule{9:} {mdesc(Y1,N)} {msg(X), anc ( X , X1 , N ),\lbok flat (X1,X2 ),
\lbok sg ( X2 , Y2 ) , flat ( Y2 , Y1 )} \\
\lrule{10:} {mdesc (X,N-1)} {mdesc(X,N), N~>~1} \\
\lfact{11:} {msg( 1 )} \\
\lrule{12:} {query(X)} {sg ( 1 , X )}
}

There are two non-trivial SCCs in the rule graph of $ P2 $.
The fair orderings chosen for each of the Rule-SCCs is cycle preserving.
Combining the fair orderings for each Rule-SCC, the fair rule ordering used for
$ P2 $ is $ 11 \cdot ( 7 \cdot 1 \cdot 2 \cdot 8 ) \cdot 5 \cdot
( 9 \cdot 10 \cdot 3 \cdot 4 \cdot 6 ) \cdot 12 $.
Combining the nested orderings for the Rule-SCCs, the nested ordering used for 
this program is $ 11 \cdot ( 7 \cdot 1 \cdot ( 2 )^{\ast} \cdot 8 )^{\ast} 
\cdot 5 \cdot ( 9 \cdot 10 \cdot 3 \cdot ( 4 )^{\ast} \cdot 6 )^{\ast} 
\cdot 12 $.

\begin{figure}
\centerline{\psfig{figure=figures/A10.ps,height=4.0cm,bbllx=170pt,bblly=696pt,bburx=641pt,bbury=919pt}}
\caption{Data Set $ A10 $}
\label{fig:A10}
\end{figure}

\begin{figure}
\centerline{\psfig{figure=figures/B64.ps,height=4.0cm,bbllx=207pt,bblly=701pt,bburx=638pt,bbury=890pt}}
\caption{Data Set $ B64 $}
\label{fig:B64}
\end{figure}

\begin{figure}
\centerline{\psfig{figure=figures/C16.ps,height=4.0cm,bbllx=206pt,bblly=701pt,bburx=639pt,bbury=890pt}}
\caption{Data Set $ C16 $}
\label{fig:C16}
\end{figure}

\begin{figure}
\centerline{\psfig{figure=figures/S64.ps,height=5.0cm,bbllx=110pt,bblly=593pt,bburx=606pt,bbury=957pt}}
\caption{Data Set $ S64 $}
\label{fig:S64}
\end{figure}

Data sets $ A10 $ and $ B64 $ are the same as those used in \cite{sippu90:eval}.
They are depicted in Figures~\ref{fig:A10} and \ref{fig:B64} respectively.

A {\em grid} is defined to be a structure such that: 
\begin{enumerate}
\item If $i$ and $j$ are nodes in the same column and $i$ is below $j$,
there is a fact $ up ( i, j ) $ as well as a fact $ down (j,i) $, and 
\item If $i$ and $j$ are nodes in the same row and $j$ is immediately to
the right of $i$, there is a fact $ flat ( i , j ) $.
\end{enumerate}

Data set $ Cn $ is a grid with $ n $ rows and $ 8 $ columns.
We depict $C16$ in Figure~\ref{fig:C16}.
Data set $ F10 $ represents a $ 10 \times 10 $ grid, with the additional
facts $ up ( i, j) $ and $ down ( j,i) $ for every pair of nodes $ i $ , $ j $
that are in the same column, and $ i $ is below (but not necessarily 
immediately below) $ j $.
Data set $ S64 $ is as shown in Figure~\ref{fig:S64}.

\bibliography{lib/bib/moredb,lib/bib/dbimp}

\end{document}

