Determinacy and query rewriting for conjunctive queries and views

作者：Afrati Foto N^*

来源：Theoretical Computer Science, 2011, 412(11): 1005-1021.

DOI：10.1016/j.tcs.2010.12.031

• Determinacy
• Views
• Query rewriting
• Query answering
• Conjunctive queries
• Chain queries
• Path queries
• First order logic

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, CQ(path), 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.

• 出版日期2011-3-11