Affordable Access

Publisher Website

Determinacy and query rewriting for conjunctive queries and views

Authors
Journal
Theoretical Computer Science
0304-3975
Publisher
Elsevier
Publication Date
Volume
412
Issue
11
Identifiers
DOI: 10.1016/j.tcs.2010.12.031
Keywords
  • Determinacy
  • Views
  • Query Rewriting
  • Query Answering
  • Conjunctive Queries
  • Chain Queries
  • Path Queries
  • First Order Logic

Abstract

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.