Answering Non-Monotonic Queries in Relational Data Exchange

Relational data exchange is the problem of translating relational data from asource schema into a target schema, according to a specification of therelationship between the source data and the target data. One of the basicissues is how to answer queries that are posed against target data. Whileconsensus has been reached on the definitive semantics for monotonic queries,this issue turned out to be considerably more difficult for non-monotonicqueries. Several semantics for non-monotonic queries have been proposed in thepast few years. This article proposes a new semantics for non-monotonicqueries, called the GCWA*-semantics. It is inspired by semantics from the areaof deductive databases. We show that the GCWA*-semantics coincides with thestandard open world semantics on monotonic queries, and we further explore the(data) complexity of evaluating non-monotonic queries under theGCWA*-semantics. In particular, we introduce a class of schema mappings forwhich universal queries can be evaluated under the GCWA*-semantics inpolynomial time (data complexity) on the core of the universal solutions.Comment: 55 pages, 3 figure