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.