Querying Data Exchange Settings beyond Positive Queries

Data exchange, the problem of transferring data from a source schema to a target schema, has been studied
for several years. The semantics of answering positive queries over the target schema has been defined
in early works, but little attention has been paid to more general queries. A few semantics proposals for
more general queries exist but they either do not properly extend the standard semantics under positive
queries, giving rise to counterintuitive answers, or they make query answering undecidable even for the
most important data exchange settings, e.g., with weakly-acyclic dependencies.
The goal of this paper is to provide a new semantics for data exchange that is able to deal with general
queries. At the same time, we want our semantics to coincide with the classical one when focusing on
positive queries, and to not trade-off too much in terms of complexity of query answering. We show that
query answering is undecidable in general under the new semantics, but it is coNP-complete when the
dependencies are weakly-acyclic. Moreover, in the latter case, we show that our semantics allow for
the construction of a representative target instance, similar in spirit to a universal solution, that can be
exploited for computing approximate answers, instead of exact ones.