\chapter{Implementation}

In this chapter, we describe our implementation of \TR. The basic 
difference between Prolog and \TR is the updates to the database. Prolog 
has a backtracking mechanism for queries only, while \TR has a backtracking 
mechanism for updates too. In Prolog, updates are not undone during 
backtracking. For instance, the Prolog command ``$assert(p(1))\ ,\ fail$'' 
asserts $p(1)$ into the database even though the execution fails. In \TRR, as described 
in Section 2.1, if the query fails, the database is rolled back to its original 
state. In addition, features from procedural programming, like while-loop, for-loop, 
and if-then-else statements, can be expressed logically in \TRR.

A \TR program is a file containing a set of transaction rules. When it 
is loaded into our program, all rules pass through the interpreter, which 
translates transaction rules into Prolog rules, and are then asserted into the 
Prolog database. Four \TR prototypes have been implemented, each testing a 
different implementation architecture. Prototype 1 is conceptually simple,
while Prototype 3 is more complex and efficient. Since many applications do 
not require backtracking, Prototype 4 was developed as a special version of 
\mbox{Prototype 3}. It handles transactions without backtracking to increase speed.

        The prototypes were designed to be used with XSB Prolog, because of its 
efficiency in handling large databases. However, with some simple adjustments, 
it runs on Quintus Prolog, Sicstus Prolog and C-Prolog.

\section{Program Overview}

\subsection{Data Objects}

Since the \TR implementation is written in Prolog, its syntax 
for rules is similar to Prolog syntax. A term is either a constant, variable, 
or a compound term. Constants are either numbers or atoms. In most Prolog 
language, atoms usually have one of the following forms:

\begin{itemize}
\item Any sequence of alphanumeric characters (including '\_'), starting with a 
	lowercase letter.
\item Any sequence from the following set of characters: 
$+$ $-$ $*$ $/$ $\backslash$ \^{ } $<$ $>$ $=$ $`$ $:$ $.$ $?$ $@$ $\#$ $\&$ 
% + - * / \ ^ < > = ` : . ? @ # &
\item Any sequence of characters delimited by single quotes. 
\item Any of: ! ; [] {}
\end{itemize}

Variables may be written as any sequence of alphanumeric characters (including 
'\_') starting with either a capital letter or '\_'. 

The structured data objects of the language are compound terms. A 
compound term comprises a functor and a sequence of one or more terms called
arguments. A functor is characterized by its name, which is an atom, and its 
arity, or number of arguments. Usually, when we need to refer explicitly to a 
functor, we will denote it by the form $Name/Arity$. For example, $p/2$ represents 
the predicate $p(X,Y)$.

\subsection{Rules and Database Tuples}

Unlike normal logic programming, there are two types of storage areas for \TR
rules: the transaction base and the database. The transaction base defines a 
set of transaction rules, while database stores a set of database rules
and database tuples (ground atomic formulas). 

An atomic formula is an expression of the form $p(t1, \ldots\ ,tn)$, 
where $p$ is a predicate symbol, and $t1, \ldots\ ,tn$ are terms. In the 
implementation, a transaction formula is an atomic formula or a formula of 
one of the following forms:

\begin{itemize}
\item if $\phi$\ and $\psi$\ are transaction formulas, so is ($\phi\ sc\ \psi$). 
	The infix operator, $sc$, called serial conjunction 
	is used to compose transactions and formulate queries. In the formal
	theory of \TR [{\em BK95}], the symbol $\otimes$\ is used instead of 
	$sc$.
\item if $\phi$\ is a transaction formula, $\alpha$\ is a database clause, $L$ 
	is a list of variable names, then ($while \; \alpha\ do \; \phi$) and 
	($with \; L\; while \; \alpha\ do \; \phi$) are transaction formulas.
\item if $\phi$\ is a transaction formula, $\alpha$\ is a database clause, 
	and $L_1$, $L_2$ are lists of variable names, then ($forall \; (unique,
	possible) \; L_1 \; in\ \alpha\ do\ \phi$) and 
	($with \; L_2 \; forall \; (unique, \\
	possible) \; L_1 \; in \; \alpha\ do\ \phi$) are transaction 
	formulas, where the flags {\em unique} and {\em possible} are optional.
\item if $\phi$\ and $\psi$\ are transaction formulas, $\alpha$\ is a database 
	clause, then ($if\ \alpha\ then\ \phi\ else\ \psi$) is a transaction 
	formula.
\end{itemize}

A database clause is either an atomic formula or a formula of the form $\phi$, 
$\beta$\ where $\alpha$\ and $\beta$\ are database clauses.

\begin{enumerate}
\item Transaction Rules: \\
	A transaction rule is either of the following: 
	\begin{enumerate}
	\item an atomic formula ; or
	\item $\phi\ \leftarrow\ \psi$, \hspace{.3in} where $\phi$\ is an 
		atomic formula and $\psi$\ is a transaction formula. 
	\end{enumerate}
\item Database Rules: \\
	A database rule is a normal Prolog rule, which has one of the following 
	forms:
	\begin{enumerate}
	\item an atomic formula; or
	\item $\phi\ :- \alpha$\ , \hspace{.3in} where $\phi$\ is an atomic 
		formula and $\alpha$\ is a database clause.
	\end{enumerate}
\item Database Tuples: \\
        During the execution of a \TR program, database updates are
        backtrackable. Database tuples are implemented differently from 
        database rules. They are not stored directly in the database; rather, 
        to ensure backtrackability, they are specially treated. In the 
	first place, the specification of a tuple should be informed by the 
	a declare statement before the tuple is inserted. The declare 
	statement contains the predicate name and arity, the number of 
	arguments in the primary key, and an indexing specification. With 
	this information, a tuple is broken down into two parts, the key of 
	the tuple, and the value denoted by the key. For instance, {\em declare age/2
        key 1} declares a tuple named age which has two arguments and the first 
        one is the primary key. With this declaration, 
        the tuple $age(sam,24)$ in database would be represented by storage of two 
        base predicates, $key\_age(sam)$ and $value\_age(sam,24)$, in database.
        More details of tuples and keys will be discussed in Section 4.3.
\end{enumerate}

\section{Modules}

The implementation consists of 10 Prolog modules: a main module ($protN$), a parsing module 
($parserN$), a loading module ($uploadN$), query module ($queryN$), two modules defining 
keys ($keys\_basicsN$ and $keys\_applN$), two modules defining elementary updates 
($tr\_basicsN$ and $tr\_applN$), a module for converting predicate names ($namingN$), 
and a module containing basic functions ($basic\_funsN)$, where
 $N$ is a number, 1, 2, 3, or 4, that represents the prototype number (to be 
discussed in Section 4.4). For instance, $prot3$ is a program for Prototype 3, and 
$upload1$ is a program for Prototype 1. Figure 4.2 shows a hierarchy of the modules. 
In this section, we give a brief description of the contents of each module.

\begin{figure*}
	\hfil\epsfbox{module.ps}
	\caption{Hierarchy of Modules}
\end{figure*}

\subsection{Main Module ({\em protN})}

To start the \TR implementation, users consult this main module, and 
then run the predicate {\em init/1}, which loads up all other modules and 
initializes their parameters.

\subsection{Parsing Module ({\em parserN})}

This is a core module of the implementation. In this module, transaction formulas 
(queries or rule bodies) are parsed and translated into Prolog formulas. New rules 
may be added during the parsing phase.

\subsection{Upload Module ({\em uploadN})}

It defines the directives {\em loadtrans/1} and {\em loadbase/1}. The former loads a 
transaction program into database, and the latter loads up a database program. When a 
transaction program is loaded, the translated Prolog code is saved in a file with the 
postfix ``\_tran'' added to the original file name.

\subsection{Query Module ({\em queryN})}

It defines the directive {\em trans/1} as an interface for transaction query.
So, in order to perform a transaction $\phi$, executes the query 
``$trans\; \phi$'' in Prolog prompt.

\subsection{Key Modules ({\em keys\_basicsN} and {\em keys\_applN})}

There are two modules for handling primary database keys, {\em keys\_basicsN} and 
{\em keys\_applN}. The first one defines basic operators for keys, i.e., {\em declare}, 
{\em create/1}, {\em destroy/1}, etc. The second defines operators for bulk updates.

\subsection{Transaction Function Modules ({\em tr\_basicsN} and {\em tr\_applN})}

These modules are used in Prototype 4 only. The {\em tr\_basicsN} module defines basic 
transaction operators like {\em ins/1}, {\em del/1}. The {\em tr\_applN} module defines 
transaction operators for bulk updates.

\subsection{Naming Module ({\em namingN})}

This module contains rules that transform predicate names. For instance, it contains rules 
outputing {\em key\_age}, or {\em value\_age}, etc., when the input is the predicate name 
{\em age}, as mentioned above.

\subsection{Basic Function Module ({\em basic\_funsN})}

This is the lowest-level module. Some of its rules may need changing when porting the 
\TR prototypes to other Prolog interpreters.


\section{General Features of the Implementation}

\subsection{Undo Operations}

At first glance, a natural method of translating elementary updates 
({\em ins} and {\em del}) from \TR formulas to Prolog formulas is to 
simply replace them by the Prolog update operators ({\em assert} and 
{\em retract}). However, the resulting program would not work correctly. 
The reason is that Prolog does not undo updates during backtracking.

To get around this problem, we need to remember the tuples being updated, 
and undo the update when backtracking. If a predicate is asserted,
then during backtracking, it must be retracted; and vice versa. Consider 
the following rules:
\myeqnbegin
on\_backtracking(X). & &\\
on\_backtracking(X) & :- & call(X),\; !,\; fail. 
\myeqnend
When $on\_backtracking(X)$ is first called, this predicate is 
true no matter what argument $X$ is, so nothing happens. During 
backtracking, the second rule
is executed and $X$ is called. With cut ($!$) and fail, this rule also 
fails but $X$ is not undone. So, this predicate has no effect when 
it is executed the first time, but the argument $X$ will be executed 
during backtracking. The following example shows how the insertion and 
deletion of tuples are undoable during backtracking.
\myeqnbegin
ins(X) & :- & assert(X), on\_backtracking(retract(X)).\\
del(X) & :- & retract(X), on\_backtracking(assert(X)).
\myeqnend
Consider the transaction query $?- ins(p(1))\; sc\; fail$. First, $p(1)$ is 
asserted. Then, the execution of $on\_backtracking(retract(p(1)))$ returns 
true without any side effect. During backtracking, $p(1)$ is retracted, 
i.e., the assert is undone. However, there is a weakness in this method, 
which will be discussed in Section 4.3.3.

\subsection{Transaction Base and Database}

In \TRR, a predicate can be defined in two places, in the database and in 
the transaction base. During transaction processing, both sets of rules are 
used; but during query processing, only database rules are used. This 
difference is accounted for the logical semantics of \TR [$BK95$].

In the implementation, database rules and transaction rules are both 
implemented as Prolog rules. To distinguish them, the \TR compiler adds a 
special pre-condition to each transaction rule, e.g., the rule 
$a \leftarrow\ b_1\; sc\; b_2\; sc\; ....\; sc\; b_n$ is compiled into the 
following Prolog rule:
\myeqnbegin
a & :- & tr,\; b_1,\; b_2,\; ....,\; b_n.	\nonumber 
\myeqnend
Thus, transaction rules can effectively be disabled by retracting the atom
 ``$tr$'' from the Prolog database.
\myeqnbegin
r1.& & \\
r2 & \leftarrow\ & p(X)\; sc\; q(X). \\
	\nonumber	\\		
r1 & :- & tr. \\
r2 & :- & tr,\; p(X),\; q(X). \\
	\nonumber	\\
r3. & & \\
r4 & :- & p(X)\;, q(X).
\myeqnend
Consider the above three pairs of rules, Rules 4.5 and 4.6 are transaction rules, 
Rule 4.7 and Rule 4.8 are their translations into Prolog, and Rule 4.9 and Rule 4.10 
shows two Prolog rules with similar structures to Rules 4.5 and 4.6. For 
transaction processing, the flag ``$tr$'' is asserted into database. After the 
flag is asserted, the pre-condition tr in all transaction rules succeeds, 
so both transaction rules and database rules can be used in subsequent
queries. To disable transaction rules, the flag ``$tr$'' is retracted from 
database. In subsequent queries, since the pre-condition tr in all 
transaction rules fails, only database rules can be used. For instance, 
if a Prolog database contains Rule 4.7, then the 
Prolog query ``$?- r1$'' fails but the query ``$?- ins(tr), r1$'' succeeds. 
Therefore, when a transaction $\phi$\ is executed, it is
converted into ``$ins(tr),\; \psi,\; del(tr)$'' where $\psi$\ is the Prolog 
translation of $\phi$. Before $\psi$\ is executed, $tr$ is asserted to 
activate transaction rules, and after the execution of $\psi$, $tr$ is 
retracted to deactivate the transaction rules. 

As discussed above, only transaction processing uses rules in the transaction 
base. Therefore, rules in database cannot use rules in transaction base. 
For instance, suppose a Prolog translation of a \TR program contains the 
following rules:
\myeqnbegin
p(1) & :- & tr. 	\nonumber	\\
p(2).& & 		\nonumber	\\	
q(X) & :- & p(X).	\nonumber
\myeqnend
Above prolog rules represent that the transaction base contains $p(1)$, and 
the database contains $p(2)$ and ``$q(X) :-\ p(X)$''. 
So, the database query $q(X)$ returns $X=2$ only. However, if the above
transaction processing method is used, then a transaction query $q(X)$ will
be translated into ``$ins(tr),\; q(X),\; del(tr)$''. The query returns
$X=1$ and $X=2$ because after $tr$ is inserted, $q(X)$ can bind $X$ to 1 and
2. However, since $q(1)$ is neither in transaction base,
nor in database (only $q(2)$ is in database), the answer from this 
transaction query is incorrect. The reason for the failure is the use of
transaction rule in a database rule. To avoid using transaction rules
from a database rule in transaction query, a predicate $dbase(X)$ is defined as follows:
\myeqnbegin
dbase(X) & :- & tr,\; !,\; del(tr),\; X,\; ins(tr) \\
	& &     ; 	\nonumber 	\\
        & &     X.	\nonumber	
\myeqnend
The predicate $dbase(X)$ executes X directly if the $tr$ flag is not in the 
database, or deletes the flag before executing X if it is in the database.
In the latter case, after finished executing X, $tr$ is inserted into database,
so that other transaction process can continue to be executed.
Also, instead of directly asserting database rules into Prolog database, we translate
the rules $p :-\ \psi$\ into $p :-\ dbase(\psi )$
in Prolog, where $p$ is an atomic formula and $\psi$\ is a database formula. 
Therefore, the database rule ``$q(X) :- p(X)$'' in the previous example becomes
$q(X) :-\ dbase(p(X))$ in Prolog. Now, during transaction processing of 
$q(X)$, after the ``$tr$'' flag is inserted, with the rule
$q(X) :-\ dbase(p(X))$, $dbase(p(X))$ is executed. The ``$tr$'' flag is then
deleted before $p(X)$ is called. In this case, X binds to 2 only.

Apart from the addition of a ``$tr$'' flag, the compiling of a transaction 
rule also involves some parsings and translations. The serial conjunction 
operator ``$sc$'' is replaced with the conjunction operator `{\em ,}' in Prolog
(as shown in Rule 2 and Rule 4 in the above examples), because the evaluation
 of a clause body in Prolog executes serially from left to right. Other 
translations of particular predefined predicates will be discussed later in 
this section.

\subsection{Delete Tags}

In Section 4.3.1, although a backtrackable insert and delete was defined, 
the query ``$?- del(p(X)), fail$'' hangs with the following database in XSB Prolog:
\myeqnbegin
        p(1).		\nonumber 	\\
        p(2).		\nonumber
\myeqnend
When we analyse the above query execution, we notice that the following 
Prolog query has a similar set of subgoals produced during execution:
\myeqnbegin
        ?- p(X),\; retract(p(X)),\; assert(p(X)),\; fail.	\nonumber
\myeqnend
The execution also hangs. The reason is that during the first evaluation of 
$p(X)$, $X$ is unified to 1. After the retraction of $p(1)$, the hash 
entry of $p(1)$ has been removed. Although $p(1)$ is asserted later during 
the backtracking, the hash table is changed. So, in the next unification, 
the program hangs due to an improper pointer. If $retract\_nr/1$ (which 
does not reclaim used space) is used in place of $retract/1$ in the above 
query, then the program goes into an infinite loop because $p(1)$ is put 
immediately back into the same place, which will then be retracted again 
(same result will be obtained if we replace $assert(p(X))$ by 
$assertz(p(X))$ ). The program does not notice that $X$ has already been 
unified to 1 and failed. Although we can use $asserta$ (add the clause in 
the argument to the database before any other clause for the same predicate 
currently in the database), it will revert the order of the database. For 
instance, the database contains $p(1)$ and $p(2)$, and $p(1)$ is located before $p(2)$.
The query \mbox{``$?- p(X),\; retract(p(X)),\; asserta(p(X)),\; fail$''} first unifies 
$X$ to 1, and retracts $p(1)$. Then, $p(1)$ is asserted (by $asserta(p(X))$)
before any other p-tuples currently in the database, i.e., before $p(2)$.
So, the order is still:
\myeqnbegin
                p(1). 	\nonumber	\\
                p(2).	\nonumber
\myeqnend
During the backtracking, $X$ is unified to 2, and $p(2)$ is retracted. Then, 
$p(2)$ is re-asserted before $p(1)$ by $asserta(p(X))$, i.e.,
\myeqnbegin
                p(2). 	\nonumber	\\
                p(1).	\nonumber	
\myeqnend
So, the order of p-tuples in the database is reversed. As mentioned before,
the execution of ``$?- del(p(X)),\; fail$'' results in the same set of 
subgoals as ``$p(X), retract(p(X)),$ \mbox{$assert(p(X)),\; fail$''}. This shows 
why the deletion predicate $del(X)$ is defined improperly in 
Section 4.3.1.

To solve this problem, we notice that if a query has multiple answers, 
backtracking can cause problems, because when undoing an update during
backtracking, the hash table can be corrupted. To overcome this, we never 
actually remove atoms from the database. Instead, we mark them as deleted, 
using delete tags. The insert tag and delete tag of a predicate 
$p(X_1,X_2, \ldots ,X_n)$ are defined by $i\_p(X_1,X_2,....,X_n)$ and 
$d\_p(X_1,X_2, \ldots ,X_n)$, respectively. The insert tag represents the 
existence of the predicate in the database, and the delete tag means the 
predicate has been deleted from database. So, a predicate is in the 
database if its insert tag is in the database, but its delete tag is not.
Similarly, a predicate is not in the database if both its insert tag and 
delete tag are in the database (i.e., it has been deleted), or neither of 
them are in the database, (i.e., it has never been inserted). Therefore, 
the insertion $ins\_p(X)$ of a predicate $p(X)$ is now defined by the 
following Prolog rules:
\myeqnbegin
ins\_p(X) & :- & not(i\_p(X)),\; ins(i\_p(X)).\\
ins\_p(X) & :- & i\_p(X),\; del(d\_p(X)). \\
       & &     {\normalsize\; where\; {\em ins}\; and\; {\em del}\; are\; 
		backtrackable\; updates\; as\; defined\; in\; 
		Section\; 4.3.1.}	\nonumber
\myeqnend
The first rule means that in the insert tag, $i\_p(X)$, is not in the database,
so the predicate has never been asserted, and we can assert the insert tag 
to represent that $p(X)$ is now in database. In the second rule, if the 
insert tag $i\_p(X)$ is in the database, then remove the delete tag 
$d\_p(X)$ from the database. In both cases, if the predicate $p(X)$ is 
successfully inserted, only $i\_p(X)$ and not $d\_p(X)$ is in the database.

Likewise, the deletion of $p(X)$ is defined as follows:
\myeqnbegin
del\_p(X) :- \; i\_p(X),\; ins(d\_p(X)).
\myeqnend
If a predicate has been inserted, its insert tags $i\_p(X)$ should be in the
database. To delete the predicate, we mark it by inserting the delete tag 
$d\_p(X)$ into the database. If the delete tag already exists, the predicate
has already been deleted, so the deletion fails.

As discussed above, a predicate is inserted if its insert tag but not its delete 
tag is in the database. So, $p(X)$ is defined by the rule:
\myeqnbegin
p(X) :-\; i\_p(X),\; not(d\_p(X)).
\myeqnend
For example, if $i\_p(1)$ and $i\_p(2)$ are in the database, and $d\_p(1)$ 
and $d\_p(2)$ are not, then $p(1)$ and $p(2)$ are true. Thus, the query 
``$?- del\_p(X),\; fail$'' executes, 
$i\_p(X)$ unifies $X$ to 1 and $d\_p(1)$ is asserted. During backtracking, 
$d\_p(1)$ is retracted. Then, $i\_p(X)$ unifies $X$ is to 2, and $d\_p(1)$ is
asserted and then retracted during backtracking. This execution does 
not hang because the hash table of $i\_p(X)$ is not changed during the 
execution. For the same reason, the order of answers to the query $p(X)$ 
is preserved.


\subsection{The Declare Statement (Key and Indexing)}

A key is a set of attributes that uniquely identifies a tuple.
Every predicate has a key, which may be, in two 
extremes, the functor name only, or the whole tuple.
In the former case, the relation contains one entry only, and the relation 
name uniquely identifies this entry. In the latter case, if any 
attribute is missing, then some tuples may be unable to identify.
Therefore, the only possible key is the whole tuple. For instance, in some of our later examples,
a predicate $count(X)$ is used to hold the current value of a counter. Since 
it has only one value at any given time, $count(X)$ is defined to have an 
empty key, and the predicate name itself uniquely identifies the value, $X$.
Similarly, suppose a predicate $edge(X,Y)$ means there is an edge from nodes 
$X$ to $Y$ in a graph. Since each vertex may have several edges, we cannot 
declare the predicate with the first argument as key only. Instead, the key 
consists of both $X$ and $Y$, i.e., the whole tuples.

Before any tuples are inserted into a table, the key information should first
be provided.This is the function of the declare statement. A declare 
statement consists of 3 parts: the predicate name and arity, the key 
specification and index information. Here is a general declare statement:
\myeqnbegin
declare {\em Name}/{\em N}\; [key\; {\em K}\; [size\; {\em M}\; index\; {\em L}]].
\myeqnend
The first part is the predicate specification, which consists of the 
predicate name Name, and arity of the predicate $N$. For instance, $p/2$ 
represents a predicate with name $p$ and arity 2, i.e., $p(X,Y)$. In the 
second part of a declaration statement, the number $K$ means that the first $K$ 
arguments of the predicate are the primary key. If $K$ is not given, then
by default, all the arguments form the primary key. The last part, index 
information is discussed later in this section.

During a declaration, the program first checks if a predicate with the 
same name and same number of arguments is already declared. It is not 
possible to have distinct predicates with same name and same number of 
arguments. However, predicates can have the same name and same key but 
different number of arguments. For instance, the two declarations $p/2\; 
key\; 1$ and $p/3\; key\; 1$ are allowed. A predicate is said to be in the 
database if both its key and the entry identified by the key, called the 
value of the key, are in the database. With the declaration $p/2\; key\; 
1$, the key of $p(X,Y)$ is denoted by $key\_2\_p(X)$, and the value is 
denoted by $value\_2\_p(X,Y)$. The number $2$ in the names of the key and 
value predicates is the number of arguments of the declared predicate 
$p(X,Y)$. With the above declaration, the following rule defining $p(X,Y)$ 
from these two predicates is added to the Prolog database:
\myeqnbegin
p(X,Y) :- key\_2\_p(X), value\_2\_p(X,Y).
\myeqnend
A predicate with same name, same key but different number of arguments can
also be declared. For instance, ``$declare\; p/3\; key\; 1$'' causes the following 
rule to be added to the Prolog database:
\myeqnbegin
p(X,Y,Z) :- key\_3\_p(X), value\_3\_p(X,Y,Z).
\myeqnend
The predicate $key\_3\_p(X)$ represents the key for $p(X,Y,Z)$, whereas 
$key\_2\_p(X)$ represents the key for $p(X,Y)$.

Thus, when there is a call to $p(a,Y)$, the system first checks if 
$key\_2\_p(a)$ is in the database. If so, it returns the unique value $Y$ 
identified by the predicate $value\_2\_p(a,Y)$. Thus, the insertion of a 
p-tuple is implemented as the insertion of two predicates: the key 
($key\_2\_p(X)$) and the value ($value\_2\_p(X,Y)$). 

The last part of a declare statement is the index information, i.e., 
$size\; M\; index\; L$. This part is also optional, so if it is not 
given, then no index is used for the predicate. The size $M$ is the 
size of the hash tables for the key and the value predicates. This is usually 
the number of ground atoms that will be inserted. The second part of the 
index information is the specification of secondary indexes, $L$. It has 
the same syntax and same meaning as index argument specifications 
in XSB Prolog. In general, $L$ can be an integer that indicates the 
argument on which to index, or a list of $IndexArg$. An $IndexArg$ is an 
integer or a sequence of integers separated by +, e.g., 1+2+3, which 
indicates that a single index is to be built using these combined arguments. 
As an example, ``$declare\; p/3\; key\; 2\; size\; 100\; index\; 
[1+2,2]$'' will construct two hash tables with 100 entries for the 
combination of the first and second argument of the key ($key\_3\_p(X,Y)$) 
and value ($value\_3\_p(X,Y,Z)$) predicates, and two other hash tables 
with 100 entries for the second argument of the key and value predicates, 
i.e., four hash tables in total. So, a call to $p/3$ will first check to see
 if both the first and second arguments are ground, and if so, use the index 
based on those arguments for the predicate $key\_3\_p(X,Y)$. Otherwise, it 
will see if the second argument is ground, and if so, use the index based on
it. Otherwise, it will use no index and search through all the clauses for
the predicate. 

By default, if an index field is not specified, indexes will be built on 
[$1+2+\ldots\ +k,\; 1+2+\ldots\ +(k-1) ,\; \ldots\; ,\; 1$]. So, 
``$declare\; p/4\; key\; 3\; size\; 100$'' is equivalent to 
``$declare\; p/4\; key\; 3\; size\; 100$ index [$1+2+3,\; 1+2,\; 1$]''.

Examples:
\begin{enumerate}
\item declare edge/2.
\item declare buffer/2 key 0.
\item declare account/3 key 2.
\item declare account/3 key 2 size 100.
\item declare account/3 key 2 size 100 index [1].
\end{enumerate}

Example 1 declares a predicate called $edge$ with 2 arguments, which together 
form the primary key. Therefore, $edge(v1,v2)$ and $edge(v1,v3)$ can both 
be stored in the database. This declare statement is equivalent to 
``$declare\; edge/2\; key\; 2$''. No indexes are created.

Example 2 declares a predicate called buffer with 2 arguments, with an empty 
key. So, $buffer(1,2)$ and $buffer(3,4)$ cannot appear in the database 
together. Since the tuple has only 1 entry, it needs no indexes.

Example 3 declares that a predicate account has 3 arguments, where the first 
two form a key. So, $account(John,savings,1000)$ and 
$account(John,checking,1000)$ can both reside in the database. However, 
the system cannot store both $account(John,savings,1000)$ and 
$account(John,savings,2000)$ in the database. Since the index information 
is not specified, no indexes are created.

Example 4 is similar to Example 3 except that it specifies hash tables of 
size 100 for the key and value predicates. Default indexes are built on 
$[1+2,1]$, i.e., an index on arguments 1 and 2 combined, and another index on 
argument 1.

Example 5 shows a user-defined index specification. It specifies hash 
tables of size 100 on the first argument of the key and value predicates.

\subsection{Key}

In Section 4.3.3, we discussed the use of insert and delete tags. The reason 
for using tags is to compensate for the loss of hash table entries during 
backtracking and to preserve the original order of facts in the Prolog 
database. If there is more than more than one choice for a unification, 
then we have to use the delete tag method. Otherwise, if there is only one 
possible unification, we can use the simple method of undoing updates 
described in {\em Rule\ 4.3} and {Rule\ 4.4}, because there is only 
one possible hash entry.

Consider the following example, in which, the predicate $distance/3$ is declared 
by \mbox{``$declare\; distance/3\; key\; 2$''}. The following rule is added according 
to Section 4.3.4:
\myeqnbegin
distance(X,Y,Z) :- key\_3\_distance(X,Y),\; value\_3\_distance(X,Y,Z).
\myeqnend
With the query, $?- distance(X,Y,Z)$, the subgoal $key\_3\_distance(X,Y)$ 
is evaluated. Suppose this subgoal binds $X$, $Y$ to $a$, $b$, then, 
$value\_3\_distance(a,b,Z)$ will unify $Z$ to $c$, for example, so
the tuple $distance(a,b,c)$ is finally returned. Since the key
uniquely identifies a tuple, there is only one possible binding for 
$value\_3\_distance(a,b,Z)$.
For this reason, we can use the simple undoing method, instead of the 
delete-tag method, for updating value predicates. On the other hand, queries on 
a key may have multiple answers, so we use the tag method for implementing
key predicates.

Section 4.3.3 showed that when a predicate is updated by the tag method, the 
predicate is not stored directly in the Prolog database. Instead, it 
becomes a defined predicate, and its insert and delete tags are base 
predicates. Therefore, the key predicate, e.g., 
$key\_3\_distance(X,Y)$,  is defined in terms of tags,
\myeqnbegin
key\_3\_distance(X,Y)\; :-\; i\_key\_3\_distance(X,Y),\; not(d\_key\_3\_distance(X,Y)).
\myeqnend
So, if the tuple $distance(a,b,1)$ is in the \TR database, then 
$i\_key\_3\_distance(a,b)$ and $value\_3\_distance(a,b,1)$, but not 
$d\_key\_3\_distance(a,b)$, are in the Prolog database. 

\subsubsection{Updates to Non-key Attributes:}
In transaction programs, updates often occur on non-key attributes, 
e.g., changes to the balance of bank account, or to the state of an object. 
Without keys, the whole tuple would have to use the tag method. So, a 
change in just one argument would require the insertion of a delete tag 
followed by the insertion of a new insert tag. With keys, a change in the 
non-key arguments results in a retraction of the value predicate and an 
assertion of the new value predicate. So, without using keys, the
database will contain two more predicates (a delete tag of old tuple and an
insert tag of new tuple) after such update. However, database contains
same number of predicates after the update if keys are used.
For the same reason, the key should be carefully 
selected. For example, if the $distance2$ predicate is declared with 3 key 
arguments, then the declaration generates the following Prolog rules:
\myeqnbegin
distance2(X,Y,Z) & :- & key\_distance2(X,Y,Z).\\
key\_distance2(X,Y,Z) & :- & i\_key\_3\_distance2(X,Y,Z), 	\nonumber \\ 
			& &	not(d\_key\_3\_distance2(X,Y,Z)).
\myeqnend
This is an optimization: since the whole tuple of $distance2$ is the key, 
the value predicate is redundant and can be discarded.

Compare the predicates $distance$ and $distance2$ again. Suppose both 
$distance(a,b,1)$ and $distance2(a,b,1)$ are in the database. Intuitively, 
each atom means that the distance from a to b is 1. We increase the 
distance from 1 to 1000 stepwise. For the predicate distance, at each step, 
$value\_3\_distance(a,b,N)$ is retracted and the new predicate 
$value\_3\_distance(a,b,N+1)$ is asserted. So, after 1000 steps, the 
database contains the atoms $i\_key\_3\_distance(a,b)$ and 
$value\_3\_distance(a,b,1000)$ to indicate the new distance. However, for 
the predicate $distance2$, at each step, $d\_key\_3\_distance2(a,b,N)$ and 
$i\_key\_3\_distance2(a,b,N+1)$ are asserted. So, after 1000 steps 
for both predicates, the database contains:
\mycolbegin
tabbing \= iikeyi3idistance2(a,b,1).loooooonger \=  dikeyi3idistance2(a,b,1). \kill
\> $i\_key\_3\_distance(a,b).$ \> $value\_3\_distance(a,b,1000).$ \\
\> $i\_key\_3\_distance2(a,b,1).$ \> $d\_key\_3\_distance2(a,b,1).$ \\
\> $i\_key\_3\_distance2(a,b,2).$ \> $d\_key\_3\_distance2(a,b,2).$ \\
\> \hspace{1.0in}  \vdots \\
\> \hspace{1.0in}  \vdots \\
\> $i\_key\_3\_distance2(a,b,998).$ \> $d\_key\_3\_distance2(a,b,998).$ \\
\> $i\_key\_3\_distance2(a,b,999).$ \> $d\_key\_3\_distance2(a,b,999).$ \\
\> $i\_key\_3\_distance2(a,b,1000).$
\mycolend
In the above example, there are two reasons to favour the declaration of 
$distance$ over $distance2$. Too see this, suppose that $distance2$ is used. 
Then, after execution, the database contains 999 pairs of insert and delete 
tags for the $key\_3\_distance2$ predicate, needlessly consuming space. 
In addition, if there is a query on $key\_3\_distance2(a,b,N)$, 
the subgoal $i\_key\_3\_distance2(a,b,N)$ will 
bind $N$ to 1 followed by the failure of the next subgoal 
$not(d\_key\_3\_distance2(a,b,N))$. The execution will backtrack to 
bind $N$ to 2, 3, etc., until $N$ is 1000, where the binding succeeds. 
On the other hand, the query $key\_3\_distance(a,b,N)$ needs only two 
steps: verifying that $i\_key\_3\_distance(a,b)$ is true, and retrieving
$value\_3\_distance(a,b,1000)$ from database. Needless to say, the 
latter requires less search time.

A drawback of breaking a predicate into separate key and value predicates
is that an insertion or deletion of a tuple requires updates to two 
predicates instead of one. Therefore, if there is a lot of creation 
and deletion of tuples, then we have to pay for it in terms of the extra
updates on value predicates.

As discussed in the previous section, if a predicate is declared with 
index information, then the key and the value predicate will indexed 
accordingly. Since the key predicate is not a base predicate, the index 
information is transferred to its tag predicates which are base. For 
instance, ``$declare\; distance/3\; key\; 2\; size\; 100\; index\; [1]$'' 
puts indexes on the first argument of $i\_key\_3\_distance/2$, 
$d\_key\_3\_distance/2$, and $value\_3\_distance/3$. 

\subsection{Create, Destroy and Set}

In our implementation, three basic operations for a database tuple are 
{\em create}, {\em destroy}, and {\em set}. The predicate {\em create} 
inserts a tuple with a new key value. Similarly, {\em destroy} deletes the 
tuple; and, {\em set} changes the value of an existing tuple. The {\em set} operation 
is allowed only when the key already exists in the database. As 
discussed in Section 4.3.4 about vis-a-vis
{\em declare}, predicates involving these operations should be preceded 
by the declare statement first.

For example, suppose $p/2$ is declared with the first argument is the key. 
Then,
\begin{itemize}
\item The operation $create(p(1,2))$ inserts a tuple $p(1,2)$ with $p(1)$ 
	as the key. Thus, $i\_key\_2\_p(1)$ and $value\_2\_p(1,2)$ are 
	asserted. 
\item The operation $destroy(p(1,2))$ effectively removes the atom $p(1,2)$ 
	by asserting \\ $d\_key\_2\_p(1)$ and retracting $value\_2\_p(1,2)$.
\item The operation $set(p(1,3))$ changes the value of the atom 
	with key $p(1)$ to 3. If the atom with key $p(1)$ originally had
	the value 2, then the operation retracts $value\_2\_p(1,2)$ and asserts 
	$value\_2\_p(1,3)$. In this way, instead of destroying the whole 
	tuple and re-creating a new one, we can use the $set$ operator to 
	modify the non-key attributes.
\end{itemize}

Each key has only one corresponding value. So, the operator {\em create} 
should check whether a tuple with same key has been previously created. If it 
has, the {\em create} operation fails. Also, consider the operator 
{\em set}. If the whole tuple is a key, then the {\em set} operation is 
invalid because there is no value to set.

\subsection{Bulk Updates}

A feature of database languages is the ability to perform bulk 
updates. For example, inserting a set of tuples from one relation into another
is a basic SQL operation. However, in most logic programming 
languages, such operations are not defined. The reason is that, unlike SQL 
operations, most logical formulations of updates are based on the 
insertion and deletion of single tuples.

In order to capture such behavior, we shall define an elementary transition 
that performs bulk updates. An example of the use of relational assignments, 
which copy the contents of one relation to another, was shown in Section 3.3.

A bulk update formula usually consists of two parts: a source formula ($S$), 
and a destination predicate ($D$). A source formula is a database query
which sets up the conditions for update, i.e., a tuple is update if $S$ is true.
The destination predicate is a database predicate where the update takes place.
Also, the predicate should have been declared (like $create/1$, $destroy/1$, etc.)
So, if $S$ is a database query and $D$ is a declared database
predicate, then the following defines three types of bulk updates: bulk insert
, bulk delete, and bulk assignment:
\begin{enumerate}
\item Bulk Insert ($bulk\_ins(S,D)$) \\
	All tuples from $D$ that satisfies condition $S$ are inserted, and
 	if a variable is not bound when the bulk insertion takes place,
	it is considered to be a free variable if it is not specified in $S$.
	For instance, $bulk\_ins(p(X,Y),q(X))$ means for every
	value $X$, if $\exists Y\ p(X,Y)$ is true in the database, then
	insert $q(X)$.\\

        {\em Examples}: The following shows the database before and after a
	bulk insert, where the declarations of $p$, $q$, $r$ are: 
	$p/2\; key\; 2$, $q/1\; key\; 1$, and $r/2\; key\; 1$:
	\begin{tabbing}
	1.....\= Database Before:longerer \= p(1,1), p(2,2), q(3) \kill
        1. \> Database Before: \> $p(1,1),\; p(2,2),\; q(3).$ \\
           \> Execution: \>       $bulk\_ins( p(X,Y), q(X) )$ \\
           \> Database After:  \> $p(1,1),\; p(2,2),\; q(1),\; q(2),\; q(3)$. \\
           \> With X bound to 1 and 2, q(1), q(2) are inserted. \\
	\\
        2. \> Database Before: \> $p(1,1),\; p(2,2),\; q(3)$ \\
           \> Execution:   \>     $bulk\_ins( p(X,2), q(X) )$ \\
           \> Database After:  \> $p(1,1),\; p(2,2),\; q(2),\; q(3)$ \\
           \> Only $p(2,2)$ satisfies the source condition and so $q(2)$ 
		is inserted. \\
	\\
        3. \> Database Before: \> $p(1,1),\; p(1,2),\; q(3)$ \\
           \> Execution:  \>      $bulk\_ins( p(X,Y), q(X) )$ \\
           \> Database After:  \> $p(1,1),\; p(1,2),\; q(1),\; q(3)$ \\
           \> Atoms $p(1,1)$, $p(1,2)$ bound $X$ to 1, and $q(1)$ is 
		inserted. Duplicated entry of \\	
	   \> $q(1)$ is discarded. \\
	\\
        4. \> Database Before: \> $p(1,1),\; p(1,2),\; p(2,2),\; q(1),\; r(3,3)$ \\
           \> Execution: \>       $bulk\_ins( (p(X,Y), q(X)), r(X,Y) )$ \\
           \> Database After:  \> $p(1,1),\; p(1,2),\; p(2,2),\; q(1),\;  r(1,1),\; 
				r(3,3).$ \\
           \> The evaluation of the source query, $( p(X,Y), q(X) )$, 
		returns $X=1$, $Y=1$, and \\
	   \> $X=1$, $Y=2$, so, $r(1,1)$, $r(1,2)$ can be added to 
		the database. However, \\
	   \> since the first argument of $r$ is the key, only one of 
		$r(1,1)$ or $r(1,2)$, \\
	   \> is added into database non-deterministically. In this case, 
		$r(1,1)$ is added. \\
	\\
        5. \> Database Before: \> $p(1,2),\; p(2,3),\; q(2)$ \\
           \> Execution:  \>      $bulk\_ins( (p(X,Y), q(X)), q(Y) )$ \\
           \> Database After:  \> $p(1,2),\; p(2,3),\; q(2),\; q(3)$ \\
           \> The evaluation of $( p(X,Y), q(X) )$, returns $X=2$, $Y=3$,
		so, q(3) is added \\
	   \> to the database. \\
	\\
	6. \> Database Before: \> $p(1,1),\; p(2,2),\; q(2),\; r(3,3)$ \\
	   \> Execution: \>	  $q(X)\; sc\; bulk\_ins(p(X,Y),r(X,Y))$ \\
	   \> Database After:  \> $p(1,1),\; p(2,2),\; q(2),\; r(2,2),\; r(3,3)$ \\
	   \> The binding of $X$ to 2 affects the bulk insert. So, only
		r(2,2) is added \\
	   \> to the database. \\
	\\
	7. \> Database Before: \> $p(1,1),\; p(2,2),\; q(2),\; r(3,3)$ \\
	   \> Execution: \>	  $bulk\_ins(p(X,Y),r(X,Y))\; sc\; q(X)$ \\
	   \> Database After:  \> $p(1,1),\; p(2,2),\; q(2),\; r(1,1),\; r(2,2),\; r(3,3)$ \\
	   \> Although the execution returns $X$ to 2, the binding of $X$
		after the bulk insert \\
	   \> does not affect the previous operation. So, both $r(1,1)$ and
		$r(2,2)$ are added. \\
	\end{tabbing}

\item Bulk Delete ($bulk\_del(D)$) \\
        All tuples satisfying $D$ are deleted. For instance, 
	$bulk\_del(p(X,Y))$ deletes all tuples of the form $p(X,Y)$.

        {\em Examples}: The predicate $p(X,Y)$ is declared as p/2 key 1.
	\begin{tabbing}
	1.....\= Database Before:longerer \= p(1,1), p(2,2), q(3) \kill
        1. \> Database Before: \> $p(1,1),\; p(2,2)$ \\
           \> Execution:   \>     $bulk\_del(p(X,Y))$ \\
           \> Database After:  \> (No $p/2$ tuples) \\
           \> All tuples of the form $p(X,Y)$ are deleted. \\
	\\
        2. \> Database Before: \> $p(1,1),\; p(2,1),\; p(3,3)$ \\
           \> Execution:    \>    $bulk\_del(p(X,1))$ \\
           \> Database After:  \> $p(3,3)$ \\
           \> All tuples of the form $p(X,1)$ are deleted from database, 
		i.e., $p(1,1)$, $p(2,1)$. \\
	\end{tabbing}

\item Bulk Assignment ($D\; :=\; S$) \\
        All tuples from $D$ are overwritten by those satisfying the 
	condition $S$. Again, variables specified in $S$ but not in $D$ are 
	considered to be free variables. For instance, \mbox{$q(X)\; :=\; p(X,Y)$} 
	selects the first elements of $p(X,Y)$ and put them into the 
	predicate $q(X)$. It is similar to $bulk\_del(q(X))$ followed by 
	$bulk\_ins(p(X,Y),q(X))$. 

        {\em Examples}: The following shows the database before and after 
	an assignment. Note the difference between bulk insert and bulk 
	assignment. In the former case, any tuple in the source predicate 
	remains in the database, while in the latter case, all tuples initially 
	in source predicate are deleted.
	\begin{tabbing}
	1.....\= Database Before:longerer \= p(1,1), p(2,2), q(3) \kill
        1. \> Database Before: \> $p(1,1),\; p(2,2),\; q(3).$ \\
           \> Execution:    \>    $q(X)\; :=\; p(X,Y)$ \\
           \> Database After:  \> $p(1,1),\; p(2,2),\; q(1),\; q(2)$ \\
           \> With $X$ bound to 1 and 2, $q(1)$, $q(2)$ are in the database 
		after the assignment. \\
	   \> Note the difference with bulk insert, where $q(3)$ remained in 
		the database after \\
	   \> the update.\\
	\\
        2. \> Database Before: \> $p(1,1),\; p(2,2),\; q(3)$ \\
           \> Execution:    \>    $q(X)\; := p(X,2)$ \\
           \> Database After:  \> $p(1,1),\; p(2,2),\; q(2)$ \\
           \> Only $p(2,2)$ satisfies the source condition, i.e., $q(X)$ was 
		deleted so the \\
	   \> predicate $q$ has extent $q(2)$ in the final database state. \\
	\\
        3. \> Database Before: \> $p(1,1),\; p(1,2),\; q(3)$ \\
           \> Execution:   \>     $q(X)\; :=\; p(X,Y)$ \\
           \> Database After:  \> $p(1,1),\; p(1,2),\; q(1)$ \\
           \> Atoms $p(1,1)$, $p(1,2)$ bind $X$ to 1, so $q(1)$ is in new 
		the database state.  \\
	   \> Duplicated entry of $q(1)$ has been discarded. \\
	\\
        4. \> Database Before: \> $p(1,1),\; p(1,2),\; p(2,2),\; q(1),\; r(3,3)$ \\
           \> Execution:    \>    $r(X,Y)\; :=\; ( p(X,Y), q(X) )$ \\
           \> Database After:  \> $p(1,1),\; p(1,2),\; p(2,2),\; q(1),\; r(1,1)$ \\
           \> The evaluation of the source query, $( p(X,Y), q(X) )$, 
		returns $X=1$, $Y=1$, and \\ 
	   \> $X=1$, $Y=2$, so, $r(1,1)$, $r(1,2)$ can be added to 
		the database. However, \\
	   \> since the first argument of $r$ is the key, only one of 
		$r(1,1)$ or $r(1,2)$ is \\
	   \> added to database non-deterministically. In this 
		case, $r(1,1)$ is added. \\
	\\
        5. \> Database Before: \> $p(1,2),\; p(2,3),\; q(2)$ \\
           \> Execution:   \>     $q(Y)\; :=\; p(X,Y),\; q(X)$ \\
           \> Database After:  \> $p(1,2),\; p(2,3),\; q(3)$ \\
           \> The evaluation of $( p(X,Y), q(X) )$, returns $X=2$, $Y=3$, 
		and $q(3)$ is added to \\
	   \> the database. Note that $q(2)$ is no longer in 
		the database after the bulk update.\\
	\\
	6. \> Database Before: \> $p(1,1),\; p(2,2),\; q(2),\; r(3,3)$ \\
	   \> Execution: \>	  $q(X)\; sc\; r(X,Y)\; :=\; p(X,Y)$ \\
	   \> Database After:  \> $p(1,1),\; p(2,2),\; q(2),\; r(2,2)$ \\
	   \> The binding of $X$ to 2 affects the bulk insert. So, only
		r(2,2) is added \\
	   \> to the database. \\
	\\
	7. \> Database Before: \> $p(1,1),\; p(2,2),\; q(2),\; r(3,3)$ \\
	   \> Execution: \>	  $r(X,Y)\; :=\; p(X,Y)\; sc\; q(X)$ \\
	   \> Database After:  \> $p(1,1),\; p(2,2),\; q(2),\; r(1,1),\; r(2,2)$ \\
	   \> Although the execution returns $X$ to 2, the binding of $X$
		after the bulk insert \\
	   \> does not affect the previous operation. So, both $r(1,1)$ and
		$r(2,2)$ are added. \\
	\end{tabbing}
\end{enumerate}

\subsection{Loops}

In most logic programming languages, only recursive rules are allowed.
Implementation of iterative loops is provided by procedural languages only. 
Since \TR is a blend of declarative and procedural programming languages, we 
can include {\em while-loop} and {\em for-loop} implementations in the 
language.

Here is the general syntax of while-loops and for-loops:
\begin{tabbing}
tabbingg \= withhh \= where \kill
\> [with {\em VList}] while {\em Cond} do {\em Body} \\
\> [with {\em VList}] forall {\em Vars} in {\em Cond} do {\em Body} \\
\>   where \>   {\em Cond} is a database query,called the loop condition, \\
\>   and   \>   {\em Body} is a transaction formula,called the loop body, \\
\>   and   \>   {\em VList} and {\em Vars} are lists of variables. 
\end{tabbing}
The optional prefix ``with {\em VList}'' is used when passing the bindings of 
variables into the loop or out from the loop, including those variables which
are bound before the loop. Variables in {\em VList} are 
considered to have constant values during loop iteration. Examples are
shown later in this section. 

\subsubsection{While Loops:}

A while-statement consists of two parts: loop condition, and loop body. 
It repeatedly executes the {\em Body}. The iteration finishes when the 
loop condition fails. At each iteration, any variables in the loop 
condition may be bound to particular values, and these values are 
passed into the loop body and used there. For example, ``$while\; p(X)\; do\;
destroy(p(X))$'' picks a value of $X$ at each iteration and removes the 
tuple $p(X)$ from database. It is interesting to notice that the execution 
of a while-loop may be non-deterministic.

\begin{tabbing}
{\em Examples}: \\
1.....\= Database Before:longerer \= p(1,1), p(2,2), q(3) \kill
1.  \>  Database Before: \> $p(1,1),\; p(2,2),\; p(3,3)$ \\
    \>  Execution:    \>    $Y = 2\; sc\; while\; p(X,Y)\; do\; destroy(p(X,Y)).$ \\
    \>  Database After: \>  $(No\; p(X,Y)\; tuples)$ \\
    \>  With specifying ``$with [Y]$'' as prefix of the while loop,
	the binding, $Y = 2$, \\
    \>	does not pass into the loop, the iteration may remove  $p(1,1)$ 
 	in the first iteration, \\
    \>	$p(2,2)$ in the next iteration, so that all $p(X,Y)$ tuples are destroyed. \\
\\
2.  \>  Database Before: \> $p(1,1),\; p(2,2),\; p(3,3)$ \\
    \>  Execution:    \>    $Y = 2\; sc\; with\; [Y]\; while\; p(X,Y)\; do\; destroy(p(X,Y))$ \\
    \>  Database After: \>  $p(1,1), p(3,3)$ \\
    \>  The execution destroys all $p(X,2)$ tuples, i.e., $p(2,2)$ only, 
	because the binding of \\
    \>  $Y$ passes into the loop by using the prefix ``with [Y]'' in the while-loop.\\
\\
3.  \>  Database Before: \> $p(1,1),\; p(2,2),\; p(3,3)$ \\
    \>  Execution:    \>    $while\; p(2,2)\; do\; destroy(p(X,Y))$ \\
    \>  The execution is non-deterministic because the loop condition only 
	states that $p(2,2)$ \\
    \>  is false at the end of the loop. The execution may destroy $p(2,2)$ 
	immediately in the \\
    \>  first iteration, leaving $p(1,1)$ and $p(3,3)$ in the database; or 
	at the other extreme, it \\
    \>  may destroy $p(1,1)$ first, then $p(3,3)$, and finally $p(2,2)$. In 
	this case, all $p(X,Y)$ \\
    \>  tuples are removed. \\
\\
4.  \>  Database Before: \> $p(1,1),\; p(2,2),\; p(3,3)$ \\
    \>  Execution:      \>  $with\; [X,Y]\; while\; p(X,Y)\; do\; destroy(p(X,Y))$ \\
    \>  This example is not too useful but worth to remember. In this case, 
	the value of $X$, \\
    \> 	$Y$ are bound in the first iteration. Suppose, $X$ and $Y$ unify to 1 
	in the first iteration, \\
    \>  only $p(1,1)$ is deleted in the iteration and the 
	database after iteration will contain  \\
    \>  $p(2,2)$ and $p(3,3)$. \\
\end{tabbing}

\subsubsection{For Loops:}

A for-statement consists of three parts: variable list, 
loop condition, and loop body. Each set of variables in {\em Vars}
that satisfies the loop condition {\em Cond} are used in each loop 
iteration. So, the number of iterations is fixed when the iteration 
starts.

\begin{tabbing}
{\em Examples}: \\
1.....\= Database Before:longerer \= p(1,1), p(2,2), q(3) \kill
1. \>   Database Before: \> $p(1,1),\; p(2,2)$ \\
   \>   Execution:     \>   $Y = 2\; sc\; forall\; [X]\; in\; p(X,Y)\; do\; create(q(X)).$ \\
   \>   Database After:  \> $p(1,1),\; p(2,2),\; q(1),\; q(2)$ \\
   \>   The loop first determines a set of values $[1,2]$ for $X$, from 
	$p(X,Y)$, and from this set, \\
   \> 	it creates $q(X)$ at each iteration. \\
\\
2. \>   Database Before: \> $p(1,1),\; p(2,2)$ \\
   \>   Execution:     \>   $Y = 2\; sc\; with\; [Y]\; forall\; [X]\; in\; p(X,Y)\; do\; create(q(X))$. \\
   \>   Database After: \>  $p(1,1),\; p(2,2),\; q(2)$ \\
   \>   $Y$ is bound to 2, so only $X = 2$ is chosen for iteration. \\
\\
3. \>   Database Before: \> $p(1,1),\; p(1,2)$ \\
   \>   Execution:      \>  $forall\; [X]\; in\; p(X,Y)\; do\; create(q(X))$ \\
   \>   Database After:  \> $p(1,1),\; p(1,2),\; q(1)$ \\
   \>   Although two tuples, $p(1,1)$ and $p(1,2)$ bind $X$ to 1, the 
	loop iterates only once.\\
   \>	If not, the iteration would fail because after $q(1)$ is created 
	in the first iteration, \\
   \>   $create(q(1))$ in the second iteration would fail. \\
\end{tabbing}

While-loops and for-loops cannot be translated into simple Prolog goals. 
Instead, they are translated into recursive rules together with a predicate 
to start the recursion. For example:

\begin{enumerate}
\item $with\; [X]\; forall\; [Y]\; in\; p(Y)\; do\; create(q(X,Y))\;$ \\
      is translated into \\
      $temp(Y)\; :=\; p(Y),\; loop1(X)$ \\
      and the following rules are created \\
      $loop1(X)\; :-\; destroy(temp(Y)),\; create(q(X,Y)),\; loop1(X).$ \\
      $loop1(X)\; :-\; not(temp(Y))$.
\item $while\; alpha\; do\; body$ \\
      is translated into \\
      $loop1$ \\
      and the following rules are created \\
      $loop1\; :-\; alpha,\; body,\; loop$ \\
      $loop1\; :-\; not(alpha)$
\end{enumerate}

Note that loop conditions are database queries which are applied to 
the database only, not including the transaction base.

\subsection{If-then-else}

The if-then-else statement provides branch selection 
within a transaction formula. The general structure of an if-then-else 
statement is: if {\em Cond} then {\em F1} else {\em F2}, where {\em Cond} is 
a database clause, and {\em F1} and {\em F2} are transaction formulas. 
Intuitively, it means that if {\em Cond} is true, then execute {\em F1}, 
otherwise execute {\em F2}. In other word, if {\em Cond} is true, execute 
{\em F1}, and if {\em Cond} is false, execute {\em F2}. The simplest way to 
translate the statement into \TR is to define a predicate {\em if(C,T,E)} as 
follows:
\myeqnbegin
if(C,T,E) & :- & call(C), call(T). \\
if(C,T,E) & :- & not(C), call(E). 
\myeqnend
So, a transaction ``$if\; Cond\; then\; F1\; else\; F2$'' can be translated 
into ``$if(Cond,T,E)$'' where $T$ and $E$ are Prolog interpretations of $F1$ 
and $F2$, respectively. For instance, $if\; p(1)\; then\; (q1\; sc\; q2)\; 
else\; (r1\; sc\; r2))$ can be translated into $if( p(1),\; (q1,\;q2),\; 
(r1,\;r2) )$.

One might want to define this predicate with cut as follows:
\myeqnbegin
if(C,T,E) & :- & call(C), !, call(T) \\
         & &     ;  		\nonumber	\\
         & &     call(E).	\nonumber
\myeqnend
However, if {\em T} fails, it would be impossible to backtrack to {\em C}
again, and then some other bindings of variables in {\em C} that cause {\em T}
success may be missed. For example, suppose the 
database contains: $p(1)$, $p(2)$, $q(2)$, and the transaction 
``\mbox{$if\; p(X)\; then\; destroy(q(X))\; else\; true$}'' is translated into 
``\mbox{$if(p(X),\; destroy(q(X)),\; true)$}''. 
Using the first definition of $if/3$, $p(X)$ binds $X$ to 1. However, 
in the next subgoal, $destroy(q(1))$ fails. In the backtracking $p(X)$ binds 
$X$ to 2, and the execution succeeds by removing tuple $q(2)$ from the 
database. On the other hand, if the second definition is used, since the 
cut(!) in the definition disallows the backtracking to $p(X)$, 
the execution fails.

\subsection{Query and Cleanup}

Before a transaction formula is executed, it passes through a parser and 
is translated into a set of a Prolog subgoals. The directive {\em trans/1} 
is a prefix operator defined as an interface for transaction query. To 
perform a transaction $\phi$,  
executes the query ``$trans\; \phi$''  in Prolog prompt. For instance, 
$trans\; create(p(1))\; sc\; create(p(2))$ creates tuples $p(1)$ and $p(2)$, 
but $trans(create(p(1)),\; create(p(2)))$ fails because 
$( create(p(1)),\; create(p(2)) )$ is not a transaction formula. 

The execution of {\em trans} consists of five parts: cleanup, parsing and 
translation, activation of transaction rules, execution of the transaction, 
and deactivation of transaction rules. 

During the translation phase, a transaction query like $trans(p(X)\; sc\; 
create(q(X)) )$ will be translated into the prolog query $p(X),\; 
create(q(X))$. Rules may also be created during the translation for the 
extra facilities provided by \TRR. For example, 
$trans\; while\; p(X)\; do\;$ $destroy(p(X))$ may be translated into 
{\em loop1} where a new rule defining {\em loop1} is asserted to the 
database, as explained in Section 4.3.8. 

As described in Section 4.3.3, although the tag method can solve the 
problems of updates during backtracking, it increases the consumption of 
database space significantly, especially if tuples are repeatedly created 
and destroyed over and over again. Since tuples with both an insert tag and a 
delete tag are regarded as non-existent in the database, both tags can be 
removed from the database after execution. This is the job of the 
cleanup phase. Similarly, temporary rules added in previous transaction
queries, such as $loop1$ in the above example, are removed 
to release program space. Therefore, the cleanup phase has two parts: the 
removal of insert tags and delete tags, and the removal of rules created in 
previous transactions. It is carried out before a transaction is 
executed, and it releases space used by the previous transaction. Since 
Prolog allows users to backtrack after a query succeeds, if the cleanup 
phase takes place after executing the query, the cleanup phase itself may 
have to backtrack. For instance, suppose the database contains $p(1)$, $p(2)$, 
and the query $trans\; p(X)$ returns $X = 1$. At this point, users can 
backtrack to find the second answer, $X = 2$. If the cleanup phase took 
place after the transaction executes, then during such kind of backtracking, 
any rule or tag, which has been deleted in the cleanup phase, should 
be re-asserted again. Otherwise, the database is inconsistent during
the backtracking. 

As shown in Section 4.3.1, transaction rules are enabled by asserting the 
atom ``$tr$'' to the Prolog database, and can be disabled by retracting it. 
So, before executing the translated subgoals, the atom ``$tr$'' is asserted 
during the activation stage. After the execution stage, the atom is retracted 
during the deactivation stage.

\section{Prototypes}

We have implemented four different \TR prototypes. In all prototypes, 
predicate declaration is a way of building a transaction base. Each 
prototype has its own features, and tests different implementation 
architectures. Prototypes 1, 2, and 3 are very similar, with the former 
being conceptual, and the latter being practical. In general, 
Prototype 1 is the slowest but simplest, and Prototype 3 is the 
fastest. Prototype 4 is a non-backtrackable version of Prototype 3 that 
optimizes the performance for problems that do not require backtracking.

\subsection{Prototype 1}

In each prototype, during the declaration of a predicate, rules are asserted 
to the Prolog database. Prototype 1 provides a simple conceptual 
implementation of \TRR. During the declaration of predicates, only one 
special rule which defines the predicate with its key is added 
to the database. Since the emphasis is on conceptual simplicity, no 
optimization is performed. For example, when the following database 
predicate is declared, only one rule is added, as follows:
\mycolbegin
tabbing \= decla \= finish  \kill
\> $declare\; p/2\; key\; 1$. \\
\>  \> $\downarrow$ \\
\> $p(X,Y)\; :-\; key(p(X),2),\; val(p(X),[Y],2)$.
\mycolend
Rather than using particular key and value predicates for each newly 
declared predicate, two general predicates $key/2$ and $val/3$ are 
defined for storing keys and values, respectively. With the general predicate 
$key(X,N)$, $X$ is a function term representing key value of a predicate of
arity $N$. For example, $key(p(X),2)$ is a key for $p/2$, and $key(q(X,Y),5)$
is a key for $q/5$. Likewise, in the general predicate 
$val(X,Y,N)$, $X$ is a function term representing a key value of a predicate.
$Y$ is a list which stores the remaining values of the predicate, and $N$ is 
the arity of the predicate. For example, the value predicates of
above example are $value(p(X),[Y],2)$ and $value(q(X,Y),[A,B,C],5)$, 
respectively.

As discussed in section 4.3.3, the key of a tuple is stored using tags.
Therefore, the key predicate $key(X,Y)$ is not stored as a base predicate in 
Prolog. Instead, there is a general rule defining $key/2$ in terms of its 
tags:
\myeqnbegin
        key(X,N) & :- & i\_key(X,N),\; not(d\_key(X,N)).
\myeqnend
So, with the above declaration, the atom $p(1,1)$ is stored as 
$i\_key(p(1),2)$, $val(p(1),[1],2)$ in database, and $p(2,2)$ is 
stored as $i\_key(p(2),2)$, $val(p(2),[2],2)$ in database.

In Prolog, if the indexed argument is a predicate, then the name of the 
predicate is used for indexing. So, Prolog indexes the key on the predicate
name, which is almost equivalent to no indexing because tuples are
exhaustively searched in access time.

For this reason, access to the base predicates, $i\_key(X,Y)$, 
$d\_key(X,Y)$, and \mbox{$val(X,Y,Z)$}, requires an exhaustive search of the 
database, so search times 
are proportional to the number of predicates in the database. This linear 
search time for predicates explains why Prototype 1 is the slowest of the 
four. Since Prototype 1 is extremely slow, it is only 
suitable for small databases. Also, since there is effectively no indexing in 
Prototype 1, the index information in a declare statement has no effect.

Since this prototype is conceptual only, it does not 
have any optimization. The most noticeable example is when all arguments of a
predicate are the primary key. For example:
\vspace{3mm}
\begin{small}
\begin{tabbing}
tabbing \= decla \= finish  \kill
\> $declare\; p/2\; key\; 2.\; $      (or $\; declare\; p/2.$ ) \\
\> \> 	$\downarrow$ \\
\> $p(X,Y)\; :-\; key(p(X,Y),2),\; val(p(X,Y),[],2)$.
\end{tabbing}
\end{small}
\vspace{3mm}
Since the value predicate does not contain any extra information, it 
can be omitted from the rule, thus preventing a needless search of the
entire database. Such optimization will be performed in later prototypes.

\subsection{Prototype 2}

Unlike Prototype 1, Prototype 2 allows user-defined indexing on database 
tuples. Prototype 2 is a transition prototype between the 
conceptual version (Prototype 1) and the practical version (Prototype 3). 
It performs many runtime computations, as well as a little optimization 
on predicate definition. 

In this prototype, each predicate has its own key predicate, which means 
that the predicate declaration also creates a rule for 
for accessing its corresponding key tags. During declaration, 
rules for the predicate and its key are created, as in the following 
examples,
\vspace{3mm}
\begin{small}
\begin{tabbing}
tabbing \= decla \= finish  \kill
\> $declare\; p/2\; key\; 1. $ \\
\> \>   $\downarrow$ \\
\> $p(X,Y)\; :-\; key\_2\_p(X),\; val\_2\_p(X,Y).$ \\
\> $key\_2\_p(X) :-\; i\_key\_2\_p(X), not(d\_key\_2\_p(X)).$ \\
\\
\> $declare\; q/2.$ \\
\> \>   $\downarrow$ \\
\> $q(X,Y)\; :-\; key\_2\_q(X,Y).$ \\
\> $key\_2\_q(X,Y)\; :-\; i\_key\_2\_q(X,Y),\; not(d\_key\_2\_q(X,Y)).$ 
\end{tabbing}
\end{small}
\vspace{3mm}
As described in Section 4.3.4, if the declare statement contains index 
information, then the tags (e.g., $i\_key\_2\_p(X)$, $d\_key\_2\_p(X)$,
$i\_key\_2\_q(X,Y)$, and $d\_key\_2\_q(X,Y)$ ) and the value predicate 
(e.g., $val\_2\_p(X,Y)$ ) are indexed accordingly, and this can improve the 
access time to predicates.

Unlike Prototype 1, simple optimizations are implemented in this prototype.
If the whole tuple is the key, then the value field is unnecessary, so 
there is no need to include the value predicate in the predicate definition 
rule, i.e., $q(X,Y)\; :-\; key\_2\_q(X,Y).$ in above example. 
The removal of the value predicate in this case reduces the search 
time of the tuple but, of course, such optimization has no effect if the 
key a proper subset of the arguments, such as the above example for
$p/2\; key\; 1$.

For instance, consider the above example. To insert $p(1,2)$ into 
database, in Prototype 1, $i\_key(p(1),2)$ and $value(p(1),[2],2)$ are 
inserted into database. These two base predicates are easily generated by 
decomposing $p(1,2)$ into $p(1)$, and $[2]$, which are stored as the arguments of
two general predicates, $i\_key/2$ and $value/3$. In Prototype 2, 
with the same update, two predicates $i\_key\_2\_p(1)$ and $value\_2\_p(1,2)$ 
are generated from $p(1,2)$. This processing requires a lot of run-time 
execution to create functor names for the key and value predicates, i.e., 
at run-time, the names $i\_key\_2\_p$ and $value\_2\_p$ are generated from the 
predicate name $p$. Procedures for generating predicate names are 
defined in the $naming$ module. In this prototype, since the base 
predicates (the tags and value predicate) can be indexed on the attributes 
rather than the predicate name (like Prototype 1), there is a considerable 
gain in access time. For this reason, although updates in Prototype 2 
require extra run-time computations, it is still more efficient than 
Prototype 1 because the loss in computation time is negligible comparing 
to the gain in search time.

In Prototype 2, since each predicate has its own set of key and value predicates, 
indexes can be used in this prototype. Indexing on the 
arguments in the key can speed up access to large databases. Note 
that indexing is applied to the tags (the insert tag and delete tag of the 
key), and the value predicate.

\subsection{Prototype 3}

Prototype 3 is designed for practical use. It is also the most recommended 
version among the three general prototypes. During the declaration of 
predicates, rules defining elementary transitions are constructed and 
added to the Prolog database. They include rules 
for creating or destroying a tuple, changing (setting) the value of a key, 
inserting or deleting key predicates, etc. For example, if $p/2$ is 
declared with 1 key attribute, then the following rules are constructed:
\myeqnbegin
p(X,Y) & :- & key\_2\_p(X), val\_2\_p(X,Y).\\
key\_2\_p(X) & :- & i\_key\_2\_p(X), not(d\_key\_2\_p(X)).\\
create\_p(X,Y) & :- & ins\_key\_2\_p(X), insertbase(val\_2\_p(X,Y)).\\
destroy\_p(X,Y) & :- & del\_key\_2\_p(X), deletebase(val\_2\_p(X,Y)).\\
set\_p(X,Y) & :- & key\_2\_p(X), deletebase(val\_2\_p(X,\_)), insertbase(val\_2\_p(X,Y)).\\
ins\_key\_2\_p(X) & :- & not(i\_key\_2\_p(X)), insertbase(i\_key\_2\_p(X)).\\
ins\_key\_2\_p(X) & :- & i\_key\_2\_p(X), deletebase(d\_key\_2\_p(X)).\\
del\_key\_2\_p(X) & :- & key\_2\_p(X), insertbase(d\_key\_2\_p(X)). \\
 & &    {\normalsize where} 		\nonumber	\\
 & &    insertbase/1\; {\normalsize and}\; deletebase/1\; {\normalsize are\; 
	predicates\; defined\; as\; backtrackable} 	\nonumber	\\
 & & 	assert\; {\normalsize and\;}\; retract,\; {\normalsize same\; as\;}
	ins/1\; {\normalsize and\;} del/1\; {\normalsize described\; in\;
	Section\; 4.3.1}.		\nonumber
\myeqnend
Unlike Prototype 2, basic functions for a tuple like $create$, $destroy$ 
and $set$ are defined separately for each predicate. Therefore, during the 
executions of these functions, it is not necessary to perform a sequence 
of predicate transformations as in Prototype 2, and so such executions 
will be faster.

In Prototype 3 (and in Prototype 4), there are several implementations of 
for-loops. In general, there are three types of for-loops:
\mycolbegin
tabbingggg \=  \kill
\>      [with {\em VList}] forall {\em Vars} in {\em Cond} do {\em Body} \\
\>      [with {\em VList}] forall unique {\em Vars} in {\em Cond} do {\em Body}\\
\>      [with {\em VList}] forall possible {\em Vars} in {\em Cond} do {\em Body}
\mycolend
The first type of for-loop is the most efficient. It does not remove 
duplicate answers to the query $Cond$. It also has limited backtracking 
capabilities. In general, users should be aware of duplicate answers which 
may cause the loop iteration to fail. For example, attempting to
destroy a tuple which has been deleted in previous iteration will fail,
causing the entire loop to fail.

The second type of for-loop is similar to the first except it eliminates 
duplicate query answers.

The third type of for-loop is the general for-loop used in Prototype 1 
and Prototype 3. The option {\em possible} refers to possible orders for 
choosing values for the variables. Without backtracking, it should perform 
in the same behavior as the second type, i.e., with option {\em unique}. 
However, in backtracking, the first and second types of for-loop
undo the all iterations of the loop. In this type, it will
backtrack and iterate with other orders on the values of the loop
variables.

{\em Examples}: Database contains: $p(1,1)$, $p(1,2)$, and $p(3,3)$
\begin{enumerate}
\item  $forall\; [X]\; in\; p(X,Y)\; do\; create(q(X))$ \\
        The loop fails because the loop variable Y binds to be 
	1, 1, 3. After $q(1)$ is created in the first iteration, the program 
	fails when attempting to create it again.
\item  $forall\; unique\; [X]\; in\; p(X,Y)\; do\; create(q(X))$ \\
        The loop succeeds because duplicated answers for X are removed. So, 
	$q(1)$ and $q(3)$ are successfully created.
\item  $forall\; possible\; [X]\; in\; p(X,Y)\; do\; (not(q(1))\; sc\; create(q(Y))$ \\
        Suppose the first iteration binds $X$ to 1, $q(1)$ is created. 
	However, in the second iteration, $X$ is bound to 3, and
	the loop body ``$not(q(1))\; sc\; create(q(X))$'' fails. Using 
	the first or the second type of loop, the entire loop fails. 
	In this formula, however, the loop backtracks and tries other
	order on the values for the variables, i.e., binds $X$ to 3 first,
	and then $X$ to 1. In this way, $q(3)$ is created successfully
	in the first iteration. Then, in the second iteration,
	$not(q(1))\; sc\; create(q(X))$ also succeeds because
	$q(1)$ was not in the database when this subgoal is called.
\end{enumerate}
Examples of the implementation are as follows: 
\begin{enumerate}
\begin{small}
\item   $with\; [X]\; forall\; [Y,Z]\; in\; p(Y,Z)\; do\; create(q(X,Y,Z))$ \\
        is translated into \\
        \indent$bagof([Y,Z],p(Y,Z),List),\; loop1(List,X)$\\
        and the following rules are created \\
        \indent$loop1([[Y,Z]|List],X)\; :-\; create(q(X,Y,Z)),\; loop1(List,X).$ \\
        \indent$loop1([],X).$ 
\item   $with\; [X]\; forall\; unique\; [Y,Z]\; in\; p(Y,Z)\; do\; create(q(X,Y,Z))$ \\
        is translated into \\
        \indent$setof([Y,Z],p(Y,Z),List),\; loop1(List,X)$ \\
        and the following rules are created \\
        \indent$loop1([[Y,Z]|List],X)\; :-\; create(q(X,Y,Z)),\; loop1(List,X).$ \\
        \indent$loop1([],X).$ 
\item   $with\; [X]\; forall\; possible\; [Y]\; in\; p(Y)\; do\; create(q(X,Y))$ \\
        is translated into \\
        \indent$temp(Y)\; :=\; p(Y),\; loop1(X)$ \\
        and the following rules are created \\
        \indent$loop1(X)\; :-\; destroy(temp(Y)),\; create(q(X,Y)),\; loop1(X).$ \\
        \indent$loop1(X)\; :-\; not(temp(Y)).$ 
\end{small}
\end{enumerate}

Prototype 3 will generally be faster than Prototype 2. However, there is a
drawback in this prototype. If new predicates are continuously declared, 
there will be more and more non-erasable rules residing in the database, 
and this may affect the total usable executional space. Also, the 
accumulation of rules is not neat when viewing the contents of the Prolog
translation of a \TR transaction base.

\subsection{Prototype 4}

Some transaction programs do not backtrack through updates, e.g., 
many P-time graph algorithms. Prototype 4 optimizes the \TR implementation for
such problems. 

Since updates have no backtracking in this prototype, there is no need 
to use the special tag method to store keys, because this method is 
implemented to handle update backtracking. Instead, we can directly use $assert$ and 
$retract$ in the implementation. However, in order to use the same 
declaration method, we still have to check that each key has a unique value 
when a new tuple is created. Checking is performed when inserting 
a key. Thus, if $p/2$ is declared with 1 argument as key, then 
``$create(p(1,2))\; sc\; create(p(1,3))$'' would fail.

Moreover, since there is no backtracking, we can include the 
Prolog ``$cut$'' in some formulas to speed up execution. Also, some Prolog 
languages like, Quintus Prolog and Sicstus Prolog, provide optimizations 
on tail recursive rules, i.e., rules of the form: 
\myeqnbegin
                Rule\_head & :- & Rule\_body,\ !,\ Rule\_head.
\myeqnend
Therefore, in Prototype 4, loops can be translated to tail recursive 
rules, so that the performance of loops will be optimized by the Prolog 
interpreter. For example, in Prototype 4, the translations of $while\_loop$ 
and $for\_loop$ are:
\begin{enumerate}
\begin{small}
\item   $while\; Cond\; do\; Body$ \\
        is translated into \\
        \indent$loop$   \\
        and the following rules are created \\
        \indent$loop\; :-\; Cond,\; Body,\; !,\; loop.$ \\
        \indent$loop\; :-\; not(Cond).$ 
\item   $with\; [X]\; forall\; [Y,Z]\; in\; p(Y,Z)\; do\; create(q(X,Y,Z))$ \\
        is translated into \\
        \indent$bagof([Y,Z],p(Y,Z),List),\; loop1(List,X)$ \\
        and the following rules are created \\
        \indent$loop1([[Y,Z]|List],X)\; :-\; create(q(X,Y,Z)),\; !,\; loop1(List,X).$ \\
        \indent$loop1([],X).$
\item   $with\; [X]\; forall\; unique\; [Y,Z]\; in\; p(Y,Z)\; do\; create(q(X,Y,Z))$ \\
        is translated into \\
        \indent$setof([Y,Z],p(Y,Z),List),\; loop1(List,X)$ \\
        and the following rules are created \\
        \indent$loop1([[Y,Z]|List],X)\; :-\; create(q(X,Y,Z)),\; !,\; loop1(List,X).$ \\
        \indent$loop1([],X).$ 
\end{small}
\end{enumerate}
Note that the last type of for-loop ( $forall\; possible$ ) can be 
implemented exactly as the second type ( $forall\; unique$ ) because 
there is no backtracking in Prototype 4. Also, with the use of ``$cut$'' in 
these interpreted rules, choice points can be released in each loop 
iteration, which releases space from the choice point stack.

\section{Prolog Interpreters}

The \TR implementation was designed to run under XSB Prolog, which provides 
facilities for user-defined indexes on any combination of arguments of a predicate. 
When a \TR program is running in other Prolog environments, some facilities 
which are provided by XSB Prolog, such as indexing, might not be available.

We have separated the implementation into a number of modules. To port the 
implementation from one Prolog interpreter to another, minor adjustments 
must be made to each module. To minimize and isolate the changes
each module, the $basic\_funs$ module contains the most basic rules which 
may need to be modified. So, most changes will be to this module.

To illustrate the modifications, we will show the changes necessary to run
the program in Quintus Prolog or in Sicstus Prolog. Also, we will briefly 
describe some special features provided by these interpreters which are 
used in our implementations.

\subsection{XSB Prolog}

XSB Prolog is a research-oriented Logic Programming system for Unix-based 
systems. It was designed to be used as a module-oriented Prolog system. A 
module contains one or more export declarations, which specify the set of 
visible predicates that can be used by other modules. It may also contain 
import declarations, which allow predicates defined and exported by other 
modules to be used in the current module. Export and import declarations 
have the following forms:
\mycolbegin
tabbingggg \=  \kill
\>      :- export $pred_1$, $pred_2$, $\ldots$ , $pred_m$.\\
\>      :- import $pred_1$, $pred_2$, $\ldots$ , $pred_n$ from $module$.\\
\>      where each $pred_i$ has the form $functor / arity$.
\mycolend
Using modules, it is easier for us to maintain the \TR implementation when 
making changes.

Another useful feature provided by XSB Prolog is indexing. Most Prolog 
compilers put an index on the principal functor of the first argument 
of a predicate, but XSB Prolog allows a user to put indexes on any 
argument or combination of arguments by means of an index directive. This
directive has the form:
\mycolbegin
tabbingggg \=  \kill
\>   $:-\; index(Functor/Arity,\; IndexArgSpec,\; HashTableSize).$
\mycolend
which allows users to specify the size of the hash table to use for 
indexing a predicate. In this directive, $IndexArgSpec$ is either an integer,
indicating the argument to be indexed, or a list of $IndexArgs$. An 
$IndexArg$ may be an integer, indicating the argument to be indexed, or a 
sequence of up to three integers separated by +. The latter indicates 
that an index is to be built a combination of arguments.

As an example, the command $:-\; index(p/3,\; [1+2,1,3],\; 100)$ specifies an 
index on predicate $p/3$. With this declaration, three hash tables are 
created, and each of them has 100 entries.  A call to $p/3$ first checks to 
see if both the first and second arguments are bound, and if so, uses an 
index based on these two values. Otherwise, it checks if the first argument 
is bound, and if so, uses an index based on it. If not, it checks if the fourth 
argument is bound, and if so, uses an index based on it. Otherwise, it uses 
no index, and searches through all the clauses for this predicate in the database.
Users should be aware of the size of hash tables. For example, if $p(X)$ 
has 100 entries in database, then setting the hash table size to 10,000 can 
severely affect tuple access time. 

If a predicate is called before it is defined, most Prologs will display 
error messages, and some will even abort the execution. In our 
implementation, when creating a tuple, we have to check if the tuple is 
already in the database. If it exists, then the creation fails. However, 
if this is the first time a tuple is created after its predicate is 
declared, then during the checking, some warning messages may appear to 
inform users the predicate has not been defined, or the execution may abort. 
To avoid such behavior, when a predicate is declared, all database 
predicates (i.e., all tag and value predicates) should be defined 
dynamically ( i.e., so they can be retracted from the Prolog database). For 
example, in executing the declaration $p/2\;key\; 1$, the tags $i\_key\_2\_p/1$ and 
$d\_key\_2\_p/1$ together with the value predicate $val\_2\_p/2$ 
are defined as dynamic predicates so that calls to $p(X,Y)$ can fail 
quietly. In the implementation, we define $dynpred(X)$ for this function.
In XSB Prolog, since the built-in predicate {\em dynamic/1} performs the 
required function, $dynpred/1$ can defined by the $dynpred(X)\; :-\; 
dynamic(X)$. Since $dynamic/1$  may be a built-in predicate with other 
purpose in other Prologs, like Quintus Prolog, we do not use it directly in 
the implementation, so that we can minimize the changes in the implementation
when porting it to other Prologs. 

\subsection{Sicstus Prolog}

Sicstus Prolog was developed at the Sweden Institute of Computer Science. 
It consists of a Warren Abstract Machine emulator written in C, a library 
and runtime system written in C and Prolog, and an interpreter and a 
compiler written in Prolog. To run a \TR program in Sicstus Prolog, the 
following changes should be made to the XSB implementation of \TRR:

\begin{itemize}
\item Since Sicstus Prolog does not support modules, all export or 
	import declarations from the source code should be removed 
	from the code. 
\item Sicstus Prolog indexes a predicate according to the principal 
	functor of the first argument in the head of the clause, and 
	does not allow a user to define hash table size. So, rules for 
	declaring the index information should be removed from the 
	$key\_basics$ module.
\item Sicstus Prolog does not provide any built-in predicate similar to 
	$dynamic/1$ in XSB Prolog. So, a user-defined 
	rule for $dynamic$ should be written. In our Sicstus implementation
	of \TRR, the predicate $dynpred/1$ is defined in the $basic\_funs$ 
	module as follows: 
	\myeqnbegin
	        dynpred(X) & :- & retract(X),\; !,\; assert(X)  \\
                        & &	;		\nonumber	\\
                        & &	true.		\nonumber
	\myeqnend
\end{itemize}

In Sicstus Prolog, when $retract(Y)$ is called,
$Y$ is defined to be dynamic no matter whether the execution succeeds or not.
So, the predicate $dynpred/1$ defines a predicate 
to be dynamic by intentionally retracting the predicate from database. 
For instance, when $dynpred(p(X))$ is called, the system first defines $p(X)$
to be dynamic by trying to 
retract $p(X)$ from database. If $p(X)$ has a tuple in the database, 
$retract(p(X))$ retracts the tuple, and then re-asserts it without affecting 
the content of the database. If $retract(p(X))$ fails, the execution 
succeeds with the disjunction to the subgoal $true$.

\subsection{Quintus Prolog}

Like Sicstus Prolog, Quintus Prolog does not support modules, and 
therefore, import and export declarations should be removed from our XSB 
implementation of \TR before porting it to Quintus. Like
Sicstus Prolog, Quintus Prolog indexes predicates on the principal functor 
of the first argument, and does not allow users to define their own 
indexes and hash tables. Thus, all indexing predicates should also be 
removed. 

Unlike Sicstus Prolog, if a predicate is non-dynamic, then $retract/1$ does 
{\em not} define the predicate to be dynamic. So, another rule defining $dynpred/1$ 
is used:
\myeqnbegin
        dynpred(X) & :- & predicate\_property(X,(dynamic)),\; !,\; true \\
                  & &    ; 			\nonumber	\\
                  & &    assert(X),\; retract(X).	\nonumber
\myeqnend
Quintus Prolog provides a useful pre-defined predicate $predicate\_property/2$ 
to check the status of a predicate. The goal $predicate\_property(X,(dynamic))$
returns true if $X$ is defined as a dynamic predicate. If the predicate is 
dynamic, the execution succeeds. If the predicate is not dynamic, we 
deliberately assert the predicate into database, which defines the 
predicate dynamically. To keep the consistency, the predicate is removed 
immediately, so that the database is unchanged afterwards. Note that suppose
$p(1)$ is already in the database, by definition, $p(X)$ is dynamic. The 
execution of $dynpred(p(X))$ will not cause $p(1)$ to be retracted because
$predicate\_property(p(X),(dynamic))$ is true.
