Database Reference
In-Depth Information
the naıve semantics is that, while it does compute certain answers of unions of conjunctive
queries, it fails to do so for any proper extension of this class of queries (see
Section 2.3
).
Therefore, it is not strange that beyond the class of positive queries, the certain answers
semantics exhibits a counter-intuitive behavior.
Thus, to define a CWA semantics that avoids as many anomalies as possible, we need
to keep in mind that target instances in data exchange are tables with nulls. In particular,
we need to make use of the techniques that have been developed for handling this kind of
tables, and that were introduced in
Section 2.3
. Those techniques, however, only apply to
the OWA, and hence we need to adjust them now for the case of the CWA.
Recall that the semantics of an instance
T
with nulls is given by the set
Rep
(
T
) of
complete instances that are
represented
by
T
. An instance
T
without nulls belongs to
Rep
(
T
) if there is a homomorphism
h
:
T
T
. Notice that the previous definition leaves
complete instances represented by
T
open for adding new facts. The reason is that instances
T
in
Rep
(
T
) may contain tuples that do not belong to the homomorphic image of
T
in
T
.
But this certainly does not go well with our goal of having a semantics based on the CWA.
Hence we need to refine the previous notion, and define the set of complete instances
represented by
T under the
CWA. This is what we do next.
As expected, an instance
T
with nulls represents, under the CWA, the set
Rep
CWA
(
T
)
of complete instances that are homomorphic images of
T
. Notice that in this way, under
the CWA, we no longer let instances be open for adding new tuples. Moreover, the sizes
of instances in
Rep
CWA
(
T
) do not exceed the size of
T
itself (contrary to
Rep
(
T
),which
contains instances of arbitrarily large sizes).
In order to evaluate a query
Q
over an incomplete instance
T
, the standard approach is
to compute the set:
→
Q
(
T
)=
{
Q
(
D
)
|
D
∈
Rep
CWA
(
T
)
}
.
This set is usually called the certain answers of
Q
with respect to
T
under the CWA in the
incomplete information literature, but we prefer to represent it by
Q
(
T
) here, in order
to avoid confusion with the certain answers as defined for data exchange. Note that in
general this set may be different from
{
|
∈
}
;however,if
Q
is a union of
conjunctive queries, it does not matter whether
Rep
or
Rep
CWA
is used.
We now define the notion of query answering under the CWA.
Q
(
D
)
D
Rep
(
T
)
Definition 8.14 (CWA certain answers) Let
Σ
st
) be a mapping,
Q
a query
over R
t
,and
S
a source instance. Then the CWA
certain answers
of
Q
with respect to
S
under
M
=(R
s
,
R
t
,
, denoted by
certain
CWA
M
M
(
Q
,
S
), is the set of tuples that would be in
Q
(
D
) for every
CWA solution
T
and every
D
∈
Rep
CWA
(
T
).Thatis:
(
Q
,
S
)=
certain
CWA
M
S
OL
CWA
M
{
Q
(
T
)
|
T
∈
(
S
)
}
.
We illustrate the definition with an example.
Example 8.15 (
Example 8.11
continued) We use again the source instance
S
=
{
P
(
a
,
b
)
}
