Rewriting Regular Expressions in Semi-Structured Data

Proc. of ICDT 1999 Workshop on Query Processing for Semi-Structured Data and Non-Standard Data Formats. 1999.

In this paper we address the problem of query rewriting in the context of semi-structured data. We present a method for computing the rewriting of a regular expression E in terms of other regular expressions. The method computes the exact rewriting (the one that defines the same regular language as E) if it exists, or the rewriting that defines the maximal language contained in the one defined by E, othwerwise. We present a complexity analysis of both the problem and the method, showing the latter is essentially optimal. Finally, we illustrate how to exploit the above mentioned method in order to devise an algorithm for rewriting regular path queries for semi-structured data using views. The complexity results established for the rewriting of regular expressions apply also to the case of regular path queries.

@inproceedings{ICDT-1999-WS,
   title = "Rewriting Regular Expressions in Semi-Structured Data",
   year = "1999",
   author = "Diego Calvanese and De Giacomo, Giuseppe and Maurizio
Lenzerini and Moshe Y. Vardi",
   booktitle = "Proc. of ICDT 1999 Workshop on Query Processing for
Semi-Structured Data and Non-Standard Data Formats",
}