Horizontal Query Optimization 
              on Ordered Semistructured Data
 
                     Hartmut Liefke
 
 
 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.
 
 In this talk, I will describe a query language for querying ordered
 semistructured data. This query language provides primitives for
 specifying more powerful queries on ordered semistructured data.
 Furthermore, I will describe how type information in DTDs is used to
 optimize queries based on horizontal finite state automata.