Rewriting queries using views with negation

Article type: Research Article

Authors: Afrati, Foto | Pavlaki, Vassia

Affiliations: Department of Electrical and Computer Engineering, NTUA, Greece E-mail: {afrati,vpavlaki}@softlab.ece.ntua.gr

Abstract: Data integration and query reformulation are classical examples of problems that require techniques developed in both AI and database systems fields. In this work we address the problem of rewriting queries using views which has many applications. In particular, we consider queries and views that are conjunctive queries with safe negation (CQNs). We prove that given a CQN query and a set of CQN views, finding equivalent rewritings is decidable in both cases where the rewriting is in the language of CQNs or unions of CQNs. We prove decidability by giving upper bounds on the number of subgoals of the rewritings. We limit the search space of potential equivalent CQN rewritings and Maximally Contained CQN Rewritings (MCRs) to the language of unions of CQs in the case where the query is CQ. Finally, we give a sound and complete algorithm for finding equivalent rewritings in the language of unions of CQNs and we prove that if we consider the rewritings without negated subgoals, then they compute only certain answers under the OWA. Of independent interest is a simple test for checking containment between two unions of CQNs.

Keywords: Query rewritings, negation, data integration

Journal: AI Communications, vol. 19, no. 3, pp. 229-237, 2006