\chapter{Applications}

Since \TR formulas can capture the features of database and knowledge-base 
systems, a wide variety of interesting and useful formulas in this 
area can be constructed in \TR. These include transaction definition 
and execution, ad hoc queries, consistency maintenance, bulk updates, 
non-determinism, sampling, etc. In this chapter, we will describe some 
of these applications. We shall also see how \TR can be used in solving 
graph theory problems and to simulate circuits.

The examples in Section 3.1-3.4 are adapted from [$BK95$]. To start 
with our discussion, we shall consider some simple database 
transactions first. 

\section{Update Consistency}

In many database systems, when updating one relation, it is often to 
make additional updates to other relations in order to maintain the 
consistency. For instance, in a banking system, when a certain amount 
of money is transferred from one account to another, same amount of 
money should be deducted from one account and added to the other. In 
normal logic programming, since update operations are non-backtrackable, 
if the execution fails after the first update, the database would be 
in an inconsistent state because the previous update cannot be undone. 
On the other hand, consistency can be maintained easily in \TR by simple 
transaction formulas.

For example, suppose a school has a database of students, courses, and 
professors. This database includes the following base relations: 

\mytabbegin
$takes(Student, Course)$\\
$course\_size(Course,N)$\\
$courses\_taken(Student,Total)$\\
\mytabend

Using elementary updates, we can define two procedures by which a 
student drops a course and a teacher is relieved of teaching a course, 
respectively. When a student drops a course, in order to ensure 
database consistency, the number of students taking the course and 
the total number of courses taken by the student must be decremented.
This is accomplished by the following transaction rules, adapted from 
[$BK95$]:
\myeqnbegin
drop(Student,Course) & \leftarrow\ &
		del:takes(Student,Course) \otimes\ 
		decr\_class(Course) \otimes\ 	\\
	&  &  	decr\_total(Student).		\nonumber	\\
decr\_total(Student) & \leftarrow\ &
		del:courses\_taken(Student,N) \otimes\ 		\\
	&  &	N_1\  is\  N-1 \otimes\ ins:course\_taken(Student,N_1). \nonumber \\
decr\_class(Course) & \leftarrow\ &
		del:course\_size(Course,N) \otimes\ 
		N_1\  is\  N-1 \otimes\ 		\\
	&  &	ins:course\_size(Student,N_1). 	\nonumber
\myeqnend
The first rule defines the procedure for dropping a course. The last two 
rules define sub-procedures for decrementing the number of courses taken 
by the student and the current course size. If either of the base 
predicates is missing, which causes the procedure to fail, the whole 
execution will be undone and will leave the database in its original state.

\section{Circuit Design}

Horn Logic can conveniently simulate physical systems without internal 
state such as combinational digital circuits. In such circuits, the 
output depends on the input only. The input of the circuit can be 
stored in the database, and then a logic program can compute the 
output.

However, for systems with internal state, such as counters 
and flip-flops, the output depends on the inputs and on the internal 
state of the systems. It is natural to simulate the internal states 
by the database because it can guarantee the persistence of internal 
states. Also, the internal states can be queried and changed by database 
transactions. Unfortunately, since classical logic programming and 
deductive databases do not provide a clean theory of updates, logic 
programmers cannot represent such systems in this natural way.

A digital circuit can be represented as a collection of logic gates 
connected by wires. Each gate has input ports and an output port. Each 
port is attached to a wire. Each wire is connected to two ports. There 
is a device called ``$split$'' which divides a wire into two. It has an 
input port and two output ports, which have same value. Using the split 
device, the output of one gate can be propagated to many other gates. 
Also, each wire has a name and a value of $0$ or $1$. A base predicate 
$val(N,V)$ means the wire with name $N$ has the value $V$.

A gate is the smallest element of a circuit, and we use a 
predicate called {\em gate} to represent it. There are different versions 
of this predicate which have different arities to represent different 
numbers of input and output ports. Gates with two inputs and one 
output, such as and-gate, or-gates, nand-gates, etc., are represented 
by $gate(Type,In_1,In_2,Out)$, where {\em Type} is name of this kind of 
gate,\ $In_1$, $In_2$ are the names of the input ports, and {\em Out} is 
the output port. Similarly, $gate(inv,In,Out)$ represents an inverter 
which has one input and one output. To represent the split device, 
we use the predicate $split(In,Out_1,Out_2)$. The R-S flip-flop in
Figure 3.1 is represented by the following database:

\begin{figure*}[t]
	\hfil\epsfbox{gate.ps}
	\caption{Circuit of a R-S flip-flop}
\end{figure*}

\mycolbegin
tabbing \= gate(inv,Sin,S1)longer  \= gate(nand,S1,R3,S2)longer \= split(S2,S3,Sout) \kill
\> $gate(inv,sin,s1)$  \>	$gate(nand,s1,r3,s2)$ \> $split(s2,s3,sout)$ \\
\> $gate(inv,rin,r1)$  \>	$gate(nand,r1,s3,r2)$ \> $split(r2,r3,rout)$ \\
\> val(Sin,0)long \= val(S1,1)long \= val(S2,1)long \= val(S3,0)long \= val(Sout,0)\kill
\> $val(sin,0)$ \>	$val(s1,1)$ \>	$val(s2,1)$ \>	$val(s3,0)$ \>	$val(sout,0)$\\
\> $val(rin,0)$ \>	$val(r1,1)$ \>	$val(r2,0)$ \>	$val(r3,1)$ \>	$val(rout,1)$\\
\> dangling(Sout)longer \=	dangling(Rout) \kill
\> $dangling(sout)$	\>	$dangling(rout)$ 
\mycolend

The S-R flip-flop has two input lines, {\em sin} and {\em rin}, and two output 
lines, {\em sout} and {\em rout}. The outputs of two NAND gates cross-connect to 
each other's inputs. Such feedback gives the flip-flop an internal 
state, and therefore, the outputs of the flip-flop depend on its
current internal state. We assume there is just one flip-flop in the
circuit, and so $sout$ and $rout$ are dangled.
Initially, the flip-flop is holding the state 0, with both
input lines $sin$ and $rin$ are low, the output line $sout$ is low, 
$rout$ is high. 

To simulate this circuit, we first have to define the function of each 
gate. We use a predicate called {\em table} to store the truth table of the 
gates. For gates with two inputs, we use $table(Type,In_1,In_2,Out)$, 
where $Type$ is the type of the logic gate, $In_1$ and $In_2$ are the two 
input values, and $Out$ is the output value. Thus, the truth table of 
a NAND gate is represented as follows:

\mycolbegin
longer \= table(nand,0,0,1)longer \= table(nand,0,1,1) \kill
\> $table(nand,0,0,1)$ \>	$table(nand,0,1,1)$ \\
\> $table(nand,1,0,1)$ \>	$table(nand,1,1,0)$
\mycolend

Like the predicate gate, an inverter has one input and one output. 
The predicate table thus has a different arity for the inverter.

\mycolbegin
longer \= table(inv,0,1)longer \= table(inv,0,1) \kill
\> $table(inv,0,1)$ \>  $table(inv,1,0) $
\mycolend

The truth tables can be stored in the transaction base rather than 
in the database. (However, if we store the truth tables in the database, 
they may be corrupted by users.) To simulate the logic circuit, apart 
from the behavior of the gates, we also need to describe the dynamic 
changes of the circuit. If the input line of one gate changes, the 
value of the output line may change and eventually more lines will 
be affected. Therefore, a change in value of a line is considered 
as a basic event or action. The predicate $setline(Line,Val)$ is defined 
to set the value of a line with name $Line$ to $Val$. For example, 
$setline(S1,1)$ sets the value of the line $S1$ to $1$. Like most 
events, $setline$ does not just set the value of a line. It may 
also trigger other events, which may trigger other events, etc., 
leading to a cascade of triggered events. This cascade may 
eventually reach a stable state (when the new value and the old value of 
a line are the same, or the propagation ends at a dangling tuple)
, or the circuit may oscillate 
forever. The following rules, taken from [$BK95$], capture the dynamic 
behavior of logic gates:
\vspace{.8in}
\myeqnbegin
setline(Line,NewVal) & \leftarrow\ & val(Line,NewVal). \\
setline(Line,NewVal) & \leftarrow\ & val(Line,OldVal) \otimes\ \\
	& &	NewVal \neq\ OldVal \otimes\ \nonumber \\ 
	& &	del:val(Line,OldVal) \otimes\ ins:val(Line,NewVal) \otimes\ \nonumber \\
	& &	propagate(Line). \nonumber \\
\nonumber	\\
propagate(In)	& \leftarrow\ & dangling(In). \\
propagate(In)	& \leftarrow\ & 
		split(In,Out_1,Out_2) \otimes\ val(In,Val) \otimes\ \\
	& &	setline(Out_1,Val) \otimes\ setline(Out_2,Val). \nonumber \\
propagate(In) 	& \leftarrow\ &	
		gate(inv,In,Out) \otimes\ val(In,Val1) \otimes\ \\
	& &	table(inv,Val_1,Val_2) \otimes\ setline(Out,Val_2). \nonumber \\
propagate(In) 	& \leftarrow\ &
	 	[ gate(Type,In_1,In_2,Out) \vee\; gate(Type,In_2,In_1,Out) ] \otimes\ \\
	& &	val(In1,Val_1) \otimes\ val(In_2,Val_2) \otimes\ \nonumber \\
	& &	table(Type,Val_1,Val_2,Val_3). \nonumber
\myeqnend

These rules define two recursive predicates, setline and propagate. 
The predicate \\$setline(Line,NewVal)$ defines the action of setting 
the value of a line. $Rule\ 3.4$ terminates the recursion if the old 
value is the same as the new value. $Rule\ 3.5$ represents the case 
when the old value and the new value are different. The rule 
changes the value of the line, and propagates the effect of the 
change to other lines by invoking the predicate propagate.

Similarly, $Rule\ 3.6$ terminates the propagation when the line is an 
open end (i.e., a dangling line). $Rule\ 3.7$ represents the function 
of the split device, which divides a line into two. This rule sets 
the value of both output lines to the same value as the input line. 
The final two rules, $Rule\ 3.8$ and $Rule\ 3.9$, encode the behaviors of 
logic gates by consulting the corresponding truth table and setting 
the output line accordingly.

To illustrate the behavior of these rules, we will show their use in simulating
the R-S flip-flop of {\em Figure 3.1}. In the example, the initial values of the input 
lines, $sin$ and $rin$, are both 0, and the output lines, $sout$ and $rout$, 
have values 1 and 0, respectively.

If the user issues the command $?- setline(sin,0)$, nothing should 
happen because the value of $sin$ is already 0. In the simulation, 
the event terminates immediately via $Rule\ 3.4$.

But, if the user issues the command $?- setline(sin,1)$, by $Rule\ 3.5$, 
the value of $sin$ will change to 1, and a new subgoal $propagate(sin)$
is issued. The execution propagates the changes of states to $s1$, $s2$, 
etc. The propagation terminates at the dangling wire $sout$ and at $r3$ 
because the new value matches the old one. The entire simulation is 
summarized by the following series of subgoals, adapted from [$BK95$]:

\mycolbegin
tabbing \= ?- propagate(Sin) loggggggggggggggggggggggggggggg \=  \kill
\> $?- setline(sin,1)$ \\			
\> $?- propagate(sin)$ \> 		(value of sin change to 1)\\
\> $?- setline(s1,0)$  \\
\> $?- propagate(s1)$ \>		(value of s1 change to 0)\\
\> $?- setline(s1,1)$ \\
\> $?- propagate(s2)$ \>		(value of s2 change to 1) \\
\> $?- setline(sout,1) \otimes\ setline(s3,1)$ \>	(s2 split to sout and s3) \\
\> $?- propagate(sout) \otimes\ setline(s3,1)$ \>	(value of sout change to 1) \\
\> $?- setline(s3,1)$ \>			(sout dangled) \\
\> $?- propagate(s3)$ \> 		(value of s3 change to 1) \\
\> $?- setline(r3,0)$
\mycolend
The last subgoal sets the value of $r3$ to $0$, which is the same as the 
original value of $r3$, and terminates the simulation. A detailed 
explanation can be found in [$BK95$].

\section{Bulk Updates}

A prominent feature of database languages is bulk 
updates. It is a basic function to insert or delete a set of tuples 
in database languages such as SQL. However, such updates are not as 
simple in most logic programming languages. 
In logic programming languages, updates are typically based on the insertion 
and deletion of single tuples. However, database languages like SQL 
evaluate a query first, and then insert the resulting set of tuples into 
a relation, or delete the set from a relation.

Like procedural database languages, \TR provides elementary state 
transitions to capture the behavior of bulk updates at the lowest 
level. In \TRR, relational assignment, {\em :=}, is defined so
$p(X,Y) := q(X,Y)$ copies the whole extent of 
$q$ (source formula) to $p$ (destination predicate) overwriting the 
contents of $p$, where $p$ is a base predicate. In this example, 
$p$ and $q$ will contain the same data 
after the assignment. So, the transition oracle contains the 
following formulas:

\mytabbegin
$p(X,Y) := q(X,Y) \; \in \; 
	O^t(\{ q(1,1), q(2,2) \},\;  \{ p(1,1), p(2,2), q(1,1), q(2,2)\} )$ \\
$p(X,Y) := q(X,Y) \; \in \;
	O^t(\{ p(1,1), q(1,1), q(2,2) \},\; \{ p(1,1), p(2,2), q(1,1), q(2,2) \})$ \\ 
$p(X,Y) := q(X,Y) \; \in \;
	O^t(\{ p(3,3), q(1,1), q(2,2) \},\;  \{ p(1,1), p(2,2), q(1,1), q(2,2)\} )$  
\mytabend

The source of the assignment needs not necessary to be a base predicate. 
It can be a derived predicate or a query. For instance, 
suppose the database contains the following predicates and rules:

\mycolbegin
tabbing \= q(X,Y) :- r(X) \=  \kill 
\> $r(1)$ \> $r(3)$ \\
\> $p(1,1)$	\> $p(2,2)$ \\
\> $q(X,Y) :-\  r(X), p(X,Y)$ 
\mycolend

In order to be in serial Horn \TRR, the source of the assignment should be 
defined by a database formula, rather than by a transaction formula. 
Therefore, in the above example, $q$ is defined as a derived database 
predicate, rather than as a transaction formula. This is indicated by the
syntax of the rule for $q$, which uses ``{\em :-}'' instead of ``$\leftarrow$''.
With the above database, $q(1,1)$ is derived from $p$ and $r$. So, 
after the assignment of $p(X,Y) := q(X,Y)$, the relation $p$ contains 
$p(1,1)$ only. As mentioned above, we can use a query instead of a predicate
in the source of the assignment. For instance, the assignment $p(X,Y) :=
r(X),\ p(X,Y)$ can produce the same outcome as $p(X,Y) := q(X,Y)$.

Note that the destination predicate should contain no free variables. 
Variables in the destination predicate must also appear in the source 
predicate or be unified before the assignment takes place. For example, 
``$X = 1 \otimes\ p(X,Y) := q(X,Y)$'' is equivalent to 
``$p(1,Y) := q(1,Y)$'', which removes all entries of $p(X,Y)$ in the database,
and copies all $q(1,Y)$ tuples to $p(1,Y)$. On the other hand, free 
variables may appear in the source. For instance, in the assignment, 
$r(X) := p(X,Y)$, $Y$ is a free variable which means that for every $X$, 
there exists $Y$ such that $p(X,Y)$ is in database. So, the following 
transitions are defined in transaction base:
\mytabbegin
$r(X) := p(X,Y) \; \in \; 
	O^t(\{ p(1,1), p(2,2) \} ,\ \{ r(1), r(2), p(1,1), p(2,2)\} )$ \\ 
$r(X) := p(X,Y) \; \in \;
	O^t(\{ p(1,1), p(2,2), r(3)\} ,\; \{ r(1), r(2), p(1,1), p(2,2) \} )$ \\ 
$r(X) := p(X,Y) \; \in \;
	O^t(\{ p(1,1), p(1,2), p(2,2)\} ,\; \{ r(1), r(2), p(1,1), p(1,2), p(2,2)\} )$ \\ 
$r(X) := p(X,Y) \; \in \;
	O^t(\{ p(1,1), p(1,2), p(2,2), r(3)\} ,\; \{ r(1), p(1,1), p(1,2), p(2,2)\} )$ 
\mytabend
The last two formulas show that any duplicate predicates created 
in the assignment are discarded. 

\subsubsection{Examples}
Some complex transactions can easily be expressed by relational 
assignment. For instance, the transaction, ``Increase the balance 
of all savings account by adding 5\% interest, and retrieve all persons 
who have an account balance less than \$100'', can be expressed as 
follows.
\myeqnbegin
update(Name,NewBal,savings) & \leftarrow\ & 
		account(Name,Bal,savings) \otimes\ \\
	& &	NewBal is Bal \times\ 1.05. 	\nonumber	\\
update(Name,Bal,Type) &	\leftarrow\ &
		 account(Name,Bal,Type) \otimes\ Type \neq\ savings. \\
retrieve(Name) & \leftarrow\ &
	 	account(N,B,T) := update(N,B,T) \otimes\ \\
	& &	account(Name,Bal,Type) \otimes\ 	\nonumber \\
	& &	Bal < 100. 	\nonumber
\myeqnend
The first two rules compute the updated content of account, which 
is temporarily stored in the relation update. When the transaction 
$?- retrieve(Name)$ is invoked, the base predicate account in the database 
will be modified by the assignment and the query will return the 
specified user names. Actually, we do not need the rules for the 
temporary predicate update. Instead, we can redefine $retrieve$ as follows:
\myeqnbegin
retrieve(N) & \leftarrow\ & 
		account(N,NewB,savings) := 
		(account(N,B,savings), NewB is B \times\ 1.05) \otimes\ \nonumber \\
	& &	account(N,Bal,Type) \otimes\ Bal < 100.
\myeqnend
With the ability to compute queries and assign the output to a base 
relation, this kind of generalized bulk update has most of the power 
of bulk updates in SQL. As a special case, bulk insertion and bulk 
deletion can be expressed by relational assignment. 

\section{Planning}

In \TRR, action-definitions and planning strategies can be defined in 
the transaction base. There is no need to include any special 
mechanisms because both types of knowledge can be represented 
as serial Horn rules.

This section illustrates an approach to planning called ``{\em script-based 
planning}''. The presentation and examples are adapted from [$BK95$].
This approach describes actions and plans by a set of 
``{\em scripts}'' which suggest ways to achieve goals. The line differentiating 
between action definition and planning strategy is fuzzy. Actions 
are specific and low-level, whereas plans are abstract and high-level. 
We will use a simple example from the blocks world to demonstrate 
the use of \TR in planning problem.

The following rules define a hierarchy of planning strategies to 
simulate movements of a robot arm in the blocks world. There are 
two possible states of a block; $on(x,y)$, which says that block $x$ 
is on top of block $y$, and $isclear(x)$, which says that nothing is 
on block $x$. These rules define four actions that can change the state 
of a block. Note that each action has pre-conditions. If the
pre-conditions are not satisfied, the action fails.
\myeqnbegin
stackTwoBlocks(X,Y,Z) & \leftarrow & move(Y,Z) \otimes\ move(X,Y). \\
move(X,Y) & \leftarrow & on(X,Y). \\
move(X,Y) & \leftarrow & pickup(X) \otimes\ putdown(X,Y). \\
pickup(X) & \leftarrow & isclear(X) \otimes\  on(X,Y) \otimes\
		 del:on(X,Y) \otimes\ \\
	& &	ins:isclear(Y). \nonumber  \\
putdown(X,Y) & \leftarrow & X \neq\ Y \otimes\ isclear(Y) \otimes\
		 ins:on(X,Y) \otimes\  \\
	& &	del:isclear(Y). \nonumber 
\myeqnend
The most basic robot actions, $pickup(X)$ and $putdown(X,Y)$, mean 
``pick up block $X$'' and ``put down block $X$ on top of block $Y$``, 
respectively. They are defined in terms of the elementary functions 
$ins$ and $del$, which change the state of the blocks. The remaining 
rules combine these simple actions into complex ones. For example, 
$move(X,Y)$ means ''move block $X$ to the top of block $Y$`` which is defined 
as ''pick up block $X$, and put block $X$ down on top of block $Y$``; 
$stackTwoBlocks(X,Y,Z)$ means ``stack up block $X$ on top of block $Y$ 
and block $Y$ on the top of block $Z$''. 

The planning problem is fairly simple. It assumes all blocks that 
are picked up are clear. If the blocks involved are not clear, the 
action fails. Consider the following example:
\vspace{1.5in}
\begin{figure*}[h]
	\hfil\epsfbox{block1.ps}
\end{figure*}
\mycolbegin
Database:spaceeeee \= on(blkB,blkA) spaceeeeeeee \= isclear(blkB) \kill
Database: \> $on(blkB,blkA)$  \> $isclear(blkB)$ \\
	  \> $on(blkA,table1)$ \> $isclear(blkC)$ \\
	  \> $on(blkC,table2)$
\mycolend
The command ``$move(blkA,blkC)$'' fails, as shown by the following 
trace of subgoals during execution:
\mycolbegin
tabbing \= ?-- \= \kill
\>$ ?- move(blkA,blkC)$ \\
\>$ ?- pickup(blkA) \otimes\ putdown(blkA,blkC)$ \\
\>$ ?- isclear(blkA) \otimes\ on(blkA,X) \otimes\
	 del:on(blkA,X) \otimes\ ins:isclear(X)\ \otimes\ $ \\
\> \> $putdown(blkA,blkC)$
\mycolend
Since block $A$ is not clear, the execution fails. However, the command 
$?- move(blkB,blkC)$ succeeds because both blocks are clear. The actual 
sequence of subgoals during execution is:
\mycolbegin
tabbing \= \kill
\> $?- move(blkB,blkC)$ \\
\> $?- pickup(blkB) \otimes\ putdown(blkB,blkC)$ \\
\> $?- isclear(blkB) \otimes\ on(blkB,X) \otimes\ del:on(blkB,X) 
		\otimes\ ins:isclear(X) \otimes\ putdown(blkB,blkC)$ \\
\> $?- on(blkB,blkA) \otimes\ del:on(blkB,blkA) \otimes\ ins(isclear(blkA) 
		\otimes\ putdown(blkB,blkC)$ \\
	\hspace{4in} ( X is unified with blkA ) \\
\> $?- putdown(blkB,blkC)$	
	\hspace{.5in}	( on(blkB,blkA) is deleted and isclear(blkA) is inserted ) \\
\> $?- blkB \neq\ blkC  \otimes\  isclear(blkC) \otimes\  ins:on(blkB,blkC) 
	\otimes\ del:isclear(blkC)$ \\
\> !! succeed
\mycolend
All subgoals in the last step succeed. The state of the blocks is now:
\begin{figure*}[h]
	\hfil\epsfbox{block2.ps}
\end{figure*}
\mycolbegin
Database:spaceeeee \= on(blkB,blkA) spaceeeeeeee \= isclear(blkB) \kill
Database: \> $on(blkB,blkC)$  \> $isclear(blkA)$ \\
	  \> $on(blkA,table1)$	\> $isclear(blkB)$ \\
	  \> $on(blkC,table2)$
\mycolend
The example above is too simplistic for many AI applications. It 
is not difficult to modify the example so that the robot can plan 
to clear a block before picking it up. However, some extra actions 
are needed to provide this flexibility. We introduce the predicate 
$achieve\_clear(X)$, which tries to clear the top of block $X$. Two
predicates, $achieve\_stack(X,Y,Z)$ and $achieve\_on(X,Y)$, are defined
using $achieve\_clear$. The former predicate 
stacks up blocks $X$, $Y$, $Z$ even if their tops are not clear initially. 
The latter predicate finds and executes a plan to put block $X$ on the 
top of block $Y$. With these meanings, $achieve\_clear$, $achieve\_stack$ and 
$achieve\_on$ can be defined as follows [$BK95$]:
\myeqnbegin
achieve\_stack(X,Y,Z) & \leftarrow\ & achieve\_on(Y,Z) \otimes\ achieve\_on(X,Y). \\
achieve\_on(X,Y) & \leftarrow\  & achieve\_clear(X) \otimes\ achieve\_clear(Y) 
		\otimes\ move(X,Y). \\
achieve\_clear(X) & \leftarrow\ & isclear(X). \\
achieve\_clear(X) & \leftarrow\ & on(Y,X) \otimes\ achieve\_clear(Y) \otimes\
		 clear(Z) \otimes\ Z \neq\ Y \otimes\ move(Y,Z). \nonumber \\
\myeqnend
The above rules are straightforward. For instance, in the last rule, 
in order to clear block X, anything on the top of block X is moved 
somewhere that is clear. However, this intuitive definition is not completely 
correct since achieving some subgoals may destroy previously 
achieved subgoals. For instance, in the rule for $achieve\_stack(X,Y,Z)$, 
after successfully putting block $Y$ on top of block $Z$, the subgoal 
$achieve\_on(X,Y)$ may undo the effect of $achieve\_on(Y,Z)$, and so, 
after finishing execution, block $Y$ may not be on the top of block $Z$. 
To overcome this problem, the postcondition $on(Y,Z)$ should be included 
in the rule as follows [$BK95$]:
\myeqnbegin
achieve\_stack(X,Y,Z) & \leftarrow\ & achieve\_on(Y,Z) \otimes\
		 achieve\_on(X,Y) \otimes\ on(Y,Z). 
\myeqnend
So, after the first two subgoals, if block $Y$ is not on the top of 
block $Z$, the system will backtrack and try other possible ways to 
achieve the stack. Note that the postcondition $on(X,Y)$ can be omitted 
because it is guaranteed by the subgoal $achieve\_on(X,Y)$.

The rest of this section describes another, more efficient way to 
avoid subgoal interaction, as proposed in [$BK95$]. Consider the second 
rule $achieve\_on(X,Y)$, the subgoal $move(X,Y)$ guarantees that both block $X$ and block $Y$ are 
clear, and will backtrack if either of them is not clear. However, 
it is possible to avoid too much backtracking, and therefore, increase 
efficiency. Once a block is clear, we can lock the block to avoid putting
anything on top of it again. This is achieved by introducing a 
base predicate $locked\_clear(X)$ which means the atom $clear(X)$ is 
locked. We can lock and unlock block $X$ by inserting and deleting 
$locked\_clear(X)$ from the database. The modified rules for $achieve\_on$ 
are as follows [$BK95$]:
\myeqnbegin
achieve\_on(X,Y) & \leftarrow\ & on(X,Y).  \\
achieve\_on(X,Y) & \leftarrow\ & \neg\ on(X,Y) \\
	     & &  achieve\_clear(X) \otimes\ ins:locked\_clear(X) \otimes\ \nonumber \\
	     & &  achieve\_clear(Y) \otimes\ del:locked\_clear(X) \otimes\ \nonumber \\
	     & &  move(X,Y). \nonumber 
\myeqnend
We also have to modify the definition of putdown to ensure the robot does 
not put a block onto a locked block [$BK95$]. 
\myeqnbegin
putdown(X,Y) & \leftarrow\ & clear(Y) \otimes\ X \neq\ Y \otimes\ ins:on(X,Y)) \otimes\ \\
	     & &  \neg locked\_clear(Y) \otimes\  del:clear(Y).	\nonumber
\myeqnend
In this way, once a block is cleared and locked, no other block can be 
put on top of it until it is unlocked. Unfortunately, However, this 
program is very inefficient for some anomalous situations, in which the 
stacking is obviously impossible. For example, the command 
$?- stackTwoBlocks(blkA,blkB,blkA)$ is clearly impossible in any blocks 
world, but the system is not clever enough to figure this out, and 
needs to search all possible moves exhaustively. There are many other 
possible optimizations, which we leave for future work.

\section{Graph Algorithms}

In computer science, engineering, mathematics, and many other areas, 
problems are represented by the relationships among data. Graphs are  
often used to model such relationships. Most graph algorithms are 
presented in procedural programming style, and they are difficult to 
translate into logic programs. As described earlier, \TR integrates 
logic programming and procedural programming, so we can use it to 
implement graph algorithms conveniently. In this section, we shall see 
how algorithms for finding connected components, all pairs shortest path, 
Hamiltonian cycle, and maximum clique can be implemented in \TRR. In these 
problems, the graph is stored in the database as two relations: $node(X)$ 
and $edge(X,Y)$. The former means that $X$ is a node, and the latter means 
there is a directed edge from node $X$ to node $Y$ in the graph.

\subsection{Polynomial Time Algorithms}

Transaction Logic can express loops from procedural programming, 
which allows simple translation of an algorithm to a \TR program. The 
following examples show the simple use of while loops and for loops in \TR 
program. Detailed implementation are shown in section 4.3.8.

\begin{enumerate}
\item $forall\; [X,Y]\; in\; p(X,Y)\; do\; ins:q(X,Y)$  \\
	select all possible values of $X$ and $Y$ such that $p(X,Y)$ is true,
	and insert $q(X,Y)$ into the database.
\item $with\; [Y]\; forall\; [X]\; in\; p(X,Y)\; do\; ins:q(X,Y)$ \\
	with the value of $Y$ imported from outside the loop, select all 
	possible values of $X$ such that $p(X,Y)$ is true, and insert 
	$q(X,Y)$ into database.
\item $while\; p(X,Y)\; do\; q(X,Y)$ \\
 	call $q(X,Y)$ until $p(X,Y)$ is no longer true for any $X$ or $Y$.
\item $with\; [Y]\; while\; p(X,Y)\; do\; q(X,Y)$ \\
	with the value of $Y$ imported from outside the loop, 
	call $q(X,Y)$ until $p(X,Y)$ is no longer true for any $X$ or $Y$.
\end{enumerate}

The following examples show the use of \TR in two P-time algorithms.

\subsubsection{Example 1: Connected Components}

A connected component of a graph G is a maximal connected subgraph.
One method of finding a connected component is to pick an arbitrary 
vertex and then use depth first search to reach all vertices in the 
same component. This process continues until all vertices have been visited.

\vspace{1.0in}
The following is a simple algorithm of finding connected component by 
depth first search:
\begin{small}
\begin{quote}
\em	
	findComponent: 
	\begin{quote}
		mark all vertices v as unvisited; \\
		for each vertex v do; \\
		if v is not visited then dfs(v,v) \\
		(i.e., start searching a new component with name v)
	\end{quote}
	dfs(c,v): (c is the component name, and v is a vertex in the component)
	\begin{quote}
		record that node v is in component c; \\
		mark v as visited; \\
		for each unvisited vertex w such that edge(v,w) do 
		\begin{quote}
				dfs(c,w) 
		\end{quote}
	\end{quote}
\end{quote}
\end{small}
A sample \TR program for the above algorithm is:
\myeqnbegin
findComponents & \leftarrow\ &	
		unvisited(P) := node(P)\; \otimes\ \\
	& &	while\; unvisited(V)\; do\; dfs(V,V). \nonumber \\
dfs(C,V) & \leftarrow\	& 
		ins:component(C,V) \otimes\ \\
	& &	del:unvisited(V) \otimes\ 	\nonumber \\
	& &	with\; [C,V]\; while\; (edge(V,W),\; unvisited(W))\; do\; 
			dfs(C,W). \nonumber
\myeqnend
Note that the \TR program is almost a direct translation of the 
algorithm.

\subsubsection{Example 2: All-Pairs Shortest Paths}

Another famous P-time problem is the all-pairs shortest paths program. 
In this problem, we have to  construct a table that gives the shortest 
distance from any node to any other node in a graph. 

Dijkstra's algorithm uses a ``greedy'' technique to solve the 
shortest path problem. It keeps a set of vertices whose shortest distance 
from the source is already known. At each step, it adds to the set a 
vertex with the next shortest distance to the source. Since the algorithm 
visits the vertices radially from the source, it eventually finds the 
shortest distance from the source to each vertex.

In an unweighted graph, Dijkstra's algorithm is equivalent to a 
breadth first search of the graph starting from the source. We can solve 
the all-pairs shortest path problem on such graphs by doing a breadth first 
search from each vertex in the graph. 
The rule $bfs$ in the following program
implements a modification of Dijkstra's algorithm. 
Starting from a source, $v$, it repeatedly finds all the unvisited 
neighbors of the ``wave front'', using the predicate $newfront$. A wave 
front is a list of vertices in the next level of search. In an 
unweighted graph, all vertices in the same wave front have the same 
distance from the source. For example, the first level of wave front 
from $v$ is the neighbors of $v$ (i.e., with distance 1 from $v$), and the 
following level of wave front is the neighbors of the previous wave 
front (i.e., with distance 2 from $v$). At each level of search,
the program stores the distances from $v$ 
to the nodes in the wave front are stored.

\begin{quote}
\begin{small}
\em
	apsp: 
	\begin{quote}
	for each vertex v do bfs(v)
	\end{quote}
	bfs(v): 
	\begin{quote}
	record v as the current wavefront list; \\
	D = 0; \\
	assign distance from v to v to 0; \\
	repeat until the current wavefront list is empty do 
		\begin{quote}
		repeat the wavefront list with all vertices in the next level  \\
		(i.e., unvisited neighbors of the vertices in the current wavefront list) \\
		D := D+1; \\
		assign the distances D from v to the vertices in wavefront list  \\
		\end{quote}
	\end{quote}
\end{small}
\end{quote}

Here is the corresponding \TR program:
\myeqnbegin
apsp & \leftarrow\ & ins:tempD(0) \otimes\ \\
	& & 	 for \ [V] \ in \ node(V) \  do \ bfs(V). \nonumber \\
bfs(V) & \leftarrow\ & front(X) := front(V) \otimes\ \\
	& &	del:tempD(\_) \otimes\ ins:tempD(0) \otimes\ \nonumber \\
	& &	ins:dist(V,V,0) \otimes\ 		\nonumber \\
	& & 	with \ [V] \ while \ newFront(V,\_) \ do  \nonumber \\
	& &	( 					\nonumber \\
	& &	\hspace{.3in}del:tempD(T) 		\nonumber \\
	& &	\hspace{.3in}D \ is \ T+1 \otimes\ 	\nonumber \\
	& &	\hspace{.3in}ins:tempD(D) \otimes\ 	\nonumber \\
	& &	\hspace{.3in}front(M) := newFront(V,M) \otimes\ 	\nonumber \\
	& &	\hspace{.3in}dist(V,N,D) := (front(N), dist(X,Y,Z)) 	\nonumber \\
	& &	).					\nonumber
\myeqnend
We also have to define the rule of $newFront(R,N)$. A vertex $N$ 
belongs to the new wave front if it is unvisited and is a neighbor 
of one of the front vertices. A vertex is visited if its distance 
from the source has been calculated:
\myeqnbegin
visited(R,N) & :- & dist(R,N,\_). \\
newFront(R,N) & :- & front(M), edge(M,N), not(visited(R,N)). 
\myeqnend
Since the rule newFront is involved in a relational assignment in the \TR 
program, and relational assignment is defined for database predicates only, 
the above rules should be defined in the database instead of in the 
transaction base.
We will explain the \TR program on the following graph:
\begin{figure*}[h]
	\hfil\epsfbox{apsp1.ps}
\end{figure*}

Starting with the source $v1$, it has distance 0 to $v1$ itself, and 
it is the only vertex in the wave front. The predicate newfront is 
defined as unvisited neighbors of the vertices in the wave front. 
In the first iteration, the neighbors of $v1$, $(v2, v4, v6)$, are 
found, and inserted into the predicate front as the next front wave. 
Also, all these nodes have distance 1 from the source. In the next 
iteration, the program finds the unvisited neighbors of $(v2, v4, v6)$, 
which are $(v3, v5)$. The vertices $v3$ and $v5$ have distance 2 from the 
source. Since there is no more unvisited vertices, the program terminates.

The database evolves as follows:
\[
\begin{array}{clc}
Before \ iteration: &	After \ first \ iteration: & After \ second \ iteration: \\
dist(v1,v1,0)	&	dist(v1,v1,0)	&	dist(v1,v1,0) \\
front(v1) 	&	dist(v1,v2,1)	&	dist(v1,v2,1) \\
tempD(0)	&	dist(v1,v4,1)	&	dist(v1,v4,1) \\
		&	dist(v1,v6,1)	&	dist(v1,v6,1) \\ 
		&	front(v2)	&	dist(v1,v3,2) \\
		&	front(v4)	&	dist(v1,v5,2) \\
		&	front(v6)	&	front(v3) \\ 
		&	tempD(1)	&	front(v5) \\
		&			&	tempD(2)  
\end{array}
\]

\subsection{NP-Complete Problems}

The class NP has the characteristic that all known algorithms 
for solving NP-complete problems run in exponential time. Typically,
these algorithms search a space of exponential size until a solution
is found. Since \TR program allows backtrackable updates, 
formulating such search problems is relatively easy in \TRR.

\subsubsection{Example 1: Hamiltonian Cycles}
A Hamiltonian path is a path which visits each vertex in a graph 
exactly once. Similarly, a Hamiltonian cycle is a Hamiltonian path 
together with an edge connecting the first and the last vertices on 
the path.

One way to find Hamiltonian paths is to use depth first search to 
exhaustively check all possible paths until a Hamiltonian path is found. 
If there is an edge connecting the two ends, the path, together with 
the edge, is a Hamiltonian cycle.
\myeqnbegin
Transaction\; Program: & & 	\nonumber \\
\nonumber \\
findhamo & \leftarrow\ & 
		unvisited(P) := node(P) \otimes\ 	\\
	& &	del:unvisited(X) \otimes\ 		\nonumber \\
	& &	searchpath(X,X). 			\nonumber \\
searchpath(S,X) & \leftarrow\ &
		edge(X,Y) \otimes\ \\
	& &	del:unvisited(Y) \otimes\ 		\nonumber \\
	& &	ins:cycle(X,Y) \otimes\ 		\nonumber \\
	& &	searchpath(S,Y). 			\nonumber \\
searchpath(S,X) & \leftarrow\ & 
		\neg\ uninvisited(Y) \otimes\ \\
	& &	edge(X,S) \otimes\ 			\nonumber \\
	& &	ins:cycle(X,S) 				\nonumber 
\myeqnend
The predicate $findhamo$ first marks all nodes as unvisited. Then, it 
chooses a node as the start node and repeatedly searches for a Hamiltonian 
path. $Rule\ 3.34$ searches for an unvisited neighbor, adds the edge into 
the cycle, and then continues the search starting from the neighbor. 
$Rule\ 3.35$ defines the termination condition to be when all nodes are 
visited (which means a Hamiltonian path has been found), and there is an 
edge connecting the last node and the starting node (which converts 
the path to a cycle).

We use the following graph to illustrate the execution of the
program: 
\begin{figure*}[h]
	\hfil\epsfbox{hamo1.ps}
\end{figure*}
\begin{enumerate}
\item Suppose, $v1$ is the starting node. $Rule\ 3.33$ marks all nodes 
	as unvisited except $v1$. So, in addition to the graph itself,
	the database now contains:
\mytabbegin
		unvisited(v2), unvisited(v3), unvisited(v4)
\mytabend

\item Using $Rule\ 3.34$, the system selects $v2$ as the next node and 
	stores $(v1,v2)$ as the first edge on the Hamiltonian cycle. 
	In subsequent calls to $Rule\ 3.34$, edges $(v2,v3)$ and 
	$(v3,v4)$ are chosen. The database now contains:
\mytabbegin
		cycle(v1,v2), cycle(v2,v3), cycle(v3,v4)
\mytabend

\item Since there are no unvisited adjacent nodes from $v4$, $Rule\ 3.35$ 
	tests the termination condition. However, since there is no 
	edge between $v4$ and $v1$, the termination condition fails and 
	the program backtracks. 

\item The program backtracks until $v3$ and $v4$ are unvisited. At this 
	time, the database contains:
\mytabbegin
		unvisited(v3), unvisited(v4), cycle(v1,v2)
\mytabend

\item In $Rule\ 3.34$, rather than choosing $edge(v2,v3)$, the program 
	unifies $edge(X,Y)$ to $edge(v2,v4)$, which becomes an edge of 
	the growing path. In the next step, $Rule\ 3.34$ chooses the 
	$edge(v4,v3)$ as the next edge of the path, and the database becomes:
\mytabbegin
		cycle(v1,v2), cycle(v2,v4), cycle(v4,v3) 
\mytabend

\item Finally, the program terminates by choosing $edge(v3,v1)$
	as the final edge in the cycle. Therefore, the Hamiltonian 
	cycle is: $(v1,v2,v4,v3,v1)$.
 
\end{enumerate}

\subsubsection{Example 2: Clique}

A $k-clique$ is a set of $k$ vertices, each pair of which is connected by 
an edge, i.e., it is a complete graph with $k$ nodes. It is a NP-complete 
problem to find a $k-clique$ in a graph, where $k$ is part of the input to 
the problem.

Since a clique is a complete graph, there are $k(k-1)$ directed edges 
in a clique with $k$ vertices. The following \TR program specifies an 
algorithm that determines whether there is a {\em k-clique} in a graph:
\myeqnbegin
cliqueSize(K) & \leftarrow\ &
		node(N) \otimes\ \\
	& &	candidate(CN) := edge(N,CN) \otimes\ 	\nonumber \\
	& &	buildClique(K,N). 			\nonumber \\
buildClique(1,\_). & & \\
buildClique(K,N1) & \leftarrow\ & 
		K>1 \otimes\ \\
	& &	candidate(CN) := newCandidate(N1,CN) \otimes\ 	\nonumber \\
	& &	candidate(N2) \otimes\ 		\nonumber \\
	& &	K1\; is\; K-1 \otimes\ 		\nonumber \\
	& &	buildClique(K1,N2).		\nonumber 
\myeqnend
Database rule:
\myeqnbegin
	newCandidate(N,CN) & :- & candidate(CN), edge(N,CN).
\myeqnend
The predicate $cliqueSize$ arbitrarily picks a node $N$ and marks all 
neighbor nodes as candidates for a clique containing node $N$. With
this set of candidate nodes, the program starts to build a k-clique.
In general, a candidate set holds those nodes which are neighbors of 
{\em all} previously visited nodes. The predicate $newCandidate(N,CN)$ 
is defined to find a new candidate node $CN$, which is the neighbor of 
$N$, from the current candidate set. 
Using $newCandidate$, the predicate $buildClique(K,N)$ builds the k-clique 
by shrinking the candidate set. Since all nodes in the candidate set are 
neighbors of the input node, $N$, if there is a k-clique in the original 
candidate set, there will be a $(k-1)$-clique in the new candidate set. 
If such clique is not found, it backtracks and starts with other nodes. 

\begin{figure*}[h]
	\hfil\epsfbox{clique1.ps}
\end{figure*}

For example, in the above graph, the transaction query $?- cliqueSize(3)$ 
should hold because the graph has a clique of size 3, $(v2, v3, v4)$. 
The following shows the candidate sets and the subgoals of $buildClique$ 
made during the execution:
\begin{enumerate}
\item Suppose $v1$ is picked as the first node. Then the candidate 
	set is initially: \{$v2$\}, and a subgoal $buildClique(3,v1)$, 
	is invoked.
\item During the execution of the subgoal $buildClique(3,v1)$, the new 
	candidate set is still \{$v2$\} and the subgoal 
	$buildClique(2,v2)$ is invoked.
\item Node v2 is the only atom left in the candidate set. Since the new 
	candidate set is empty, $buildClique(2,v2)$ fails. 
\item Since there is no alternative choice in $buildClique$, the 
	process backtracks to the initial state and picks $v2$ in
	$Rule\ 3.36$. There are two adjacent nodes and the candidate set 
	now contains \{$v3,v4$\}. 
\item Suppose $v3$ is chosen in the candidate set, the next subgoal is 
	$buildClique(2,v3)$. Its adjacent node $v4$ is also in the 
	candidate set and so the new candidate set becomes \{$v4$\} 
	and a new subgoal $buildClique(1,v4)$ is invoked. 
\item The subgoal $buildClique(1,v4)$ succeeds immediately, and so the 
	query $cliqueSize(3)$ succeeds.
\end{enumerate}

As mentioned above, a candidate set holds the nodes which are neighbors 
of all previously visited nodes.  For example, in step 4 above, the 
candidate set \{$v3,v4$\} is the set of neighbors of $v2$. In step 5, the 
candidate set \{$v4$\} is the joint neighbor set of previously visited,
nodes $v3$ and $v2$. Therefore, these three nodes are vertices in the 
{\em 3-clique}.

The complexity of $cliqueSize(K)$ grows exponentially in the 
number of nodes for an arbitrary graph and value $K$. However, if $K$ is 
fixed, since the depth of recursive calls to $cliqueSize$ is at most $K$, 
the complexity of the program becomes polynomial with degree $K$.

