\documentstyle{tproc}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% MACRO DEFINITIONS


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% COMMANDS FOR COMMENTING, REMINDERS, EATING TEXT etc.
%    \eat{..}: 
%	Useful for temporarily removing text from the output.
%    \comment{..}:
%    \inlinecomment{..}:
%    \reminder{..}:  
%	This is a very useful command.  It adds the argument as inline text
%	delimited by [[ .. ]].  It creates an arrow in the right margin
%	which makes it very easy to locate reminders.  Can be redefined to
%	eat up reminders when creating a version of the paper for
%	distribution.
%    \fullversion{..}:
%%%%%%%%%%

\newcommand{\eat}[1]{}
% \newenvironment{comment}{\noindent \begin{footnotesize} \{{\bf Comment:}}{\}\end{footnotesize}}

\newcommand{\comment}[1]{\noindent \begin{footnotesize} {\bf Comment:} #1 \end{footnotesize}\\}

\newcommand{\inlinecomment}[1]{\begin{quotation} [[[ #1 ]]] \end{quotation}}
\newcommand{\reminder}[1]{ [[[ \marginpar{\mbox{$<==$}} #1 ]]] }
\newcommand{\eatreminders}[0]{\renewcommand{\reminder}[1]{}}
\newcommand{\fullversion}[1]{ }


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%   The following commands can be changed to alter several 
%	commands/environments defined in this file 
%
%  \noBox:
%     	The \condBox command is used in several environments below, such as
%     	propositions to generate a box at the end of the environment.  
%     	If you don't want a box be generated, insert the command
%     	\noBox within the desired environment.  You can even add it to the
%     	beginning of the document for it to have a global effect.
%
%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\condBox}{{\raggedleft \mbox{$ \Box $}}}
\newcommand{\noBox}{\renewcommand{\condBox}{}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% SPACE CRUNCHING COMMANDS
%  \crunchspace: 
%	use small font in several environments (to find out in which
%	look for uses of \crunchbegin and \crunchend
%  \spcrunch:
%	Eats vertical space.
%  \sections:
%  \subsections:
%  \subsubsections:
%  \subsubsubsections:
%	The above four commands eat vertical space around section names.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\spcrunch}{\vspace{-0.15in}}


\newcommand{\crunchbegin}{} % These two commands are redefined to \begin{small}
\newcommand{\crunchend}{}   % and \end{small} if space crunching is required

\newcommand{\crunchspace}{
	\renewcommand{\crunchbegin}{\begin{small}}
	\renewcommand{\crunchend}{\end{small}}
    }

\newcommand{\sections}[1]{\vspace{-0.2in} \section{#1} \vspace{-0.15in}}
\newcommand{\subsections}[1]{\vspace{-0.1in} \subsection{#1} \vspace{-0.1in}}
\newcommand{\subsubsections}[1]
	{\vspace{-0.1in} \subsubsection{#1} \vspace{-0.1in}}
\newcommand{\subsubsubsections}[1]
	{\vspace{-0.2in} \subsubsubsection{#1} \vspace{-0.1in}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% MISC. COMMANDS.
%
%   \tuple{..}:
%	Creates an overline to indicate that this is a vector/tuple.
%
%   \lbok:
%	Tells latex that it's ok to break a line here.
%%%%%%%%%%%%%%%

\newcommand{\tuple}[1]{\overline{#1}}
\newcommand{\lbok}{\linebreak[0]}

\newcommand{\semijoin}{\mathrel{\raise1pt\hbox{\vrule
	height5pt depth0pt\hskip-1.5pt$>$\hskip -2.5pt$<$}}}
\newcommand{\fd}{\rightarrow}
\newcommand{\mvd}{\rightarrow\!\rightarrow}

\newcommand{\intersection}{\cap}
\newcommand{\union}{\cup}
\newcommand{\ifff}{\mbox{$ \leftarrow $}} 
   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Environments for Definitions, Lemmas, Theorems, Propositions etc:
%  The environments must be used in one of the following way:
%  	Environments that do not start with "named" do not take any 
%		parameters and are used as follows.
%  	\begin{definition} 
%         	... fill in definition ;  
%  	\end{definition}
%  	Environments that take parameters are used as follows:
%  	\begin{nameddefinition}{name of definition} 
%         	... fill in definition 
%  	\end{nameddefinition}
%  The numbering of the environments is done independently for each
%  environment type.  This can be changed if desired.
%
%  List of Environments:
%  --------------------
%	theorem
%	namedtheorem
%	lemma
%	namedlemma
% 	proposition	(Creates a box at the end)
%	namedproposition	(Creates a box at the end)
%	definition	(Creates a box at the end)
%	nameddefinition	(Creates a box at the end)
%	example		(Creates a box at the end)
%	namedexample	(Creates a box at the end)
%	assumption
%	claim
%	conjecture	(Creates a box at the end)
%	property	(Creates a box at the end)
%	namedproperty	(Creates a box at the end)
%
% WARNING:  When defining environments, DO NOT leave gaps between the 
%	    argument definitions.  Latex screws up if this is done.
%	Eg.  \newenvironment{haha}{..}{..} is ok,
%	BUT  \newenvironment{haha} {..} {..} is NOT OK.

%%%%%%%%%%%%%%%%%%%%%%%%%%
%  The following set the numbering style for several environments defined
%	above.
%%%%
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemm}{Lemma}[section]
\newtheorem{prop}{Proposition}[section]
\newtheorem{coroll}{Corollary}[section]
\newtheorem{conj}{Conjecture}[section]
\newtheorem{claims}{Claim}[section]

\newtheorem{ex}{Example}[section]
\newtheorem{alg}{Algorithm}[section]
\newtheorem{defin}{Definition}[section]
\newtheorem{assump}{Assumption}[section]
\newtheorem{propty}{Property}[section]

%% Environments with merged numbering
\newtheorem{mtheorem}{Theorem}[section]
\newtheorem{mlemm}[theorem]{Lemma}
\newtheorem{mprop}[theorem]{Proposition}
\newtheorem{mcoroll}[theorem]{Corollary}
\newtheorem{mconj}[theorem]{Conjecture}
\newtheorem{mclaims}[theorem]{Claim}

\newtheorem{mdefin}{Definition}[section]
\newtheorem{massump}[defin]{Assumption}
\newtheorem{mpropty}[defin]{Property}
\newtheorem{mex}{Example}[section]
\newtheorem{malg}{Algorithm}[section]

\newcommand{\propc}{prop}
\newcommand{\lemmc}{lemm}
\newcommand{\corollc}{coroll}
\newcommand{\conjc}{conj}
\newcommand{\claimsc}{claims}

\newcommand{\separatenumbering}{
    \renewcommand{\propc}{prop}
    \renewcommand{\lemmc}{lemm}
    \renewcommand{\corollc}{coroll}
    \renewcommand{\conjc}{conj}
    \renewcommand{\claimsc}{claims}
}

\newcommand{\mergednumbering}{
    \renewcommand{\propc}{mprop}
    \renewcommand{\lemmc}{mlemm}
    \renewcommand{\corollc}{mcoroll}
    \renewcommand{\conjc}{mconj}
    \renewcommand{\claimsc}{mclaims}
}

\newenvironment{namedtheorem}[1]{\begin{theorem}{\bf (#1)\hspace{1mm}:} \begin{rm} \crunchbegin }{ \crunchend \end{rm} \end{theorem}}

\newenvironment{proposition}{\begin{\propc} \crunchbegin }{\condBox \crunchend \end{\propc}}

\newenvironment{namedproposition}[1]{\begin{proposition}{\bf (#1)\hspace{1mm}:} \begin{rm} \crunchbegin }{ \crunchend \end{rm} \end{proposition}}

\newenvironment{lemma}{\begin{\lemmc} \crunchbegin }{\crunchend \end{\lemmc}}

\newenvironment{namedlemma}[1]{\begin{lemma}{\bf (#1)\hspace{1mm}:} \begin{rm} \crunchbegin }{ \crunchend \end{rm} \end{lemma}}

\newenvironment{corollary}{\begin{\corollc} \crunchbegin }{\crunchend \end{\corollc}}

\newenvironment{conjecture}{\begin{\conjc} \crunchbegin }{\condBox \crunchend \end{\conjc}}

\newenvironment{claim}{\begin{\claimsc} \crunchbegin }{\crunchend \end{\claimsc}}

\newenvironment{namedproof}[1]{\noindent {\bf Proof:}~(#1)\\ \nopagebreak \crunchbegin}{\crunchend {\raggedleft$\Box$}}

\newenvironment{proof}{\noindent {\bf Proof}: \crunchbegin \nopagebreak}{\crunchend {\raggedleft$\Box$}}

\newenvironment{namedexample}[1]{\begin{ex}{\bf (#1)}\\ \crunchbegin \begin{rm}}{\condBox \end{rm} \crunchend \end{ex}}

\newenvironment{example}{\begin{ex} \nopagebreak \crunchbegin \begin{rm}}{\condBox \end{rm} \crunchend \end{ex}}

\newenvironment{nameddefinition}[1]{\begin{defin}{\bf #1\hspace{1mm}:} \begin{rm} \crunchbegin }{ \condBox \crunchend \end{rm} \end{defin}}

\newenvironment{definition}{\begin{defin} \begin{rm} \crunchbegin }{\condBox \crunchend \end{rm} \end{defin}}

\newenvironment{assumption}{\begin{assump} \crunchbegin }{\condBox \crunchend \end{assump}}

\newenvironment{namedproperty}[1]{\begin{propty}{\bf #1\hspace{1mm}:} \begin{rm} \crunchbegin }{ \condBox \crunchend \end{rm} \end{propty}}

\newenvironment{property}{\begin{propty} \begin{rm} \crunchbegin }{\condBox \crunchend \end{rm} \end{propty}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% THE ALGORITHM command
%
%    \algorithm:
%    	The command \algorithm, takes one argument, to format
%	algorithms.  It sets font to \sf, and sets up a tabbing environment,
%	and creates lines above and below the algorithm to set off the 
%	algorithm from other text.  
%	
%
%    \ordinalg:
%    	If you don't want the separating lines, but want other features of the
%	\algorithm command, use the command \ordinalg
%
%   The default tabbing for algorithms is four spaces.	If you use 
%	\setprocdefaults this is changed to two spaces.
%
%    \pseudocode:
%	This commands creates the separating lines just like \algorithm,
%	but does not set up tabbing mode.
%
%  \setalgseplinelen{<length>}:
%   	The default length of the separating line is 6 inches.  If you use
%	\setprocdefaults this is reduced.  If you want finer control use this
%	command.
%   

%%%%%%%%%%%%%%%%%
\newcommand{\algtab}{1234}

\newcommand{\setalgtab}[1]{\renewcommand{\algtab}{#1}}

\newcommand{\algseplinelen}{6in}
\newcommand{\setalgseplinelen}[1]{\renewcommand{\algseplinelen}{#1}} 
\newcommand{\algsepline}{\rule{\algseplinelen}{0.1mm}\\}

\newcommand{\ordinalg}[1]{\begin{sf} \crunchbegin \begin{tabbing}
\algtab\=\algtab\=\algtab\=\algtab\=\algtab\=\algtab\=\algtab\=\algtab\=\algtab\=\algtab\=\kill
#1 
\end{tabbing} \crunchend \end{sf}}

\newcommand{\algorithm}[1]{\begin{sf} \crunchbegin \begin{tabbing}
\algtab\=\algtab\=\algtab\=\algtab\=\algtab\=\algtab\=\algtab\=\algtab\=\algtab\=\algtab\=\kill
\raisebox{4ex}[5ex][2mm]{\algsepline}
#1 \\
\raisebox{0ex}[.1mm][.1mm]{\algsepline}
\end{tabbing} \crunchend \end{sf}}

\newcommand{\pseudocode}[1]{\begin{sf} \crunchbegin 
\noindent \raisebox{0mm}[.2mm][.2mm]{\algsepline} \\
#1 
\noindent \raisebox{0ex}[.1mm][.1mm]{\algsepline} \\
\crunchend \end{sf}}

\newcommand{\moduleprog}[1]{\noindent 
\raisebox{4ex}[5ex][2mm]{\algsepline}
#1 \\
\raisebox{0ex}[.1mm][.1mm]{\algsepline}
}

%% \newenvironment{namedalgorithm}[1]
%%   {{\bf #1}\\ \nopagebreak\begin{sf}\begin{small}\begin{tabbing}
%% \algtab\=\algtab\=\algtab\=\algtab\=\algtab\=\algtab\=\algtab\=\algtab\=\algtab\=\algtab\=\kill}
%%   {\end{tabbing}\end{small}\end{sf}}

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%
% See also redefinition of condition in \procdefaults mode
%%%%%%%%%%%%%

\newcommand{\condition}[2]{\crunchbegin \begin{description}\item [Condition #1]:#2 \condBox \end{description} \crunchend }

\newcommand{\proctechnique}[2]{\crunchbegin \noindent {\bf Technique #1}:~#2 \condBox \crunchend }

\newcommand{\proccondition}[2]{\crunchbegin \noindent {\bf Condition #1}:~#2 \condBox \crunchend }

%%%%
% This command ( \technique) is useful to desccribe a collection of short 
% techniques.  Each of the techniques begins with an \item [<description>] 
% The list of techniques is demarcated by long dividing lines.
%%%%
\newcommand{\technique}[2]{\begin{sf} \crunchbegin
\noindent \raisebox{0mm}[.2mm][.2mm]{\algsepline}
\vspace{-2mm}
\begin{description}
\item [Technique #1:] #2 
\end{description}
\vspace{-2mm}
\noindent \raisebox{0ex}[.1mm][.1mm]{\algsepline} \\
\crunchend \end{sf}}

\newcommand{\techniques}[1]{\begin{sf} \crunchbegin
\noindent \raisebox{0mm}[.2mm][.2mm]{\algsepline}
\vspace{-2mm}
\begin{description}
#1 
\end{description}
\vspace{-2mm}
\noindent \raisebox{0ex}[.1mm][.1mm]{\algsepline} \\
\crunchend \end{sf}}

%% The command \itemizes and \enumerates are used as replacements for 
%% \itemize and \enumerate, that save space.
%% Use the command \items within these commands instead of \item
%% The enumerates command currently does not generate numbers.  It should
%% be fixed.

	    \newcommand{\items}{\\ \hspace*{.75cm} $ \bullet $~} 

\newenvironment{itemizes}{}{} 

\newenvironment{enumerates}{ \newcommand{\items}{\\ \hspace*{.75cm}}}{} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Rule Formatting Section
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%   \logicprog{...}:
% 	The command \logicprog creates an inline logic program.
%	It formats the program in a nice manner.
%	Several commands described below can be used to create rules withing
%	the program.
%	NOTE:  \\ must be used to create new lines, or latex will complain.
%
%   \logicprogfig{ <caption and optional label> }{...}:
% 	The command \logicprogfig creates a separate figure.  It takes two
% 	arguments - a caption and then the logic program itself within { ... }
%
%   Commands for use within logicprog mode:
%   --------------------------------------
%
%   \lfact {<Rulename>} {<fact>}
%   \lrule {<Rulename>} {<Rulehead>} {<Rulebody>}
%   \lquery {<query>}
%   \lcomment{<C style comment>}
%   \lheader {<Any text that spans the entire line>}
%   \lrulecont {<Rulename>} {<Rulehead>} {<PartialRulebody>}
%   \lcontrule {} 	    {}		 {<Rest of rule body>.}
%
%   \setrulebodywidth{<width>}:
%	Particularly useful when non-standard page width is used.
%
%   Commands for use outside logicprog mode:
%   ---------------------------------------
%    \hornclause {<Rulename>} {<Rulehead>} {<Rulebody>}
%    \inlineclause {<Rulename>} {<Rulehead>} {<Rulebody>}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\newcommand{\lheader}[1]{\multicolumn{4}{l}{\mbox{#1}}}
\newcommand{\lcomment}[1]{\multicolumn{4}{l}{\mbox{/* #1 */}}}
\newcommand{\lannotation}[1]{\multicolumn{4}{l}{\mbox{#1}}}
\newcommand{\lrule}[3]{#1&#2&\ifff&$ #3. $}
\newcommand{\lrulecont}[3]{#1&#2&\ifff&$ #3 $}
\newcommand{\lcontrule}[3]{#1&#2&&$ #3$}
\newcommand{\lqrule}[4]{#1&#2&\mbox{$\leftarrow #3 -$}&$ #4. $}
\newcommand{\lfact}[2]{#1&\multicolumn{3}{l}{#2.}}
\newcommand{\lquery}[1]{\multicolumn{4}{l}{\mbox{Query: ?-$ #1 .$}}}
\newcommand{\hornclause}[3]{\[ #1~#2 \ifff #3. \]}
\newcommand{\inlineclause}[3]{$ #1~#2 \ifff #3$}

\newcommand{\rulebodywidth}{4.5in}
\newcommand{\setrulebodywidth}[1]{\renewcommand{\rulebodywidth}{#1}}

\newcommand{\logicprog}[1]{\[ {\renewcommand{\arraycolsep}{.5mm}\renewcommand{\arraystretch}{.75}\begin{array}{lllp{\rulebodywidth}}#1\end{array}}\]}
%

\newcommand{\logicprogfig}[2]{\begin{figure}\[ 
	{\renewcommand{\arraycolsep}{.5mm}\renewcommand{\arraystretch}{.75}
	\begin{array}{lllp{\rulebodywidth}}#2\end{array}}\]\vspace{-5mm}
	\caption{#1}\end{figure}}
\newcommand{\widelogicprogfig}[2]{\begin{figure*}\[ 
	{\renewcommand{\arraycolsep}{.5mm}\renewcommand{\arraystretch}{.75}
	\begin{array}{lllp{\rulebodywidth}}#2\end{array}}\]\vspace{-5mm}
	\caption{#1}\end{figure*}}
\newcommand{\logicprogcfig}[3]{\begin{figure}[#1]\[ 
	{\renewcommand{\arraycolsep}{.5mm}\renewcommand{\arraystretch}{.75}
	\begin{array}{lllp{\rulebodywidth}}#3\end{array}}\]\vspace{-5mm}
	\caption{#2}\end{figure}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% SETTING PROC OR NORMAL ENVIRONMENT
%   \setnormaldefaults:
%	Set up a number of defaults such as text width/height etc.,
%	for normal format.
%   \setprocdefaults:
%	Set up a number of defaults for two column format.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\setnormaldefaults}{
% 
\input{psfig}
% page layout
\addtolength{\topmargin}{-0.8in}    % move top margin up
\setlength{\textheight}{8.85in}      % text height
\addtolength{\oddsidemargin}{-0.5in} 
\setlength{\textwidth}{6.25in}
\addtolength{\columnsep}{2.5ex}
\addtolength{\itemsep}{-1ex}
\addtolength{\topsep}{-1.5ex}
\addtolength{\parskip}{2ex}
\abovedisplayskip=2mm  % Spacing for math line mode formulas (using \[ \])
\belowdisplayskip=2mm
\abovedisplayshortskip=1mm  % As above, for formulas that start beyond the 
			    % last character of previous line
\belowdisplayshortskip=2mm
\topsep=-1mm  % The amount of space in addition to \parskip, above and 
	      % below list envs (eg. enumerate).  Beware of negative spacing 
	      % if parskip is too small
\partopsep=0mm % As above, when there is a blank line preceding the list
\renewcommand{\baselinestretch}{1.1}    % one and a half spacing approx.
\mergednumbering			% Theorems, lemmas etc are numbered 
					% together.
}

\newcommand{\setprocdefaults}{
\setnormaldefaults
% \renewcommand{\maketitle}{??} - fill this in 
\setlength{\oddsidemargin}{-.20in}
\setlength{\topmargin}{-.40in}  % In order to get .75in seperation
\setlength{\topskip}{10pt}
\setlength{\headsep}{0pt}
\setlength{\textheight}{9.25in}
\setlength{\textwidth} {6.99in}
\setlength{\columnsep} {0.33in}
\setrulebodywidth{2in} \setalgtab{12}
\setalgseplinelen{2.5in}
\setlength{\parskip}{1mm}
\renewcommand{\condition}{\proccondition}
\crunchspace	% use small font in several environments (to find out in which
		% look for uses of \crunchbegin and \crunchend
\mergednumbering		% Theorems, lemmas etc are numbered 
				% together.
}

\renewcommand{\ifff}{\mbox{$ :- $}}
\def\imp{\hbox{$:-$}}
\def\G{{\cal G}}
\def\H{{\cal H}}

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

\begin{opening}
\title{EFFICIENT BOTTOM-UP EVALUATION OF LOGIC PROGRAMS}

\author{Raghu Ramakrishnan}
\author{Divesh Srivastava}
\author{S. Sudarshan}
\institute{Computer Sciences Department\\
University of Wisconsin -- Madison\\
Madison WI 53706, U.S.A.}
\end{opening}

\date{ }  %current date if % appears in first column; no date - otherwise.

\begin{document}

\begin{abstract}
In recent years, much work has been directed towards evaluating
logic programs and queries on deductive databases by using an
iterative bottom-up fixpoint computation.  The resulting techniques
offer an attractive alternative to Prolog-style top-down evaluation
in several situations.  They are sound and complete for positive Horn
clause programs, are well-suited to applications with 
large volumes of data (facts), and can support a variety of extensions to
the standard logic programming paradigm.

We present the basics of database query evaluation and logic programming
evaluation, and then discuss bottom-up fixpoint evaluation.  We discuss
an approach based upon using a program transformation (``Magic Templates'')
to restrict search, followed by fixpoint computation using a technique
(``Semi-naive evaluation'') that avoids repeated inferences.  The program
transformation technique focuses the fixpoint evaluation, which is
a forward-chaining strategy, by propagating
bindings in the goal in a manner that essentially mimics the backward-chaining
behavior of top-down evaluation strategies.

After presenting the basic framework for bottom-up evaluation, we discuss
several refinements that optimize the treatment of non-ground terms, 
improve memory utilization, reduce the cost of duplicate checking,
and utilize the declarative semantics of the program to perform
semantic query optimization in a number of ways.
We also consider several extensions to the logic programming paradigm, and
discuss how the bottom-up evaluation framework can be used to support
these extensions.  The extensions include support for negation, set-terms,
constraint manipulation and quantitative reasoning.

Finally, we discuss several systems
based upon bottom-up evaluation, including Aditi (Univ. of Melbourne),
EKS-V1 (ECRC-Munich), Glue/NAIL! (Stanford Univ.) and LDL (MCC-Austin). 
We have developed such a system, called CORAL, and we present this in
more detail.

\keywords
Logic Programs, Bottom-Up Evaluation, Deductive Databases, 
Database Query Languages.
\end{abstract}

\section{Introduction}

Traditionally, logic programming language implementations have evaluated
programs top-down.  Recent developments in evaluation of database
queries have provided a means of evaluating logic programs bottom-up
while still retaining the focusing properties of top-down evaluation,
based in large part on optimizing program transformations.

\begin{example}
\label{ex:tc1}
As a simple example of the power of the bottom-up approach, consider a
definition of transitive closure
\[\begin{array}{lcl}
t(X,Y) & \imp & e(X,W), t(W,Y). \\
t(X,Y) & \imp & e(X,Y). \\
query(Y) & \imp & t(5,Y).
\end{array}\]
If $e$ is cyclic, Prolog will not terminate on this program.  
Even if $e$ is not cyclic, there are values for~$e$ such that Prolog
takes time exponential in the size of the answer.

To evaluate the original query bottom-up, we first obtain the
following program by first applying the Magic
Templates\footnote{Earlier versions of the algorithm were called Magic
Sets. See Section~\ref{sec:buxforms} for details.} transformation 
(Section~\ref{sec:magic}) and
then predicate factoring (Section~\ref{sec:predicatefactoring}):
\[\begin{array}{lcl}
magic\_t^{bf}(W) & \imp & ft(W). \\
magic\_t^{bf}(5). & &\\
ft(Y) & \imp & magic\_t^{bf}(X), e(X,Y). \\
query(Y) & \imp & ft(Y).
\end{array}\]
Evaluating this program using Semi-naive bottom-up evaluation
(Section~\ref{sec:iterativefp}) always
terminates and computes the answer to the query in time linear in the
answer size.

Essentially the same program results if Magic Templates plus factoring
is applied to versions of the transitive closure expressed with
different forms of the recursive rule, including the left-recursive
and binary recursive forms (upon which Prolog does not terminate for
any values of $e$).  This example is presented in detail in
Section~\ref{sec:otheropt}.
\end{example}

This is an example where the bottom-up approach based on program
transformations has notable success.   Even on programs for which the
transformations do not achieve such large gains, the Magic Templates
transformation ensures that no ``irrelevant'' goals or facts are
generated, and in many cases significant advantages accrue when
bottom-up evaluation is used, primarily because:
\begin{itemize}
\item With memoing, it implements a form of dynamic
programming, which eliminates a great deal of redundant computation, and
\item It is sound and complete, 
and thus the declarative semantics
of the program (which is taken to be its least Herbrand model)
is preserved. This non-procedural approach
allows for much more flexibility in program transformation and
optimization.
\end{itemize}

In this paper, we give a tutorial introduction to
the bottom-up approach to logic program evaluation. 
We introduce notation and preliminary definitions in
Section~\ref{sec:notation}, and present a summary of the bottom-up
evaluation method based on the Magic Templates program transformation
and Semi-naive fixpoint evaluation in Section~\ref{sec:buxforms}.  
In this section, we also discuss some alternatives to the
Magic Templates approach and compare top-down and bottom-up
methods briefly.
We present a survey of some related program transformations
used in the bottom-up approach in Section~\ref{sec:otheropt}.  
In Section~\ref{sec:extensions}, we discuss various extensions to the
Horn clause logic programming paradigm.  We describe some
systems based upon bottom-up evaluation in Section \ref{sec:busystems},
and discuss one of them (CORAL) in more detail in Section \ref{sec:coral}.

We note that some related evaluation techniques (e.g., Vieille's
QSQR and QoSaQ \cite{v:rec,v:dat,v:qosaq}, 
parallel evaluation techniques (e.g., work by
Gonzalez-Rubio, Bradier and Rohmer \cite{grb87:ddc},
Ganguly, Silberschatz and Tsur \cite{gst:afr}, Cohen and Wolfson \cite{cw:why},
and others, e.g.\ \cite{d:ond,r:par,v:ame,ws:sha}),
work on integrity constraints (e.g., Bry, Decker and
Manthey \cite{bdm88:constr}, Vieille et al.\ \cite{vbk91:ic:eks} and others), 
work on production rule systems (e.g., Forgy \cite{f:rete},
Sellis, Lin and Raschid \cite{slr88:prod}, Widom et al. \cite{wcl91:setprod},
and others, and systems such as OPS 5),
work on intelligent query answering (e.g.\ \cite{m:seave,cd:qrb})
etc. are not discussed in this tutorial presentation due to lack
of space.  Our coverage attempts to present one coherent set
of results that are indicative of the field, rather than a survey,
and is doubtless influenced by our personal perspectives.

\section{Notation and Preliminary Definitions}
\label{sec:notation}

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 mutually disjoint.
It is assumed, without loss of generality, that with each function
symbol {\it f} and each predicate symbol {\it p}, is associated a
unique natural number {\it n}, referred to as the {\it arity} of the
symbol; {\it f} and {\it p} are then said to be {\it n}-ary symbols.
A 0-ary function symbol is referred to as a constant.  A {\it term} in
a first order language is a variable, a constant, or a compound term
$f(t_1 , \ldots , t_n )$ where {\it f} is an {\it n}-ary function
symbol and the~$t_i$ are terms.  A tuple of terms is sometimes denoted
simply by the use of an overbar, e.g.,~$\bar{t}$.

A substitution is an idempotent mapping from the set of variables of
the language under consideration to the set of terms.  
Substitution operations are usually written in postfix form.
A substitution
$\sigma$ is {\em more general} than a substitution~$\theta$ if there
is a substitution~$\varphi$ such that $ \theta = \sigma[\varphi] $.
%%%% $\theta = \varphi\circ\sigma$.
Substitutions are denoted by lower case Greek letters $\theta,
\sigma, \phi$, etc.
Two terms~$t_1$ and~$t_2$ are said to be {\it unifiable} if there is a
substitution~$\sigma$ such that $ t_1 [\sigma] = t_2 [\sigma] $.
%%%% $\sigma(t_1) = \sigma(t_2)$;
$\sigma$ is said to be a {\it unifier} of~$t_1$ and~$t_2$.
Note that if two terms have a unifier, they have a most general
unifier that is unique up to renaming of variables.

A clause is the disjunction of a finite number of literals, and is
said to be Horn if it has at most one positive literal.  A Horn clause
with exactly one positive literal is referred to as a {\it definite
clause}.  The positive literal in a definite clause is its {\it head},
and the remaining literals, if any, constitute its {\it body}. 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 $\langle P,
Q\rangle$ where~$P$ is a set of predicate definitions and {\it Q} is
the {\it input}, which consists of a query, or goal, and possibly a
set of facts for ``database predicates'' appearing in the program.  

We follow the convention in deductive database literature of
separating the set of rules with non-empty bodies (the set~$P$) from
the set of facts, or unit clauses, which appear in~$Q$ and are called
the {\it database}. ~$P$ is referred to as the {\it program}, or the
set of rules.  The motivation is that the rewriting algorithms to be
discussed 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}.

Following the syntax of Edinburgh Prolog, definite clauses (rules) are
written as
\begin{quotation}
\noindent
$p$ \ifff $q_1 , \ldots, q_n .$
\end{quotation}
read declaratively as~$q_1$ and~$q_2$ and \dots and~$q_n$ implies~$p$.
Names of variables begin with upper case letters, while names of
non-variable (i.e., function and predicate) symbols begin with lower
case letters.
In addition, the
following notation is used for lists: the empty list is written $ [~] $, and a
list with head {\it H} and tail {\it L} is written $[H | L ]$.
Note that control primitives such as Prolog's cut are not allowed.

\eat{
We will use {\it derivation trees} in several proofs:

\begin{definition} \rm
Given a program~$P$ and input~$Q$, derivation trees in $\langle P,
Q\rangle$ are defined as follows:
\begin{itemize}
\item
Every fact~$h$ in~$Q$ is a derivation tree for itself,
consisting of a single node with label~$h$.
\item
Let~$r$ be a rule: $h$ \ifff $b_1, b_2, \ldots , b_k$ in~$P$, let
$d_i,~i=1 \ldots k$ be atoms with derivation trees~$t_i$, and let
$\theta$ be the {\em mgu} of $(b_1, \ldots , b_k ) $ and $ (d_1,
\ldots , d_k )$.  Then, the following is a derivation tree for
$h[\theta]$: The root is a node labeled $h[\theta]$, and each $t_i,~i = 1
\ldots n$, is a child of the root.  Each arc from the root to a child
has the label~$r$.
\end{itemize}
\end{definition}

Note that the substitution~$\theta$ is not applied to the children
of $h[\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.
The {\em height} of a derivation tree is defined to be the
number of nodes in the longest path (which is always from the root to a leaf).
}

\section{The Bottom-Up Approach}
\label{sec:buxforms}

The bottom-up approach that we consider consists of a two-part
process.  First, the program is rewritten in a form so that the
bottom-up fixpoint evaluation of the program will be more efficient;
next, the fixpoint of the rewritten program is computed by bottom-up
iteration.  Subsection~\ref{sec:magic} describes the initial
rewriting, while Subsection~\ref{sec:iterativefp} investigates the
computation of the fixpoint of the rewritten program.  
Both these steps can be refined further; this is discussed in
later sections.

\subsection{The Magic Templates Rewriting Algorithm}
\label{sec:magic}

As described in~\cite{br:ont,r:mag}, the initial rewriting of a
program and query is guided by a choice of {\em sideways information
passing strategies}, or sips.  For each rule, the associated sip
determines the order in which the body literals are evaluated.
In analogy to top-down evaluation, we can think of rules being
used to generate answers to queries on the head predicate, with
some arguments bound to given terms;
different sips can be chosen for each head binding pattern.

We present a simplified version of the Magic Templates
algorithm, tailored to the case that sips correspond to left-to-right
evaluation with all arguments considered ``bound'' (perhaps to
a free variable), as in Prolog.  
The idea is to compute a set of auxiliary predicates that contain the
goals. The rules in the program are then modified by attaching
additional literals that act as filters and prevent the rule from
generating irrelevant tuples.

\begin{definition}\rm
{\bf The Magic Templates Algorithm}\\
Let $ P $ be a program, and $ ?- q(\tuple{c}) $ a query on the program.
We construct a new program $P^{mg}$. Initially,
$P^{mg}$ is empty.
\begin{enumerate}
\item Create a new predicate $magic\_p$ for each predicate~$p$ in~$P$.
The arity is that of~$p$.
\item 
For each rule in~$P$, add the {\it modified version} of the rule to $P^{mg}$.
If rule~$r$ has head, say, $p(\bar{t})$, the modified version is obtained
by adding the literal $magic\_p (\bar{t})$ to the body.        
\item  
For each rule~$r$ in~$P$ with head, say, $p(\bar{t} )$, and for each 
literal ${q_i} (\bar{t}_i )$ in its body, add a {\em magic rule}  to $P^{mg}$.
The head is $magic\_{q_i} (\bar{t}_i )$. The body contains 
the literal $magic\_p(\bar{t} )$, and all literals
that precede~$q_i$ in the rule.
\item 
Create a $seed$ fact $magic\_{q} (\overline{c}) $ from the query.
\end{enumerate}
\end{definition}

\begin{example}\label{ex:sg} 
Consider the following program.
\[\begin{array}{lcl}
sg(X,Y)& \imp &flat(X,Y).\\
sg(X,Y)& \imp &up(X,U), sg(U,V), down(V,Y).\\
?- sg(john,Z) & &
\end{array}\]
For a choice of sips that orders body literals from left to right, as
in Prolog, the Magic Templates algorithm rewrites it as follows:
\[\begin{array}{lcl}
sg(X,Y) & \imp & magic\_sg(X,Y), flat(X,Y).\\
sg(X,Y) & \imp & magic\_sg(X,Y), up(X,U), sg(U,V), \\
	&      & ~~~~~~~~~~~~~~~~ down(V,Y).\\
magic\_sg(U,V) & \imp & magic\_sg(X,Y), up(X,U).\\
magic\_sg(john,Z). & &\\
\end{array}\]
\end{example}

We present some results that characterize the transformed program
$P^{mg}$ with respect to the original program~$P$, from~\cite{r:mag}. 
The following theorem ensures soundness.

\begin {theorem}\cite{r:mag}
$\langle P,Q \rangle$ is equivalent to $\langle P^{mg},Q \rangle$ with
respect to the set of answers to the query.
\end {theorem}

\begin {definition}\rm
Let us define the {\em Magic Templates Evaluation Method} as follows:
\begin {enumerate}
\item
Rewrite the program $\langle P,Q \rangle$ according to the choice of sips
using the Magic Templates algorithm.
\item
Evaluate the fixpoint of the rewritten program.
\end {enumerate}
\end {definition}

We hope that the slight abuse of notation in having the same name for
the evaluation method and the rewriting algorithm will not lead to
confusion; the distinction should be clear from the context.
The second step above is presented in more detail in the next subsection.
The rewriting has the important effect of mimicking Prolog in that
(modulo optimizations such as tail recursion optimization and 
intelligent backtracking) only goals and facts generated by Prolog 
are generated.
\footnote{ This is strictly true only for programs that do not generate
non-ground facts. 
The method can be modified slightly
to make the claim valid for all programs and to allow
tail recursion optimization.  For details, see
\cite{rs91:tdvsbup2}.}

The careful reader will notice that some joins are repeated in
the bodies of rules defining magic predicates and modified rules.
The {\em supplementary} version of the rewriting algorithm 
essentially identifies these common sub-expressions and stores
them (with some optimizations that allow us to delete
some columns from these intermediate, or supplementary, relations).
We refer the reader to~\cite{br:ont} for details.

Magic Templates is often presented along with an adornment rewriting 
that annotates predicates with a string composed of characters
`f' and `b', with one character for each argument.  
This step, along with a modification of Magic Templates rewriting that 
projects out of magic predicates those arguments that have an $ f $ adornment,
is used to ensure that the rewritten program generates only ground facts.
For brevity, we omit this step.

\subsection {Iterative Fixpoint Evaluation}
\label{sec:iterativefp}

We describe a refinement of bottom-up fixpoint
evaluation called 
Semi-naive fixpoint evaluation, which is cited as the method of
choice in the deductive database literature. 
Derivations made in one iteration are not repeated in subsequent iterations 
since in each iteration, only rule instantiations
that utilize at least one new fact (i.e., one generated for the 
first time in the previous iteration) are
considered. 

We follow the presentation in~\cite{mr:dej} in the rest of this
section, with some simplifications.

Let us first define a binary operator $W_P$, whose role is similar to
that of the well-known $T_P$ operator of~\cite{ek:the}.  We use square
brackets ($[ \ldots ]$) to denote multisets:\\
$
\begin{array}{ll}
W_P(X, Y) =
[ h[\theta] \ |\ & h \ \imp \  b_1, \ldots , b_k
\mbox{ is a rule of $P$},\\&
\theta \mbox{ is mgu of } (b_1, \ldots , b_k ) \mbox{ and } (d_1, \ldots , d_k ),\\&
Y \subseteq X,
\{ d_1, \ldots , d_k \} \subseteq X, \mbox{ and}\\&
\mbox{$k \geq 0$ and }
\{ d_1, \ldots , d_k \} \cap Y \neq \emptyset.
]
\end{array}
$

The multiplicity of an element $h[\theta]$ is determined by the number
of distinct rule instantiations of which it is the head literal.
A more rigorous definition that formally accounts for the multiplicity
is given in \cite{mr:dej}; we have chosen to use an informal presentation
for ease of exposition.
Intuitively, $W_P$ only allows deductions from the set of facts~$X$
that use the ``new'' facts~$Y$, and ``counts'' a fact as often as it
is derived (using distinct rule instantiations).
We now define Semi-naive iteration. In the following definition, $set$ is an
operator that takes a multiset and returns a set, and $subs$ is an
operator that takes a multiset and returns an irredundant set. (An
irredundant set, or {\em irrset},
is a set of elements such that no element subsumes another.)

\begin {definition}\rm {\bf Semi-naive Iteration (SN)}\\
$
\mbox{Let } S_{-1} = S_{0} = \delta_{0} = {\cal F}. \\
\begin{array}{ll}
\delta_{n+1} &= dup\_elim(W_P( S_{n} , \delta_{n} - S_{n-1})) \\
S_{n+1} &= dup\_elim( S_{n} \cup \delta_{n+1}) \\
S            & =  \lim_{n \rightarrow \infty} S_{n}\\
GC           & = set(S)\\
\end{array}
$

\noindent
where $\cal F$ is the set of facts, or rules with empty bodies, in the
program~$P$, and $dup\_elim$ is either $set$ or $subs$.  We refer to
the variant with $dup\_elim = set$ as SN$_S$, and the variant with
$dup\_elim = subs$ as SN$_I$.
\end {definition}

In Semi-naive iteration, the set of facts produced in iteration~$n$
($\delta_n$) is compared with the set of known facts ($S_{n-1}$) to
identify the new facts produced ($\delta_{n} - S_{n-1}$).  Duplicates
generated within the same iteration are eliminated by the~$set$
operation.  Only derivations that use one of these new facts are
carried out in iteration~$n+1$.  This avoids generating many duplicate
facts by avoiding repeated derivations.  
The algorithm terminates (at
step~$n+1$) when $S_{n+1} = S_n$; we must test whether $\delta_{n+1}
\subseteq S_n$.  Consequently, Semi-naive iteration terminates if and
only if~$S$ is finite.

In this presentation we ignore the issue of how to ensure that only
derivations that use a new fact are carried out.
This is addressed in several papers (e.g.\ \cite{b:nai,b85:qeddb:sn,br:adijlp}).
The problem becomes more complicated when it is desired to apply rules
in a specified order in each iteration.
This issue is discussed in \cite{sippu90:eval,rss90:eval,schmidt91:metacontrol}.

The set $GC$ is the set of {\em generated consequences} of the program.

Let $ground$ be an operator that takes a set of possibly non-ground
facts and a domain $\cal D$ and returns the set of ground facts
containing only constants from~$\cal D$ that are instances of the
input set.  The following result shows that the above iterative
methods are consistent with the usual least Herbrand model semantics
of~\cite{ek:the}; here implicitly~$\cal D$ is the domain for the program
in question.  We denote the least Herbrand model of the program by
$\cal M$.

\begin {proposition} \cite{mr:dej}
The set of generated consequences $GC$ of a program computed
using Semi-naive Iteration (either SN$_S$ or SN$_I$)
is such that $ground( GC) = \lbok  {\cal M}$.
\end {proposition}

We note that ordinary fixpoint evaluation --- frequently called
``Naive'' (N) iteration in the deductive database literature ---
corresponds to the case where the second argument of $W_P$ in the
definition of Semi-naive Iteration is replaced by $S_{n}$.

\begin{example}
The following program illustrates the difference between N and SN.
\[\begin{array}{lcl}
d & \imp & c.\\
c & \imp & b.\\
b & \imp & a.\\
a. \\
b.\\
\end{array}\]
Note that SN$_S$ and SN$_I$ behave identically on this program.
Both N and SN generate $a$ and $b$ in the first iteration.
In the second iteration, SN generates $c$ and a second occurrence of~$b$, and
eliminates the duplicate~$b$.  In the next iteration,
it generates only~$d$, since~$c$
was the only new fact found in the second iteration.
In contrast, N additionally generates in each iteration
all the facts that it generated in previous iterations.
\end{example}

\subsection{Related Work}
\label{sec:magicrelatedwork}

The Alexander method was proposed independently of the
Magic Sets approach in~\cite{rlk:the}. It is essentially
the {\em supplementary} variant of the Magic Templates method,
described in~\cite{br:ont}.  Seki has
generalized the method to deal with non-ground facts and function
symbols, and has called the generalized version Alexander
Templates~\cite{s:ont}.  The Alexander methods always use
a single left-to-right sip for each rule, for all possible goals.

The Magic Templates idea was developed in a series of papers
(\cite{bmsu:mag,br:ont,r:mag}).
Several variants of the Magic Templates idea have also been proposed.
For example, it is possible to compute supersets of the magic sets
without compromising soundness.  Although this results in some
irrelevant computation, it may be possible to compute supersets more
efficiently than the magic sets themselves~\cite{ss:mag}.  

Although the Magic Templates idea was introduced to deal with
recursion, it provides significant improvements for non-recursive queries
as well. 
In \cite{mpr90:aggregates,mfpr:magcond} it is shown that the technique can 
be extended to deal with SQL programs, including those containing features 
like group-by, aggregation and arithmetic conditions.
In \cite{mfpr:mag} a performance evaluation, carried out on a
DB2 relational system, is presented, demonstrating that the technique
performs comparably to standard database techniques, and is often
significantly better.

The Magic and Alexander methods are based on program transformations.
Other methods use a combination of top-down and bottom-up control to
propagate bindings.  Pereira and Warren presented a memoing top-down
evaluation procedure based on Earley deduction~\cite{pw:par}.  This
evaluation procedure may be viewed as a top-down evaluation procedure
that incorporates memoing.  Vieille has proposed a method called
QSQ \cite{v:rec,v:dat,v:qosaq} that can be viewed as follows. Goals are
generated with a top-down invocation of rules, as in Prolog.  However,
there are two important differences:~1) whenever possible, goals and
facts are propagated set-at-a-time, and~2) all generated goals and 
facts are memoed. If a newly generated goal is already memoed, this is
recognized by duplicate elimination.  
Dietrich and Warren have proposed a method called Extension 
Tables~\cite{dw:ext}.
This method is very similar to QSQ, but performs computation
tuple at a time.

Finally, Kifer and Lozinskii have proposed a method called Filtering,
which is based on constructing a rule-goal graph
\cite{kl:afr,kl:syg}. There is a node in the graph for each
predicate, and for each rule, and arcs from predicate nodes to each
rule node in whose body it appears, and from rule nodes to the
predicates that they define. The idea is to compute the fixpoint by
propagating tuples along these arcs, and to restrict the computation
by attaching ``filters'' to arcs. 

The reader is referred to \cite{nr:aun} for a more detailed
discussion of related work.

\section{Top-Down Versus Bottom-Up}
\label{sec:tdvsbu}

In the past, bottom-up methods have not been seriously considered for
the evaluation of logic programs because of a serious drawback: no
techniques were known that avoided computing an unbounded number of
irrelevant facts.  Now that such techniques are known, it is worth
reconsidering bottom-up approaches.  They offer three significant
advantages:  (1) The declarative least Herbrand model semantics is
guaranteed for positive Horn clause programs.  (2) Redundant derivations
are avoided through memoing, leading to asymptotic gains in efficiency
for programs in which goals or facts can be derived in many ways.
(3) As a consequence of (1), no operational guarantees need be made,
thereby making possible a number of semantic optimizations.
One example of a powerful optimization made possible by the
declarative semantics is {\em factoring}, discussed
in Section~\ref{sec:otheropt}.

There are a number of top-down evaluation techniques for logic programs such
as Prolog, the Query-Subquery (QSQ) approach and its extensions
\cite{v:rec,v:qosaq}, and Extension Tables \cite{dw:ext}.
SLD-AL resolution is a theoretical model of the execution of
top-down evaluation techniques that perform memoization of facts.
Memoing top-down evaluations are similar to the bottom-up approach
with respect to advantages (1), (2), and to some extent (3) above.
A natural question is how bottom-up evaluation techniques compare
with memoing as well as non-memoing top-down evaluation techniques.

Initial comparisons were based on the number of facts derived by
the different techniques.
Thus, Ramakrishnan \cite{r:mag,r:par} presents a class of evaluations
and shows that within this class bottom-up evaluation of a program rewritten
using Magic Templates computes an optimal number of facts.
Seki \cite{s:ont} presents a direct comparison between the set of 
facts computed using Alexander Templates rewriting, and using 
SLD-AL resolution.
Bry \cite{b:quer} shows that several top-down and bottom-up evaluation
techniques can be viewed as specializations of a technique called
Backward Fixpoint Procedure.
Thus the least fixpoints of all these techniques have the same set of 
facts.
Given a bottom-up evaluation that does not repeat derivation steps,
these comparisons can be extended to include the number of derivations made.

There are three limitations to the above results.
The first is that the comparisons do not include the cost of each
inference.
The second is that these comparisons ignore optimizations that 
are routinely performed on Prolog programs such as tail-recursion
optimizations (Section~\ref{sec:tro}).
And third, the comparisons assume that all answers are required,
and do not provide enough insight for the case that only one 
answer is needed (although there is no change in the worst case comparison).

Ullman \cite{u:bot} addressed the first problem, and compared the time cost of
evaluation of Datalog programs using bottom-up evaluation, and a 
particular top-down evaluation technique.
This comparison showed that for the class of safe Datalog programs 
(i.e., only ground facts are computed and no uninterpreted function 
symbols are allowed), 
bottom-up evaluation can be performed with a cost that is no more than that
of the top-down evaluation in order of magnitude.
Ramakrishnan and Sudarshan \cite{rs91:tdvsbup} compared a model of 
Prolog evaluation that performs tail recursion optimization with a 
model of bottom-up evaluation that uses a rewriting due to 
Ross \cite{ross91:tro} that performs tail recursion optimization.
They showed that with this model of bottom-up evaluation
the number of inferences and the time cost are (in order of magnitude) 
no more than that of Prolog, for a class of programs that includes 
safe Datalog and that allows ground terms to be constructed using 
uninterpreted function symbols, but with some restrictions.
The rewritten program may generate non-ground facts, although the original
program is not allowed to do so (for the class of programs considered).
For the general case, where arbitrary non-ground terms are allowed,
there are several problems that increase the cost per inference.
These problems are faced not just by bottom-up evaluation schemes, but also
by top-down evaluation schemes that perform memoization of facts.
These issues are discussed in Section~\ref{sec:ng}.

\section{Some Important Program Optimizations}
\label{sec:otheropt}

In this section, we survey a number of optimizations that apply to
positive Horn programs and guarantee query equivalence in the least
fixpoint model. That is, the same set of answers according to the
declarative semantics of logic programs is computed. Note that no
further guarantees are offered: no equivalence is guaranteed with
respect to other program predicates, nor is any ordering preserved in
the generation of answers.  

This survey is not intended to be comprehensive, but rather to provide
an indication of the flexibility that is available when we only need
to preserve the declarative semantics. Ensuring that the declarative
semantics is preserved has long been viewed as a bar to efficient
evaluation; the results surveyed here indicate that it can sometimes
be considerably more efficient to guarantee this semantics, rather
than an operational semantics.
For lack of space we do not cover some approaches to query optimization
such as the semantic query optimization techniques proposed
by Minker, King and others (see e.g.\ \cite{k81:quist,cgm:semopt}).


\subsection{Predicate Factoring}
\label{sec:predicatefactoring}

The basic idea behind predicate factoring is to replace a
predicate by two predicates of strictly smaller arity. 
This can result in significant speedups, as the example in this 
section illustrates.
We present a simplified description that is tailored to the case of programs
obtained by applying the Magic Templates algorithm described in
Section~\ref{sec:magic}. Our presentation is through the use
of examples, and we do not describe sufficient conditions
for the optimization to apply in general.
We refer the reader to~\cite{nrsu:ari} for a detailed treatment.

In essence, we seek to take advantage of the magic predicates
to replace the original predicate in $P^{mg}$ by its projection
onto its $ f $ argument positions. Thus, the original (non-magic)
predicate in $P^{mg}$ is factored into the magic predicate,
which computes the $ b $ argument positions, and this new predicate,
which computes the $ f $ argument positions. 

\begin{example} \rm
We begin with a familiar example, transitive closure. While efficient
algorithms are known, the rewriting algorithms presented
in~\cite{nrsu:sigmod} were the first to automatically derive unary
programs for single-selection queries, for all three forms
(left-linear, right-linear, non-linear) of the recursive rule. We
achieve the same result here by first applying the Magic Templates
transformation and then factoring the rewritten program. To illustrate
the technique, we consider a single program that includes all three
forms of the recursive rule, although any one would suffice. It should
be evident that we would also obtain a unary program if the original
program contained just one of the recursive rules. Consider the
program and single-selection query below:
\[\begin{array}{lcl}
t(X,Y) & \imp & ~t(X,W), t(W,Y). \\
t(X,Y) & \imp & ~e(X,W), t(W,Y). \\
t(X,Y) & \imp & ~t(X,W), e(W,Y). \\
t(X,Y) & \imp & ~e(X,Y). \\
query(Y) & \imp & ~t(5,Y).
\end{array}\]
The Magic Templates algorithm rewrites this to:
\[\begin{array}{lcl}
magic\_t^{bf}(W) & \imp & ~magic\_t^{bf}(X), t^{bf}(X,W). \\ 
magic\_t^{bf}(W) & \imp & ~magic\_t^{bf}(X), e(X,W). \\ 
magic\_t^{bf}(5). & & \\ 
t^{bf}(X,Y) & \imp & ~magic\_t^{bf}(X), t^{bf}(X,W), t^{bf}(W,Y). \\
t^{bf}(X,Y) & \imp & ~ magic\_t^{bf}(X), e(X,W), t^{bf}(W,Y). \\
t^{bf}(X,Y) & \imp & ~ magic\_t^{bf}(X), t^{bf}(X,W), e(W,Y). \\
t^{bf}(X,Y) & \imp & ~ magic\_t^{bf}(X), e(X,Y). \\
query(Y) & \imp & ~t^{bf}(5,Y).
\end{array}\]
If we identify $magic\_t^{bf}$ tuples with goals in a top-down evaluation,
we see that only the last occurrence of $t^{bf}$ in a rule body
generates new goals, and further, the answer to a new goal is also
an answer to the goal that invoked the rule. In fact, every answer
to a subgoal is also an answer to the query goal $magic\_t^{bf}$.
A second observation is that if~$c$ is generated as an answer to a
subgoal, then a new subgoal $magic\_t^{bf}(c)$ is also generated. These
observations lead us to conclude that it does not matter to which
subgoal an answer corresponds; its role in the computation is the same
in any case. That is, $t^{bf}(X,Y)$ can be factored into $bt(X)$ and $ft(Y)$
in the Magic program. 
%%%%%%%%%%%%
% Doing this yields:
% \[\begin{array}{lcl}
% magic\_t^{bf}(W) & \imp & ~magic\_t^{bf}(X), bt(X), ft(W). \\ 
% magic\_t^{bf}(W) & \imp & ~magic\_t^{bf}(X), e(X,W). \\ 
% magic\_t^{bf}(5). \\ 
% bt(X) & \imp & ~magic\_t^{bf}(X), bt(X), ft(W), bt(W), ft(Y). \\
% bt(X) & \imp & ~ magic\_t^{bf}(X), e(X,W), bt(W), ft(Y). \\
% bt(X) & \imp & ~ magic\_t^{bf}(X), bt(X), ft(W), e(W,Y). \\
% bt(X) & \imp & ~ magic\_t^{bf}(X), e(X,Y). \\
% ft(Y) & \imp & ~magic\_t^{bf}(X), bt(X), ft(W), bt(W), ft(Y). \\
% ft(Y) & \imp & ~ magic\_t^{bf}(X), e(X,W), bt(W), ft(Y). \\
% ft(Y) & \imp & ~ magic\_t^{bf}(X), bt(X), ft(W), e(W,Y). \\
% ft(Y) & \imp & ~ magic\_t^{bf}(X), e(X,Y). \\
% query(Y) & \imp & ~bt(5), ft(Y).
% \end{array}\]
%%%%%%%%%%%%%
Doing this and applying some simple syntactic optimizations, 
which are discussed in~\cite{nrsu:ari},
we finally obtain the following unary program:
\[\begin{array}{lcl}
magic\_t^{bf}(W) & \imp & ~ ft(W). \\ 
magic\_t^{bf}(5). & & \\ 
ft(Y) & \imp & magic\_t^{bf}(X), e(X,Y). \\
query(Y) & \imp & ft(Y).
\end{array}\]
\end{example}

Predicate factoring, as described above, requires the entire program
to satisfy the required conditions.
Kemp et al.~\cite{krs90:context} generalized this transformation
so that it can be applied even if a subprogram satisfies the
required conditions; this allows for sharing of subcomputation
across multiple calls to a factored predicate.

\subsection{Tail Recursion Optimization}
\label{sec:tro}

An optimization that is closely related to factoring is tail-recursion
optimization.
Consider a program of the form
{\setrulebodywidth{2.00in}
\logicprog{
\lfact{}{p(0,1)}\\
\lrule{}{p(X,Y)} {X>0,p(X-1,Y)}
}
}
If there is a query $ ?-p(10,X) $, queries $ ?- p(9,X) $ and so on
till $ ?- p(0,X) $ are set up.
At this point an answer $ p(0,1) $ is generated by bottom-up evaluation
of a program rewritten using Magic Templates.
However a Prolog system can recognize that the second rule 
is ``tail-recursive,'' and can avoid generating answers for intermediate
goals.
The reason is that any answer substitution for the last goal results in an
answer for the head of this rule with the same answer substitution.
Applying this optimization for each goal on this rule, 
when the goal $ ?- p(0,X) $ succeeds, an answer $ p(10,1) $ is created
directly, rather than an answer $ p(0,1) $.

Ross \cite{ross91:tro} shows how the same optimization can be performed 
in bottom-up evaluation.
The details are beyond the scope of this paper, but the essential idea
is to generate goal facts of the form 
$ query(p1(\overline{t1}), p2(\overline{t2})) $; such a fact
says the first argument is a subgoal for $ p1 $, and any 
answer substitution that solves it should be used to generate answers for 
$ p2(\overline{t2}) $ rather than for $ p1(\overline{t1}) $.

\subsection{Projecting Arguments}
\label{sec:projection}

Query optimization for relational database queries exploits
the commutativity of {\em selection} and {\em projection}
operators with respect to the {\em join} operator whenever
possible, in order to reduce the size of relations that are
being joined. This is often referred to as ``pushing''
selections and projections. Pushing selections is achieved
through the use of the Magic Templates transformation; the
introduction of recursion makes it necessary to compute
auxiliary sets. Pushing projections has also been explored,
and the gains can be significant. We will illustrate the
idea through examples, and refer the reader to~\cite{rbk:opt}
for details. 

\begin{example}
Consider the transitive closure program of Example \ref{ex:tc1}, 
but with the query $query(Y)$  $\imp$  $t(\_ ,Y).$
The underscore ``\_'' indicates that we do not care about the value
in the first argument position; we simply want the set of values
that appear in the second argument position of~$t$ 
(with some arbitrary value in the first argument position).
Note that such queries are likely to arise during the course of
query optimization.
\end {example}

An adornment that distinguishes don't-care argument positions ($d$)
from the rest (needed or~$n$) was used in~\cite{rbk:opt} to push
projections. 

%%%%%%%%%%%%%%%%%%%%
% An adorned program is generated using an algorithm
% similar to that described in Section \ref{sec:magic}.  The different
% nature of the adornments is reflected in how we determine adornments
% for body literals from the adornment for the rule head: In choosing an
% adornment for a body literal, an argument position is~$d$ if it
% contains only a variable that does not appear anywhere else in the
% rule, except possibly as the argument in a~$d$ position of the head;
% all other argument positions are~$n$.
%%%%%%%%%%%%%%%%%%%%

\begin{example}
Consider a simplified version of the transitive closure program:
\[\begin{array}{lcl}
t(X,Y) & \imp & t(X,W), e(W,Y). \\
t(X,Y) & \imp & e(X,Y). \\
query(Y) & \imp & t(\_ ,Y).\\
\end{array}\]
The adorned program --- using~$n$ and~$d$ adornments --- is:
\[\begin{array}{lcl}
t^{dn}(X,Y) & \imp & t^{dn}(X,W), e(W,Y). \\
t^{dn}(X,Y) & \imp & e(X,Y). \\
query(Y) & \imp & t^{dn}(\_ ,Y).\\
\end{array}\]
It is easy to see that the~$d$ argument positions can be uniformly
deleted, and this leaves us with a program in which the recursive
predicate is unary.
\end {example}

The previous example illustrated how the adornment algorithm can
sometimes push the projection through recursion and thereby reduce the
arity of recursive predicates. (The observation that pushing
projections could reduce arity of recursive predicates was first made
by Aho and Ullman~\cite{au:uni}, and later Kifer and
Lozinskii~\cite{kl:afr} and Apers et al.~\cite{ahb:rec}. 
The adornment algorithm in \cite{rbk:opt} generalizes
their results.) The acute reader will have observed that more can be
achieved --- the recursive rule may be deleted entirely.
Algorithms for deleting redundant rules and literals can be utilized
to detect this; in fact, since such opportunities are frequently
created by pushing projections, we can devise special algorithms for
rule and literal deletion that exploit this. 
The following program is obtained in the above example
using the techniques of~\cite{rbk:opt}:
\[\begin{array}{lcl}
t^{dn}(Y) & \imp & e(X,Y). \\
query(Y) & \imp & t^{dn}(Y).\\
\end{array}\]

\subsection{Counting} 
\label{sec:counting}

Counting (\cite{bmsu:mag,sz:the,br:ont})
is a refinement of the Magic Sets approach. Whereas the Magic
Sets method restricted the computation to relevant facts, Counting
additionally computes indices for each fact that indicate why it is
relevant, and this additional information is used to delete some
literals from rule bodies and to reduce the arity of some predicates
by deleting some argument positions.

Goals correspond to magic facts, as we noted earlier. In the Counting
program, magic facts are called {\em count} facts. The index value for
a non-count fact is simply the index value of the goal for which it
was generated as an answer.
Index values can be encoded in various ways; we will not consider the
details.

\begin{example}\label{ex:sg3} 
Consider the program of Example \ref{ex:sg} again. 
The Counting algorithm generates:
\[\begin{array}{lcl}
sg^{bf}(Y,I) & \imp & count\_sg^{bf}(X,I), flat(X,Y).\\
sg^{bf}(Y,I) & \imp & sg^{bf}(V,I+1), down(V,Y).\\
count\_sg^{bf}(U,I+1) & \imp & count\_sg^{bf}(X,I), up(X,U).\\
count\_sg^{bf}(john,0). & &\\
\end{array}\]
We essentially
compute (i) ``count'' facts (analogous to ``magic'' facts)
that are numbered with their distance from the
query (the $count$ facts), and 
(ii) values in the free argument positions of program ($sg$) 
facts (which we will refer to as ``answers'' in this example), 
also numbered according to the ``count'' fact used to generate them.
Thus, we only compute sets of goals and answers, all numbered 
according to their distance from the query.  The answers to the original query are
the (new, reduced arity) $sg$ facts at distance (index value) 0.  The key
observation here is that we can no longer identify the set of answers to any
intermediate subgoals since we only maintain sets of goals and sets of facts,
and there may be several goals at a given distance (except 0, where the only
goal is the original query).  The potential gain in the method derives from
this observation --- where several goals have the same, or largely overlapping,
answer sets we gain by not associating an answer with each of these goals.
On the other hand, it is possible to lose in performance if each goal/answer
appears at several distances from the query.  This can happen for example
if there is a cycle in the $up$ relation.  Indeed, such a cycle can lead
to non-termination.  It is usually suggested that if a goal is derived with
two different distances  (i.e. two $count$ facts differ only in the index values),
the Counting method should be abandoned in favor of Magic Sets.
\end{example}

\subsection{Space Optimization}

Bottom-up evaluation derives new facts, but has no mechanism built in to
discard facts during the evaluation --- all facts are retained till the 
end of the evaluation.
It is important to discard facts during an evaluation, once they are not needed,
for otherwise space requirements may grow in an unbounded fashion.
Facts are needed to make derivations and to detect duplicate 
derivations of facts (which may be needed for termination).
Consider the  following program which computes fibonacci numbers:
{\setrulebodywidth{2.70in}
\logicprog{
\lfact{R1:} {fib (0, 1)} \\
\lfact{R2:} {fib (1, 1)} \\
\lrule{R3:} {fib (N, X1+X2)} {N > 1, fib (N-1, X1), fib (N-2, X2)} 
}
}
In a Semi-naive evaluation of this program, once a fact $ fib(n,\_) $
is deduced, there is no need to keep any facts $ fib(m,\_) $ for
$ m \leq n-2 $, since all derivations using such facts have been made, 
and the facts will not be derived again.
Such facts can then be discarded during the evaluation.
This issue is studied in detail in \cite{nr90:history,ssrn91:space},
where several sufficient conditions for discarding facts are developed.

\subsection{Duplicate Elimination}

In general, when a fact is derived in a bottom-up evaluation, duplicate
checking needs to be done to see if the fact was derived earlier.
If it was not, derivations can be made using the fact.
If it was, the fact can be discarded.
This check is important for termination of many programs.
However, for some programs such as the fibonacci program above,
with Semi-naive bottom-up evaluation, duplicate facts are never generated.
Hence duplicate elimination need not be done for such programs.
Maher and Ramakrishnan study this issue in detail in \cite{mr:dej},
and provide sufficient conditions to detect if a program will not 
compute duplicate facts.

\subsection{Linearizing Programs}
\label{sec:linear}

An interesting class of program transformations has recently
been explored by a number of researchers \cite{iw:tow,zyt:ane,s:lin,rsuv:pro}.
The objective is to transform a program that contains non-linear
rules into an equivalent one that contains only linear rules; this
may make some of the other transformations surveyed in this
paper applicable, or permit simplifications in the implementation
of the fixpoint evaluation phase. We do not consider these results here
due to space limitations.

\subsection{Bounded Recursion and Redundant Literals}
\label{sec:redundantlit}

One interesting optimization that has been
studied in some detail is that
of {\em bounded recursion}, where a recursive program is bounded if
it can be replaced by a nonrecursive program.

Note that here we are not asking when recursion can be replaced by
iteration; rather, we are asking when a logic program containing
recursive clauses has an equivalent finite logic program in which no clause
is recursive.

\begin{example}
The following example is from~\cite{n:dat}.
\[\begin{array}{lcl}
buys(X,Y) & \imp & likes(X,Y). \\
buys(X,Y) & \imp & trendy(X), buys(Z,Y). \\
\end{array}\]
In English, a person~$X$ buys a product~$Y$ if either~$X$ likes~$Y$,
or~$X$ is trendy and a person~$Z$ has bought~$Y$.  This recursive
program is equivalent to the following nonrecursive program:
\[\begin{array}{lcl}
buys(X,Y) & \imp & likes(X,Y). \\
buys(X,Y) & \imp & trendy(X), likes(Z,Y). 
\end{array}\]
\end{example}

In general, detecting bounded recursions is undecidable.  A rich classification
of sets of programs for which detecting boundedness is decidable or undecidable
has been developed in the literature; see, for 
example,~\cite{cgkv:dec,i:bou,gmsv:und,n:dat,ns:ade,v:dec}.
A related problem is to identify literals and rules that are redundant,
i.e., that do not change the set of answers for any input database.
For more details about detecting and eliminating redundancy from recursive
Datalog programs, see \cite{ns:min}. 

\subsection{Algebraic Properties of Programs}
\label{sec:algebra}

The fixpoint evaluation of a logic program can be refined by taking
certain algebraic properties of the program into consideration. Such
refinements, and techniques for detecting when they are applicable,
have been investigated by several researchers
\cite{h:det,iw:tow,m:sem,n:com,rsuv:pro}.
Ioannidis presents an algebraic formulation of Datalog programs
that is particularly suited to reasoning about such properties of
programs~\cite{iw:tow}. 
The following idea is illustrative of this class of optimizations.

\begin{example}\label{example:commute}
We begin with an example that illustrates {\em commutativity} of rules.
The idea has been studied in the references cited above,
and several sufficient conditions are known for detecting when this
property holds. 
\[\begin{array}{lcl}
r_1:	p(X,Y) & \imp & a(X,Z), p(Z,Y).\\
r_2:	p(X,Y) & \imp & p(X,Z), b(Z,Y).\\
r_3:	p(X,Y) & \imp & c(X,Y).\\
\end{array}\]
It can be shown that applications of rules~$r_1$ and~$r_2$
commute. That is, $r_1 . r_2 = r_2 . r_1$. This fact can
be utilized to avoid many redundant derivations by
evaluating the fixpoint of the program as follows: first
apply rule~$r_3$, then apply~$r_2$ as often as possible,
and finally apply~$r_1$ as often as possible.
\end{example}

\subsection{Non-Ground Facts}
\label{sec:ng}

Non-ground facts are useful for several reasons.
They are often useful in knowledge representation, where we can 
say that a fact is true for all values of a variable.
They are useful in a database that stores (and possibly manipulates)
rules.
They are also useful for specifying patterns in queries, and are 
necessary for representing constraint facts.

However, supporting non-ground facts in a bottom-up evaluation (actually,
in general in an evaluation that memos facts) has an associated cost.
(1) When making an inference, facts have to have their variables renamed
so that they do not share variable names.
(2) When a head fact with a large term as an argument is generated, we
must share the structure of subterms with facts used to derive it,
or do extensive copying.  
This is easy with ground terms, but with non-ground terms structure 
sharing becomes more difficult.
(3) If variables in a large term get instantiated during the inference, 
creation of the head fact is made more complicated.
(4) Unification of large non-ground terms using currently known techniques
is inefficient, especially compared to the cost of unification for ground
terms using hash-consing \cite{goto74:hashcons,sg76:hashcons}.
(5) Indexing of facts containing variables using currently known 
techniques is inefficient, especially compared to the cost of indexing
ground facts using, say, hash tables.

Consider a program to append two lists:
{\setrulebodywidth{2.40in}
\logicprog{
\lfact{}{append([],Z,Z)}\\
\lrule{}{append([X|Y], Z, [X|Y1])} {append(Y, Z, Y1)}\\
\lquery{append([A,B,C],[D,E,F],ANS)}
}
The Magic Templates rewriting of the above program is 
\logicprog{
\lrule{}{append([],Z,Z)}{magic\_append([],Z)}\\
\lrulecont{}{append([X|Y], Z, [X|Y1])} {magic\_append([X|Y],Z),}\\
\lcontrule{} {}                        {~~~~~~~~~append(Y, Z, Y1)}\\
\lfact{}{magic\_append([A,B,C],[D,E,F])}
}
}
If the query uses ground lists, this program runs in $ O(n) $ time,
where $n$ is the size of the lists to be appended.
If the query uses non-ground lists, and the program is evaluated without
any special optimizations for non-ground terms, the evaluation takes
$ O(n^2) $ time.

The structure sharing scheme of Boyer and Moore \cite{bm72:strshr}
addresses the first three problems.
The idea is to maintain binding environments with terms, and note 
variable bindings there; this also makes sharing subterms easier.
A somewhat complicated naming scheme helps rename all variables in a term
in constant time.
However, in the worst case, the cost of looking up variable bindings is
large since many binding environments may need to be searched.
Also, this scheme does nothing to solve the fourth problem, namely
the cost of unification.

There appears to be no general solution for theorem proving systems,
which is the context in which these problems first appeared.
However, in special cases of bottom-up evaluation of logic programs,
efficient techniques are possible.

In the case of the append program there is no need to do 
renaming for the first and last rule of the magic program. 
For the second rule if the terms to which the variables $ Y $ and $ Z $
are bound by the first literal are exactly the same (pointer match),
there is no need for renaming - the variables in the term to which 
$ Y1 $ is bound can be deduced to be the same as 
those in the terms that $ Y $ and $ Z $ are bound to.
This same optimization can perform unification in constant time.
Efficient indexing techniques are possible when Supplementary Magic Templates
rewriting is used.
No variable instantiation occurs within large terms, and this makes
sharing of subterms easy.
Putting these optimizations together, the program can be evaluated
in $ O(n) $ time.
A class of programs for which these optimizations are possible is
discussed in Sudarshan and Ramakrishnan \cite{sr92:ng}.

\section{Extensions to the Horn Clause Logic Programming Paradigm}
\label{sec:extensions}

\subsection{Negation}

A deductive database query language can be enhanced by permitting
nega\-ted literals in the bodies of rules in programs.
This provides the ability to deal with non-monotonic deduction.
However, in the presence of negated literals, a program may not have
a least model.
For example, the program:
{\setrulebodywidth{2.00in}
\logicprog{
\lrule {} {p(a)} {\neg p(b)}
}
}
has two minimal models, $\{ p(a) \}$ and $\{ p(b) \}$, but no
least model.
The meaning of a program with negation is usually given by some 
``intended'' model 
(\cite{ch:hor,abw88:strat,p88:lstrat,pp88:weak,gl88:stable,r90:modstrat,pry90:ext:stable,vgrs:wf}, among others).

One important class of negation that has been extensively studied
is stratified negation~\cite{ch:hor,abw88:strat}.
Intuitively, a program is stratified if there is no recursion through
negation.
Programs in this class have an intuitive semantics and can also be
efficiently evaluated.
The following example describes a stratified program.

\begin{example}
Consider the following program $P2$:
{\setrulebodywidth{2.00in}
\logicprog{
\lrule {r1:} {anc(X,Y)} {par(X,Y)} \\
\lrule {r2:} {anc(X,Y)} {par(X,Z), anc(Z,Y)} \\
\lrule {r3:} {nocyc(X,Y)} {anc(X,Y), \neg anc(Y,X)} 
}
}
Intuitively, this program is stratified because the definition of
the predicate $nocyc$ depends (negatively) on the definition of $anc$,
but the definition of $anc$ does not depend on the definition of $nocyc$.

A bottom-up evaluation of $P2$ would proceed SCC-by-SCC.
First, we would compute a fixpoint of rules $r1$ and $r2$ (the rules 
defining $anc$).
Rule $r3$ is applied only when the all $anc$ facts are known.
This can be seen to be as efficient as the evaluation of programs without
negation.

However, the Magic Templates transformation of a stratified program may
become unstratified, and the evaluation of the resulting unstratified
program has received considerable attention in the 
literature (\cite{bprm:strat,kp88:strat,kss91:wfn,brss:neg}, among others).
\end{example}

A natural extension of stratified programs is the class of locally
stratified programs~\cite{p88:lstrat}.
Intuitively, a program $P$ is locally stratified if the (propositional) 
program $Gr(P)$ obtained by taking all ground instances of all rules in $P$
is stratified.
Local stratification has been extended to modular stratification in
\cite{r90:modstrat}.
A program $P$ is said to be modularly stratified
if each strongly connected component (SCC) of $P$ is locally stratified after
removing instantiated rules containing literals that are false in lower SCCs.

\setrulebodywidth{2.50in}
\begin{example}
Consider the following program $P3$:
\logicprog{
\lfact {r1:} {even(0)} \\
\lrule {r2:} {even(s(X))} {\neg even(X)}
}

This program can be seen to be locally stratified.
Consider the following variant $P4$ of the above program:
\logicprog{
\lfact {r1:} {even(0)} \\
\lrule {r2:} {even(X)} {succ(X,Y), \neg even(Y)} \\
\lheader {$~~~succ(1,0).~~~~succ(2,1).~~~succ(3,2).$}
}
Since rule $r2$ can be instantiated to give the same value for $X$ and $Y$,
program $P4$ is not locally stratified.
However, it is modularly stratified.
Locally and modularly stratified programs can be evaluated using
the techniques described in \cite{r90:modstrat,kss91:wfn}.
The evaluation of the Magic Templates transformation of this class of 
programs has also been considered in the literature
(\cite{r90:modstrat,kss91:wfn,rss91:ord:search}).
\end{example}
 

\subsection{Set Grouping and Aggregation}
\label{sec:setgrp:agg}

\setrulebodywidth{3.00in}
The {\em group-by} construct is used in SQL to partition a relation based
on the values of some of the attributes of the relation.
A variant of this construct is used in LDL \cite{bnrst:set,nt:ldl:bk}
to create nested sets within facts.
We use the syntax of LDL in our discussion; however, 
the semantics we use is from the CORAL\cite{rbss90:coral} system, 
and is a minor
variant of the LDL semantics.
The following example illustrates the use of set grouping construct
$ <~> $:
{\setrulebodywidth{1.5in}
\logicprog{
\lrulecont{}{multiset\_of\_grades(Class, <Grade>)} {student(Name,Class,}\\
\lcontrule{} {} {~~~~~~~~~Grade).}
}
}
We assume that there is at most one occurrence of the $ <~> $ operator 
in the head of any rule, and the operator does not occur in the body.
We also assume for now that the program is stratified wrt the $ <~> $ 
operator, i.e., 
the definition of the predicate in the body does not depend on the 
head predicate if the head of the rule has an occurrence of the $ <~> $ 
operator.
We first (conceptually) create a multiset of tuples for
$ multiset\_of\_grades $ using the rule
{\setrulebodywidth{1.5in}
\logicprog{
\lrulecont{}{multiset\_of\_grades(Class, Grade)} {student(Name,Class,}\\
\lcontrule{} {} {~~~~~~~~~Grade).}
}
}
Now for each value of $ Class $ (in general,
each value of the arguments of the head that are not enclosed in the 
$ <~> $), we create a multiset containing all the corresponding values for 
$ Grade $.
For each value of $ Class $ let this multiset be called $ S_{Class} $;
we then create a fact $ multiset\_of\_grades(Class, S_{Class}) $ for 
each value of $ Class $.

Aggregate operations such as $ count $, $ sum $, $ min $, and $ max $,
which can be applied to sets of values,
are permitted in relational database query languages such as SQL.
These can be incorporated into logic programming too, using the 
set grouping construct to create multisets that are aggregated on.
Extending the above example, consider the following rule:
The following example illustrates the use of aggregation:
{\setrulebodywidth{1.5in}
\logicprog{
\lrulecont{}{max\_grade(Class, max<Grade>)} {student(Name, Class, }\\
\lcontrule{} {} {~~~~~~~~~~Grade)}
}
}
As before, for each value of $ Class $ we create a multiset.
But now we apply the aggregate operation $ max $ to the multiset, and create
a head fact using this value rather than the set itself.

There are several approaches to relaxing the assumption of stratification.
Several of the approaches used for negation carry over to set grouping.
There are approaches based on weaker forms of stratification such as group
stratification and magical stratification \cite{mpr90:aggregates}, or
modular stratification \cite{r90:modstrat}.
Extensions of the well-founded and stable models to deal 
with aggregates are considered in \cite{ks91:aggs}.
Monotonic programs, where a derivation using an incomplete set does
not affect the set of facts computed, are discussed in 
\cite{cm:lowcagg,mpr90:aggregates}.

In certain contexts, an incomplete set may be used to generate facts
that would not be generated using a complete set, without affecting the
final answer to some queries on a program.
One such context is when subsumption of facts is defined in such a 
way that facts created using incomplete sets will be found to be 
subsumed and will be discarded.
Ross and Sagiv \cite{rosa91:monaggr} examine such classes of programs.
Cruz and Norvell \cite{cn89:agg:clos} examine the use of such forms of
aggregation in the context of transitive closure.
Ganguly, Greco and Zaniolo \cite{ggz90:minmax} examine how to evaluate a
class of programs that are monotonic in a sense different from
that used in \cite{mpr90:aggregates}.
Ganguly et al.\ \cite{ggz90:minmax} and Sudarshan and Ramakrishnan 
\cite{sr91:aggr} examine rewrite optimizations of programs that use 
aggregation, and the rewriting can result in unstratified programs.
The following program for computing the shortest path length benefits from
these optimizations:
{\setrulebodywidth{1.50in}
\hspace*{-.1in}
\logicprog{
\lrule{R1:} {s\_p\_length(X,Y,min(<C>) )} {path(X,Y,C)} \\
\lrulecont{R2:}{path(X,Y,C1)} {path(X,Z,C),}\\
\lcontrule{} {} 		{~~~~edge(Z,Y,EC),}\\
\lcontrule{}{}			{~~~~C1 = C + EC.} \\
\lrule{R3:}{path(X,Y,C)}{edge(X,Y,C)} \\
\lquery{s\_p\_length(X,Y,C)}
}
}
For the above program, both the above techniques reduce the number of 
facts computed from possibly infinite
to polynomial, and both evaluation techniques can be 
implemented to be as efficient as Dijkstra's algorithm for shortest paths.

%%%
% The generalized forms of transitive closure with aggregation
% studied in earlier papers
% (e.g., \cite{rhmd86:transv:rec,adj88:trans:path,cn89:agg:clos})
% can be easily written as recursive queries with aggregation.
%%%%
\subsection{Constraint Query Languages}

Constraint query languages 
(\cite{kkr:cqlang,r:datalog:int,c:time:query,bnp:time:repr} among others)
differ from deductive database query languages in several ways:

\begin{enumerate}
\item With each rule $r$ in a constraint query language, we can have
a conjunction of constraints over some algebraic structure, in addition
to the other literals in the body of the rule.

\item Each fact $p(\overline{X}; C)$ is a conjunction of constraints 
over the given structure, a relation is a finite collection of such 
facts (a disjunction of conjunctions of constraints), and a database 
is a finite collection of such relations.
\end{enumerate}

Constraint query languages provide a model for reasoning about 
(potentially) infinite sets of ground facts using finite representations.
This is because a constraint fact $p(\overline{X}; C)$ is a finite
representation of the (potentially) infinite set of
ground facts that satisfy the conjunction of constraints $C$.

Jaffar and Lassez~\cite{jl:clp} gave a model theory, a fixpoint theory,
and a top-down operational semantics for such programs.
Kanellakis et al.~\cite{kkr:cqlang} gave a bottom-up operational semantics
for some classes of constraint query languages.

\begin{example}
\label{ex:lac:prog1}
Consider the following constraint logic program $P$ with a 
query:
\logicprog{
\lrule {r1:} {p(X)} {X \leq 5, p1(X), p2(X)} \\
\lrule {r2:} {p(X)} {X \geq 7, p2(X)} \\
\lrule {r3:} {p1(X)} {X \geq 1, X \leq 6} \\
\lrule {r4:} {p2(X)} {X \geq 3, X \leq 9} \\
\lrule {r5:} {p2(X)} {X \geq 11, X \leq 15}\\
\lquery{p(X),C}
}
where $p$ is the query predicate, and
$C$ is a conjunction of constraints on the query.
The least model of the program $P$ is the (infinite) set of 
ground facts $\{ p1(a), 1 \leq a \leq 6; 
p2(b), 3 \leq b \leq 9; p2(c), 11 \leq c \leq 15; 
p(d), 3 \leq d \leq 5; p(e), 7 \leq e \leq 9; p(f), 11 \leq f \leq 15 \}$.

Given the above query,
program $P$ can be rewritten using Magic Templates and 
left-to-right sips for each rule to obtain $\langle P^{mg}, Q^{mg} \rangle$
as follows:

{\setrulebodywidth{2.5in}
\logicprog{
\lrule {r1:} {p(X)} {magic\_p(X), X \leq 5, p1(X), p2(X)} \\
\lrule {r2:} {p(X)} {magic\_p(X), X \geq 7, p2(X)} \\
\lrule {r3:} {p1(X)} {magic\_p1(X), X \geq 1, X \leq 6} \\
\lrule {r4:} {p2(X)} {magic\_p2(X), X \geq 3, X \leq 9} \\
\lrule {r5:} {p2(X)} {magic\_p2(X), X \geq 11, X \leq 15} \\
\lrule {r6:} {magic\_p1(X)} {magic\_p(X), X \leq 5} \\
\lrule {r7:} {magic\_p2(X)} {magic\_p(X), X \leq 5, p1(X)} \\
\lrule {r8:} {magic\_p2(X)} {magic\_p(X), X \geq 7} \\
\lrule {Q^{mg}:} {magic\_p(X)} {C}
}
}
We associate the desired query constraints with the corresponding seed
magic fact.

The magic program is also a constraint logic program.
The magic predicates can be considered to define a relation consisting
of the subgoals that a top-down evaluation (\cite{jl:clp}) would 
generate, and the constraints associated with each magic fact correspond
to the desired constraints for answers to that subgoal.

We describe the evaluation of the magic program
$\langle P^{mg}, Q^{mg} \rangle$ for various constraints $C$:

\begin{itemize}
\item $C \equiv (X \geq 7) \& (X \leq 12)$:

All $p(a)$ facts, $7 \leq a \leq 9$, and $p(b)$ facts,
$11 \leq b \leq 12$ are in the least model of $P$, and are answers to the 
query.

In the bottom-up evaluation of the magic program,
$magic\_p(X; X \geq 7, X \leq 12)$ is first derived (using rule $Q^{mg}$).
Rule $r8$ can now be applied to derive $magic\_p2(X; X \geq 7, X \leq 12)$.
(Rule $r6$ cannot be applied because the constraints in the body of the
rule are not satisfied.)
This fact can now be used in rules $r4$ and $r5$ to derive
$p2(X; X \geq 7, X \leq 9)$ and $p2(X; X \geq 11, X \leq 12)$.
These $p2$ facts can be used in the body of rule $r2$ to derive
$p(X; X \geq 7, X \leq 9)$ and $p(X; X \geq 11, X \leq 12)$.

This gives a finite representation of the desired answers to the query,
and mimics the top-down evaluation as well.
Note that the bottom-up evaluation does not compute any facts for
$p1$ since these are irrelevant to answering the query.

\item $C \equiv X \leq 2$:

There are no $p$ facts in the least model that are answers to the query.
In the bottom-up evaluation of the magic program,
$magic\_p(X; X \leq 2)$ is first derived.
Rule $r6$ can now be applied to derive $magic\_p1(X; X \leq 2)$.
(Rule $r8$ is not applicable.)
This fact can be used in the body of rule $r3$ to derive
$p1(X; X \geq 1, X \leq 2)$.
Rule $r7$ can now be applied to derive $magic\_p2(X; X \geq 1, X \leq 2)$.
However, this fact cannot be used in either rule $r4$ or rule $r5$ 
and the evaluation terminates.

Again, this mimics the top-down evaluation.
$\Box$
\end{itemize}
\noBox
\end{example}

\subsection{Quantitative Logic Programs}

Quantitative logic programs  (also referred to as fuzzy databases)
(\cite{shap83:quant,ve86:quant,kl88:quant}, among others) 
differ from ordinary logic programs in several ways:

\begin{enumerate}
\item With each fact $p(\overline{a})$, we associate a ``certainty,'' 
$0 \leq \alpha \leq 1$, which is a measure of the strength of the 
evidence for $p(\overline{a})$.

\item With each rule $r$ in a quantitative logic program, we associate 
a certainty function $f_r$ that is used to compute the certainty of
the head fact, given the certainties of facts in the body.

\item With each predicate $p$, we associate an evidence combination 
function $F_p$ that combines the strengths of evidences obtained
from different sources all supporting the same fact.
\end{enumerate}

This provides a model for rule-based reasoning in expert systems,
where the usual logical reasoning in terms of the truth values
{\bf true} and {\bf false} is insufficient.

We describe the restricted case of K-standard sequence logics
(\cite{shap83:quant,ve86:quant}), and refer the interested reader 
to Kifer and Li~\cite{kl88:quant} for more general types of quantitative
logic programs.
Quantitative logic programs based on K-standard
sequence logics were considered by Van Emden~\cite{ve86:quant},
who gave a model theory, a fixpoint theory, and a top-down operational 
semantics for such programs.
A rule in a quantitative logic program with K-standard sequence logic is 
of the form:
{
\setrulebodywidth{2.1in}
\logicprog{
\lrule {r:} {p (\overline{X}): c_r * \min \{ \alpha_1, \alpha_2, \ldots,
\alpha_n \}}
    {p1 (\overline{X_1}): \alpha_1, \ldots, p_n (\overline{X_n}): \alpha_n}
}
}
Thus, the rule certainty function, $f_r$, associated with rule $r$ is 
\[ f_r = c_r * \min \{ \alpha_1, \ldots, \alpha_n \} \]
where $c_r$ is some constant, $0 < c_r \leq 1$, associated with the rule.
The evidence combination function $ F_p (\{ \alpha_1, \ldots, \alpha_m \}) $
in such a logic is defined as $ \max \{\alpha_1, \ldots, \alpha_m \} $.

\begin{example}
\label{ex:kss:prog1}
Consider the following program $P1$ in K-standard sequence logic, with
query $ Q $:
{
\setrulebodywidth{2.25in}
\logicprog{
\lrule {r1:} {p(X):0.5* \min \{\alpha_1, \alpha_2 \}} {p1(X): \alpha_1,
p2(X): \alpha_2} \\
\lrule {r2:} {p(X):0.45* \alpha_1} {p2(X): \alpha_1} \\
\lfact {r3:} {p1(1):0.4} \\
\lfact {r4:} {p2(1):0.5} \\
\lfact {r5:} {p2(2):0.25} \\
\lquery {p(1):c_p}
}
}
where $p$ is the query predicate, and $c_p$ is the desired certainty for 
$p(1)$.
The least model of the program $P1$ is $\{p1(1):0.4, p2(1):0.5, p2(2):0.25,
p(1):0.225, p(2):0.1125 \}$.

Given the above query,
program $P1$ can be rewritten using (a variant of) Magic Templates and 
left-to-right sips for each rule to obtain $\langle P1^{mg}, Q^{mg} \rangle$ 
as follows:
{
\setrulebodywidth{1.950in}
\logicprog{
\lrulecont {r1:} {p(X):0.5* \min \{\alpha_1, \alpha_2 \}}
{magic\_p(X): \alpha_0, p1(X): \alpha_1,}\\
\lcontrule{} {} {~~~~p2(X): \alpha_2,}\\
\lcontrule{} {} {~~~~\alpha_0 \leq 0.5* \min \{\alpha_1, \alpha_2 \}.} \\
\lrulecont {r2:} {p(X):0.45* \alpha_1} {magic\_p(X): \alpha_0, p2(X): \alpha_1,}\\
\lcontrule{} {}				{~~~~\alpha_0 \leq 0.45* \alpha_1.}\\
\lrule {r3:} {p1(1):0.4} {magic\_p1(1): \alpha_0, \alpha_0 \leq 0.4} \\
\lrule {r4:} {p2(1):0.5} {magic\_p2(1): \alpha_0, \alpha_0 \leq 0.5} \\
\lrule {r5:} {p2(2):0.25} {magic\_p2(2): \alpha_0, \alpha_0 \leq 0.25} \\
\lrule {r6:} {magic\_p1(X): \alpha_0 /0.5} {magic\_p(X): \alpha_0} \\
\lrulecont {r7:} {magic\_p2(X): \alpha_0 /0.5} {magic\_p(X): \alpha_0, 
				p1(X): \alpha_1,}\\
\lcontrule{} {} 			   {~~~~\alpha_1 \geq \alpha_0 /0.5} \\
\lrule {r8:} {magic\_p2(X): \alpha_0 /0.45} {magic\_p(X): \alpha_0} \\
\lfact {Q^{mg}:} {magic\_p(1):c_p}
}
}
We associate the desired query certainty with the corresponding seed 
magic fact $magic\_p(1)$.

Note that the magic program cannot be viewed as a quantitative logic program
in K-standard sequence logic.
The magic predicates can be considered to define a relation consisting
of the subgoals that a top-down evaluation would generate, and
the number associated with the magic fact corresponds to the certainty
desired for answers to that subgoal---this number can thus be semantically
viewed as a ``cutoff.''

We describe the evaluation of the magic program 
$\langle P1^{mg}, Q^{mg} \rangle$ for various values of $c_p$:

\begin{itemize}
\item $c_p = 0.2$:

Since $p(1):0.225$ is in the least model of $P1$, so is $p(1):0.2$.
The desired answer to the query is {\bf yes}.

In the bottom-up evaluation of the magic program, $magic\_p(1)$ is first 
derived (using rule $Q^{mg}$) with a cutoff of $0.2$.
Rule $r6$ can now be applied to derive $magic\_p1(1)$ with a cutoff
of $0.4$, and rule $r8$ can be applied to derive
$magic\_p2(1)$ with a cutoff of $0.444$.
Rule $r3$ can then be applied to derive $p1(1)$ with certainty
$0.4$ (since the constraint in the body is satisfied);
rule $r4$ can also be applied to derive $p2(1)$ with
certainty $0.5$.
Now, the magic fact $magic\_p2(1)$ also can be derived using rule $r7$
with a cutoff of $0.4$.
The fact $p2(1):0.5$ is now derived again.
Finally, rule $r1$ can be applied to compute $p(1):0.2$, and
rule $r2$ can be applied to compute $p(1):0.225$.

This gives the required answer to the query, and mimics the top-down
evaluation (\cite{ve86:quant}) as well.
Note that the bottom-up evaluation does not compute facts
$p2(2):0.25$ and $p(2):0.1125$ which are irrelevant to answering the query.

\item $c_p = 0.25$:

The desired answer to the query is {\bf no}.
In the bottom-up evaluation of the magic program, $magic\_p(1)$ is first
derived with a cutoff of $0.25$.
The magic fact $magic\_p1(1)$ can now be derived (using rule $r6$)
with a cutoff of $0.5$ (indicating that we need to compute
$p1$ with a certainty of at least $0.5$); $magic\_p2(1)$ can
also be derived (using rule $r8$) with a cutoff of $0.556$.
However, neither $p1(1)$ nor $p2(1)$ can be derived, since the constraints
in the appropriate bodies (of rules $r3$ and $r4$) fail.
Since no $p1$ or $p2$ fact is derived, no further derivations
are made, and there is no answer to the query (as expected).

Again, this mimics the top-down evaluation, and no irrelevant facts
are computed.
$\Box$
\end{itemize}
\noBox
\end{example}

\section{Deductive Database System Implementations}
\label{sec:busystems}

There have been a number of implementations of deductive databases.
In this section we briefly discuss some of them.

One of the early implementations was LDL \cite{nt:ldl:bk,ldl89:open,ldl:proto}.
LDL is a main-memory database system implemented at MCC Austin.
It extends the declarative semantics of Horn clauses by allowing
set grouping and aggregate operations.
The treatment of sets allows set-terms to be specified in the body of
rules; set-matching is used to support this feature.
It also allows rules to perform updates, which means that such rules
do not have the usual declarative semantics.
Rather, their semantics is defined in a constructive fashion 
\cite{nk88:updates}.
LDL also provides some control primitives such as choice, provides
a module feature for organizing code, and provides primitives for 
integration with C.

NAIL! \cite{u:imp,muv:des,mnsuv:yaw} was another early deductive database
system.
The current version is compiled into a set-oriented procedural
language called Glue \cite{pdr91:glue}.
NAIL! provides higher order syntactic
features, using the semantics of Hilog \cite{ckw89:hilog}.
Glue/NAIL! is currently implemented on top of Prolog, and is main-memory
oriented.

EKS-V1 \cite{vbkl:eksv1:short} is a deductive database system that 
combines features of disk-oriented and in-memory databases.
It is implemented on top of the MEGALOG logic programming system
which supports access to secondary storage.
It provides facilities for handling negation and aggregation in a 
set-oriented fashion.
Unlike the other deductive database systems discussed here,
it provides support for integrity constraint maintenance and 
hypothetical reasoning.

Aditi \cite{vrkss:aditi} is a deductive database system 
that is primarily disk oriented. 
It provides support for parallelization of the low level operations 
such as joins.
It is integrated with Prolog, and is compiled into an intermediate language
which is then interpreted.
All relational operations are performed with relations assumed to be
disk resident, and join techniques such as sort-merge and hash-join are
used, which means that Aditi is aimed at applications that are 
I/O intensive, but typically perform few iterations.

Starburst SQL (see e.g.\ \cite{mpr90:aggregates}) extends 
SQL with recursive view definitions.
This provides greater expressive power to SQL users, while providing the I/O 
optimization facilities of SQL in a direct manner for recursive applications.

CORAL \cite{rbss90:coral} is a deductive database system developed by the
authors, and is described in detail in a separate section.
LDL, NAIL! and CORAL belong in one family of deductive database systems
in that they are main-memory oriented.
They attempt to provide the power of logic programming using 
complex terms built using uninterpreted function symbols, and 
add new constructs to standard Horn clause logic programs.
EKS-V1, Aditi and Starburst SQL on the other hand are oriented more 
towards secondary storage, and provide less support for complex terms.

\section{CORAL---A Deductive Database Programming Language}
\label{sec:coral}

CORAL\footnote{ CORAL stands for ``COmbining Relations And Logic''.}
is a database programming language being developed at UW-Madison.
An important goal of CORAL is 
to provide a powerful declarative query language.
A second goal of CORAL is to provide a clean interface between an imperative
language (C++) and the declarative language.
This is necessary for several reasons such as permitting the user
to perform actions such as updates and to implement time
critical functions more efficiently.
To this end C++ is extended with several types, constructs and 
library functions.

A CORAL program can be viewed as a collection of {\em declarative modules},
and an {\em imperative module}.
CORAL provides a convenient syntax for defining predicates using the
extended version of C++, and for invoking queries on the
declarative modules from the imperative module.
Declarative modules are compiled into C++ classes, and
the runtime system is written in C++. 
Thus, CORAL reduces the impedance mismatch between the declarative modules
and the C++ module at both the language level and the implementation level.

While there are many similarities to the other deductive database systems
mentioned earlier, there are important differences as well.  For example, 
CORAL supports non-ground terms and ground multisets.
The use of general updates is not allowed in declarative rules.  
A number of the control features supported in CORAL are novel,
as is the approach to integrating with an imperative language
such as C++.

\subsection {Declarative Modules}
\label{sec:declar}

Declarative programming is supported by allowing the user to 
organize sets of rules and facts into {\em declarative modules}.
We introduce the syntax using a program to append two lists.

{
\setrulebodywidth{2.0in}
\logicprog{
\lheader{{\sf module} $ Listroutines $.} \\
\lheader{{\sf export} $ append $ ($ bbf, bfb, fbb $).} \\
\\
\lfact{}{append ([~], L, L)} \\
\lrule{}{append ([H \mid T], L, [H \mid L1])}{append (T, L, L1)} \\
\\
\lheader{{\sf end\_module}.}
}
}

This program illustrates the notion of modules, and CORAL's support for 
complex objects such as lists.
The $ export $ statements at the beginning of each module define what
forms of external queries are permitted on the module 
(``$b$'' denotes an argument that must be bound in the query, 
and ``$f$'' an argument that can be free).

CORAL allows facts to have variables within them.
Thus, it is possible to query $ append $ as follows:
\logicprog{
\lquery{append([1,2,3,4,X],[Y,Z], ANS)}
}
and get the answer
\[ ANS = [1,2,3,4,X,Y,Z] \]

In this CORAL differs from Aditi, EKS-V1, LDL, Glue/NAIL! and Starburst SQL, 
which restrict the facts in a database to be ground.
The cost and benefits of non-ground facts is discussed in 
Section~\ref{sec:ng}.

\subsubsection{Sets and Negation}

The keyword {\sf not} is used as a prefix to indicate a negated body literal.
A program is non-floundering if all variables in a negated literal are
ground before the literal is evaluated (in the left-to-right rule 
order).
CORAL supports a class of programs with
negation that properly contains the class of non-floundering 
modularly stratified programs (Ross \cite{r90:modstrat}).

Sets can be constructed by {\em set-enumeration}, or by {\em set-grouping}.
Set grou\-ping was discussed in Section~\ref{sec:setgrp:agg}.
The following rule (fact) illustrates set-enumeration.
{\setrulebodywidth{.2in}
\logicprog{
\lfact{}{children(john,\{mary, peter, paul\})}% \hspace*{4cm}
}
}

%%%%%%%%%%%%%
% The following rule illustrates the use of set-grouping.
% \logicprog{
% \lrule{}{p (X, <Y>)}{q (X,Y,Z)}
% }
% This rule uses facts for $ q $ to generate a multiset $ S $ of
% instantiations for the variables $ X, Y$, and $ Z $.
% For each value $ x $ for $ X $ in this set it creates a fact 
% $ p( x, \pi_Y \sigma_{X=x} S) $, where $\pi_Y$ is a multiset projection,
% and $ \sigma $ a selection operator.
% $\pi_Y$ projects the relation it is provided on the arguments corresponding
% to $ Y $, and does not do duplicate elimination.
% $ \sigma_{X=x} $ selects from its input set those tuples that have 
% a value $ x $ for attributes $ X $.
% Thus with facts $ q(1,2,3), q(1,2,5) $ and $ q(1,3,4) $ we get the fact 
% $ p(1,\{2,2,3\}) $.
% This construct is much more powerful than set-enumeration.
%%%%%%%%%%%%%

All elements of sets generated thus must be ground terms (i.e., not contain any
variables).
General matching or unification of sets (where one or both of the sets can have
variables, respectively) is not supported.
CORAL requires the use of the set-grouping operator to be modularly-stratified
(in the same way as negation).
When programs allow the creation of sets (and nested structures that include 
sets) the domain (or universe) of discourse has to be extended beyond
the Herbrand universe that is standard in logic programming.
Beeri et al.\ \cite{bnst:sets:LDL} describe such an
extended Herbrand universe.

CORAL provides several standard operations on sets and multisets as
built-in predicates.
These include $ {\sf member} $, $ {\sf union} $, $ {\sf intersection} $,
$ {\sf difference} $,
$ {\sf multisetunion} $, $ {\sf cardinality} $, $ {\sf subset} $, 
and $ {\sf set} $.
%%%%%%%%%%
% For reasons of efficiency,
% most of these (other than {\sf member}) are restricted to testing, and will 
% not permit generation --- 
% for example, the $ {\sf subset} $ predicate cannot be used to generate
% subsets of a set, but can be used to test if a given set is a subset of 
% another.
%%%%%%%%%%%
CORAL also provides several aggregate operations for use on sets and multisets
such as $ {\sf count}, 
{\sf min}, \lbok {\sf max},\lbok {\sf sum}, {\sf product}, {\sf average} $
and $ {\sf any} $.

\subsection{Other Declarative Module Features}
\label{sec:modules}

CORAL uses bottom-up evaluation as the basic paradigm for evaluation of
declarative modules.
It uses a variety of optimization techniques including 
program transformations such as Magic Templates
(\cite{br:ont,r:mag}), optimizations of bottom-up evaluation such as
Semi-naive evaluation, rule and predicate orderings, efficient unification
techniques such as hash-consing \cite{goto74:hashcons,sg76:hashcons}
and sharing of structure for ground terms, and efficient indexing techniques.
Currently, evaluation is completely in-memory, although we plan to 
implement disk-resident relations in future versions of CORAL.
More optimization techniques will be incorporated in future versions of 
CORAL.

Modules are the unit of compilation in CORAL.
Numerous annotations are allowed in modules, and many of these
have a global effect on the module.
Unlike Glue/NAIL!, where modules have only a compile time meaning and 
no run-time meaning, modules in CORAL have important run-time semantics.
Several run-time optimizations are done at the module level.

In most cases, facts (other than answers to the 
query) computed during the 
evaluation of a module are best discarded to save space (since bottom-up
evaluation stores many facts, space is generally at a premium).
Module calls provide a convenient unit for discarding intermediate
answers, which may take up too much space otherwise.
By default CORAL does precisely this --- it discards all intermediate
facts and subgoals computed by a module at the end of a call to the 
module.
This can be overridden by the user, by using an annotation 
$ {\sf save\_module} $ within a module definition.

CORAL provides utilities to take a text file organized as a table, parse it
into fields and records, and convert it into a relation.
Similarly, utilities for output of relations in tabular form are also
provided.
This provides some of the features of the AWK string manipulation language
that is available on Unix systems.

CORAL supports Ordered Search \cite{rss91:ord:search}, which 
is an evaluation mechanism that 
orders the use of generated subgoals in a program.
Subgoals and answers to subgoals are generated asynchronously, as
in the regular bottom-up evaluation of the magic program.
However, the order in which generated subgoals are made available for use 
is somewhat similar to a top-down evaluation.
Ordered search 
maintains information about dependencies between subgoals, which
can be used to evaluate a large class of programs with negation.
It also provides an ordering to the computation that 
hides subgoals; this could be useful in situations when only a single 
answer is desired for a query.

CORAL provides some basic facilities for debugging of programs.
A {\sf trace} facility 
lets the user know what rules are being evaluated, and
prints out answers and subgoals as they are generated.
CORAL also provides some high-level profiling facilities, that use as the
unit of measurement the unification operation (unification of large
subterms are treated as generating recursive calls to unification for
the purpose of this count).

\subsection{Imperative Modules in CORAL}
\label{sec:imperative}

An imperative module is a program in an imperative language, which consists of 
C++ augmented by adding a layer of new types and constructs.
We introduce some features of imperative modules using the program in 
Figure~\ref{fig:imperative}, which updates the salary of a person depending on
the number of employees that work for the person (directly or 
indirectly).
The program gives an intuitive idea of the features we provide for
imperative modules.

\begin{figure}
\ordinalg{
\> void Update\_Sals (Relation *emp) \\
\> $\{$ \+ \\
\\
% \> /* EmpTuple is a declared to be subclass of tuple with string fields \\
% \> \> ename (employee name) and mname (manager name) and an \\
% \> \> integer field sal.*/ \\
% \> /* NumempsTuple is declared to be subclass of tuple with string \\
% \> \> fields  mname (manager name) and numemps (number of\\
% \> \> employees) */ \\
% \> /* The declarations are omitted for brevity */ \\
% 
\> TupleType(EmpTuple,3) \\
\> \> TupleArg(1, string, ename); ~~ TupleArg(2, string, mname); \\
\> \> TupleArg(3, int, sal); \\
\> EndTupleType(EmpTuple) \\
\> TupleType(NumempsTuple,2) \\
\> \> TupleArg(1, string, mname); ~~ TupleArg(2, int, numemps); \\
\> EndTupleType(NumempsTuple) \\
%
\> EmpTuple *emp\_tuple, new\_tuple;\\
\> NumempsTuple query, *result\_tuple, pattern;\\
\> Relation *numofemps = new IndexedRelation(2); \\
\\
\> query.set\_mname(make\_var(0)); \\
\> query.set\_numemps(make\_var(1)); \\
\> call\_coral ("numofemps", \&query, numofemps); \\
% \> call\_coral ("numofemps", make\_tuple(make\_var(0), make\_var(1)),
%	numofemps); \\
\\
\> FOR\_EACH\_TUPLE (emp\_tuple, emp)  $\{$ \\
\> \> pattern.set\_mname( emp\_tuple$\rightarrow$ename()); \\
\> \> pattern.set\_numemps( make\_var(0) );\\
\> \> int newsal = emp\_tuple$\rightarrow$sal(); \\
\> \> FOR\_EACH\_MATCHING\_TUPLE(result\_tuple, numofemps, \\
\> \> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\&pattern) \{ \\
\> \> \> newsal += 10* result\_tuple$\rightarrow$numemps(); \\
\> \> $ \} $ END\_EACH\_TUPLE(result\_tuple)\\
\> \> copy\_tuple(emp\_tuple, new\_tuple); \\
\> \> new\_tuple$\rightarrow$set\_sal(newsal); \\
\> \> update\_tuple(emp, emp\_tuple, new\_tuple); \\
\> $ \} $ END\_EACH\_TUPLE(emp\_tuple)\\
\- \\
\> $\}$
}

{
\setrulebodywidth{1.75in}
\logicprog{
\lheader{{\sf module} Employee.} \\
\lheader{{\sf export} $numofemps$ (bf).} \\
\\
\lrule{}{worksfor(E,M)}{emp(E,M,S)} \\
\lrulecont{}{worksfor(E,M)}{worksfor(E,E1),}\\
\lcontrule{} {}            {~~~~emp(E1,M,S)} \\
\lrule{}{numofemps(M,{\sf count}(set(<E>)))}{worksfor(E,M)} \\
\\
\lheader{\sf end module.}
}
}
\caption{Updating Employee Salaries}
\label{fig:imperative}
\end{figure}

A {\em relation} is a set of tuples.
The user can create two types of relations: {\em unindexed relations\/}
and {\em indexed relations\/}.
Indices can be added to an existing $ indexed $ relation by means of a 
procedure call.

A C++ user can also directly access a database relation (not just get a 
copy of it) by providing the name of the relation and its arity.
CORAL provides facilities to insert tuples into, and delete tuples from 
relations using the ``$ += $'' and ``$ -= $'' operators.
A procedure {\sf update\_tuple} to update tuples in a relation is 
also provided, as illustrated in the example.

CORAL provides two iterative constructs for accessing the tuples of a 
relation (the tuples are returned in an arbitrary order).
Both these are illustrated in the example.
{\sf FOR\_EACH\_TUPLE} successively instantiates its first argument to
each tuple in the relation given by the second argument.
{\sf FOR\_EACH\_MATCHING\_TUPLE} successively instantiates its first argument 
to each tuple in the relation given by the second argument 
that matches the pattern specified by the third argument.
A variety of other functions are available to the imperative language programmer
to manipulate relations.
These include all the set and aggregate functions described earlier. 

A C++ user can invoke a query on a relation that is defined declaratively
(and exported by a declarative module), using the procedure
{\sf call\_coral} illustrated in the example.
There are two variants of this procedure, one of which takes a single
query, and the other a set of queries.
In later versions of CORAL we plan to allow 
inline declaration of a declarative module within imperative code.
This will provide a simpler syntax for calling declarative modules
and could be interpreted as a direct extension of the C++ language.
CORAL provides a simple convention for defining predicates using 
C++ code.

To provide efficient support for novel applications, CORAL allows the user to
create new abstract data types and integrate them with the declarative 
query language in a simple and clean fashion, without modifying or
recompiling system code.
For instance, when dealing with DNA sequences, a type $ sequence $ that 
provides several built-in operations such as approximate subsequence matching,
indexing etc.\ is very useful.

\section{Conclusion}
\label{sec:conclusion}

We have reviewed a collection of results on bottom-up evaluation
of logic programs, and attempted to place them in the perspective
of a coherent approach to logic program evaluation. The main
points, in our opinion, are the following:
\begin {itemize}
\item
Efficient bottom-up evaluation methods are available 
that are sound and complete with respect to the declarative semantics.
\item
Systems based upon these methods are being developed, and offer
rich support for rule-based applications.
\end {itemize}

\acknowledgements

This paper is based upon a tutorial to be presented at COMPEURO 92 by
R. Ramakrishnan.  It has borrowed some material from other papers,
in particular \cite{nr:aun}.

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,
and NSF grant IRI-9011563.


% \bibliographystyle{plain}
% \bibliography{lib/bib/dbimp,lib/bib/moredb,lib/bib/clp}

\begin{thebibliography}{100}

\bibitem{au:uni}
Alfred~V. Aho and Jeffrey~D. Ullman.
\newblock Universality of data retrieval languages.
\newblock In {\em Proceedings of the Sixth ACM Symposium on Principles of
  Programming Languages}, pages 110--120, San Antonio, Texas, 1979.

\bibitem{ahb:rec}
P.M.G. Apers, M.A.W. Houtsma, and F.~Brandse.
\newblock Processing recursive queries in relational algebra.
\newblock In {\em Data and Knowledge (DS-2), Proc. of the Second IFIP 2.6
  Working Conference on Database Semantics}, pages 17--39. North Holland, 1986.

\bibitem{abw88:strat}
K.~R. Apt, H.~Blair, and A.~Walker.
\newblock Towards a theory of declarative knowledge.
\newblock In J.~Minker, editor, {\em Foundations of Deductive Databases and
  Logic Programming}, pages 89--148. Morgan-Kaufmann, San Mateo, Calif., 1988.

\bibitem{bprm:strat}
I.~Balbin, G.~S. Port, K.~Ramamohanarao, and K.~Meenakshi.
\newblock Efficient bottom-up computation of queries on stratified databases.
\newblock {\em \em Journal of Logic Programming}.
\newblock To Appear.

\bibitem{br:adijlp}
I.~Balbin and K.~Ramamohanarao.
\newblock A generalization of the differential approach to recursive query
  evaluation.
\newblock {\em Journal of Logic Programming}, 4(3), September 1987.

\bibitem{b:nai}
Francois Bancilhon.
\newblock Naive evaluation of recursively defined relations.
\newblock In Brodie and Mylopoulos, editors, {\em On Knowledge Base Management
  Systems --- Integrating Database and AI Systems}. Springer-Verlag, 1985.

\bibitem{bmsu:mag}
Francois Bancilhon, David Maier, Yehoshua Sagiv, and Jeffrey~D. Ullman.
\newblock Magic sets and other strange ways to implement logic programs.
\newblock In {\em Proceedings of the ACM Symposium on Principles of Database
  Systems}, pages 1--15, Cambridge, Massachusetts, March 1986.

\bibitem{bnp:time:repr}
Marianne Baudinet, Marc Niezette, and Pierre Wolper.
\newblock On the representation of infinite temporal data and queries.
\newblock In {\em Proceedings of the Tenth ACM Symposium on Principles of
  Database Systems}, pages 280--290, Denver, Colorado, May 1991.

\bibitem{b85:qeddb:sn}
R.~Bayer.
\newblock Query evaluation and recursion in deductive database systems.
\newblock Unpublished Memorandum, 1985.

\bibitem{brss:neg}
C.~Beeri, R.~Ramakrishnan, D.~Srivastava, and S.~Sudarshan.
\newblock Valid computations and the {M}agic implementation of stratified
  programs.
\newblock Manuscript, September 91.

\bibitem{bnrst:set}
Catriel Beeri, Shamim Naqvi, Raghu Ramakrishnan, Oded Shmueli, and Shalom Tsur.
\newblock Sets and negation in a logic database language.
\newblock In {\em Proceedings of the ACM Symposium on Principles of Database
  Systems}, pages 21--37, San Diego, California, March 1987.

\bibitem{bnst:sets:LDL}
Catriel Beeri, Shamim Naqvi, Oded Shmueli, and Shalom Tsur.
\newblock Set constructors in a logic database language.
\newblock {\em The Journal of Logic Programming}, pages 181--232, 1991.

\bibitem{br:ont}
Catriel Beeri and Raghu Ramakrishnan.
\newblock On the power of {Magic}.
\newblock In {\em Proceedings of the ACM Symposium on Principles of Database
  Systems}, pages 269--283, San Diego, California, March 1987.

\bibitem{bm72:strshr}
R.~S. Boyer and J.~S. Moore.
\newblock The sharing of structure in theorem-proving programs.
\newblock {\em Computational Logic}, pages 101--116, 1972.

\bibitem{bdm88:constr}
F.~Bry, H.~Decker, and R.~Manthey.
\newblock A uniform approach to constraint satisfaction and constraint
  satisfiability in deductive databases.
\newblock In {\em Procs. International Conference on Extending Database
  Technology}, February 1988.

\bibitem{b:quer}
Francois Bry.
\newblock Query evaluation in recursive databases: Bottom-up and top-down
  reconciled.
\newblock {\em IEEE Transactions on Knowledge and Data Engineering},
  5:289--312, 1990.

\bibitem{cgm:semopt}
U.~S. Chakravarthy, J.~Grant, and J.~Minker.
\newblock Logic-based approach to semantic query optimization.
\newblock {\em ACM Transactions on Database Systems}, 15(2):162--207, June
  1990.

\bibitem{ch:hor}
Ashok~K. Chandra and David Harel.
\newblock Horn clause queries and generalizations.
\newblock {\em J. Logic Programming}, 2(1):1--15, April 1985.

\bibitem{ckw89:hilog}
Weidong Chen, Michael Kifer, and Davis~S. Warren.
\newblock Hilog: A first-order semantics for higher-order logic programming
  constructs.
\newblock In {\em Proceedings of the North American Conference on Logic
  Programming}, pages 1090--1114, 1989.

\bibitem{ldl89:open}
D.~Chimenti, R.~Gamboa, and R.~Krishnamurthy.
\newblock Towards an open architecture for {LDL}.
\newblock In {\em Proceedings of the International Conference on Very Large
  Databases}, pages 195--204, 1989.

\bibitem{ldl:proto}
D.~Chimenti, R.~Gamboa, R.~Krishnamurthy, S.~Naqvi, S.~Tsur, and C.~Zaniolo.
\newblock The {LDL} system prototype.
\newblock {\em IEEE Transactions on Knowledge and Data Engineering},
  2(1):76--90, 1990.

\bibitem{cd:qrb}
L.~Cholvy and R.~Demelombe.
\newblock Querying a rule base.
\newblock In {\em Procs. 1st International Conference on Expert Database
  Systems}, pages 365--371, April 1986.

\bibitem{c:time:query}
Jan Chomicki.
\newblock Polynomial time query processing in temporal deductive databases.
\newblock In {\em Proceedings of the Ninth ACM Symposium on Principles of
  Database Systems}, pages 379--391, Nashville, Tennessee, April 1990.

\bibitem{cw:why}
S.R. Cohen and O.~Wolfson.
\newblock Why a single parallelization strategy is not enough in knowledge
  bases.
\newblock In {\em Proceedings of the ACM Symposium on Principles of Database
  Systems}, pages 200--216, Philadelphia, Pennsylvania, March 1989.

\bibitem{cm:lowcagg}
M.~P. Consens and A.~O. Mendelzon.
\newblock Low complexity aggregation in {Graphlog} and {Datalog}.
\newblock In {\em Procs. International Symposium on Database Theory}, Paris,
  1990.

\bibitem{cgkv:dec}
Stavros~S. Cosmadakis, Haim Gaifman, Paris Kanellakis, and Moshe~Y. Vardi.
\newblock Decidable optimization problems for database logic programs.
\newblock In {\em Proceedings of the Twentieth Symposium on the Theory of
  Computation}, pages 477--490, Chicago, Illinois, May 1988.

\bibitem{cn89:agg:clos}
I.~F. Cruz and T.~S. Norvell.
\newblock Aggregative closure: An extension of transitive closure.
\newblock In {\em Proc. IEEE 5th Int'l Conf. Data Engineering}, pages 384--389,
  1989.

\bibitem{dw:ext}
Suzanne~W. Dietrich and David~S. Warren.
\newblock Extension tables: Memo relations in logic programming.
\newblock In {\em Proceedings of the Symposium on Logic Programming}, pages
  264--272, 1987.

\bibitem{d:ond}
G.~Dong.
\newblock On distributed processing of {Datalog} queries by decomposing
  databases.
\newblock In {\em Proceedings of the ACM SIGMOD International Conference on
  Management of Data}, pages 26--35, Portland, Oregon, June 1986.

\bibitem{f:rete}
C.~Forgy.
\newblock Rete: A fast algorithm for the many pattern/many object pattern
  matching problem.
\newblock {\em Artificial Intelligence}, 19(1):17--37, 1982.

\bibitem{gmsv:und}
Haim Gaifman, Harry Mairson, Yehoshua Sagiv, and Moshe~Y. Vardi.
\newblock Undecidable optimization problems for database logic programs.
\newblock In {\em Proceedings of the Second IEEE Symposium on Logic in Computer
  Science}, pages 106--115, Ithaca, New York, June 1987.

\bibitem{gst:afr}
S.~Ganguly, A.~Silberschatz, and S.~Tsur.
\newblock A framework for the parallel processing of {Datalog} queries.
\newblock In {\em Proceedings of the ACM SIGMOD International Conference on
  Management of Data}, Atlantic City, New Jersey, May 1990.
\newblock To appear.

\bibitem{ggz90:minmax}
Sumit Ganguly, Sergio Greco, and Carlo Zaniolo.
\newblock Minimum and maximum predicates in logic programming.
\newblock In {\em Proceedings of the ACM Symposium on Principles of Database
  Systems}, 1991.

\bibitem{gl88:stable}
M.~Gelfond and V.~Lifschitz.
\newblock The stable model semantics for logic programming.
\newblock In {\em Proc. Fifth International Conference and Symposium on Logic
  Programming}, 1988.

\bibitem{grb87:ddc}
R~Gonzalez-Rubio, J.~Rohmer, and A.~Bradier.
\newblock An overview of {DDC}: {D}elta {D}riven {C}omputer.
\newblock In {\em Parallel Architectures and Languages Europe, Volume 1:
  Parallel Architectures}, Lecture Notes in Computer Science, No.\ 258, pages
  414--433, 1987.

\bibitem{goto74:hashcons}
E.~Goto.
\newblock Monocopy and associative algorithms in an extended lisp.
\newblock Technical Report 74-03, Information Science Laboratory, Univ. of
  Tokyo, Tokyo, Japan, May 1974.

\bibitem{h:det}
A.~Richard Helm.
\newblock Detecting and eliminating redundant derivations in deductive database
  systems.
\newblock Technical Report RC 14244 (\#63767), IBM Thomas Watson Research
  Center, December 1988.

\bibitem{i:bou}
Yannis~E. Ioannidis.
\newblock Bounded recursion in deductive data\-bases.
\newblock {\em Algorithmica}, 1(4):361--385, October 1986.

\bibitem{iw:tow}
Yannis~E. Ioannidis and Eugene Wong.
\newblock Towards an algebraic theory of recursion.
\newblock Technical Report 801, Computer Sciences Department, University of
  Wisconsin-Madison, October 1988.

\bibitem{jl:clp}
J.~Jaffar and J-L. Lassez.
\newblock Constraint logic programming.
\newblock In {\em Proceedings of the 14th ACM POPL}, pages 111--119, Munich,
  January 1987.

\bibitem{kkr:cqlang}
Paris~C. Kanellakis, Gabriel~M. Kuper, and Peter~Z. Revesz.
\newblock Constraint query languages.
\newblock In {\em Proceedings of the Ninth ACM Symposium on Principles of
  Database Systems}, pages 299--313, Nashville, Tennessee, April 1990.

\bibitem{krs90:context}
D.~Kemp, K.~Ramamohanarao, and Z.~Somogyi.
\newblock Right-, left-, and  multi-linear rule transformations that
maintain context information.
\newblock In {\em Proceedings of the Sixteenth International Conference on Very
  Large Databases}, pages 380--391, August 1990.

\bibitem{kss91:wfn}
David Kemp, Divesh Srivastava, and Peter Stuckey.
\newblock Magic sets and bottom-up evaluation of well-founded models.
\newblock In {\em Proceedings of the International Logic Programming
  Symposium}, pages 337--351, San Diego, CA, U.S.A., October 1991.

\bibitem{ks91:aggs}
David Kemp and Peter Stuckey.
\newblock Semantics of logic programs with aggregates.
\newblock In {\em Proceedings of the International Logic Programming
  Symposium}, pages 387--401, San Diego, CA, U.S.A., October 1991.

\bibitem{kp88:strat}
J.M. Kerisit and J.M. Pugin.
\newblock Efficient query answering on stratified databases.
\newblock In {\em Proc. of the International Conference on Fifth Generation
  Computer Systems}, pages 719--725, Tokyo, Japan, November 1988.

\bibitem{kl88:quant}
Michael Kifer and Ai~Li.
\newblock On the semantics of rule based expert systems with uncertainty.
\newblock In {\em Proceedings of 2nd ICDT}, Bruges, Belgium, 1988.

\bibitem{kl:afr}
Michael Kifer and Eliezer~L. Lozinskii.
\newblock A framework for an efficient implementation of deductive databases.
\newblock In {\em Proceedings of the Advanced Database Symposium}, Tokyo,
  Japan, 1986.

\bibitem{kl:syg}
Michael Kifer and Eliezer~L. Lozinskii.
\newblock {SYGRAF}: Implementing logic programs in a database style.
\newblock {\em IEEE Transactions on Software Engineering}, 1988.

\bibitem{k81:quist}
J.~J. King.
\newblock {QUIST}: A system for semantic query optimization in relational
  databases.
\newblock In {\em Proceedings of the International Conference on Very Large
  Databases}, pages 510--517, August 1981.

\bibitem{sippu90:eval}
J.~Kuittinen, O.~Nurmi, S.~Sippu, and E.~{Soisalon-Soininen}.
\newblock Efficient implementation of loops in bottom-up evaluation of logic
  queries.
\newblock In {\em Proceedings of the Sixteenth International Conference on Very
  Large Databases}, August 1990.

\bibitem{m:sem}
Michael~J. Maher.
\newblock {\em Semantics of Logic Programs}.
\newblock PhD thesis, Department of Computer Science, University of Melbourne,
  Melbourne, Australia, 1985.

\bibitem{mr:dej}
Michael~J. Maher and Raghu Ramakrishnan.
\newblock D\`ej\'a vu in fixpoints of logic programs.
\newblock In {\em Proceedings of the Symposium on Logic Programming},
  Cleveland, Ohio, 1990.

\bibitem{mnsuv:yaw}
Katherine Morris, Jeffrey~F. Naughton, Yatin Saraiya, Jeffrey~D. Ullman, and
  Allen Van~Gelder.
\newblock {YAWN!} ({Y}et {A}nother {W}indow on {NAIL!}).
\newblock {\em Database Engineering}, December 1987.

\bibitem{muv:des}
Katherine Morris, Jeffrey~D. Ullman, and Allen Van~Gelder.
\newblock Design overview of the {NAIL!} system.
\newblock In {\em Proceedings of the Third International Conference on Logic
  Programming}, 1986.

\bibitem{m:seave}
A.~Motro.
\newblock {SEAVE}: The mechanism for verifying user presuppositions.
\newblock {\em ACM TOIS}, 4(4):312--330, October 1986.

\bibitem{mfpr:mag}
I.~S. Mumick, S.~Finkelstein, H.~Pirahesh, and R.~Ramakrishnan.
\newblock Magic is relevant.
\newblock In {\em Proceedings of the ACM SIGMOD International Conference on
  Management of Data}, Atlantic City, New Jersey, May 1990.

\bibitem{mpr90:aggregates}
Inderpal~S. Mumick, Hamid Pirahesh, and Raghu Ramakrishnan.
\newblock Duplicates and aggregates in deductive databases.
\newblock In {\em Proceedings of the Sixteenth International Conference on Very
  Large Databases}, August 1990.

\bibitem{mfpr:magcond}
Inderpal~Singh Mumick, Sheldon~J. Finkelstein, Hamid Pirahesh, and Raghu
  Ramakrishnan.
\newblock Magic conditions.
\newblock In {\em Proceedings of the Ninth ACM Symposium on Principles of
  Database Systems}, pages 314--330, Nashville, Tennessee, April 1990.

\bibitem{nk88:updates}
S.~Naqvi and R.~Krishnamurthy.
\newblock Database updates in logic programming.
\newblock In {\em Proceedings of the ACM Symposium on Principles of Database
  Systems}, 1988.

\bibitem{nt:ldl:bk}
Shamim Naqvi and Shalom Tsur.
\newblock {\em A Logical Language for Data and Knowledge Bases}.
\newblock Principles of Computer Science. Computer Science Press, New York,
  1989.

\bibitem{n:com}
Jeffrey~F. Naughton.
\newblock Compiling separable recursions.
\newblock In {\em Proceedings of the SIGMOD International Symposium on
  Management of Data}, pages 312--319, Chicago, Illinois, May 1988.

\bibitem{n:dat}
Jeffrey~F. Naughton.
\newblock Data independent recursion in deductive databases.
\newblock {\em Journal of Computer and System Sciences}, 38(2):259--289, April
  1989.

\bibitem{nr90:history}
Jeffrey~F. Naughton and Raghu Ramakrishnan.
\newblock How to forget the past without repeating it.
\newblock In {\em Proceedings of the Sixteenth International Conference on Very
  Large Databases}, August 1990.

\bibitem{nr:aun}
Jeffrey~F. Naughton and Raghu Ramakrishnan.
\newblock Bottom-up evaluation of logic programs.
\newblock In {J-L}. Lassez, editor, {\em Computational Logic: Essays in Honor
  of Alan Robinson}. The MIT Press, 1991.

\bibitem{nrsu:ari}
Jeffrey~F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, and Jeffrey~D. Ullman.
\newblock Argument reduction through factoring.
\newblock In {\em Proceedings of the Fifteenth International Conference on Very
  Large Databases}, pages 173--182, Amsterdam, The Netherlands, August 1989.

\bibitem{nrsu:sigmod}
Jeffrey~F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, and Jeffrey~D. Ullman.
\newblock Efficient evaluation of right{-,} left{-,} and multi-linear rules.
\newblock In {\em Proceedings of the ACM SIGMOD International Conference on
  Management of Data}, pages 235--242, Portland, Oregon, May 1989.

\bibitem{ns:ade}
Jeffrey~F. Naughton and Yehoshua Sagiv.
\newblock A decidable class of bounded recursions.
\newblock In {\em Proceedings of the ACM Symposium on Principles of Database
  Systems}, pages 227--236, San Diego, California, March 1987.

\bibitem{ns:min}
Jeffrey~F. Naughton and Yehoshua Sagiv.
\newblock Minimizing expansions of recursions.
\newblock In Hasan Ait-Kaci and Maurice Nivat, editors, {\em Resolution of
  Equations in Algebraic Structures}, volume~1, pages 321--349, San Diego,
  California, 1989. Academic Press, Inc.

\bibitem{pw:par}
F.C.N. Pereira and D.H.D. Warren.
\newblock Parsing as deduction.
\newblock In {\em Proceedings of the twenty-first Annual Meeting of the
  Association for Computational Linguistics}, 1983.

\bibitem{pdr91:glue}
Geoffrey Phipps, Marcia~A. Derr, and Kenneth~A. Ross.
\newblock {Glue-NAIL!}: A deductive database system.
\newblock In {\em Proceedings of the ACM SIGMOD Conf. on Management of Data},
  pages 308--317, 1991.

\bibitem{pp88:weak}
H.~Przymusinska and T.C. Przymusinski.
\newblock Weakly perfect model semantics for logic programs.
\newblock In {\em Proceedings of the Fifth International Conference/Symposium
  on Logic Programming}, 1988.

\bibitem{p88:lstrat}
T.C. Przymusinski.
\newblock On the declarative semantics of stratified deductive databases.
\newblock In J.~Minker, editor, {\em Foundations of Deductive Databases and
  Logic Programming}, pages 193--216, 1988.

\bibitem{pry90:ext:stable}
T.C. Przymusinski.
\newblock Extended stable semantics for normal and disjunctive programs.
\newblock In {\em Seventh International Logic Programming Conference}, pages
  459--477, 1990.

\bibitem{r:mag}
Raghu Ramakrishnan.
\newblock Magic {T}emplates: A spellbinding approach to logic programs.
\newblock In {\em Proceedings of the International Conference on Logic
  Programming}, pages 140--159, Seattle, Washington, August 1988.

\bibitem{r:par}
Raghu Ramakrishnan.
\newblock Parallelism in logic programs.
\newblock In {\em Proceedings of the ACM Symposium on Principles of Programming
  Languages}, San Francisco, California, 1990.

\bibitem{rbk:opt}
Raghu Ramakrishnan, Catriel Beeri, and Ravi Krishnamurthy.
\newblock Optimizing existential {Datalog} queries.
\newblock In {\em Proceedings of the ACM Symposium on Principles of Database
  Systems}, pages 89--102, Austin, Texas, March 1988.

\bibitem{rbss90:coral}
Raghu Ramakrishnan, Per Bothner, Divesh Srivastava, and S.~Sudarshan.
\newblock Coral: A database programming language.
\newblock In Jan Chomicki, editor, {\em Proceedings of the NACLP `90 Workshop
  on Deductive Databases}, October 1990.
\newblock Available as Report TR-CS-90-14, Department of Computing and
  Information Sciences, Kansas State University.

\bibitem{rsuv:pro}
Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey~D. Ullman, and Moshe Vardi.
\newblock Proof-tree transformation theorems and their applications.
\newblock In {\em Proceedings of the ACM Symposium on Principles of Database
  Systems}, Philadelphia, Pennsylvania, March 1989.

\bibitem{rss90:eval}
Raghu Ramakrishnan, Divesh Srivastava, and S.~Sudarshan.
\newblock Rule ordering in bottom-up fixpoint evaluation of logic programs.
\newblock In {\em Proceedings of the Sixteenth International Conference on Very
  Large Databases}, August 1990.

\bibitem{rss91:ord:search}
Raghu Ramakrishnan, Divesh Srivastava, and S.~Sudarshan.
\newblock Controlling the search in bottom-up evaluation.
\newblock Manuscript, submitted for publication, 1991.

\bibitem{rs91:tdvsbup}
Raghu Ramakrishnan and S.~Sudarshan.
\newblock {Top-Down} vs.\ {Bottom-Up} {Revisited}.
\newblock In {\em Proceedings of the International Logic Programming
  Symposium}, 1991.

\bibitem{rs91:tdvsbup2}
Raghu Ramakrishnan and S.~Sudarshan.
\newblock {Top-Down} vs.\ {Bottom-Up} {Revisited}.
\newblock In preparation (full version of paper that appeared in ILPS'91),
  1992.

\bibitem{r:datalog:int}
Peter~Z. Revesz.
\newblock A closed form for datalog queries with integer order.
\newblock In {\em International Conference on Database Theory}, pages 187--201,
  France, December 1990.

\bibitem{rlk:the}
J.~Rohmer, R.~Lescoeur, and J.~M. Kerisit.
\newblock The {A}lexander method --- a technique for the processing of
  recursive axioms in deductive database queries.
\newblock {\em New Generation Computing}, 4:522--528, 1986.

\bibitem{r90:modstrat}
Kenneth Ross.
\newblock Modular {S}tratification and {M}agic {S}ets for {DATALOG} programs
  with negation.
\newblock In {\em Proceedings of the ACM Symposium on Principles of Database
  Systems}, pages 161--171, 1990.

\bibitem{ross91:tro}
Kenneth Ross.
\newblock Modular acyclicity and tail recursion in logic programs.
\newblock In {\em Proceedings of the ACM Symposium on Principles of Database
  Systems}, 1991.

\bibitem{rosa91:monaggr}
Kenneth Ross and Yehoshua Sagiv.
\newblock Monotonic aggregation in deductive databases.
\newblock In {\em Proceedings of the post-ILPS'91 Workshop on Deductive
  Databases}, 1991.

\bibitem{sz:the}
Domenico Sacca and Carlo Zaniolo.
\newblock The generalized counting methods for recursive logic queries.
\newblock In {\em Proceedings of the First International Conference on Database
  Theory}, 1986.

\bibitem{s:lin}
Yatin Saraiya.
\newblock Linearizing nonlinear recursions in polynomial time.
\newblock In {\em Proceedings of the ACM SIGACT-SIGART-SIGMOD Symposium on
  Principles of Database Systems}, pages 182--189, Philadelphia, Pennsylvania,
  March 1989.

\bibitem{sg76:hashcons}
M.~Sassa and E.~Goto.
\newblock A hashing method for fast set operations.
\newblock {\em Information Processing Letters}, 5(4):31--34, June 1976.

\bibitem{schmidt91:metacontrol}
Helmut Schmidt.
\newblock {\em Meta-Level Control for Deductive Database Systems}.
\newblock Lecture Notes in Computer Science, Number 479. Springer-Verlag, 1991.

\bibitem{s:ont}
H.~Seki.
\newblock On the power of {A}lexander templates.
\newblock In {\em Proc. of the ACM Symposium on Principles of Database
  Systems}, pages 150--159, 1989.

\bibitem{slr88:prod}
T.~Sellis, C.~Lin, and L.~Raschid.
\newblock Implementing large production systems in a {DBMS} environment.
\newblock In {\em Proceedings of the ACM SIGMOD Conf. on Management of Data},
  pages 404--412, June 1988.

\bibitem{shap83:quant}
Ehud Shapiro.
\newblock Logic programs with uncertainties: A tool for implementing rule-based
  systems.
\newblock In {\em Proceedings of IJCAI}, pages 529--532, 1983.

\bibitem{ss:mag}
Seppo Sippu and Eljas {Soisalon-Soinen}.
\newblock An optimization strategy for recursive queries in logic databases.
\newblock In {\em Proceedings of the Fourth International Conference on Data
  Engineering}, Los Angeles, California, 1988.

\bibitem{sr91:aggr}
S.~Sudarshan and Raghu Ramakrishnan.
\newblock Aggregation and relevance in deductive databases.
\newblock In {\em Proceedings of the Seventeenth International Conference on
  Very Large Databases}, September 1991.

\bibitem{sr92:ng}
S.~Sudarshan and Raghu Ramakrishnan.
\newblock Optimizations of bottom-up evaluation with non-ground terms.
\newblock In preparation, 1992.

\bibitem{ssrn91:space}
S.~Sudarshan, Divesh Srivastava, Raghu Ramakrishnan, and Jeff Naughton.
\newblock Space optimization in the bottom-up evaluation of logic programs.
\newblock In {\em Proceedings of the ACM SIGMOD Conf. on Management of Data},
  1991.

\bibitem{u:imp}
Jeffrey~D. Ullman.
\newblock Implementation of logical query languages for databases.
\newblock {\em ACM Transactions on Database Systems}, 10(4):289--321, September
  1985.

\bibitem{u:bot}
Jeffrey~D. Ullman.
\newblock Bottom-up beats top-down for {Datalog}.
\newblock In {\em Proceedings of the Eighth ACM Symposium on Principles of
  Database Systems}, pages 140--149, Philadelphia, Pennsylvania, March 1989.

\bibitem{vrkss:aditi}
Jayen Vaghani, Kotagiri Ramamohanarao, David Kemp, Zoltan Somogyi, and Peter
  Stuckey.
\newblock The {Aditi} deductive database system.
\newblock In {\em Proceedings of the NACLP'90 Workshop on Deductive Database
  Systems}, 1990.

\bibitem{ve86:quant}
M.~H. {Van Emden}.
\newblock Quantitative deduction and its fipoint theory.
\newblock {\em Journal of Logic Programming}, (1):37--53, 1986.

\bibitem{ek:the}
M.~H. van Emden and R.~A. Kowalski.
\newblock The semantics of predicate logic as a programming language.
\newblock {\em Journal of the ACM}, 23(4):733--742, October 1976.

\bibitem{vgrs:wf}
A.~{Van Gelder}, K.~Ross, and J.~S. Schlipf.
\newblock Unfounded sets and well-founded semantics for general logic programs.
\newblock {\em Journal of the ACM}, 38(3):620--650, 1991.

\bibitem{v:ame}
Allen Van~Gelder.
\newblock A message passing framework for logical query evaluation.
\newblock In {\em Proceedings of the ACM SIGMOD International Conference on
  Management of Data}, pages 349--362, Washington, DC, May 1986.

\bibitem{v:dec}
Moshe~Y. Vardi.
\newblock Decidability and undecidability results for boundedness of linear
  recursive queries.
\newblock In {\em Proceedings of the Seventh ACM Symposium on Principles of
  Database Systems}, pages 341--351, Austin, Texas, March 1988.

\bibitem{vbk91:ic:eks}
L.~Vieille, P.~Bayer, and V.~{K\"{u}chenhoff}.
\newblock Integrity checking and materialized views handling by update
  propagation in the {EKS-V1} system.
\newblock Technical report, CERMICS - Ecole Nationale Des Ponts Et Chaussees,
  France, June 1991.
\newblock Papport de Recherche, CERMICS 91.1.

\bibitem{vbkl:eksv1:short}
L.~Vieille, P.~Bayer, V.~{K\"{u}chenhoff}, and A.~Lefebvre.
\newblock {EKS-V1}, a short overview.
\newblock In {\em AAAI-90 Workshop on Knowledge Base Management Systems}, 1990.

\bibitem{v:rec}
Laurent Vieille.
\newblock Recursive axioms in deductive databases: The query-subquery approach.
\newblock In {\em Proceedings of the First International Conference on Expert
  Database Systems}, pages 179--193, Charleston, South Carolina, 1986.

\bibitem{v:dat}
Laurent Vieille.
\newblock Database complete proof procedures based on {SLD}-resolution.
\newblock In {\em Proceedings of the Fourth International Conference on Logic
  Programming}, pages 74--103, 1987.

\bibitem{v:qosaq}
Laurent Vieille.
\newblock From {QSQ} towards {QoSaQ}: Global optimizations of recursive
  queries.
\newblock In {\em Proc. 2nd International Conference on Expert Database
  Systems}, April 1988.

\bibitem{wcl91:setprod}
J.~Widom, R.J. Cochrane, and B.~G. Lindsay.
\newblock Implementing set-oriented production rules as an extension to
  {Starburst}.
\newblock In {\em Proceedings of the International Conference on Very Large
  Databases}, pages 275--285, August 1991.

\bibitem{ws:sha}
O.~Wolfson and A.~Silberschatz.
\newblock Sharing the load of logic program evaluations.
\newblock In {\em Proceedings of the 7th ACM SIGMOD-SIGACT-SIGART Symposium on
  Principles of Database Systems}, Philadelphia, Pennsylvania, March 1989.

\bibitem{zyt:ane}
W.~Zhang, C.~T. Yu, and D.~Troy.
\newblock A necessary and sufficient condition to linearize doubly recursive
  programs in logic databases.
\newblock Unpublished manuscript, Department of EECS, University of Illinois at
  Chicago, 1988.

\end{thebibliography}
\end{document}









