Database Reference
In-Depth Information
always coincides with the existence of universal solutions, and, therefore, the problem
of existence of universal solutions is tractable. Furthermore, if a solution exists, then a
particular universal solution - called
canonical
universal solution - can be materialized in
polynomial time.
Finally, in
Section 6.4
we address the problem of computing the
smallest
universal so-
lution, which can be understood as the problem of computing a universal solution with the
least amount of redundant information. Smallest universal solutions are shown to be unique
(up to renaming of nulls) and to coincide with the graph-theoretic notion of the
core
of the
universal solutions. The smallest universal solution can always be computed in polynomial
time for mappings with a weakly acyclic set of tgds.
Computing certain answers
Once a target instance is materialized, we need to answer queries against it. Recall that
in the context of data exchange, we are interested in computing the certain answers of a
query. That is, if
st
) is a relational mapping,
Q
is a query in some query
language over the target schema R
t
,and
S
is a source instance, we want to find
certain
answers of Q with respect to S under
M
defined as
certain
M
(
Q
,
S
)=
M
=(R
s
,
R
t
,
Σ
t
,
Σ
{
Q
(
T
)
|
T
∈
S
OL
M
(
S
)
}
.
Example 4.4 (
Examples 4.1
and
4.3
continued) Consider again the source instance
S
=
{
FLIGHT
(
Paris
,
Santiago
,
AirFrance
,
2320)
}
.
The certain answers of the query
Q
=
ROUTES
(
x
,
y
,
z
) with respect to
S
is the empty set.
This is because if a tuple belongs to the certain answers of
Q
it can only be formed by
constants, and there is no fact of the form
ROUTES
(
a
,
b
,
c
),for
a
,
b
,
c
∈
C
ONST
, such that
ROUTES
(
a
,
b
,
c
)
T
.
On the other hand, it is not hard to see that
certain
M
(
Q
,
S
)=
∈
{
(
Paris
,
Santiago
)
}
,
Q
=
for
∃
x
ROUTES
(
x
,
y
,
z
).
Indeed, every solution for
S
must contain a fact
of
the form
ROUTES
(
x
,
Paris
,
Santiago
),
and,
thus,
it must
satisfy the query
∃
x
ROUTES
(
x
,
Paris
,
Santiago
).
Given a mapping
M
and a query
Q
over R
t
, the problem of computing certain answers for
Q
under
M
is defined as follows:
PROBLEM
:
(
Q
).
INPUT:
A source instance
S
and a tuple
t
of elements
from
S
.
QUESTION
: D s
t
belong to
certain
M
(
Q
,
S
)?
CERTAIN
M
We study query answering in
Chapter 7
. We start by showing in
Section 7.1
that com-
puting certain answers of FO queries is an undecidable problem, even when we deal with
relational mappings without target dependencies. This implies the need for restrictions on
