Database Reference
In-Depth Information
Formally, an annotation for a mapping
M
is a function
α
that maps every position of a
variable in a target atom into
cl
or
op
. We refer to the pair (
) as an
annotated mapping
.
To define the notion of a canonical solution under an annotated mapping, we need to
consider annotated instances: these are instances in which every constant or null is labeled
with
cl
or
op
. The semantics of such an instance
T
is a set
Rep
(
T
) on instances over C
ONST
obtained as follows: after applying a valuation
M
,
α
to
T
, any tuple (
...,
a
op
,...
) in
ν
ν
(
T
)
can be replicated arbitrarily many times with (
...,
b
,...
),for
b
∈
C
ONST
. For example,
Rep
(
{
(
a
cl
,⊥
op
)
}
) contains all binary relations whose projection on the first attribute is
(
a
cl
,
cl
)
{
a
}
,and
Rep
(
{
⊥
}
) contains all one-tuple relations
{
(
a
,
b
)
}
with
b
∈
C
ONST
.
).These
generate the
annotated canonical universal solution
C
AN
S
OL
(
M,
α)
(
S
) in the same way
as the usual mapping will generate the canonical universal solution except that now we
have an annotated instance. For example, if we have a tuple (#1,'Data exchange') in re-
lation
Papers
, the first st-tgd in the mapping will produce a tuple (#1
cl
,
Now suppose we have a source instance
S
and an annotated mapping (
M
,
α
op
) in relation
⊥
Assignment
.
The first observation is that the two extreme cases of annotated mappings correspond
precisely to the open-world and the closed-world semantics we have seen earlier. Let
(
in which every position is anno-
tated
op
(respectively,
cl
). Then, for each source instance
S
we have
M
,
op
) (respectively, (
M
,
cl
)) stand for the mapping
M
•
S
OL
M
(
S
)=
Rep
(C
AN
S
OL
(
M,
op
)
(
S
));
S
OL
CWA
M
•
(
S
)=
Rep
(C
AN
S
OL
(
M,
cl
)
(
S
)).
Annotated solutions can be defined in a way similar to the CWA solutions, using the
notion of justification. Since we consider settings without target constraints, we can obtain
their algebraic characterization: annotated solutions
T
for
S
under (
) are homomor-
phic images of C
AN
S
OL
(
M,
α)
(
S
) so that there is a homomorphism from
T
into an
expan-
sion
of C
AN
S
OL
(
M,
α)
(
S
). An expansion of the annotated instance C
AN
S
OL
(
M,
α)
(
S
) is
obtained by expanding
op
-annotated elements; that is, every tuple in the expansion must
agree with some tuple in the instance on all
cl
-annotated attributes.
With this, we have some expected properties of annotated solutions:
M
,
α
•
Rep
(C
AN
S
OL
(
M,
α)
(
S
)) is precisely the set of all annotated solutions under (
M
,
α
);
α
is obtained from
•
if
α
by changing some
cl
annotations to
op
, then each annotated
α
).
solution under (
M
,
α
) is an annotated solution under (
M
,
Given an annotated mapping (
M
,
α
) and a query
Q
over the target schema, we define
certain
(
M,
α)
(
Q
,
S
)=
Q
(
D
)
)-solution
.
|
D
∈
Rep
(
T
) where
T
is an (
M
,
α
For unions of conjunctive queries, this notion coincides with those we have seen.
Proposition 8.34
If
M
is a mapping, Q is a union of conjunctive queries, S is a source
instance, and
α
is an arbitrary annotation, then
certain
M
(
Q
,
S
)=
certain
CWA
(
Q
,
S
)=
certain
(
M,
α)
(
Q
,
S
)
.
M
