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