Abstract
Query answering using views amounts to computing the answer to a query having information only on the extension of a set of views. This problem is relevant in information integration over the web, where data are typically modeled by means of semi-structured mechanisms. We address query answering using views in a context where both the query and the views are expressed in terms of regular expressions (regular path queries), and denote the pairs of objects in the database connected by a matching path. This setting is typical in those cases where the database is conceived as a graph, such as in semi-structured data. In particular, we study algorithms for answering regular path queries using views under different assumptions, namely, closed and open domain, and sound, complete, and exact information on view extensions. We characterize data, expression and combined complexity of the problem, showing that the proposed algorithms are essentially optimal.