6 - Good solutions

Summary

As we know by now, solutions in data exchange are not unique; indeed, if a source instance has a solution under a relational mapping M, then it has infinitely many of them. But if many solutions exist, which one should we materialize? To answer this question, we must be able to distinguish good solutions from others. As we already mentioned in Section 4.2, good solutions in data exchange are usually identified with the most general solutions (see Example 4.3), whichinturn can be characterized as the universal solutions. We will see in this chapter that universal solutions admit different equivalent characterizations.

The existence of solutions does not in general imply the existence of universal solutions (in fact, checking whether universal solutions exist is an undecidable problem). However, this negative theoretical result does not pose serious problems in data exchange. Recall from the previous chapter that the class of mappings M = (R_s, R_t, Σ_st, Σ_t), such that Σ_t consists of a set of egds and a weakly acyclic set of tgds, is particularly well-behaved for data exchange. Indeed, for this class the existence of solutions – that is undecidable in general – can be checked in polynomial time, and, in case a solution exists, at least one solution can be efficiently computed. We will see in this chapter that for this class, the existence of solutions implies the existence of universal solutions. Furthermore, when one exists, it can be efficiently computed.