Computing certain answers in the presence of dependencies

In this paper we consider conjunctive queries and views, and we investigate the problem of query answering using views in the presence of dependencies and in particular the problem of finding equivalent and maximally contained rewritings of a query using a set of views in the presence of dependencies. We present an efficient sound and complete algorithm CoreCoverCC which finds equivalent rewritings with the minimum number of subgoals in the presence of weakly acyclic local as view tuple generating dependencies (CLAVw). We also present an efficient algorithm MiniconCC that finds maximally contained rewritings (MCRs) with respect to the language of finite unions of conjunctive queries (UCQ) of a UCQ query Q   in the presence of CLAVw. We also prove that an MCR of a UCQ query Q with respect to UCQ computes all the certain answers of Q   both in the absence and presence of a set of dependencies CC if the chase of Q   with CC terminates (and, in the case of dependencies, if such an MCR exists).