Database Reference
In-Depth Information
(7.15)
with different assignments that E
QUAL
(
a
,
,
b
) hold in
T
. Notice
that this rule is trying to prove that
certain
M
(
Q
,
S
)=
false
, and hence it forces
⊥
) and E
QUAL
(
⊥
to be
equal to
a
and to
b
. Now by using rule
(7.10)
, we obtain that E
QUAL
(
a
,
b
) holds in
T
.
But this cannot be the case since
a
and
b
are distinct constants and, thus, rule
(7.16)
is
used to conclude that
certain
M
(
Q
,
S
)=
true
. Note that this conclusion is correct. Indeed,
if
T
is an arbitrary solution for
S
, then there exists a homomorphism
h
:
T
⊥
T
.Given
→
that
a
and
b
are distinct constants, we have that
a
). It follows that
there are elements
w
1
,
w
2
,
w
3
∈
D
OM
(
T
) such that (
w
1
,
w
2
) and (
w
2
,
w
3
) belong to
V
T
,
w
1
,
w
3
∈
U
T
and
w
1
=
h
(
⊥
) or
b
=
h
(
⊥
=
w
3
. Thus, we conclude that
certain
M
(
Q
,
S
)=
true
.
It is now an easy exercise to show that
certain
M
(
Q
,
S
)=
certain
M
(
Π
Q
,
S
),forevery
source instance
S
.
The D
ATALOG
C(
=)
program
Π
Q
shown in the previous example made use of constant-
inequalities. It is not hard to prove that constant-inequalities are, indeed, necessary in this
case. That is, there is no D
ATALOG
program
Π
such that
certain
M
(
Q
,
S
)=
certain
M
(
Π
,
S
),
for every source instance
S
. We leave this as an exercise to the reader.
Notice that all the results in this section have been established for mappings without
target dependencies. It is easy to see that
Theorem 7.8
remains true when mappings are
allowed to contain egds in
Σ
t
. This implies that certain answers of unions of conjunctive
queries, with at most one negated atom per disjunct, can be computed in polynomial time
for relational mappings (R
s
,
R
t
,
Σ
t
consists of a set of egds. It can also be
proved, by using slightly different techniques based on a refinement of the chase procedure,
that the latter result remains true even for mappings that allow in
Σ
st
,
Σ
t
) such that
Σ
t
a set of egds and a
weakly acyclic set of tgds.
7.5 Rewritability over special solutions
Recall that a very desirable property for query answering in data exchange is to be able
to compute certain answer to queries over a materialized solution. The query that one
evaluates over a materialized solution is not necessarily the original query
Q
,butrathera
query
Q
obtained from
Q
, or, in other words, a
rewriting
of
Q
. The key property of such a
rewriting
Q
is that, for each given source
S
and materialized target
T
,wehave
certain
M
(
Q
,
S
)=
Q
(
T
)
.
(7.17)
Comparing this with
(7.1)
, we see that
Q
naıve
was a rewriting for unions of conjunctive
queries, over universal solutions.
In general, the rewriting
Q
of a query
Q
need not be a query in the same language as
Q
.
But usually, one looks for rewritings in languages with polynomial time data complexity
(e.g., relational algebra or, equivalently, FO). In this chapter we deal with FO-rewritings.
We now define the notion of rewritings precisely. For that, we continue using the unary
predicate C that distinguishes constants in target instances. The extension of the target
schema R
t
with this predicate C is denoted by R
t
. For the rest of this section, we only deal
