## Answering Regular Path Queries Using Views

**Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and
Moshe Y. Vardi**
*Proc. of the 16th IEEE Int. Conf. on Data Engineering (ICDE
2000).* 2000.

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 several fields, such as query
optimization, information integration, data warehousing, mobile
computing, and maintaining physical data independence. 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.

@inproceedings{ICDE-2000,
title = "Answering Regular Path Queries Using Views",
year = "2000",
author = "Diego Calvanese and De Giacomo, Giuseppe and Maurizio
Lenzerini and Moshe Y. Vardi",
booktitle = "Proc. of the 16th IEEE Int. Conf. on Data Engineering
(ICDE 2000)",
pages = "389--398",
doi = "10.1109/ICDE.2000.839439",
}

ps.gz
pdf