Rewriting of regular expressions and regular path queries

Publisher Website
Google Scholar
Abstract
Recent work on semi-structured data has revitalized the interest in path queries, i.e., queries that ask for all pairs of objects in the database that are connected by a path conforming to a certain specification, in partic- ular to a regular expression. Also, in semi-structured data, as well as in data integration, data warehousing, and query optimization, the problem of query rewriting using views is receiving much attention: Given a query and a collection of views, generate a new query which uses the views and provides the answer to the original one. In this paper we address the problem of query rewrit- ing using views 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 expres- sions. 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 lan- guage contained in the one defined by E, otherwise. We present a complexity analysis of both the problem and the method, showing that the latter is essentially opti- mal. Finally, we illustrate how to exploit the method to rewrite regular path queries using views in semi- structured data. The complexity results established for the rewriting of regular expressions apply also to the case of regular path queries.

This publication has 23 references indexed in Scilit: