Database Reference
In-Depth Information
5
Existence of solutions
Before we address the problem of materializing target instances, we need to address a more
basic problem, that is, whether solutions exist in the first place. As we already mentioned,
the most general version of this problem is undecidable. To obtain decidability - and, as it
turns out, tractability as well - one has to restrict the class of relational mappings. We show
that there is a simple syntactic restriction that only depends on the class of tgds used in tar-
get constraints
Σ
t
and that guarantees these good properties. In order to obtain tractability
for this syntactic class we make use of the well-known chase procedure, which was first
developed in the early 1980s as a tool for checking the implication of data dependencies.
5.1 The problem and easy cases
Recall that in this chapter we study the problem of existence of solutions in data exchange,
defined as follows:
PROBLEM
:
OL
E
XISTENCE
M
.
INPUT:
A source instance
S
.
QUESTION
:
Is there a solution for
S
under
M
?
We start by analyzing some easy cases of the problem, and show the following.
•
In the absence of target dependencies the problem is trivial for mappings specified by
st-tgds: every source instance has a solution.
•
If we use more powerful mappings, in which source-to-target constraints are specified
by arbitrary FO sentences, then the problem is undecidable.
Relational mappings without target dependencies
We now consider relational mappings of the form
M
=(R
s
,
R
t
,
Σ
st
), i.e., mappings without
target dependencies, in which all dependencies in
Σ
st
are st-tgds. In this case, the problem
of the existence of solutions becomes trivial, that is, every source instance has a solution
(in fact, infinitely many of them). Furthermore, for each source instance
S
, a solution
T
for
S
can be constructed in polynomial time. In fact, it is the same procedure that we used in
the last chapter to produce a solution
T
on page
39
for the instance
S
from
Example 4.1
.
