\chapter{Introduction}

Transaction Logic (abbreviated \TRR) is a recently proposed predicate 
logic which extends first-order logic with transaction specifications 
to account for update-related phenomena. It was developed by Bonner 
and Kifer to account for state changes in logic programs and databases 
[$BK95$]. \TR has a natural model theory and a sound and complete proof 
theory as well as a procedural semantics for a ``Horn'' version. Unlike 
other logics, it can specify and execute procedures that update and 
permanently change a database or a logic program. To be more specific, 
transactions can be defined as logic programs because the ``Horn'' 
version of \TR has has both a procedural and a declarative semantics. 
 
Like procedural languages, \TR can use sequential operators to specify
transactions by combining simple actions into complex ones. It supports
a wide range of functionality in different areas including database
queries and updates, bulk updates, transaction definition, deterministic 
and non-deterministic transactions, conditions on actions, etc. With
the increase in expressiveness and functionality, \TR can be used in
a wide class of applications, especially in relational and deductive
databases, logic programming and AI.

As described above, like classical logic, \TR has a ``Horn'' version,
called serial-Horn \TRR. Execution of transactions in serial-Horn \TR
can be considered as an extension of classical query processing methods. Although
much research has been done on query processing in recent years,
researchers in this area still do not pay much attention to the
execution of updating transactions. For example, Prolog executes
simple updates using the non-logical operators, ``$assert$'' and ``$retract$'',
in conjunction with other logical operators.

Transaction Logic was developed as a general logic to solve a wide range
of update-related problems. It can extend the theory of logic programming
to include updates as queries with the maintenance of semantic consistency.
In AI, it suggests a logical account of planning. By storing nodes and
edges of a graph into predicates,
\TR can be used to solve a lot of graph problems, such
as connected component problem, and Hamiltonian cycle problem. The
capabilitity of undoing operation can be used not only in solving
graph problems, but also in simulating circuit designs.

In this thesis, we present an implementation\footnote{
	The implementation is available in the directory
	{\em pub/goku/transaction\_logic} by anonymous ftp to
	{\em db.toronto.edu}.}
of serial-Horn \TR
in Prolog. Readers are assumed to be familiar with Prolog. Four
prototypes have been implemented;
they range from simple but slow, to fast but complex. The programs
define transaction directives of serial conjunctions, backtrackable
updates and bulk updates, as well as some iteration methods in a
declarative fashion. Both transaction base and database of \TR are stored 
in Prolog database. Transaction rules are specially treated so that they 
are used in transaction queries only. In addition, database tuples are
not stored directly in Prolog database. A database predicate must be 
declared before it is created or called. The declaration informs the 
system that some attributes
are defined as the primary key. Indexing on predicates can also be 
specified in the declaration. Although our implementation was developed 
on top of XSB Prolog, it can also be run on other Prologs with some simple
adjustments. Comparisons between the performance of the implementation in
several Prolog systems, including XSB Prolog, Quintus Prolog, and Sicstus
Prolog, have been made, and the tests in chapter 5 shows some of the 
strength and the weakness of each systems. 

\subsubsection{Thesis Outline}

The thesis is organized as follows:

        Chapter 2 provides an overview of Transaction Logic, general 
\TR and serial-Horn \TR programs, the model theory, and the notion 
of executional entailment.

        Chapter 3 develops applications of \TR. They exploit features 
of \TR such as transaction definition and execution, consistency
maintenance, and bulk updates. We will also see how \TR handles 
planning in the ``$blocks\; world$''. 

        Chapter 4 describes our implementation of \TRR. It discusses the 
features of \TR together with brief explanations of how they 
are implemented. The implementation includes four distinct prototypes 
which range from simple but inefficient (Prototype 1), to efficient but 
complex (Prototype 3), as well as providing a special version for transactions
that do not backtrack through updates. Although our implementation is 
developed in XSB Prolog, this chapter shows how to modify 
the prototypes for other Prologs.

        Chapter 5 compares the performance of Prototype 3 and Prototype 
4 of the implementations in XSB Prolog, Sicstus Prolog and Quintus Prolog.
The tests include graph 
problems such as finding connected components, all pairs shortest paths, 
Hamiltonian cycle, and clique. Each test exercises different features 
of the implementations. 

        Chapter 6 concludes the work and suggests future directions
for research.
