| Our aim is to speed up the processing of queries on XML data. Such queries and data are abundant on the world wide web, making this a timely research topic. As XML documents are structured as trees, an important part of each query is about navigation in trees. This is done by the W3C-standard language XPath. Each XPath statement can be transformed into an algebraic expression evaluated on trees. Independent of the physical representation of the XML-trees, algebraically equivalent expressions may differ in the time needed to evaluate them. Hence, rewriting expressions can lead to speed-ups. Such rewriting is best done at the algebraic level, just as in the case of relational databases. The innovative part of the project is that we start with finding a complete axiomatization of the set of algebraic identities. Based on these we search for optimal rewrite strategies, which is the challenging part. We believe that the insights gained from the mathematical-logical task of axiomatization give us an advantage in finding optimal rewrite rules. The project is interdisciplinary in its direct link between classical mathematics (algebraization) and practical computer-science (XML processing), in fact with the Internet of today. |
