Database Reference
In-Depth Information
Summary
In summary, the following holds for the problem of existence of universal solutions in
relational data exchange:
•
For arbitrary relational mappings defined by (st)-tgds and egds the problem is undecid-
able. Moreover, the existence of solutions does not necessarily imply the existence of
universal solutions.
•
For the class of relational mappings
Σ
t
consists of a set
of egds and a weakly acyclic set of tgds, the problem becomes decidable (using the
chase procedure), and, indeed, tractable. In addition, the existence of solutions implies
the existence of universal solutions.
M
=(R
s
,
R
t
,
Σ
st
,
Σ
t
) such that
•
For the latter class of mappings, and in the case when a source instance
S
has solutions,
a canonical universal solution
T
for
S
can be computed in polynomial time.
6.4 The core
We start this section with an example.
Example 6.12 (
Example 4.1
continued) Consider the source instance
S
=
{
FLIGHT
(
Paris
,
Amsterdam
,
KLM
,
1410)
,
FLIGHT
(
Paris
,
Amsterdam
,
KLM
,
2230)
,
GEO
(
Paris
,
France
,
2
M
)
}.
There are no target constraints, so the chase computes the canonical universal solution
T
for
S
:
{
ROUTES
(
⊥
1
,
Paris
,
Amsterdam
)
,
ROUTES
(
⊥
3
,
Paris
,
Amsterdam
)
,
INFO FLIGHT
(
⊥
1
,
1410
,
⊥
2
,
KLM
)
,
INFO FLIGHT
(
⊥
3
,
2230
,
⊥
4
,
KLM
)
,
SERVES
(
KLM
,
Paris
,
France
,
⊥
5
)
,
SERVES
(
KLM
,
Paris
,
France
,
⊥
6
)
}
.
T
∗
Now consider
the
instance
obtained from
T
by
removing the
tuple
⊥
6
).Then
T
∗
is also a solution for
S
, and, moreover,
there are homomorphisms
h
:
T
SERVES
(
KLM
,
Paris
,
France
,
T
∗
(that is the identity on every element except
→
⊥
6
,
T
(simply because
T
∗
is contained in
T
). It follows
therefore that
T
∗
is also a universal solution for
S
.
⊥
5
)and
h
∗
:
T
∗
→
where
h
takes value
We can draw an interesting conclusion from this example: among all possible universal
solutions, the canonical universal solution is not necessarily the smallest, as
T
∗
is strictly
contained in
T
. Moreover, in the example,
T
∗
is actually the smallest universal solution (up
to isomorphism).
The first natural question is whether there is always a unique smallest universal solution.
As we will see later, this question has a positive answer. It can be argued that this smallest
