Database Reference
In-Depth Information
6
Good solutions
As we know by now, solutions in data exchange are not unique; indeed, if a source instance
has a solution under a relational mapping
, 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
), which in turn 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
Σ
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. The reason behind these good properties is that
the result of a successful chase sequence for a source instance with
M
=(R
s
,
R
t
,
Σ
st
,
Σ
t
), such that
t
is always a
universal solution. Hence, the class of mappings that behaves well with respect to checking
for the existence of solutions also behaves well if one wants to materialize solutions with
good properties.
We will see in
Chapter 7
that universal solutions are also crucial for the task of query
answering in data exchange. In particular, all the positive properties of universal solutions
we show in this chapter will be later used to obtain efficient query evaluation algorithms
for relevant fragments of the relational algebra in a data exchange scenario.
Σ
st
and
Σ
6.1 Universal solutions
How do we formally define the notion that a solution is as general as any other solution?
To do so, recall that a solution
T
is in general an instance with nulls. Such an instance
