
\documentstyle[12pt]{article}

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

% \newfont{\mmk}{cmr6} % For gremlin size 8

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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 $}} 
\newcommand{\ifff}{\mbox{$ :- $}} 
   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  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>}
%    \lhornclause {<Rulename>} {<Rulehead>} {<Rulebody>} {<RuleLabel>}
%    \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{\lhornclause}[4]{\[ #1~#2 \ifff #3. #4 \]}
\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{\setprocminordefaults}{
\setlength{\topskip}{10pt}
\setlength{\headsep}{0pt}
\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.
}

\newcommand{\setprocdefaults}{
\setnormaldefaults
% \renewcommand{\maketitle}{??} - fill this in 
\setlength{\oddsidemargin}{-.20in}
\setlength{\topmargin}{-.40in}  % In order to get .75in seperation
\setlength{\textheight}{9.25in}
\setlength{\textwidth} {6.99in}
\setlength{\columnsep} {0.33in}
\setprocminordefaults

% \setlength{\topskip}{10pt}
% \setlength{\headsep}{0pt}
% \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.
}

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

\setnormaldefaults

\renewcommand{\ifff}{\mbox{$ :- $}}
\newcommand{\inguide}[1]{ }
\newcommand{\implnote}[1]{\footnote{#1}}
\newcommand{\inpaper}[1]{#1}

\renewcommand{\comment}[1]{}
\renewcommand{\fullversion}[1]{}
\newcommand{\heading}[1]{\noindent{\bf #1:}}

\author{Raghu Ramakrishnan \and
Praveen Seshadri \and
Divesh Srivastava \and
S. Sudarshan \\
{\em Computer Sciences Department,}\\
{\em University of Wisconsin--Madison, WI 53706, U.S.A.}}

\date{}
\makeindex


\begin{document}

\title{\bf THE CORAL USER MANUAL\\
A Tutorial Introduction to CORAL\thanks
{The authors' e-mail addresses are 
\{raghu,divesh,praveen\}@cs.wisc.edu; sudarsha@research.att.com.}}

\maketitle

\newpage
\tableofcontents
\newpage

\section{Preface}

CORAL\footnote{CORAL stands for ``COntrol, Relations And Logic''.}
is a database programming language based on Horn clause logic
developed at the University
of Wisconsin--Madison.  Source code for CORAL (written in C++)
is available by anonymous ftp over the internet.
The CORAL project was initiated in 1988-89, under the name Conlog,
and a preliminary report was presented at a workshop in the NACLP 89
conference.  Preliminary versions of the system have been used
by a few groups, but this is the first widely available release.
We would welcome any feedback on the system.  Comments, bug reports
and questions should be mailed to {\em coral@cs.wisc.edu}.

We would like to acknowledge the contributions of the following people to
the CORAL system.  Per Bothner, who was largely responsible for
the initial implementation of CORAL that served as the basis for subsequent
development, was a major early contributor.
Joseph Albert worked on some aspects of the set-manipulation code;
Tarun Arora 
implemented several utilities and built-in/library routines in CORAL,
and contributed to the explanation package;
Tom Ball implemented an early prototype of the Seminaive evaluation system;
Lai-chong Chan did the initial implementation of existential query optimization;
Sumeer Goyal implemented embedded CORAL constructs in C++;
Vish Karra did the initial implementation of pipelining;
Robert Netzer did the initial implementation of Magic rewriting; and
Bill Roth created test suites, improved some of the I/O routines
and implemented the graphical aspects of the explanation package.

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.

\noindent
{\bf R. Ramakrishnan \\
P. Seshadri \\
D. Srivastava \\
S. Sudarshan}

\newpage

\section{Introduction}
\label{chap:intro}
\input{intro.chap}
\newpage

\section{A First Session}
\label{chap:start}
\input{start.chap}
\newpage

\section{Declarative Language Features:  Basics}
\label{chap:declba}
\input{declba.chap}
\newpage

\section{Declarative Language Features:  Negation}
\label{chap:declne}
\input{declne.chap}
\newpage

\section{Declarative Language Features:  Sets and Multisets}
\label{chap:declse}
\input{declse.chap}
\newpage

\section{Declarative Language Features:  Advanced}
\comment{Aggregate selections, head updates, prioritization}
\label{chap:declad}
\input{declad.chap}
\newpage

\section{Modules in CORAL}
\comment{styles, neg/grouping, save modules ...}
\label{chap:modules}
\input{modules.chap}
\newpage

\section{Declarative Language Features:  Annotations and Control}
\label{chap:declac}
\input{declac.chap}
\newpage

\section{Declarative Language Features:  Pipelined Evaluation}
\comment{Prolog-style evaluation.}
\label{chap:pipe}
\input{pipe.chap}
\newpage

\section{Some Useful Built-in Predicates}
\label{chap:builtins}
\input{builtins.chap}
\newpage

\section{CORAL Commands}
\label{chap:cmds}
\input{cmds.chap}
\newpage

\section{CORAL and C++}
\label{chap:impmod}
\input{impmod.chap}
\newpage

\section{Extensibility in CORAL}
\label{chap:extens}
\input{extens.chap}
\newpage

\section{Programming in CORAL:  Some Guidelines}
\label{chap:proghints}
\input{proghints.chap}
\newpage

\section{Current Status}
\label{chap:currstat}
\input{currstat.chap}
\newpage

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

\begin{thebibliography}{{Van}92}

\bibitem[BR87]{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[Bra90]{bratko:prolog:book}
I.~Bratko.
\newblock {\em Prolog Programming for Artificial Intelligence}.
\newblock Addison-Wesley, 1990.

\bibitem[Bry89]{b:log}
Francois Bry.
\newblock Logic programming as constructivism: A formalization and its
  application to databases.
\newblock In {\em Proceedings of the ACM SIGACT-SIGART-SIGMOD Symposium on
  Principles of Database Systems}, pages 34--50, Philadelphia, Pennsylvania,
  March 1989.

\bibitem[CDRS86]{cdrs86:exodus:manager}
Michael Carey, David DeWitt, Joel Richardson, and Eugene Shekita.
\newblock Object and file management in the {EXODUS} extensible database
  system.
\newblock In {\em Proceedings of the International Conference on Very Large
  Databases}, August 1986.

\bibitem[KRS90]{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 International Conference on Very Large
  Databases}, pages 380--391, Brisbane, Australia, 1990.

\bibitem[Llo87]{lloyd:logic:pgm}
J.~W. Lloyd.
\newblock {\em Foundations of Logic Programming}.
\newblock Springer-Verlag, second edition, 1987.

\bibitem[NRSU89]{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[Ram88]{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[RBK88]{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[Ros90]{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[RS91]{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[RS92]{rosa91:monaggr}
Kenneth Ross and Yehoshua Sagiv.
\newblock Monotonic aggregation in deductive databases.
\newblock In {\em Proceedings of the ACM Symposium on Principles of Database
  Systems}, pages 114--126, 1992.

\bibitem[RSS90]{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[RSS92a]{rss92:ord:search}
Raghu Ramakrishnan, Divesh Srivastava, and S.~Sudarshan.
\newblock Controlling the search in bottom-up evaluation.
\newblock In {\em Proceedings of the Joint International Conference and
  Symposium on Logic Programming}, 1992.

\bibitem[RSS92b]{rss92:coral}
Raghu Ramakrishnan, Divesh Srivastava, and S.~Sudarshan.
\newblock {CORAL}: {C}ontrol, {R}elations and {L}ogic.
\newblock In {\em Proceedings of the International Conference on Very Large
  Databases}, 1992.

\bibitem[RSSS92]{rsss:coral:impl}
Raghu Ramakrishnan, Divesh Srivastava, S.~Sudarshan, and Praveen Seshadri.
\newblock Implementation of the {CORAL} deductive database system.
\newblock Submitted, 1992.

\bibitem[RSSS93]{rsss93:coraloverview}
Raghu Ramakrishnan, Praveen Seshadri, Divesh Srivastava, and S.~Sudarshan.
\newblock An overview of coral.
\newblock Manuscript (full version of \cite{rss92:coral}, which appeared in
  VLDB92)., 1993.

\bibitem[{Van}92]{vg92:wfagg}
A.~{Van Gelder}.
\newblock The well-founded semantics of aggregation.
\newblock In {\em Proceedings of the ACM Symposium on Principles of Database
  Systems}, pages 127--138, 1992.

\bibitem[VRS91]{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.

\end{thebibliography}


\newpage

\appendix

% This section has been changed to be a pointer to the text file INSTALL
% in the distribution.
\section{The CORAL Installation Guide}
\label{chap:install}
\input{install.chap}
\newpage

% RR Direct the interested user to a more up to date version
\section{The CORAL--C++ Interface Specification}
\label{chap:intspec}
%\input{intspec.chap}

The document ``doc/Interface'' included with the CORAL distribution
describes using CORAL with C++ and/or Tk/Tcl.

\newpage

% RR I think this sort of thing would be better done as a pointer
%    to the file's location from the previous section, this avoids
%    the printed manual becoming out-of-date too quickly.  
%\section{A Sample makefile for C++ Code with Embedded CORAL}
%\label{chap:makefile}
%\input{makefile.chap}
%\newpage

% RR Eliminating - This code is no longer valid
%\section{Adding an Array Data Type}
%\label{chap:arrays}
%\input{arrays.C}
%\newpage

\input{manual.ind}
\newpage

\end{document}
