Horizontal Query Optimization on Ordered Semistructured Data

The exchange and storage of XML data is becoming increasingly important. In contrast to conventional semistructured data [4, 1], the labels in a document-oriented representation such as XML are ordered. Furthermore, regular expressions (DTDs) describe the horizontal (and vertical) structure of the data. Traditional 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