View-Based Query Processing for Regular Path Queries with Inverse

Proc. of the 19th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS 2000). 2000.

View-based query processing is the problem of computing the answer to a query based on a set of materialized views, rather than on the raw data in the database. The problem comes in two different forms, called query rewriting and query answering, respectively. In the first form, we are given a query and a set of view definitions, and the goal is to reformulate the query into an expression that refers only to the views. In the second form, besides the query and the view definitions, we are also given the extensions of the views and a tuple, and the goal is to check whether the knowledge on the view extensions logically implies that the tuple satisfies the query. In this paper we address the problem of view-based query processing in the context of semistructured data, in particular for the case of regular-path queries extended with the inverse operator. Several authors point out that the inverse operator is one of the fundamental extensions for making regular-path queries useful in real settings. We present a novel technique based on the use of two-way finite-state automata. Our approach demonstrates the power of this kind of automata in dealing with the inverse operator, allowing us to show that both query rewriting and query answering with the inverse operator has the same computational complexity as for the case of standard regular-path queries.

@inproceedings{PODS-2000,
   title = "View-Based Query Processing for Regular Path Queries with
Inverse",
   year = "2000",
   author = "Diego Calvanese and De Giacomo, Giuseppe and Maurizio
Lenzerini and Moshe Y. Vardi",
   booktitle = "Proc. of the 19th ACM SIGACT SIGMOD SIGART Symp. on
Principles of Database Systems (PODS 2000)",
   pages = "58--66",
   doi = "10.1145/335168.335207",
}