What is View-Based Query Rewriting?

Proc. of the 7th Int. Workshop on Knowledge Representation meets Databases (KRDB 2000). Volume 29 of CEUR Workshop Proceedings, https://ceur-ws.org/. 2000.

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. Based on recent results, we first show that already for very simple query languages, 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. However, a tight connection between view-based query answering and constraint-satisfaction problems, allows us to show that the above characterization is going to be difficult.

@inproceedings{KRDB-2000-rew,
   title = "What is View-Based Query Rewriting?",
   year = "2000",
   author = "Diego Calvanese and De Giacomo, Giuseppe and Maurizio
Lenzerini and Moshe Y. Vardi",
   booktitle = "Proc. of the 7th Int. Workshop on Knowledge Representation
meets Databases (KRDB 2000)",
   pages = "17--27",
   volume = "29",
   publisher = "CEUR-WS.org",
   series = "CEUR Workshop Proceedings, https://ceur-ws.org/",
}