XPath is a language for navigating an XML tree and returning a set of
answer nodes.  These expressions are used in XQuery \cite{xquery}, XML
Schema \cite{xmlschema}, XLink \cite{xlink}, and XPointer
\cite{xmlptr}.  In addition they are often used to query large XML
databases such as the PIR-International Protein Sequence Database
\cite{pirdb}.

Document Type Definitions (DTDs) provide a means of constraining XML
documents by defining their structure.  A DTD is commonly modeled as a
number of expressions $n \rightarrow R$ where $R$ is a regular
expression describing the children that are allowed to appear directly
beneath nodes labeled $n$.

Databases are more commonly being stored as XML, and database queries
are then being carried out through XPath evaluation.  It is therefor
imperative for these queries to perform efficiently.  That said, a
common problem when evaluating XPath queries on XML documents is that,
at a given node, we don't necessarily know what are the ``meaningful''
nodes to explore next -- i.e. what nodes could possibly lead to the
result set of query.  Luckily, there is an analogous problem in
traversing object graphs in Adaptive Programming (AP).

AP is a technique for Object-Oriented programming in which traversals
of objects are specified in \term{strategies} \cite{karl:demeter}.  In
this setting a \term{class graph} specifies the layout of objects that
are arranged in an \term{object graph}.  A user may then specify
traversals over this object graph by writing \term{strategies}.  
These
strategies are written as a graph where each edge defines a set of paths that
must be visited in a traversal.  If we view the class graph
and strategy as automata we can create a \term{traversal graph} from
the cross product of the strategy and class graph.  Thus, we can
ignore paths that could never lead to an accepting state, and the
object graph can be efficiently traversed \cite{973102}.

In this paper we focus on improving the performance of XPath queries
for XML documents whose DTD is available by making use of this meta
information.  We draw the following connection between the XML and
AP worlds, also shown in Table \ref{tab:rel}: XML
documents can be modeled by unordered trees; object graphs are
unordered graphs.  DTDs define the structure of XML documents; class
graphs define the structure of object graphs.  XPath expressions
define the nodes to visit when navigating an XML tree; strategies
define the nodes to visit when navigating an object graph.

\begin{table}
\begin{center}
\begin{tabular}{ll}
{\bf XPath} & {\bf Adaptive Programming} \\
DTD & Class graph \\
XML document & Object graph \\ 
XPath expression & Strategy \\
\end{tabular}
\label{tab:rel}
\caption{Relating XPath to Adaptive Programming}
\end{center}
\end{table}

We first show that evaluating XPath queries
without meta-information may be exponentially slower than with
meta-information.  We then show how to use meta-information to speed
up query evaluation.