Computing certain answers in the presence of dependencies

作者:

Highlights:

摘要

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 CoreCoverC 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 MiniconC 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 C if the chase of Q with C terminates (and, in the case of dependencies, if such an MCR exists).

论文关键词:Conjunctive queries,Views,Certain answers,Query rewritings,Dependencies

论文评审过程:Available online 3 September 2009.

论文官网地址:https://doi.org/10.1016/j.is.2009.08.002