Fifteenth Annual IEEE Symposium on

Logic in Computer Science (LICS 2000)

Paper: View-Based Query Processing and Constraint Satisfaction (at LICS 2000)

Authors: Diego Calvanese Giuseppe de Giacomo Maurizio Lenzerini Moshe Y. Vardi


View-based query processing requires answering a query posed to a database only based on 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 conjunctive regular-path queries with a fixed number of variables.


    author = 	 {Diego Calvanese and Giuseppe de Giacomo and Maurizio Lenzerini and Moshe Y. Vardi},
    title = 	 {View-Based Query Processing and Constraint Satisfaction},
    booktitle =  {Proceedings of the Fifteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2000},
    year =	 2000,
    editor =	 {Martin Abadi},
    month =	 {June}, 
    pages =      {361--371},
    location =   {Santa Barbara, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}