Database Reference
In-Depth Information
proof of this result shows that universal solutions are crucial to query answering in data
exchange.
Theorem 7.2
Σ
t
consists of a set of
egds and a weakly acyclic set of tgds, and let Q be a union of conjunctive queries. Then
CERTAIN
Let
M
=(R
s
,
R
t
,
Σ
st
,
Σ
t
)
be a mapping, such that
(
Q
)
can be solved in
P
TIME
.
M
Theorem7.2
can be easily proved in a way that also produces an algorithm for computing
certain answers. Namely, we can show that
certain
M
(
Q
,
S
)=
Q
naıve
(
T
)
,
(7.1)
when
Q
is a union of conjunctive queries and
T
is an arbitrary universal solution. Recall
that
Q
naıve
(
T
) is the naıve evaluation of
Q
over
T
, as described in
Section 2.3
. That is, one
first treats nulls as if they were values, evaluates
Q
, and then removes tuples containing
nulls from the result.
This can be easily shown when we put together the following facts.
1. For the class of mappings in
Theorem 7.2
, it is the case that if a source instance
S
has
at least one solution, then a universal solution
T
for
S
can be computed in polynomial
time (
Corollary 6.11
).
2. If
T
is a universal solution for a source instance
S
, then there is a homomorphism
h
:
T
T
for every
T
∈
→
S
OL
M
(
S
). But (unions of) conjunctive queries are preserved
under homomorphisms. Hence, if
t
is a tuple not containing nulls in
Q
(
T
),thenitalso
belongs to
Q
(
T
). Thus,
null-free tuples in
Q
(
T
)
.
null-free tuples in
Q
(
T
)
⊆
T
∈
S
OL
M
(
S
)
The other inclusion is true since
T
itself is a solution, and hence we have the equality
above. Now note that the right-hand side is
certain
M
(
Q
,
S
), since certain answers could
not contain any nulls, and the left-hand side is
Q
naıve
(
T
) by definition. Thus, we have
proved
(7.1)
.
3. FO-queries, and in particular, unions of conjunctive queries, have polynomial time data
complexity (as explained in
Section 2.4
). Hence, computing
Q
naıve
(
T
) is done in poly-
nomial time, as well as computing
T
itself.
Thus, in order to compute the certain answers of a union of conjunctive
queries
Q
with respect to a source instance
S
, one can use the algorithm
C
OMPUTE
C
ERTAIN
A
NSWERS
(
Q
,
) shown below. Note that in the algorithm one can
use any universal solution. For example, if we compute the core instead of the canonical
universal solution, the output of the algorithm is still the set of certain answers.
In summary, conjunctive queries form a very good class for data exchange as their certain
answers can always be obtained in polynomial time by means of naıve evaluation over a
materialized universal solution. A natural question at this point is whether this positive
behavior extends to other interesting classes of queries. For instance, conjunctive queries
M
