Affordable Access

Publisher Website

Determinacy and query rewriting for conjunctive queries and views

Theoretical Computer Science
Publication Date
DOI: 10.1016/j.tcs.2010.12.031
  • Determinacy
  • Views
  • Query Rewriting
  • Query Answering
  • Conjunctive Queries
  • Chain Queries
  • Path Queries
  • First Order Logic


Abstract Answering queries using views is the problem which examines how to derive the answers to a query when we only have the answers to a set of views. Constructing rewritings is a widely studied technique to derive those answers. In this paper we consider the problem of the existence of rewritings in the case where the answers to the views uniquely determine the answers to the query. Specifically, we say that a view set V determines a query Q if for any two databases D 1 , D 2 it holds: V ( D 1 ) = V ( D 2 ) implies Q ( D 1 ) = Q ( D 2 ) . We consider the case where query and views are defined by conjunctive queries and investigate the question: If a view set V determines a query Q , is there an equivalent rewriting of Q using V ? We present here interesting cases where there are such rewritings in the language of conjunctive queries. Interestingly, we identify a class of conjunctive queries, C Q p a t h , for which a view set can produce equivalent rewritings for “almost all” queries which are determined by this view set. We introduce a problem which relates determinacy to query equivalence. We show that there are cases where restricted results can carry over to broader classes of queries.

There are no comments yet on this publication. Be the first to share your thoughts.