Horizontal Query Optimization on Ordered Semistructured Data

The exchange  and storage of XML data is  becoming increasingly  important.
In contrast to conventional semistructured data,  the labels in a
document-oriented representation  such as  XML are  ordered.
Furthermore,  regular expressions  (DTDs)  describe  the  horizontal
(and  vertical)  structure.

Conventional query languages for semi-structured data ignore the horizontal
order and are therefore limited in their expressiveness and optimizability.

We describe a query language for querying ordered semistructured data. This
query language provides primitives  for specifying more powerful queries on
ordered semistructured data.  Furthermore, we describe  how horizontal type
information in DTDs is used to optimize queries based on finite automata.