Database Reference
In-Depth Information
Proposition 5.1
Σ
st
consists of a
finite set of st-tgds. Then every source instance S has infinitely many solutions under
Let
M
=(R
s
,
R
t
,
Σ
st
)
be a relational mapping, where
M
.
Moreover, at least one solution for S can be constructed in polynomial time.
Proof
We first define a procedure that takes as input a source instance
S
and computes a
solution
T
for
S
. For each st-tgd in
Σ
st
of the form:
R
k
(
x
k
,
w
k
)
,
where
x
and
w
are the tuples of variables that appear in the
x
i
's and the
w
i
's, for 1
w
R
1
(
x
1
,
w
1
)
ϕ
(
x
)
→∃
∧··· ∧
≤
i
≤
k
,
(
a
), choose a tuple
¯
and for each tuple
a
from D
OM
(
S
) of length
|
x
|
such that
S
|
=
ϕ
⊥
of
length
|
w
|
of fresh distinct null values over V
AR
. Then populate each relation
R
i
,1
≤
i
≤
k
,
π
w
i
(
¯
with tuples (
π
x
i
(
a
)
,
⊥
)),where
π
x
i
(
a
) refers to the components of
a
that occur in the
π
w
i
(
¯
positions of
x
i
, and likewise for
⊥
). It is easy to see that the resulting target instance
T
is a solution for
S
under
, as the process ensures that every st-tgd is satisfied. Moreover,
each target instance
T
that extends
T
with new tuples is also a solution for
S
. Thus, every
source instance
S
admits infinitely many solutions. Finally, since
M
M
is fixed, the process
of constructing
T
is done in polynomial time in
S
, since computing sets of tuples
a
such
that
S
|
=
ϕ
(
a
) can be done in polynomial time.
Relational mappings defined in
FO
We mentioned in
Section 4.1
that admitting arbitrary expressive power for specifying de-
pendencies in data exchange easily leads to undecidability of the problem of existence of
solutions. The next result confirms this, even for relational mappings with no target depen-
dencies, and just a single source-to-target dependency given by an FO sentence.
Proposition 5.2
Σ
st
con-
sists of a single
FO
dependency over the symbols in
R
s
and
R
t
, such that the problem
S
OL
E
XISTENCE
M
is undecidable.
This result confirms the fact that relational mappings have to be restricted in order to
become useful for data exchange purposes. A possible proof of
Proposition 5.2
goes by a
rather tedious codification of the halting problem for Turing machines. We postpone the
proof, however, because in the next section we show a stronger result, with a much more
concise and elegant proof, that immediately implies the above.
There exists a relational mapping
M
=(R
s
,
R
t
,
Σ
st
)
,where
5.2 Undecidability for st-tgds and target constraints
The fact that arbitrary expressive power of source-to-target dependencies destroys decid-
ability of the most basic data exchange problem was one of the reasons why in
Section
4.1
we decided to impose a restriction that mappings be of the form
M
=(R
s
,
R
t
,
Σ
st
,
Σ
t
),
where
Σ
t
consists of a finite set of tgds and egds.
So a natural question then is: does this restriction guarantee decidability of the problem
of existence of solutions? It turns out that it is still insufficient for decidability, let alone
efficiency.
Σ
st
consists of a finite set of st-tgds and
