\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$.