Unique solutions in data exchange under sts mappings
In classical data exchange, multiple solutions may appear and inherently cause many problems. To tackle the problem, one may use a richer language for schema mapping to have a unique solution. Therefore, in the paper, we consider a data exchange setting in which schema mapping contains a set of source-to-target dependencies and a set of target- to-source dependencies (sts mappings). Under the setting, we first study the problem of deciding whether a data exchange setting has a unique solution with respect to a source instance. We show that the problem is as hard as Unique SAT problem and provide some restricted cases where the problem is tractable. Besides, we consider a more general problem that aims to check if a data exchange setting guarantees unique solutions for arbitrary source instances. While the problem is undecidable in general, we still can characterise some fragments where the problem is decidable and complete for some complexity class. Copyright © 2016 for the individual papers by the papers's authors.