Conjunctive queries determinacy and rewriting
Daniel Pasailă · 2011
The problem of whether a query Q can be answered using a set of views V studies the possibility of computing Q when only the answers to the given set of views are available. In information-theoretic terms, we say that V determines Q iff for any two databases D1, D2, V(D1) = V(D2) implies Q(D1) = Q(D2). In the case that V determines Q, we also study the existence of equivalent rewritings of Q in terms of V in a specific rewriting language. Having a view language ν and a query language Q we say that ν-to-Q determinacy is decidable if there is an algorithm which, given a view V ε ν and a query Q ε Q, outputs whether V determines Q.