Answering Non-Monotonic Queries in Relational Data Exchange

摘要

Relational data exchange deals with translating a relational database instance over some source schema into a relational database instance over some target schema, according to a schema mapping that specifies the relationship between the source data and the target data. Various semantics for answering queries against the target schema exist, each of them suitable for a certain class of queries, and with respect to certain schema mappings. However, for each of these semantics, there are examples that show that it leads to counter-intuitive answers, or that it does not respect logical equivalence of schema mappings. In this article, we study query answering semantics for deductive databases in the context of relational data exchange. Furthermore, we propose a new semantics, called GCWA'-answers semantics, which seems to be well-suited with respect to a number of schema mappings, including schema mappings defined by st-tgds and egds. We show that the GCWA*-answers semantics coincides with the classical certain answers semantics on monotonic queries, and we further explore the data complexity of computing the GCWA*-answers to non-monotonic queries. In particular, we identify a class of schema mappings for which the GCWA*-answers to universal queries can be computed from the core of the universal solutions in polynomial time (data complexity).