Abstract
View-based query processing requires to answer a query posed to a database only on the basis of the information on a set of views, which are again queries over the same database. This problem is relevant in many aspects of database management, and has been addressed by means of two basic approaches, namely, query rewriting and query answering. In the former approach, one tries to compute a rewriting of the query in terms of the views, whereas in the latter, one aims at directly answering the query based on the view extensions. We study view-based query processing for the case of regular-path queries, which are the basic querying mechanisms for the emergent field of semi-structured data. Based on recent results, we first show that a rewriting is in general a co-NP function wrt to the size of view extensions. Hence, the problem arises of characterizing which instances of the problem admit a rewriting that is PTIME. A second contribution of the work is to establish a tight connection between view-based query answering and constraint-satisfaction problems, which allows us to show that the above characterization is going to be difficult. As a third contribution of our work, we present two methods for computing PTIME rewritings of specific forms. The first method, which is based on the established connection with constraint-satisfaction problems, gives us rewritings expressed in Datalog with a fixed number of variables. The second method, based on automata-theoretic techniques, gives us rewritings that are formulated as unions of con-junctive regular-path queries with a fixed number of variables .