Database Reference
In-Depth Information
of these classes leads to better complexity bounds for the problem we study. Second, it is
sometimes possible to show that the computational complexity of a data exchange problem
is hard even if restricted to mappings in one of these classes. This will indicate that such
problems are inherently very hard.
4.2 Key problems
As we mentioned in
Chapter 3
, one of the key goals in data exchange is to materialize a
solution that reflects as accurately as possible the given source instance. But before we do
so, we need to ask ourselves if it is possible in principle. And once we have materialized
a solution, we need to use it for query answering. These considerations give rise to three
problems we shall study in this chapter - the existence of solutions, materialization of
solutions, and query answering.
Existence of solutions
M
We now look again at the mapping
from
Example 4.1
. Under this mapping,
every
source
instance has a solution under
. In fact, since the st-tgds do not completely specify the
target, solutions are not necessarily unique and, indeed, there are infinitely many of them
for each source instance.
For the source instance
S
=
M
{
FLIGHT
(
Paris
,
Santiago
,
AirFrance
,
2320)
}
from the ex-
ample, we saw one possible solution
T
=
{
ROUTES
(
⊥
1
,
Paris
,
Santiago
)
,
INFO FLIGHT
(
⊥
1
,
2320
,
⊥
2
,
AirFrance
)
}
.
But others are possible too, for instance
T
=
{
ROUTES
(
⊥
1
,
Paris
,
Santiago
)
,
INFO FLIGHT
(
⊥
1
,
2320
,
⊥
1
,
AirFrance
)
}
,
or even a solution with no nulls:
T
=
{
ROUTES
(
AF
406
,
Paris
,
Santiago
)
,
INFO FLIGHT
(
AF
406
,
2320
,
920
,
AirFrance
)
}
.
M
is the extension of
with the target dependency
(an egd) stating that
src
is a key in
ROUTES(f#,src,dest)
. Then it is no longer true that
every source instance has a solution under
On the other hand, assume that
M
M
. Indeed, consider a source instance
S
=
{
FLIGHT
(
Paris
,
Santiago
,
AirFrance
,
2320)
,
FLIGHT
(
Paris
,
Rio
,
TAM
,
1720)
}
.
We can see that
Σ
st
implies that there are facts of the form
ROUTES
(
x
,
Paris
,
Santiago
) and
ROUTES
(
y
,
Paris
,
Rio
) in every solution
T
for
S
.Butthese
tuples violate the key constraint. Hence,
S
has no solutions under
the first st-tgd in
M
.
This suggests that to materialize a target solution for a given source instance, at the very
