.TH searchtree "" "" "/rdb Command"
.PC "Seek a string node in tree table"
\fBsearchtree [-m[bhirs]] \fItable root goal column1 column2\fR
.PP
.II "directory^search"
.II "tree^search"
.II PROLOG
The command
.B searchtree
searches
.I table
to see if string
.I root
in
.I column1
is associated with
.I goal
in
.IR column2 .
It returns
TRUE to the shell if it find that
.I root
is associated with
.IR goal ,
or FALSE if it is not.
.PP
.I goal
may be within
.IR table ,
in which case the COHERENT command
.B grep
can also find it;
.BR searchtree ,
however, will also see if
.I goal
be reached by a path from
.IR root .
.PP
The options
.B \-m[bhirs]
name the fast-access method to use.
The default is sequential (\fB\-ms\fR).
See the entry for the command
.B search
for a full description of each method of searching.
.PP
.B searchtree
is a breadth-first search that uses the
.B search
fast-access methods to find all of the children at each level of a tree.
This is the kind of search often done in artificial intelligence programs.
However,
.B searchtree
stores its data in a temporary file rather than in memory,
so that it will work on very large data bases.
.PP
Because
.B searchtree
is a shell script, you can modify it to serve many kinds of searches.
For example, you can add a message like
.I yes/no
or
.IR true/false .
You can also add shell code to print out a path.
You might want to use heuristics to guide the search at each
level, and side effects to update data or print messages along the way.
.PP
This kind of searching is also used by the PROLOG language.
.BR searchtree ,
however, differs from PROLOG in two significant respects.
First, PROLOG must have its data base in memory, which
limits the size of the database it can handle.
Second, PROLOG uses depth-first searching, which requires it to backtrack.
.SH Example
Consider the tree represented by table
.BR isa ,
as follows:
.DM
Name    Isa
----    ---
barbara human
bill    human
evan    human
rod     human
human   primate
primate mammal
cat     mammal
dog     mammal
mammal  animal
bird    animal
fish    animal
animal  lifeform
plant   lifeform
.DE
.PP
Remember that all trees, in fact all graphs, can be listed
as tables when the nodes (vertices)
that are connected by a line (arcs) that is on each row.
A directional graph is handled by having one column be
.B From
and another be
.BR To .
.PP
The following command uses
.B searchtree
to examine table
.B isa
to see if entity
.B rod
in column
.B Name
is of type
.B lifeform
as given in column
.BR Isa :
.DM
	searchtree isa rod lifeform Name Isa ; echo $?
.DE
.PP
The command
.B "echo $?"
prints the value returned by
.BR searchtree .
In this case, you see `0' (or FALSE), because
.B rod
is not a
.BR lifeform ;
rather it (or he) is a
.BR human .
.PP
Because
.B searchtree
returns only a status code, you can use it as a test condition.
Your shell program could have a statement like this:
.DM
	prompt "What is your name: "
	read NAME
	if searchtree isa $NAME lifeform Name Isa
	then
        	echo "So, I am talking to a lifeform."
	else
        	echo "So, I am talking to another machine."
	fi
.DE
.PP
The following gives an sample exchange with this script; text in \fBbold\fR
gives what the user types:
.DM
	What is your name: \fBrod\fP
	So, I am talking to a lifeform.
.DE
.PP
The result of the search of the tree was tested by the
.B if
statement, and used to decide which message to print.
.SH "See Also"
.B
search
.R
.SH Notes
.II COHware
If you wish to experiment with PROLOG, volume 2 of
.B COHware
includes the source code to a PROLOG interpreter.
.SO searchtree