<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">
This section describes how a module is compiled into intermediate structures.
The module under consideration has been passed through the rewriting stages,
and has been consulted by the parser. As part of the EndModuleFunction,
the function {\em interpret\_module} is called. This resides in {\em Compile.C}.
All compile time routines reside in {\em Compile.C} or {\em CompileRule.C}.

Each module is compiled into a QFModuleData structure. There are two subclasses
of QFModuleData, one for materialized modules, and one for pipelined modules.
Here we consider the materialized modules only. Look for pipelined modules in 
the section on pipelining. For materialized (i.e. bottom-up) modules,
a QFMaterializedModuleData structure is created. Since its name is so long
and painful, I just refer to it as a QFM in this section.

 Since a QFM
corresponds to a module, it is associated with a structure called a Table.
This represent a table of the relations used by the module. Whenever the
module code needs to access a relation, it is made to access an offset in
the table. Thus at run-time, appropriate relation pointers can be plugged
into the table, and voila, the relations get accessed. So as a first step,
a Table structure is created for the module. Also, the ParserStruct is
processed and RuleInfo structures corresponding to each module rule are
created. Each RuleInfo struct is supposed to correspond to one
syntactic rule defined in the module. This is as opposed to a seminaive
rule of which there could be several for each syntactic rule (remember,
deltas, non-linear rules, do-re-mi ...). The RuleInfo is merely a data
structure representing a syntactic rule entity. All the RuleInfos of
a module are grouped into a RuleInfoArray struct.

Just a step back to get the logical view of things first : what is a module
compilation supposed to do? (this is the DAILY DOUBLE). The predicates
in a module need to broken into strongly connected components or SCCs. 
Within each SCC, the rules corresponding to the predicates need to be
prepared to be evaluated in a seminaive fashion. This is exactly what
happens when a module is compiled. Stepping through the code is pretty
simple (if you believe that, talk to Scott Sterner). But seriously,
compiling a module involves:
\begin{itemize}
\item performing an scc analysis on the predicates in the module. The list of
predicates is available as a field of the ParserStruct. The scc analysis uses
some static structures(SccWork, etc.) declared inside {\em Compile.C}.
The algorithm used is Tarjan's algorithm (at this point,
we expect the reader to know that
its complexity is O(N), or else call toll free 1-800-COMPLEX). All it does is
provide each predicate with an scc number corresponding to the topological 
numbering of the sccs.

\item Now for each scc, an SccInfo structure is created, corresponding
to the scc. Each SccInfo struct contains an array of seminaive rules,
as well as a number of additional fields and arrays that are used for
optimizing execution. While most of these are created at compile time,
it makes sense to explain them in conjunction with the explanation
of the run-time execution. The function {\em CreateSNStructs} performs
the creation of the seminaive structures. This function looks at each
predicate in the scc and for the rules defining that predicate, creates
seminaive structures. Finally after the SccInfo struct has been completely
created, it is added to a list of SccInfos that the QFM contains. This
list is maintained in topological order of sccs (note that during execution,
the lowest scc needs to be executed first).

\item Every predicate in an scc has a bunch of rules defining it. Some of
these rules may be recursive.\footnote{Pop Quiz: If there is more than one
predicate in an scc, can there be a predicate in the scc
without a recursive rule?}
Every SemiNaive rule has a pointer to a corresponding RuleInfo (or is it
an offset into the RuleInfoArray) that specifies the syntactic rule.
Also, it keeps information about the join order in a predOrders array.
This array contains a permutation of the join order, and all access
to the predicates of the seminaive rule should be made through this
array. The current join order uses the heuristic that the delta relation
will be small, and hence is moved up front. Further (I think I put this in),
we try to move literals that have common variables with the delta ahead
of those that don't. Take a look at comments in the code that handles this
in initPredOrders(). The SemiNaive rule also contains backtracking information
to be used at run-time. This information is vital for efficient performance,
and more details of this are in the section on backtracking. There is
also a function that generates the appropriate index annotations for
the efficient execution of the rule. These annotations are appended to
the index annotation list of the QFM. The comments in the code explain
the logic behind the index creation.

\item Wherever possible, we try to perform stuff at compile-time instead of 
at run-time. This is why you will find a number of arrays called *-offsets.
These are pre-computed offsets into lists or arrays of stuff. For instance,
there is a pred\_offsets array in the SemiNaive structure that contains for
every literal, the offset of the corresponding predicate in the Predicates
array. If you don't understand the computation of these array right away,
don't worry. You will when you have to. However, this stuff is very important.
Pipelining was speeded up by almost 25\% by moving an offset
computation from the run-time code to the compile time code.
If you're competing with Quintus, {\bf nothing} is cheap.

\item Finally the QFM is complete, it is inserted into the DerivedRelation
table as the ModuleData structure corresponding to the exported query form.
The solver routine also has to be entered along with it. We have the same
solver for all bottom-up modules, and its called (quaintly) ``do\_query''.
More about that in the section on run-time stuff.

\end{itemize}

\subsection{Read At Your Own Risk}
{\em Compile.C} and {\em CompileRule.C} evolved from what
used to be {\em interp.C}. The third
branch is {\em Execute.C} which contains run-time execution code. 

This is only for Coral Gunslingers of the High Speech.
The Table was originally called a Frame (the name was subsequently changed
as a humanitarian gesture, after Raghu started chairing AI sessions).
However, as a result of this, most of the code has declarations of the
form `Table *F'. I'm sorry about that, but rescuing Raghu seemed more
important at the time.

You might ask: why is there a separate syntactic structure (the Rule class)
used for rules in the ParserStruct and rewriting, and a separate structure
(the RuleInfo class) used at compile-time. Good question: integrating the two is
your next job.

Remember that the same code used to compile and execute SemiNaive rules is also
used for imperative rules. The imperative rules are just massaged to create
SemiNaive rules, and then the same compilation occurs. It is your 
responsibility
if you change this code to ensure that it works on both kinds of rules.
In order to be able to figure out where the code has been invoked from,
I have used the field of the SemiNaive structure that points back to the
enclosing SccInfo. If the code is being called during a module compilation,
then this pointer will be non-NULL and point to the SccInfo. On the other
hand, for an imperative rule, there is no SccInfo, and no QFM, and so the
pointer is NULL. This is checked for example to determine whether to generate
index annotations (meaningless for an imperative rule).

</pre></body></html>