Answering Regular Path Queries Using Views

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",
}